Golf Paterson's Worms

11

Les vers de Paterson sont une sorte d'automate cellulaire qui existe sur une grille triangulaire infinie et, à chaque pas, ils tournent dans une certaine direction et se déplacent d'une unité. Leurs propriétés déterminantes sont qu’ils ne peuvent jamais passer deux fois au même endroit et qu’ils rencontrent le même environnement, ils prennent la même décision. Un ver "voit" toujours de son propre point de vue avec sa queue située à 3 et sa tête située au centre de cet hexagone:

Image de wikipedia

Par exemple, considérez le ver avec les règles:

  1. Si 0, 1, 2, 4 et 5 sont tous vides, déplacez-vous dans la direction 2
  2. Si 0, 1, 4 et 5 sont vides et 2 remplis, déplacez-vous dans la direction 0
  3. Si 0, 1 et 5 sont vides et que 2 et 4 sont remplis, déplacez-vous dans la direction 0

Il en résulte le chemin suivant (à partir de Wikipedia):

Chemin de ver

Si le ver se retrouve dans une situation où tous les environnements sont remplis, il se termine.

Contribution

Une liste de chiffres. Le nième nombre indique quelle décision le ver doit prendre sur la nième nouvelle situation qu'il rencontre où il doit prendre une décision. Notez que si tout sauf un de ses environs est rempli, il doit se déplacer dans la seule direction qui est vide. Cela ne compte pas comme une "décision" et ne consomme pas un nombre. Pour générer l'exemple de ver illustré ci-dessus, l'entrée serait [2, 0, 0]. L'entrée est garantie de produire un ver qui se termine et ne retrace pas son chemin, et l'entrée ne sera jamais trop courte.

Production

Afficher une liste de coordonnées indiquant où se trouve la tête du ver, en commençant par (1, 0). Nous considérerons le déplacement vers le haut et vers la droite comme une diminution de la valeur y uniquement, mais le déplacement vers le haut et vers la gauche pour une diminution de la valeur x et une diminution de la valeur y. Par exemple, la sortie du chemin pour l'exemple d'entrée est

(1, 0), (1, 1), (0, 0), (-1, -1), (0, -1), (0, 0), (0, 1), (-1, 0), (0, 0)

Cas de test

Vous pouvez également utiliser l'extrait de code javascript pour exécuter des tests.

[2,0,0]: (1,0),(1,1),(0,0),(-1,-1),(0,-1),(0,0),(0,1),(-1,0),(0,0)
[1,0,4,0,1,5]: (1,0),(2,1),(2,2),(1,2),(0,1),(0,0),(0,-1),(1,-1),(2,0),(2,1),(3,1),(4,2),(4,3),(3,3),(2,2),(1,1),(1,0),(2,0),(3,1),(3,0),(4,0),(5,1),(5,2),(4,2),(3,2),(2,1),(1,1),(0,0),(-1,0),(-2,-1),(-2,-2),(-1,-2),(0,-1),(1,0),(1,-1),(2,-1),(3,0),(4,1),(4,2),(5,3),(5,4),(4,4),(3,3),(3,4),(2,4),(1,3),(1,2),(1,1),(0,1),(-1,0),(-1,1),(-2,1),(-3,0),(-3,-1),(-2,-1),(-1,-1),(0,0)
[1,0,5,1]: (1,0),(2,1),(2,2),(1,2),(0,1),(0,0),(0,-1),(1,-1),(2,0),(2,1),(3,2),(3,3),(2,3),(1,2),(0,2),(-1,1),(-1,0),(0,0),(1,1),(1,2),(1,3),(0,3),(-1,2),(-1,1),(-2,0),(-2,-1),(-1,-1),(0,0)
[2,0,1,0]: (1,0),(1,1),(0,0),(-1,-1),(0,-1),(0,0),(-1,0),(-1,-1),(-1,-2),(0,-1),(1,0),(2,1),(1,1),(0,1),(0,0)

Le programme suivant assemblé à la hâte (peut-être buggé) affichera les vers:

soktinpk
la source
2
Cas de test suggéré : p (C'est [1,0,4,2,0,1,5].)
Arnauld
Pouvons-nous prendre l'entrée dans l'ordre inverse?
Arnauld
1
@Arnauld sûr que cela semble ok
soktinpk

Réponses:

4

JavaScript (ES6),  261 250  249 octets

[X,y]

a=>(G=[[[x=1]]],v=[0,1,1,0,-1,-1],F=y=>[[x,y],...v.every((_,i)=>k^=g(o+i)[q%3]<<i,k=63,g=o=>(r=G[Y=y-o%2*v[q=(o+3)%6]]=G[Y]||[])[X=x-o%2*v[-~q%6]]=r[X]||[])?F(y+v[g(o+=F[k]|=1/F[k]?0:k&~-k?a.pop():31-Math.clz32(k))[q%3]=1,o%6],x+=v[-~o%6]):[]])(o=0)

Essayez-le en ligne!

Il s'agit essentiellement d'un portage de l'extrait de démonstration.

Arnauld
la source
4

K (ngn / k) , 115 octets

D,:-D:2\6 3;f:{d::0;m::2/=6;X::(!6),x;{m::?m,p:2/^(+':x)?(2*h:*|x)+/:D 6!d+!6;$[(~p)|^c:X m?p;x;x,,h+D 6!d+:c]}/,1 0}

(sans compter la partie de nommage des fonctions, f:)

Essayez-le en ligne!

D,:-D:2\6 3 génère les six directions cardinales (1 0;1 1;0 1;-1 0;-1 -1;0 -1)

d::0 est la direction actuelle, utilisée comme un index mod 6 dans D

m::2/=6génère la mémoire initiale du ver 32 16 8 4 2 1. les bits de chaque nombre codent l'environnement (0 = segment visité; 1 = non visité). mcontient initialement uniquement un environnement sans ambiguïté - ceux dans lesquels une seule sortie est disponible.

X::(!6),xsont les règles du ver. nous avons tendance 0 1 2 3 4 5à faire correspondre l'environnement ambiant initial de m.

{... }/,1 0appliquer jusqu'à convergence la fonction { }commençant par une liste à 1 élément contenant 1 0. la liste contiendra des paires de coordonnées visitées par le ver.

D 6!d+!6les six directions cardinales à partir de det dans le sens horaire

h:*|x dernier argument, c'est-à-dire la position de la tête du ver

(2*h:*|x)+/:D 6!d+!6multipliez les coordonnées de la tête par 2 et ajoutez les directions cardinales. c'est notre façon de représenter les segments entre les points.

+':x ajouter des paires de points visités adjacents - cela nous donne les représentations des segments entre eux

^(... )?... savoir lequel des segments environnants de la tête n'a pas encore été visité

p:2/ encoder binaire et attribuer à p

m::?m,pajouter met conserver le distinct, c.- pà- d. ajouter mseulement si pcela ne se produitm

$[... ;... ;... ]si-alors-sinon

c:X m?ptrouver l'index de pin met l'utiliser comme index dans X. l'indexation hors limites entraîne 0N("null")

$[(~p)|^c:X m?p;x;... ]si pest 0 (pas de chemin de sortie) ou cest 0N, alors retourne xce qui forcera la convergence et arrêtera la boucle

x,,h+D 6!d+:csinon ajouter la nouvelle tête xet répéter

ngn
la source