I was reading Godel, Escher, Bach: An Eternal Golden Braid on the train and when reading about the MU puzzle I decided to give it a go. I wrote most of the code on my lil' eeepc, but I did get a bit stuck with the recursion, it was hard to get the `apply-rules` function to return the answer once it found a path to “MU”.

In the end with some help from the good folks in #emacs and #lisp I had it working here’s the code:

``````(defvar *path*)

(defun all-matches (string pattern &key (start 0))
"Return a list of positions for all matches of the pattern in the string"
(let ((match (search pattern string :start2 start)))
(when match
(append (list match)
(all-matches string pattern :start (+ match 1))))))

(defun list-if (x)
(when x
(list x)))

(defun replace-substr (string start end new)
(concatenate 'string (subseq string 0 start) new
(subseq string end)))

(defun replace-all-once (string pattern new)
(let ((matches (all-matches string pattern)))
(remove-duplicates
(loop for match in matches
collect (replace-substr string match (+ match (length pattern)) new))
:test #'equal)))

(defun string-last (string)
(aref string (1- (length string))))

(defun rule-1 (string)
(when (eql (string-last string) #\I)
(concatenate 'string string "U")))

(defun rule-2 (string)
(when (eql (aref string 0) #\M)
(if (> (length string) 1)
(concatenate 'string string (subseq string 1))
string)))

(defun rule-3 (string)
(replace-all-once string "III" "U"))

(defun rule-4 (string)
(replace-all-once string "UU" ""))

(defun apply-rules (string depth)
"Return a list of axioms returned by the various rules"
(if (or (< depth 1) *path*)
nil
(if (equal string "MU")
(push "MU" *path*)
(let ((results (append
(list-if (rule-1 string))
(list-if (rule-2 string))
(rule-3 string)
(rule-4 string))))
(loop for match in results
collect (append (list match) (apply-rules match (1- depth)))
do (when (and match (equal (last *path*) (list match)))
(push string *path*)))))))

(defun find-mu (depth)
(let (tree *path*)
(setf tree (apply-rules "MI" depth))
(if *path*
(format t "The answer is: ~a. ~%" *path*)
(format t "Couldn't solve it by going through ~a levels of possibilities. ~%  Tree:~A" depth tree))))

(find-mu 5)``````

Now when Emacs ground to a halt trying to solve the puzzle, beach pointed out that it was actually impossible and it’s explained later in the book… whoops! Anyway, I thought it was a nifty little program so I thought I’d post it anyway.

(Try replacing “MU” with something that is possible to find to see it in action.)

Cheers, Dave.