Patersons Würmer sind eine Art zellularer Automat, der auf einem unendlichen dreieckigen Gitter existiert und sich bei jedem Schritt in eine Richtung dreht und eine Einheit bewegt. Ihre bestimmenden Eigenschaften sind, dass sie niemals zweimal über dieselbe Stelle gehen können und immer dann, wenn sie auf dieselbe Umgebung treffen, dieselbe Entscheidung treffen. Ein Wurm "sieht" immer aus seiner eigenen Perspektive, wobei sich sein Schwanz bei 3 befindet und sein Kopf sich in der Mitte dieses Sechsecks befindet:

Betrachten Sie zum Beispiel den Wurm mit den Regeln:

1. Wenn 0, 1, 2, 4 und 5 leer sind, bewegen Sie sich in Richtung 2
2. Wenn 0, 1, 4 und 5 leer sind und 2 gefüllt ist, bewegen Sie sich in Richtung 0
3. Wenn 0, 1 und 5 leer sind und 2 und 4 gefüllt sind, bewegen Sie sich in Richtung 0

Daraus ergibt sich folgender Pfad (aus Wikipedia):

Befindet sich der Wurm in einer Situation, in der alle Umgebungen gefüllt sind, endet er.

Eingang

Eine Liste von Zahlen. Die n-te Zahl gibt an, welche Entscheidung der Wurm in der n-ten neuen Situation treffen soll, in der er eine Entscheidung treffen muss. Beachten Sie, dass es sich in die einzige Richtung bewegen muss, die leer ist, wenn alle bis auf eine Umgebung gefüllt sind. Dies zählt nicht als "Entscheidung" und verbraucht keine Zahl. Um den oben gezeigten Beispielwurm zu erzeugen, wäre die Eingabe [2, 0, 0]. Die Eingabe erzeugt garantiert einen Wurm, der endet und seinen Pfad nicht zurückverfolgt, und die Eingabe wird niemals zu kurz sein.

Ausgabe

Geben Sie eine Liste von Koordinaten aus, die angeben, wo sich der Kopf des Wurms befindet, beginnend bei (1, 0). Wir werden betrachten, nach oben und rechts zu bewegen, um nur den y-Wert zu verringern, aber nach oben und links zu bewegen, um den x-Wert zu verringern und um den y-Wert zu verringern. Beispielsweise ist die Ausgabe des Pfads für die Beispieleingabe

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

Testfälle

Sie können das Javascript-Snippet auch zum Ausführen von Tests verwenden.

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

Das folgende hastig zusammengestellte (möglicherweise fehlerhafte) Programm zeigt die Würmer an:

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>

JavaScript (ES6),  261 250  249 Byte

Nimmt die Eingabeliste in umgekehrter Reihenfolge. Gibt eine Liste von Paaren zurück.$[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)

Probieren Sie es online aus!

Dies ist im Wesentlichen ein Port des Demo-Snippets.

K (ngn / k) , 115 Bytes

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}

(ohne Berücksichtigung des Funktionsbenennungsteils f:)

Probieren Sie es online aus!

D,:-D:2\6 3 erzeugt die sechs Himmelsrichtungen (1 0;1 1;0 1;-1 0;-1 -1;0 -1)

d::0 ist die aktuelle Richtung, die als Index mod 6 in verwendet wird D

m::2/=6generiert den anfänglichen Wurmspeicher 32 16 8 4 2 1. Die Bits jeder Nummer codieren die Umgebung (0 = besuchtes Segment; 1 = nicht besucht). menthält zunächst nur eindeutige Umgebungen - solche, in denen ein einziger Ausgang zur Verfügung steht.

X::(!6),xsind die Regeln des Wurms. Wir stellen uns vor 0 1 2 3 4 5, um der ursprünglichen eindeutigen Umgebung in zu entsprechen m.

{... }/,1 0bis zur Konvergenz die Funktion anwenden, die { }mit einer 1-Element-Liste beginnt, die enthält 1 0. Die Liste enthält Koordinatenpaare, die vom Wurm besucht werden.

D 6!d+!6Die sechs Himmelsrichtungen beginnen dim Uhrzeigersinn und gehen im Uhrzeigersinn umher

h:*|x Letzter des Arguments, dh die Position des Kopfes des Wurms

(2*h:*|x)+/:D 6!d+!6Multiplizieren Sie die Kopfkoordinaten mit 2 und addieren Sie die Himmelsrichtungen. Auf diese Weise können wir die Segmente zwischen Punkten darstellen.

+':x Fügen Sie Paare benachbarter besuchter Punkte hinzu - dies gibt uns die Darstellungen von Segmenten zwischen ihnen

^(... )?... herausfinden, welche der umgebenden Segmente des Kopfes noch nicht besucht wurden

p:2/ binär codieren und zuweisen p

m::?m,panhängen mund die Unterscheidungskraft beibehalten, dh nur anhängen p, mwenn pdies in nicht der Fall istm

$[... ;... ;... ]wenn-dann-sonst

c:X m?pSuchen Sie den Index von pin mund verwenden Sie ihn als Index für X. Out-of-Bound-Indizierung führt zu 0N("null")

$[(~p)|^c:X m?p;x;... ]wenn p0 ist (kein Austrittspfad) oder cist 0N, dann return, xwas die Konvergenz erzwingt und die Schleife stoppt

x,,h+D 6!d+:cAndernfalls hängen Sie den neuen Kopf an xund wiederholen Sie den Vorgang