Maze solving: Difference between revisions
Content added Content deleted
(Slightly simplified) |
m (Switch from draft to complete task) |
||
Line 1: | Line 1: | ||
{{ |
{{task|Games}} |
||
For a maze generated by [[Maze generation|this task]], write a function that |
For a maze generated by [[Maze generation|this task]], write a function that |
Revision as of 16:05, 20 December 2010
Maze solving
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
For a maze generated by this task, write a function that finds (and displays) the shortest path between two cells. Note that because these mazes are generated by the Depth-first search algorithm, they contain no circular paths, and a simple depth-first tree search can be used.
PicoLisp
<lang PicoLisp>(de shortestPath (This Goal Maze)
(let (Path NIL Best NIL) (recur (This Path) (when (and This (not (: mark))) (push 'Path This) (if (== Goal This) (unless (and Best (>= (length Path) (length Best))) (setq Best Path) ) (=: mark T) (recurse (: west) Path) (recurse (: east) Path) (recurse (: south) Path) (recurse (: north) Path) (=: mark NIL) ) ) ) (disp Maze 0 '((This) (if (memq This Best) " # " " ")) ) ) )</lang>
Using the maze produced in Maze generation#PicoLisp, this finds the shortest path from the top-left cell 'a12' to the bottom-righ exit 'p1':
: (shortestPath 'a12 'p1 (maze 16 12)) + +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 12 | # | # # # | # # # | # # # # | # # # | + + + + + +---+ + +---+---+ + +---+ +---+ + 11 | # # | | # # | | # # | | # # | | # # | # # | + +---+ +---+---+ +---+---+ + +---+---+ +---+ +---+ 10 | | | | | # # | # # | # # | # # | | + + + +---+ + + + + +---+---+ +---+ +---+ + 9 | | | | | # | # # | # # | # | # # | # # | + +---+---+ + +---+ +---+---+ + + + +---+ + + 8 | | | | # # # | # | # # | # | # | # | + + + + + +---+---+ +---+ +---+---+ +---+ + + 7 | | | | # # # | | # # | # # | # # | # | +---+ +---+---+---+---+ +---+ +---+ + +---+ +---+ + 6 | | | | # | | | # | # # # | | # | + +---+ +---+ +---+ + +---+ + +---+---+---+ + + 5 | | | # # | | # | | # | +---+ +---+ +---+ +---+ +---+---+ + +---+ +---+ + 4 | | | | # # | | # # | # | | | # # | + +---+ +---+ +---+ +---+ + + +---+---+ + +---+ 3 | | | | | # # # | # | # # # | | # # | + +---+---+ + + +---+---+---+ +---+ + + +---+ + 2 | | | | | | # # | | # | # # # | + + + +---+ + + +---+ +---+ +---+ + +---+---+ 1 | | | | # # # | # # # +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ a b c d e f g h i j k l m n o p