Copy of snippet "Maze solver"

Maze solver. I didn't realize that the only way to share was the forum. The forum doesn't display the result in monospace so you'll have to copy and paste it into notepad or something to view it properly!

Unsolved Maze:
{note}Write out your maze here.

Formatting: Use S as the start, E as the end, and . as empty spaces.
The maze must be rectangular.{endnote}
{formparagraph: name=unsolved_maze; default=OOOOOOOO
S..O...O
O....O.O
OOOOOO.O
O......O
O.O.OOOO
O.O.OO.O
O.O....O
OOOOOO.E
OOOOOOOO; trim=no}

Solved maze:
{run: grid_find = (grid, letter) -> block
 for r in seq(1, count(grid))
  for c in seq(1, count(grid[r]))
    if grid[r][c] = letter
     return [r, c]
    endif
  endfor
 endfor
 error("Letter" & letter & "not in grid")
endblock

is_empty = (grid, position) -> block
 var r = position[1]
 var c = position[2]
 return r >= 1 and r <= count(grid) and c >= 1 and c <= count(grid[r]) and grid[r][c] = "."
endblock

# generate keyed list of (pos: space before pos)
spaces_before = (grid, start, end) -> block
 var visited = [
]

 var stack = [start]
 var result = [
]


 var last = (list) -> list[count(list)]
 var remove_last = (list) -> filter(list, (item, index) -> index < count(list))

 # breadth-first search through the maze
 # while loops don't exist so we use a for
 var iterations = count(grid) * count(grid[1]) 
 for i in seq(0, iterations)
  if count(stack) = 0
   error("Unsolvable maze")
  endif

  var cur = last(stack)
  stack = remove_last(stack)
  visited = merge(visited, [cur])
   
  var r = cur[1]
  var c = cur[2]
  var neighbors = [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]
  for neighbor in neighbors
   if not includes(visited, neighbor) and is_empty(grid, neighbor)
    result = merge(result, [neighbor: cur]) 
    stack = merge([neighbor], stack)
   endif
   if neighbor = end
    result = merge(result, [neighbor: cur])
    return result
   endif
  endfor

 endfor
 error("No path through maze!")
endblock

copy = (list) -> slice(list, 1)

# generates the solved grid
solve = (grid) -> block
 var start = grid_find(grid, "S")
 var end = grid_find(grid, "E")

 var new_grid = map(grid, copy)
 var space_before = spaces_before(grid, start, end)

 var cur = end
 for i in seq(1, count(space_before))
  if cur = start
   return new_grid
  endif
  cur = space_before[cur]
  new_grid[cur[1]][cur[2]] = "*"
 endfor

 return new_grid
endblock

string_to_grid = (str) -> block
 var rows = splitregex(str, "\r?\n")
 return map(rows, (row) -> splitregex(row, ""))
endblock

# converts grid to string
grid_to_string = (grid) -> join(map(grid, (row) -> join(row, "")), "\n")

}

{=grid_to_string(solve(string_to_grid(unsolved_maze))); trim=no}