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:
Par exemple, considérez le ver avec les règles:
- Si 0, 1, 2, 4 et 5 sont tous vides, déplacez-vous dans la direction 2
- Si 0, 1, 4 et 5 sont vides et 2 remplis, déplacez-vous dans la direction 0
- 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):
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:
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]
.)Réponses:
JavaScript (ES6),
261 250249 octetsEssayez-le en ligne!
Il s'agit essentiellement d'un portage de l'extrait de démonstration.
la source
K (ngn / k) , 115 octets
(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 dansD
m::2/=6
génère la mémoire initiale du ver32 16 8 4 2 1
. les bits de chaque nombre codent l'environnement (0 = segment visité; 1 = non visité).m
contient initialement uniquement un environnement sans ambiguïté - ceux dans lesquels une seule sortie est disponible.X::(!6),x
sont les règles du ver. nous avons tendance0 1 2 3 4 5
à faire correspondre l'environnement ambiant initial dem
.{
...}/,1 0
appliquer jusqu'à convergence la fonction{
}
commençant par une liste à 1 élément contenant1 0
. la liste contiendra des paires de coordonnées visitées par le ver.D 6!d+!6
les six directions cardinales à partir ded
et dans le sens horaireh:*|x
dernier argument, c'est-à-dire la position de la tête du ver(2*h:*|x)+/:D 6!d+!6
multipliez 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,p
ajouterm
et conserver le distinct, c.-p
à- d. ajouterm
seulement sip
cela ne se produitm
$[
...;
...;
...]
si-alors-sinonc:X m?p
trouver l'index dep
inm
et l'utiliser comme index dansX
. l'indexation hors limites entraîne0N
("null")$[(~p)|^c:X m?p;x;
...]
sip
est 0 (pas de chemin de sortie) ouc
est0N
, alors retournex
ce qui forcera la convergence et arrêtera la bouclex,,h+D 6!d+:c
sinon ajouter la nouvelle têtex
et répéterla source