Construye un solucionador de rompecabezas MU

16

El rompecabezas MU es un rompecabezas en el que descubres si puedes convertirte MIen MUlas siguientes operaciones:

  1. Si su cadena termina en I, puede agregar un Ual final. (por ejemplo MI -> MIU)

  2. Si su cadena comienza con M, puede agregar una copia de la parte posterior Ma la cadena.
    (por ejemplo MII -> MIIII)

  3. Si su cadena contiene tres I' consecutivos , puede cambiarlos a a U.
    (por ejemplo MIII -> MU)

  4. Si su cadena contiene dos U' consecutivos , puede eliminarlos. (por ejemplo MUUU -> MU)

Su tarea es crear un programa que determine si esto es factible para cualquier cadena de inicio y finalización.

Su programa tomará dos cadenas como entrada. Cada cadena constará de lo siguiente:

  • uno M.

  • una cadena de hasta veintinueve Iy Us.

Su programa luego regresará true(o la representación del mismo en su lenguaje de programación / YPLRT) si la segunda cadena es accesible desde la primera cadena, y false(o YPLRT) si no lo es.

Ejemplo de entradas y salidas:

MI  MII
true

MI  MU
false

MIIIIU  MI
true

El código más corto en cualquier idioma para hacer esto gana.

code-golf puzzle-solver Joe Z.
fuente
8
Actualmente estoy leyendo Gödel, Escher, Bach y pensé en hacer un "campo de golf de 18 hoyos" basado en sus capítulos posteriores. Supongo que tengo que encontrar un nuevo "hoyo 1" ahora. ;)
Martin Ender
Esta es solo una pregunta de alcance gráfico cuya esencia se ha preguntado muchas veces antes.
Peter Taylor
1
@PeterTaylor Creo que hay una buena posibilidad de que esto no se resuelva con una búsqueda explícita del gráfico de accesibilidad. Las reglas de MIU tienen mucha estructura, y no me sorprendería si hubiera un algoritmo directo para probar la accesibilidad sin buscar nodos intermedios. Por ejemplo, los nodos a los que se puede acceder MIson exactamente M(I|U)*donde el número de Ino es múltiplo de 3. Y una verificación tan directa seguramente genera un código más corto. Además, no conozco un límite a priori en la longitud de las cadenas requeridas para los pasos intermedios, por lo que la búsqueda directa podría ser simplemente poco práctica.
xnor
1
He pensado en este problema por un tiempo y no me he acercado a una solución que no sea la fuerza bruta. Si nadie muerde, sugiero publicar una versión más fácil de la pregunta, tal vez para dar una derivación a partir MIde una cadena alcanzable dada.
xnor
1
¿Cuál debería ser la salida si IMse suministra o MUMMI?
Beta Decay

Respuestas:

7

SWI Prolog, 183 caracteres

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

¿Qué tal un Prolog, (ya que nadie ha respondido en 6 meses). Para correr, simplemente use "s (mi, mu)". El código divide los átomos en caracteres, luego busca la solución.

swstephe
fuente
2
Esto devuelve erróneamente falso s(mi,miiii), y en general cualquier cosa que requiera más de una aplicación de la regla 2 para probar.
algorithmshark