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

Jeśli twój łańcuch kończy się na I, możesz dodać a Una końcu. (np. MI -> MIU)
Jeśli ciąg zaczyna się od M, możesz dołączyć kopię części po Mnim.
(np. MII -> MIIII)
Jeśli Twój ciąg zawiera trzy kolejne I, możesz zmienić je na U.
(np. MIII -> MU)
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

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

@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

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

Jaki powinien być wynik, jeśli IMzostał dostarczony lub MUMMI?

— Beta Decay

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

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

Zbuduj solver MU puzzle

SWI Prolog, 183 znaków