16
\$\begingroup\$

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.

\$\endgroup\$
  • 8
    \$\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\$ – Martin Ender Jul 12 '14 at 6:38
  • \$\begingroup\$ This is just a graph reachability question whose essence has been asked plenty of times before. \$\endgroup\$ – Peter Taylor Jul 12 '14 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 Jul 12 '14 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 Jul 15 '14 at 13:09
  • 1
    \$\begingroup\$ What should the output be if IM is supplied or MUMMI? \$\endgroup\$ – Beta Decay Sep 10 '14 at 17:41
7
\$\begingroup\$

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.

\$\endgroup\$
  • 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\$ – algorithmshark Dec 8 '17 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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