Erstellen Sie einen MU-Rätsellöser

16

Das MU - Puzzle ist ein Puzzle , in dem Sie herausfinden, ob Sie drehen können MIin MUbestimmten den folgenden Operationen:

  1. Wenn Ihre Zeichenfolge auf endet I, können Sie ein Uam Ende hinzufügen . (zB MI -> MIU)

  2. Wenn Ihre Zeichenfolge mit beginnt M, können Sie eine Kopie des Teils danach Man die Zeichenfolge anhängen .
    (zB MII -> MIIII)

  3. Wenn Ihre Zeichenfolge drei aufeinanderfolgende Zeichenfolgen enthält I, können Sie sie in a ändern U.
    (zB MIII -> MU)

  4. Wenn Ihre Zeichenfolge zwei aufeinanderfolgende Zeichenfolgen enthält U, können Sie diese löschen. (zB MUUU -> MU).

Ihre Aufgabe ist es, ein Programm zu erstellen, das festlegt, ob dies für Start- und Zielzeichenfolgen möglich ist.

Ihr Programm nimmt zwei Zeichenfolgen als Eingabe. Jede Zeichenfolge besteht aus folgenden Elementen:

  • eins M.

  • eine Zeichenfolge von bis zu neunundzwanzig Iund U.

Ihr Programm gibt dann true(oder die Darstellung Ihrer Programmiersprache / YPLRT) zurück, wenn die zweite Zeichenfolge von der ersten Zeichenfolge aus erreichbar ist, und false(oder YPLRT), wenn dies nicht der Fall ist.

Beispiel Ein- und Ausgänge:

MI  MII
true

MI  MU
false

MIIIIU  MI
true

Der kürzeste Code in einer Sprache, um dies zu tun, gewinnt.

code-golf puzzle-solver Joe Z.
quelle
8
Ich lese gerade Gödel, Escher, Bach und habe mir überlegt, einen "18-Loch-Golfplatz" nach seinen Kapiteln zu bauen. Ich schätze, ich muss jetzt ein neues "Loch 1" finden. ;)
Martin Ender
Dies ist nur eine Frage zur Erreichbarkeit von Diagrammen, deren Wesen schon oft gestellt wurde.
Peter Taylor
1
@PeterTaylor Ich denke, es gibt eine gute Chance, dass dies nicht durch eine explizite Suche im Erreichbarkeitsgraphen gelöst wird. Die MIU-Regeln sind sehr strukturiert, und es würde mich nicht wundern, wenn es einen direkten Algorithmus zum Testen der Erreichbarkeit gibt, ohne nach Zwischenknoten zu suchen. Zum Beispiel sind die Knoten, von MIdenen aus erreicht werden kann, genau die, von M(I|U)*denen die Anzahl Ikein Vielfaches von 3 ist. Und eine solche direkte Prüfung führt mit Sicherheit zu einem kürzeren Code. Ich kenne auch keine A-priori-Grenze für die Länge der Zeichenfolgen, die für Zwischenschritte erforderlich sind, sodass die direkte Suche möglicherweise einfach unpraktisch ist.
Xnor
1
Ich habe eine Weile über dieses Problem nachgedacht und bin noch keiner Lösung nahe gekommen, die nicht brachial ist. Wenn niemand beißt, schlage ich vor, eine einfachere Version der Frage zu veröffentlichen, vielleicht um eine Ableitung ausgehend von MIeiner bestimmten erreichbaren Zeichenfolge zu geben.
XNOR
1
Was soll die Ausgabe sein, wenn IMgeliefert wird oder MUMMI?
Beta Decay

Antworten:

7

SWI Prolog, 183 Zeichen

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).

Wie wäre es mit einem Prolog (seit 6 Monaten hat niemand geantwortet). Verwenden Sie zum Ausführen einfach "s (mi, mu)". Der Code zerlegt Atome in Zeichen und sucht dann nach der Lösung.

swstephe
quelle
2
Dies gibt fälschlicherweise false zurück s(mi,miiii)und im Allgemeinen alles, was mehr als eine Anwendung von Regel 2 zum Nachweis erfordert.
Algorithmushai