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 needs more memory than is available on an Arduino Uno or ATmega328, but will run on any of the other platforms.

The program

Here's the program to solve a Tweetmaze:

(defun solve (maze queue)
  (let* ((go (- (length maze) 1)))
    (if (= (caar queue) go) 
        (reverse (car queue))
      (let* ((top (pop queue))
             (pos (first top))
             (right (+ pos (nth pos maze)))
             (left (- pos (nth pos maze))))
        (when (>= left 0) (setq queue (append queue (list (cons left top)))))
        (when (<= right go) (setq queue (append queue (list (cons right top)))))
	(solve maze queue)))))

The routine solve takes two parameters: the maze to be solved, as a list of numbers, and the queue of paths taken so far, with the shortest path at the front. It returns the solution, as a list of positions. Initially solve should be called with the queue 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.

First Tweetmaze

Here's an example of it solving the Tweetmaze shown above:

> (solve '(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:


Second Tweetmaze

Here's a more difficult Tweetmaze to solve:


Try solving it by hand before you use the program to solve it.