The MU puzzle is a puzzle in which you find out whether you can turn
MU given the following operations:
If your string ends in
I, you may add a
Uto the end. (e.g.
MI -> MIU)
If your string begins with
M, you may append a copy of the part after
Mto the string.
MII -> MIIII)
If your string contains three consecutive
I's, you may change them into a
MIII -> MU)
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:
a string of up to twenty-nine
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.
MIare exactly the
M(I|U)*where the number of
Iisn'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\$
MIof a given reachable string. \$\endgroup\$
IMis supplied or