Golf Paterson's Worms

11

Robaki Patersona są rodzajem automatu komórkowego, który istnieje na nieskończonej trójkątnej siatce i na każdym kroku obracają się w pewnym kierunku i poruszają jedną jednostkę. Ich decydującymi właściwościami jest to, że nigdy nie mogą przejść dwa razy w to samo miejsce, a ilekroć napotkają to samo otoczenie, podejmują tę samą decyzję. Robak zawsze „widzi” z własnej perspektywy z ogonem umieszczonym na 3 i głową umieszczoną na środku tego sześciokąta:

Obraz z wikipedii

Na przykład rozważ robaka z regułami:

  1. Jeśli 0, 1, 2, 4 i 5 są puste, przejdź w kierunku 2
  2. Jeśli 0, 1, 4 i 5 są puste, a 2 jest wypełnione, przejdź w kierunku 0
  3. Jeśli 0, 1 i 5 są puste, a 2 i 4 są wypełnione, przejdź w kierunku 0

To prowadzi do następującej ścieżki (z Wikipedii):

Ścieżka robaka

Jeśli robak znajdzie się w sytuacji, gdy całe otoczenie jest wypełnione, kończy się.

Wejście

Lista liczb. N-ta liczba wskazuje, jaką decyzję powinien podjąć robak w n-tej nowej napotkanej sytuacji, w której musi podjąć decyzję. Zauważ, że jeśli całe otoczenie oprócz jednego jest wypełnione, musi poruszać się w jedynym pustym kierunku. Nie liczy się to jako „decyzja” i nie zużywa liczby. Aby wygenerować przykładowego robaka pokazanego powyżej, dane wejściowe to [2, 0, 0]. Dane wejściowe gwarantują wytworzenie robaka, który kończy działanie i nie podąża ścieżką, a dane wejściowe nigdy nie będą zbyt krótkie.

Wynik

Wypisuje listę współrzędnych wskazujących, gdzie znajduje się głowa robaka, zaczynając od (1, 0). Rozważymy przesunięcie w górę i w prawo, aby zmniejszyć tylko wartość y, ale przesunięcie w górę i w lewo, aby zmniejszyć wartość x i spadek wartości y. Na przykład dane wyjściowe ścieżki dla przykładowego wejścia to

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

Przypadki testowe

Możesz także użyć fragmentu javascript do uruchomienia testów.

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

Następujący pospiesznie złożony (prawdopodobnie błędny) program wyświetli robaki:

soktinpk
źródło
2
Sugerowany przypadek testowy : p (To jest [1,0,4,2,0,1,5].)
Arnauld
Czy możemy wziąć dane wejściowe w odwrotnej kolejności?
Arnauld,
1
@Arnauld na pewno wydaje się ok
soktinpk

Odpowiedzi:

4

JavaScript (ES6),  261 250  249 bajtów

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

Wypróbuj online!

Jest to zasadniczo port fragmentu wersji demonstracyjnej.

Arnauld
źródło
4

K (ngn / k) , 115 bajtów

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}

(nie licząc części nazewnictwa funkcji f:)

Wypróbuj online!

D,:-D:2\6 3 generuje sześć głównych kierunków (1 0;1 1;0 1;-1 0;-1 -1;0 -1)

d::0 to bieżący kierunek, stosowany jako indeks mod 6 cali D

m::2/=6generuje początkową pamięć robaka 32 16 8 4 2 1. bity każdej liczby kodują otoczenie (0 = odwiedzany segment; 1 = nie odwiedzony). początkowo mzawiera tylko jednoznaczne otoczenie - te, w których dostępne jest jedno wyjście.

X::(!6),xsą zasadami robaka. staramy 0 1 2 3 4 5się dopasować do pierwotnego jednoznacznego otoczenia w m.

{... }/,1 0stosuje się do momentu konwergencji funkcji { }zaczynającej się od 1-elementowej listy zawierającej 1 0. lista będzie zawierać pary współrzędnych odwiedzanych przez robaka.

D 6!d+!6sześć głównych kierunków, zaczynając od di obracając się zgodnie z ruchem wskazówek zegara

h:*|x ostatni argument, tj. pozycja głowy robaka

(2*h:*|x)+/:D 6!d+!6pomnóż współrzędne głowy przez 2 i dodaj główne kierunki. w ten sposób reprezentujemy segmenty między punktami.

+':x dodaj pary sąsiednich odwiedzanych punktów - to daje nam reprezentacje segmentów między nimi

^(... )?... dowiedz się, które z otaczających segmentów głowy nie były jeszcze odwiedzane

p:2/ kodowanie binarne i przypisywanie do p

m::?m,pDołącz do mi zachować odrębne, tj Dołącz pdo mtylko wtedy, gdy pnie występuje wm

$[... ;... ;... ]jeśli-to-jeszcze

c:X m?pznajdź indeks pin mi użyj go jako indeksu w X. wyniki indeksowania poza zakresem w 0N(„null”)

$[(~p)|^c:X m?p;x;... ]jeśli pjest 0 (brak ścieżki wyjścia) lub cjest 0N, to powrót, xktóry wymusi konwergencję i zatrzyma pętlę

x,,h+D 6!d+:cw przeciwnym razie dołącz nową głowę xi powtórz

ngn
źródło