Maze solving: Difference between revisions
Content added Content deleted
(Trying to make the comment more clear) |
(→{{header|PicoLisp}}: More clarity) |
||
Line 26: | Line 26: | ||
(disp Maze 0 |
(disp Maze 0 |
||
'((This) (if (memq This Best) " # " " ")) ) ) )</lang> |
'((This) (if (memq This Best) " # " " ")) ) ) )</lang> |
||
Using the maze produced in [[Maze generation#PicoLisp]], this finds the shortest |
Using the maze produced in [[Maze generation#PicoLisp]], this finds the shortest path from a given cell ('a1' in this case) to the nearest exit ('a12' in this case): |
||
path from the bottom-left cell 'a1' to the nearest exit ('a12' in this case): |
|||
<pre>: (shortestExit 'a1 Maze) |
<pre>: (shortestExit 'a1 Maze) |
||
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |
Revision as of 17:41, 15 December 2010
Maze solving is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
For a maze generated by this task, write a function that finds (and displays) for a given cell the shortest path to the next exit. 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 shortestExit (This Maze)
(let (Path NIL Best NIL) (recur (This Path) (when (and This (not (: mark))) (push 'Path This) (let Cell (val This) (if (fish =T Cell) (unless (and Best (>= (length Path) (length Best))) (setq Best Path) ) (=: mark T) (recurse (caar Cell) Path) (recurse (cdar Cell) Path) (recurse (cadr Cell) Path) (recurse (cddr Cell) 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 a given cell ('a1' in this case) to the nearest exit ('a12' in this case):
: (shortestExit 'a1 Maze) + +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 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