This uLisp program solves a logic maze puzzle consisting of a string of decimal digits. It's called a Tweetmaze because it's short enough to send in a tweet. For example, here's a 16-digit Tweetmaze:
You start from the leftmost digit, and the aim is to find a route to the last digit on the right in the shortest number of jumps. The number on each square tells you how far you can jump from that square, left or right, to the next square. So, for example, from the 7 on the starting square you can jump to the first 2 to its right, and then from that you can jump two squares to its left or right, and so on.
The program is an example of a problem that Lisp is suited to solving. With the addition of some hardware and control routines this program could form the basis for a maze-solving robot.
It will run on any of the platforms.
Here's the program to solve a Tweetmaze:
(defun sol (maz que) (let* ((go (- (length maz) 1))) (if (= (caar que) go) (reverse (car que)) (let* ((top (pop que)) (pos (first top)) (rt (+ pos (nth pos maz))) (lt (- pos (nth pos maz)))) (when (>= lt 0) (setq que (append que (list (cons lt top))))) (when (<= rt go) (setq que (append que (list (cons rt top))))) (sol maz que)))))
I've purposely used three-letter symbols so the program can run on an Arduino Uno.
The routine sol (solve) takes two parameters:
- maz, the maze to be solved, as a list of numbers.
- que, the queue of paths taken so far, with the shortest path at the front.
It returns the solution, as a list of positions. Initially sol should be called with que set to the starting position, '((0)).
If the last cell visited by the shortest path is the goal, the routine returns the path. Otherwise it pops the shortest path from the front of the queue, and adds the two new longer paths, corresponding to going left and right from the current position, to the end of the queue.
Finally it calls solve again with the updated queue.
Here's an example of it solving the Tweetmaze shown above:
> (sol '(7 3 4 7 7 3 7 2 5 8 4 9 3 4 2 0) '((0))) (0 7 5 8 3 10 14 12 15)
Here's a graphical representation of this solution:
Here's a more difficult Tweetmaze to solve:
Try solving it by hand before you use the program to solve it.