Zbuduj solver MU puzzle

16

MU zagadka jest logiczna, w której dowiesz się, czy można włączyć MIdo MUpodanych następujących operacji:

  1. Jeśli twój łańcuch kończy się na I, możesz dodać a Una końcu. (np. MI -> MIU)

  2. Jeśli ciąg zaczyna się od M, możesz dołączyć kopię części po Mnim.
    (np. MII -> MIIII)

  3. Jeśli Twój ciąg zawiera trzy kolejne I, możesz zmienić je na U.
    (np. MIII -> MU)

  4. Jeśli Twój ciąg zawiera dwa kolejne U, możesz je usunąć. (np MUUU -> MU.).

Twoim zadaniem jest zbudowanie programu, który określa, czy jest to wykonalne dla dowolnych ciągów początkowych i końcowych.

Twój program pobierze dwa ciągi jako dane wejściowe. Każdy ciąg składa się z następujących elementów:

  • jeden M.

  • ciąg do dwudziestu dziewięciu Ii Utych.

Twój program zwróci następnie true(lub jego reprezentację języka programowania / YPLRT), jeśli drugi łańcuch jest osiągalny z pierwszego łańcucha i false(lub YPLRT), jeśli nie jest.

Przykładowe dane wejściowe i wyjściowe:

MI  MII
true

MI  MU
false

MIIIIU  MI
true

Wygrywa najkrótszy kod w dowolnym języku, aby to zrobić.

code-golf puzzle-solver Joe Z.
źródło
8
Obecnie czytam Gödela, Eschera, Bacha i pomyślałem o zrobieniu „18-dołkowego pola golfowego” na podstawie jego rozdziałów. Chyba muszę teraz znaleźć nową „dziurę 1”. ;)
Martin Ender
To tylko pytanie o dostępność grafu, którego istotę zadawano już wiele razy.
Peter Taylor
1
@PeterTaylor Myślę, że istnieje spora szansa, że ​​nie zostanie to rozwiązane poprzez jednoznaczne przeszukanie wykresu osiągalności. Reguły MIU mają wiele struktur i nie zdziwiłbym się, gdyby istniał bezpośredni algorytm do testowania osiągalności bez szukania węzłów pośrednich. Na przykład, dostępne węzły MIsą dokładnie tam, M(I|U)*gdzie liczba Inie jest wielokrotnością 3. A takie bezpośrednie sprawdzenie z pewnością skraca kod. Ponadto nie znam a priori związanego z długością łańcuchów wymaganych dla pośrednich kroków, więc bezpośrednie wyszukiwanie może być po prostu niepraktyczne.
xnor
1
Myślałem o tym problemie przez jakiś czas i nie zbliżyłem się do rozwiązania, które nie jest brutalną siłą. Jeśli nikt nie gryzie, sugeruję opublikowanie łatwiejszej wersji pytania, być może w celu uzyskania pochodnej zaczynającej się od MIdanego osiągalnego ciągu.
xnor
1
Jaki powinien być wynik, jeśli IMzostał dostarczony lub MUMMI?
Beta Decay

Odpowiedzi:

7

SWI Prolog, 183 znaków

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

Co powiesz na jakiegoś Prologa (skoro nikt nie odpowiedział od 6 miesięcy). Aby uruchomić, po prostu użyj „s (mi, mu)”. Kod dzieli atomy na znaki, a następnie szuka rozwiązania.

swstephe
źródło
2
To bezprawnie zwraca wartość false s(mi,miiii)i ogólnie wszystko, co wymaga więcej niż jednego zastosowania reguły 2 w celu udowodnienia.
algorytmshark