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}