Cacing Golf Paterson

11

Cacing Paterson adalah sejenis otomat seluler yang ada pada grid segitiga tak terbatas dan, setiap langkah, mereka berputar ke beberapa arah dan memindahkan satu unit. Sifat definisinya adalah bahwa mereka tidak pernah dapat pergi ke tempat yang sama dua kali, dan setiap kali mereka menghadapi lingkungan yang sama, mereka membuat keputusan yang sama. Seekor cacing selalu "melihat" dari sudut pandangnya sendiri dengan ekornya terletak di 3 dan kepalanya terletak di tengah segi enam ini:

Gambar dari wikipedia

Sebagai contoh, pertimbangkan worm dengan aturan:

  1. Jika 0, 1, 2, 4, dan 5 semuanya kosong, pindah ke arah 2
  2. Jika 0, 1, 4, dan 5 kosong, dan 2 diisi, pindah ke arah 0
  3. Jika 0, 1, dan 5 kosong, dan 2 dan 4 diisi, pindah ke arah 0

Ini menghasilkan jalur berikut (dari Wikipedia):

Jalur cacing

Jika worm menemukan dirinya dalam situasi di mana semua lingkungan dipenuhi, ia berakhir.

Memasukkan

Daftar angka. Angka kesembilan menunjukkan keputusan apa yang harus diambil oleh cacing pada situasi baru ke-9 yang dihadapinya di mana ia harus mengambil keputusan. Perhatikan bahwa jika semua kecuali satu dari lingkungannya terisi, ia harus bergerak ke satu-satunya arah yang kosong. Ini tidak dihitung sebagai "keputusan" dan tidak mengkonsumsi nomor. Untuk menghasilkan contoh worm yang ditunjukkan di atas, inputnya adalah [2, 0, 0]. Input dijamin untuk menghasilkan worm yang berakhir dan tidak menelusuri jalannya, dan input tidak akan pernah terlalu pendek.

Keluaran

Keluarkan daftar koordinat yang menunjukkan di mana kepala worm berada, mulai dari (1, 0). Kami akan mempertimbangkan untuk bergerak naik dan ke kanan untuk hanya mengurangi nilai y, tetapi bergerak naik dan ke kiri untuk menjadi penurunan nilai x dan penurunan nilai y. Sebagai contoh, output dari path untuk input contoh adalah

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

Uji kasus

Anda dapat menggunakan potongan javascript untuk menjalankan tes juga.

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

Program yang tergesa-gesa (mungkin bermasalah) berikut ini akan menampilkan worm:

soktinpk
sumber
2
Case test yang disarankan : p (Ini [1,0,4,2,0,1,5].)
Arnauld
Bisakah kita mengambil input dalam urutan terbalik?
Arnauld
1
@Arnauld yakin itu sepertinya ok
soktinpk

Jawaban:

4

JavaScript (ES6),  261 250  249 byte

Mengambil daftar input dalam urutan terbalik. Mengembalikan daftar pasangan .[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)

Cobalah online!

Ini pada dasarnya adalah port dari cuplikan demo.

Arnauld
sumber
4

K (ngn / k) , 115 byte

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}

(tidak termasuk bagian penamaan fungsi, f:)

Cobalah online!

D,:-D:2\6 3 menghasilkan enam arah mata angin (1 0;1 1;0 1;-1 0;-1 -1;0 -1)

d::0 adalah arah saat ini, digunakan sebagai indeks mod 6 in D

m::2/=6menghasilkan memori cacing awal 32 16 8 4 2 1. bit dari setiap angka menyandikan lingkungan (0 = segmen yang dikunjungi; 1 = belum dikunjungi). pada awalnya mhanya berisi lingkungan yang tidak ambigu - lingkungan yang menyediakan satu pintu keluar.

X::(!6),xadalah aturan worm. kami 0 1 2 3 4 5cocok untuk mencocokkan lingkungan ambigu awal di m.

{... }/,1 0terapkan hingga konvergensi fungsi { }dimulai dengan daftar 1 elemen yang berisi 1 0. daftar akan berisi pasangan koordinat yang dikunjungi oleh worm.

D 6!d+!6enam arah mata angin mulai dari ddan berputar searah jarum jam

h:*|x Argumen terakhir, yaitu posisi kepala cacing

(2*h:*|x)+/:D 6!d+!6kalikan koordinat kepala dengan 2 dan tambahkan arah mata angin. ini adalah cara kami untuk mewakili segmen antar poin.

+':x tambahkan pasangan poin yang dikunjungi yang berdekatan - ini memberi kami representasi segmen di antara mereka

^(... )?... cari tahu segmen mana dari kepala yang belum dikunjungi

p:2/ menyandikan dan menetapkan biner untuk p

m::?m,pappend ke mdan menjaga berbeda, yaitu append puntuk mhanya jika ptidak terjadi dim

$[... ;... ;... ]jika-maka-lain

c:X m?pcari indeks pmasuk mdan gunakan sebagai indeks masuk X. Hasil pengindeksan di luar batas dalam 0N("null")

$[(~p)|^c:X m?p;x;... ]jika padalah 0 (tidak ada jalan keluar) atau cmerupakan 0N, kemudian kembali xyang akan memaksa konvergensi dan menghentikan loop

x,,h+D 6!d+:clain tambahkan kepala baru ke xdan ulangi

ngn
sumber