Maze solving: Difference between revisions
Content added Content deleted
(Created draft task, added PicoLisp) |
(Doh! This was the *longest* path) |
||
Line 16: | Line 16: | ||
(let Cell (val This) |
(let Cell (val This) |
||
(if (fish =T Cell) |
(if (fish =T Cell) |
||
( |
(unless (and Best (>= (length Path) (length Best))) |
||
(setq Best Path) ) |
(setq Best Path) ) |
||
(=: mark T) |
(=: mark T) |
||
Line 29: | Line 29: | ||
<pre>: (shortestExit 'a1 Maze) |
<pre>: (shortestExit 'a1 Maze) |
||
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |
||
12 | |
12 | # | # # | | | | |
||
+ + + + + +---+ + +---+---+ + +---+ +---+ + |
+ + + + + +---+ + +---+---+ + +---+ +---+ + |
||
11 | |
11 | # # | # | | | | | | | | | |
||
+ +---+ +---+---+ +---+---+ + +---+---+ +---+ +---+ |
+ +---+ +---+---+ +---+---+ + +---+---+ +---+ +---+ |
||
10 | | | # | | |
10 | | | # | | | | | | | |
||
+ + + +---+ + + + + +---+---+ +---+ +---+ + |
+ + + +---+ + + + + +---+---+ +---+ +---+ + |
||
9 | | # # | | | |
9 | | # # | | | | | | | | | |
||
+ +---+---+ + +---+ +---+---+ + + + +---+ + + |
+ +---+---+ + +---+ +---+---+ + + + +---+ + + |
||
8 | | # # | # | |
8 | | # # | # | | | | | | | |
||
+ + + + + +---+---+ +---+ +---+---+ +---+ + + |
+ + + + + +---+---+ +---+ +---+---+ +---+ + + |
||
7 | | # | # # | |
7 | | # | # # | | | | | | | |
||
+---+ +---+---+---+---+ +---+ +---+ + +---+ +---+ + |
+---+ +---+---+---+---+ +---+ +---+ + +---+ +---+ + |
||
6 | | # # | | |
6 | | # # | | | | | | | | | |
||
+ +---+ +---+ +---+ + +---+ + +---+---+---+ + + |
+ +---+ +---+ +---+ + +---+ + +---+---+---+ + + |
||
5 | | # # | |
5 | | # # | | | | | | |
||
+---+ +---+ +---+ +---+ +---+---+ + +---+ +---+ + |
+---+ +---+ +---+ +---+ +---+---+ + +---+ +---+ + |
||
4 | | | # # | |
4 | | | # # | | | | | | | | |
||
+ +---+ +---+ +---+ +---+ + + +---+---+ + +---+ |
+ +---+ +---+ +---+ +---+ + + +---+---+ + +---+ |
||
3 | | | # | | |
3 | | | # | | | | | | | |
||
+ +---+---+ + + +---+---+---+ +---+ + + +---+ + |
+ +---+---+ + + +---+---+---+ +---+ + + +---+ + |
||
2 | # # | | # | | | |
2 | # # | | # | | | | | | | |
||
+ + + +---+ + + +---+ +---+ +---+ + +---+---+ |
+ + + +---+ + + +---+ +---+ +---+ + +---+---+ |
||
1 | # | # # # # | | |
1 | # | # # # # | | | |
||
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |
||
a b c d e f g h i j k l m n o p</pre> |
a b c d e f g h i j k l m n o p</pre> |
Revision as of 17:05, 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>
Output, using the maze produced in Maze generation#PicoLisp:
: (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