The MU puzzle is a puzzle in which you find out whether you can turn MI into MU given the following operations:

  1. If your string ends in I, you may add a U to the end. (e.g. MI -> MIU)

  2. If your string begins with M, you may append a copy of the part after M to the string.
    (e.g. MII -> MIIII)

  3. If your string contains three consecutive I's, you may change them into a U.
    (e.g. MIII -> MU)

  4. If your string contains two consecutive U's, you may delete them. (e.g. MUUU -> MU).

Your task is to build a program that determines whether this is doable for any start and finish strings.

Your program will take two strings as input. Each string will consist of the following:

  • one M.

  • a string of up to twenty-nine I's and U's.

Your program will then return true (or your programming language's representation thereof/YPLRT) if the second string is reachable from the first string, and false (or YPLRT) if it is not.

Example inputs and outputs:




The shortest code in any language to do this wins.

  • 9
    \$\begingroup\$ I'm currently reading Gödel, Escher, Bach and thought about doing an "18-hole golf course"based on its chapters afterwards. Guess I've got to find a new "hole 1" now. ;) \$\endgroup\$ Commented Jul 12, 2014 at 6:38
  • \$\begingroup\$ This is just a graph reachability question whose essence has been asked plenty of times before. \$\endgroup\$ Commented Jul 12, 2014 at 8:57
  • 1
    \$\begingroup\$ @PeterTaylor I think there's a good chance this won't be solved by an explicit search of the reachability graph. The MIU rules have a lot of structure, and I wouldn't be surprised if there's a direct algorithm to test for reachability without searching for intermediate nodes. For example, the nodes reachable from MI are exactly the M(I|U)* where the number of I isn't a multiple of 3. And such a direct check surely makes for shorter code. Also, I don't know of an a-priori bound on the lengths of strings required for intermediate steps, so direct search might be simply impractical. \$\endgroup\$
    – xnor
    Commented Jul 12, 2014 at 16:02
  • 1
    \$\begingroup\$ I've thought about this problem for a while and haven't gotten close to a solution that isn't brute-force. If nobody bites, I suggest posting an easier version of the question, perhaps to give a derivation starting from MI of a given reachable string. \$\endgroup\$
    – xnor
    Commented Jul 15, 2014 at 13:09
  • 1
    \$\begingroup\$ What should the output be if IM is supplied or MUMMI? \$\endgroup\$
    – Beta Decay
    Commented Sep 10, 2014 at 17:41

1 Answer 1


SWI Prolog, 183 characters


How about some Prolog, (since nobody has answered in 6 months). To run, just use "s(mi,mu)." The code breaks up atoms into chars, then searches for the solution.

  • 2
    \$\begingroup\$ This wrongfully returns false on s(mi,miiii), and in general anything requiring more than one application of rule 2 to prove. \$\endgroup\$ Commented Dec 8, 2017 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.