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:
Sebagai contoh, pertimbangkan worm dengan aturan:
- Jika 0, 1, 2, 4, dan 5 semuanya kosong, pindah ke arah 2
- Jika 0, 1, 4, dan 5 kosong, dan 2 diisi, pindah ke arah 0
- Jika 0, 1, dan 5 kosong, dan 2 dan 4 diisi, pindah ke arah 0
Ini menghasilkan jalur berikut (dari Wikipedia):
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:
var canvas = document.querySelector("canvas");
var ctx = canvas.getContext("2d");
var input, memory;
var log = str => {
console.log(str);
document.querySelector("textarea").value += str + "\n";
};
var orientations = [
[1, 0],
[1, 1],
[0, 1],
[-1, 0],
[-1, -1],
[0, -1]
];
var arena = {
grid: [[[1, 0, 0]]],
maxX: 1,
maxY: 0,
expandGrid: function() {
var grid = this.grid;
var newWidth = grid[0].length + 2,
newHeight = grid.length + 2;
var createRow = () => {
var result = [];
for (let i = 0; i < newWidth; ++i) result.push([0, 0, 0]);
return result;
};
for (let row of grid) {
row.push([0, 0, 0]);
row.unshift([0, 0, 0]);
};
grid.push(createRow());
grid.unshift(createRow());
},
gridWidth: function() {
return this.grid[0].length
},
gridHeight: function() {
return this.grid.length
},
get: function(x, y) {
var colOffset = Math.floor(this.gridWidth() / 2),
rowOffset = Math.floor(this.gridHeight() / 2);
return this.grid[y + rowOffset][x + colOffset];
},
isAtEnd: function(x, y) {
var colOffset = Math.floor(this.gridWidth() / 2),
rowOffset = Math.floor(this.gridHeight() / 2);
return x === -colOffset || x + colOffset + 1 === this.gridWidth() ||
y === -rowOffset || y + rowOffset + 1 === this.gridHeight();
},
getEdge: function(x, y, o) {
if (o % 2 === 0) return this.get(x, y)[o / 2];
else {
let a, b;
[a, b] = orientations[(o + 3) % 6];
return this.get(x - a, y - b)[((o + 3) % 6) / 2];
}
},
setEdge: function(x, y, o) {
if (Math.abs(x) > this.maxX) this.maxX = Math.abs(x);
if (Math.abs(y) > this.maxY) this.maxY = Math.abs(y);
if (o % 2 === 0) {
if (this.get(x, y)[o / 2]) throw new Error("Path already taken");
this.get(x, y)[o / 2] = 1;
} else {
let a, b;
[a, b] = orientations[(o + 3) % 6];
if (this.get(x - a, y - b)[((o + 3) % 6) / 2]) throw new Error("Path already taken");
this.get(x - a, y - b)[((o + 3) % 6) / 2] = 1;
}
}
};
var drawGrid = function(area) {
var width = canvas.width,
height = canvas.height;
ctx.clearRect(0, 0, width, height);
var gridWidth = arena.gridWidth(),
gridHeight = arena.gridHeight();
var triangleLen = Math.floor(Math.min(
width / (arena.maxX * 2 + arena.maxY),
height / (arena.maxY * Math.sqrt(3)),
width / 4
));
var convert = (x, y) => [(x - y / 2) * triangleLen, triangleLen * y * Math.sqrt(3) / 2];
var drawCirc = function(x, y) {
var a, b;
ctx.beginPath();
[a, b] = convert(x, y);
ctx.arc(a, b, 5, 0, 2 * Math.PI);
ctx.fill();
};
ctx.fillStyle = "black";
for (let y = 0; triangleLen * y * Math.sqrt(3) / 2 < height; ++y) {
for (let x = Math.floor(y / 2); triangleLen * (x - y / 2) < width; ++x) {
drawCirc(x, y);
}
};
var drawLine = function(a, b, c, d) {
var x, y;
ctx.beginPath();
[x, y] = convert(a, b);
ctx.moveTo(x, y);
[x, y] = convert(a + c, b + d);
ctx.lineTo(x, y);
ctx.stroke();
};
var centerY = Math.round(height / (triangleLen * Math.sqrt(3)));
var centerX = Math.round(width / (2 * triangleLen) + centerY / 2);
ctx.fillStyle = "red";
drawCirc(centerX, centerY);
for (let row = -(gridHeight - 1) / 2; row < (gridHeight + 1) / 2; ++row) {
for (let col = -(gridWidth - 1) / 2; col < (gridWidth + 1) / 2; ++col) {
let lines = arena.get(col, row);
for (let j = 0; j < lines.length; ++j) {
if (lines[j]) {
let or = orientations[2 * j];
drawLine(col + centerX, row + centerY, or[0], or[1]);
}
}
}
}
};
var step = function(x, y, absoluteOrientation) {
log('(' + x + ',' + y + ')');
var surroundings = 0;
for (let i = 0; i < 6; ++i) {
if (arena.getEdge(x, y, (absoluteOrientation + i) % 6)) {
surroundings |= (1 << i);
}
}
if (surroundings == 63) {
console.log("Done!");
return;
}
var action;
if (memory[surroundings] !== undefined)
action = memory[surroundings];
else {
action = input.shift();
memory[surroundings] = action;
}
absoluteOrientation = (absoluteOrientation + action) % 6;
arena.setEdge(x, y, absoluteOrientation);
var or = orientations[absoluteOrientation];
x += or[0];
y += or[1];
if (arena.isAtEnd(x, y)) arena.expandGrid();
drawGrid(arena);
setTimeout(function() {
step(x, y, absoluteOrientation);
}, parseFloat(document.querySelector("input[type=number]").value));
};
var go = function() {
input = document.querySelector("input[type=text]").value.split(",").map(x => parseInt(x, 10));
arena.grid = [[[1, 0, 0]]];
arena.maxX = 1;
arena.maxY = 0;
memory = {};
for (let i = 0; i < 6; ++i) {
memory[(~(1 << i)) & 63] = i;
}
arena.expandGrid();
arena.expandGrid();
step(1, 0, 0);
};
document.querySelector("button").onclick = go;
canvas {
border: 1px solid black;
}
Input: <input type="text" placeholder="Comma separated input"><br />
Delay (ms): <input type="number" placeholder="delay" value="500"/><button>Go</button><br />
<canvas width="500" height="400"></canvas><br />
<textarea></textarea>
[1,0,4,2,0,1,5]
.)Jawaban:
JavaScript (ES6),
261 250249 byteMengambil daftar input dalam urutan terbalik. Mengembalikan daftar pasangan .[x,y]
Cobalah online!
Ini pada dasarnya adalah port dari cuplikan demo.
sumber
K (ngn / k) , 115 byte
(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 inD
m::2/=6
menghasilkan memori cacing awal32 16 8 4 2 1
. bit dari setiap angka menyandikan lingkungan (0 = segmen yang dikunjungi; 1 = belum dikunjungi). pada awalnyam
hanya berisi lingkungan yang tidak ambigu - lingkungan yang menyediakan satu pintu keluar.X::(!6),x
adalah aturan worm. kami0 1 2 3 4 5
cocok untuk mencocokkan lingkungan ambigu awal dim
.{
...}/,1 0
terapkan hingga konvergensi fungsi{
}
dimulai dengan daftar 1 elemen yang berisi1 0
. daftar akan berisi pasangan koordinat yang dikunjungi oleh worm.D 6!d+!6
enam arah mata angin mulai darid
dan berputar searah jarum jamh:*|x
Argumen terakhir, yaitu posisi kepala cacing(2*h:*|x)+/:D 6!d+!6
kalikan 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 dikunjungip:2/
menyandikan dan menetapkan biner untukp
m::?m,p
append kem
dan menjaga berbeda, yaitu appendp
untukm
hanya jikap
tidak terjadi dim
$[
...;
...;
...]
jika-maka-lainc:X m?p
cari indeksp
masukm
dan gunakan sebagai indeks masukX
. Hasil pengindeksan di luar batas dalam0N
("null")$[(~p)|^c:X m?p;x;
...]
jikap
adalah 0 (tidak ada jalan keluar) atauc
merupakan0N
, kemudian kembalix
yang akan memaksa konvergensi dan menghentikan loopx,,h+D 6!d+:c
lain tambahkan kepala baru kex
dan ulangisumber