Construire un résolveur de casse-tête MU

16

Le puzzle MU est un puzzle dans lequel vous découvrez si vous pouvez vous transformer MIen MUétant donné les opérations suivantes:

  1. Si votre chaîne se termine par I, vous pouvez ajouter un Uà la fin. (par exemple MI -> MIU)

  2. Si votre chaîne commence par M, vous pouvez ajouter une copie de la partie suivante Mà la chaîne.
    (par exemple MII -> MIIII)

  3. Si votre chaîne contient trois consécutifs I, vous pouvez les changer en a U.
    (par exemple MIII -> MU)

  4. Si votre chaîne contient deux consécutifs U, vous pouvez les supprimer. (par exemple MUUU -> MU).

Votre tâche consiste à créer un programme qui détermine si cela est possible pour les chaînes de début et de fin.

Votre programme prendra deux chaînes en entrée. Chaque chaîne comprendra les éléments suivants:

  • un M.

  • une chaîne de jusqu'à vingt-neuf Iet U.

Votre programme retournera alors true(ou la représentation de votre langage de programmation / YPLRT) si la deuxième chaîne est accessible à partir de la première chaîne, et false(ou YPLRT) si ce n'est pas le cas.

Exemples d'entrées et sorties:

MI  MII
true

MI  MU
false

MIIIIU  MI
true

Le code le plus court dans n'importe quelle langue pour ce faire gagne.

code-golf puzzle-solver Joe Z.
la source
8
Je lis actuellement Gödel, Escher, Bach et j'ai pensé à faire un "parcours de golf 18 trous" basé sur ses chapitres par la suite. Je suppose que je dois trouver un nouveau "trou 1" maintenant. ;)
Martin Ender
Il s'agit simplement d'une question d'accessibilité aux graphes dont l'essence a été posée de nombreuses fois auparavant.
Peter Taylor
1
@PeterTaylor Je pense qu'il y a de fortes chances que cela ne soit pas résolu par une recherche explicite du graphique d'accessibilité. Les règles MIU ont beaucoup de structure, et je ne serais pas surpris s'il existe un algorithme direct pour tester l'accessibilité sans rechercher de nœuds intermédiaires. Par exemple, les nœuds accessibles MIsont exactement ceux M(I|U)*où le nombre de In'est pas un multiple de 3. Et une telle vérification directe rend sûrement le code plus court. De plus, je ne connais pas de limite a-priori sur les longueurs de chaînes requises pour les étapes intermédiaires, donc la recherche directe peut être tout simplement impossible.
xnor
1
J'ai réfléchi à ce problème pendant un certain temps et je ne me suis pas approché d'une solution qui n'est pas de force brute. Si personne ne mord, je suggère de publier une version plus simple de la question, peut-être pour donner une dérivation à partir MId'une chaîne accessible donnée.
xnor
1
Quelle devrait être la sortie si elle IMest fournie ou MUMMI?
Beta Decay

Réponses:

7

SWI Prolog, 183 caractères

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 diriez-vous d'un Prolog, (puisque personne n'a répondu dans 6 mois). Pour exécuter, utilisez simplement "s (mi, mu)". Le code décompose les atomes en caractères, puis recherche la solution.

swstephe
la source
2
Cela renvoie faussement false s(mi,miiii)et, en général, tout élément nécessitant plus d'une application de la règle 2 pour prouver.
algorithmshark