# Build a MU puzzle solver

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:

MI  MII
true

MI  MU
false

MIIIIU  MI
true


The shortest code in any language to do this wins.

• 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. ;) Jul 12, 2014 at 6:38
• This is just a graph reachability question whose essence has been asked plenty of times before. Jul 12, 2014 at 8:57
• @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.
– xnor
Jul 12, 2014 at 16:02
• 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.
– xnor
Jul 15, 2014 at 13:09
• What should the output be if IM is supplied or MUMMI? Sep 10, 2014 at 17:41

# SWI Prolog, 183 characters

m(A,A).
m([i],[i,u]).
m([i,i,i|T],B):-m([u|T],B).
m([u,u|T],B):-m(T,B).
n([m|A],[m|B]):-(m(A,B);append(A,A,X),m(X,B)).
n(A,B):-m(A,B).
s(A,B):-atom_chars(A,X),atom_chars(B,Y),n(X,Y).


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.

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