Los gusanos de Paterson son una especie de autómata celular que existe en una cuadrícula triangular infinita y, a cada paso, giran en alguna dirección y mueven una unidad. Sus propiedades definitorias son que nunca pueden pasar por el mismo lugar dos veces, y cada vez que se encuentran con el mismo entorno, toman la misma decisión. Un gusano siempre "ve" desde su propia perspectiva con su cola ubicada en 3 y su cabeza ubicada en el centro de este hexágono:
Por ejemplo, considere el gusano con las reglas:
- Si 0, 1, 2, 4 y 5 están en blanco, muévase en la dirección 2
- Si 0, 1, 4 y 5 están en blanco, y 2 está lleno, muévase en la dirección 0
- Si 0, 1 y 5 están en blanco, y 2 y 4 están llenos, muévase en la dirección 0
Esto da como resultado la siguiente ruta (de Wikipedia):
Si el gusano se encuentra en una situación en la que se llenan todos los alrededores, termina.
Entrada
Una lista de números. El enésimo número indica qué decisión debe tomar el gusano en la enésima situación nueva que encuentra donde tiene que tomar una decisión. Tenga en cuenta que si todos menos uno de sus alrededores están llenos, debe moverse en la única dirección que está vacía. Esto no cuenta como una "decisión" y no consume un número. Para generar el gusano de ejemplo que se muestra arriba, la entrada sería [2, 0, 0]
. La entrada está garantizada para producir un gusano que termina y no vuelve sobre su camino, y la entrada nunca será demasiado corta.
Salida
Emite una lista de coordenadas que indica dónde está la cabeza del gusano, comenzando en (1, 0)
. Consideraremos que moverse hacia arriba y hacia la derecha es una disminución solo en el valor y, pero moverse hacia arriba y hacia la izquierda es una disminución en el valor xy una disminución en el valor y. Por ejemplo, la salida de la ruta para la entrada de ejemplo es
(1, 0), (1, 1), (0, 0), (-1, -1), (0, -1), (0, 0), (0, 1), (-1, 0), (0, 0)
Casos de prueba
También puede usar el fragmento de JavaScript para ejecutar pruebas.
[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)
El siguiente programa rápidamente ensamblado (posiblemente con errores) mostrará los gusanos:
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]
)Respuestas:
JavaScript (ES6),
261 250249 bytesPruébalo en línea!
Esto es esencialmente un puerto del fragmento de demostración.
fuente
K (ngn / k) , 115 bytes
(sin contar la parte de denominación de funciones
f:
)Pruébalo en línea!
D,:-D:2\6 3
genera las seis direcciones cardinales(1 0;1 1;0 1;-1 0;-1 -1;0 -1)
d::0
es la dirección actual, utilizada como índice mod 6 enD
m::2/=6
genera la memoria inicial del gusano32 16 8 4 2 1
. Los bits de cada número codifican el entorno (0 = segmento visitado; 1 = no visitado). inicialmentem
contiene solo entornos no ambiguos, aquellos en los que hay una única salida disponible.X::(!6),x
son las reglas del gusano. que anteponer0 1 2 3 4 5
para que coincida con el entorno sin ambigüedades en intialm
.{
...}/,1 0
aplique hasta la convergencia la función que{
}
comienza con una lista de 1 elemento que contiene1 0
. La lista contendrá pares de coordenadas visitadas por el gusano.D 6!d+!6
las seis direcciones cardinales que comienzand
y van en sentido horarioh:*|x
último argumento, es decir, la posición de la cabeza del gusano(2*h:*|x)+/:D 6!d+!6
multiplique las coordenadas de la cabeza por 2 y agregue las direcciones cardinales. Esta es nuestra forma de representar los segmentos entre puntos.+':x
agregue pares de puntos adyacentes visitados, esto nos da las representaciones de segmentos entre ellos^(
...)?
... descubra cuáles de los segmentos circundantes de la cabeza aún no han sido visitadosp:2/
codificar binario y asignar ap
m::?m,p
anexados param
y mantener la diferencia, es decir, anexadosp
am
sólo sip
no se produce enm
$[
...;
...;
...]
si-entonces-másc:X m?p
encuentre el índice dep
inm
y úselo como índice enX
. resultados de indexación fuera de límites en0N
("nulo")$[(~p)|^c:X m?p;x;
...]
sip
es 0 (sin ruta de salida) oc
es0N
, entonces devuelvex
lo que forzará la convergencia y detendrá el buclex,,h+D 6!d+:c
de lo contrario, agregue la nueva cabezax
y repitafuente