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.