Построить MU решатель головоломок

16

Головоломка MU - головоломка , в которой вы узнаете, можно ли включить MIв MUданных следующих операций:

  1. Если ваша строка заканчивается I, вы можете добавить Uв конец. (например MI -> MIU)

  2. Если ваша строка начинается с M, вы можете добавить копию части после Mстроки.
    (например MII -> MIIII)

  3. Если ваша строка содержит три последовательных I, вы можете изменить их на U.
    (например MIII -> MU)

  4. Если ваша строка содержит два последовательных U, вы можете удалить их. (например MUUU -> MU).

Ваша задача - создать программу, которая определяет, выполнимо ли это для любых начальных и конечных строк.

Ваша программа примет две строки в качестве входных данных. Каждая строка будет состоять из следующего:

  • один M.

  • строка до двадцати девяти I«s и U» s.

Затем ваша программа вернет true(или представление вашего языка программирования / YPLRT), если вторая строка достижима из первой строки, и false(или YPLRT), если это не так.

Пример входов и выходов:

MI  MII
true

MI  MU
false

MIIIIU  MI
true

Самый короткий код на любом языке для этого выигрывает.

code-golf puzzle-solver Джо З.
источник
8
В настоящее время я читаю Геделя, Эшера, Баха и думал о создании «поля для гольфа с 18 лунками», основанного на его главах впоследствии. Думаю, мне нужно найти новую «дыру 1». ;)
Мартин Эндер
Это всего лишь вопрос доступности графа, суть которого задавалась много раз раньше.
Питер Тейлор
1
@PeterTaylor Я думаю, что есть хороший шанс, что это не будет решено явным поиском графа достижимости. Правила MIU имеют большую структуру, и я не удивлюсь, если есть прямой алгоритм проверки доступности без поиска промежуточных узлов. Например, достижимые узлы MI- это именно то место, M(I|U)*где число Iне кратно 3. И такая прямая проверка, безусловно, способствует сокращению кода. Кроме того, я не знаю априорной оценки длин строк, необходимых для промежуточных шагов, поэтому прямой поиск может быть просто непрактичным.
xnor
1
Я думал об этой проблеме некоторое время и не приблизился к решению, которое не является грубой силой. Если никто не кусается, я предлагаю опубликовать более простой вариант вопроса, возможно, чтобы дать вывод, начиная с MIзаданной достижимой строки.
xnor
1
Каким должен быть выход, если IMпоставлен или MUMMI?
бета-распад

Ответы:

7

SWI Пролог, 183 персонажа

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

Как насчет Пролога (так как никто не ответил через 6 месяцев). Для запуска просто используйте «s (mi, mu)». Код разбивает атомы на символы, а затем ищет решение.

swstephe
источник
2
Это ошибочно возвращает false s(mi,miiii), и в целом все, что требует более одного применения правила 2 для доказательства.
алгоритмическая