Construir um solucionador de quebra-cabeças MU

16

O quebra - cabeça MU é um quebra-cabeça no qual você descobre se pode se transformar MInas MUseguintes operações:

  1. Se sua string terminar I, você poderá adicionar Ua no final. (por exemplo MI -> MIU)

  2. Se sua sequência começar M, você poderá anexar uma cópia da peça depois Mà sequência.
    (por exemplo MII -> MIIII)

  3. Se a sua string contiver três consecutivas I, você poderá alterá-las para a U.
    (por exemplo MIII -> MU)

  4. Se sua string contiver dois consecutivos U, você poderá excluí-los. (por exemplo MUUU -> MU).

Sua tarefa é criar um programa que determine se isso é possível para qualquer sequência de início e fim.

Seu programa terá duas seqüências de caracteres como entrada. Cada sequência consistirá no seguinte:

  • um M.

  • uma sequência de até vinte e nove I'e U'.

Seu programa retornará true(ou a representação da sua linguagem de programação / YPLRT) se a segunda string estiver acessível a partir da primeira string e false(ou YPLRT) se não estiver.

Exemplos de entradas e saídas:

MI  MII
true

MI  MU
false

MIIIIU  MI
true

O código mais curto em qualquer idioma para fazer isso vence.

code-golf puzzle-solver Joe Z.
fonte
8
Atualmente, estou lendo Gödel, Escher, Bach e pensei em fazer um "campo de golfe de 18 buracos" com base em seus capítulos depois. Acho que tenho que encontrar um novo "buraco 1" agora. ;)
Martin Ender
Esta é apenas uma questão de alcançabilidade gráfica, cuja essência já foi solicitada várias vezes antes.
Peter Taylor
11
@ PeterTaylor Acho que há uma boa chance de isso não ser resolvido por uma pesquisa explícita no gráfico de acessibilidade. As regras do MIU têm muita estrutura e não me surpreenderia se houvesse um algoritmo direto para testar a acessibilidade sem procurar nós intermediários. Por exemplo, os nós alcançáveis MIsão exatamente M(I|U)*onde o número de Inão é um múltiplo de 3. E essa verificação direta certamente contribui para um código mais curto. Além disso, não conheço um limite a priori no comprimento das seqüências necessárias para etapas intermediárias, portanto, a pesquisa direta pode ser simplesmente impraticável.
Xnor
11
Penso nesse problema há um tempo e não cheguei nem perto de uma solução que não seja de força bruta. Se ninguém morde, sugiro postar uma versão mais fácil da pergunta, talvez para fornecer uma derivação a partir MIde uma determinada sequência acessível.
Xnor
11
Qual deve ser a saída se IMfor fornecida ou MUMMI?
Beta Decay

Respostas:

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

Que tal um Prolog, (já que ninguém responde em 6 meses). Para executar, basta usar "s (mi, mu)". O código divide os átomos em caracteres e depois procura a solução.

swstephe
fonte
2
Isso retorna errado por engano s(mi,miiii)e, em geral, qualquer coisa que exija mais de uma aplicação da regra 2 para provar.
algorithmshark