Golf Paterson's Worms

Question

Paterson's worms are a kind of cellular automaton that exist on an infinite triangular grid and, every step, they turn in some direction and move one unit. Their defining properties are that they can never go over the same spot twice, and whenever they encounter the same surroundings, they make the same decision. A worm always "sees" from its own perspective with its tail located at 3 and its head located in the center of this hexagon:

For example, consider the worm with the rules:

1. If 0, 1, 2, 4, and 5 are all blank, move in direction 2
2. If 0, 1, 4, and 5 are blank, and 2 is filled, move in direction 0
3. If 0, 1, and 5 are blank, and 2 and 4 are filled, move in direction 0

This results in the following path (from Wikipedia):

If the worm finds itself in a situation where all surroundings are filled, it terminates.

Input

A list of numbers. The nth number indicates what decision the worm should make on the nth new situation it encounters where it has to make a decision. Note that if all but one of its surroundings are filled, it must move in the only direction that is empty. This does not count as a "decision" and does not consume a number. To generate the example worm shown above, the input would be [2, 0, 0]. The input is guaranteed to produce a worm that terminates and does not retrace its path, and the input will never be too short.

Output

Output a list of coordinates indicating where the head of the worm is, starting at (1, 0). We will consider moving up and to the right to be a decrease in only the y-value, but moving up and to the left to be a decrease in the x-value and a decrease in the y-value. For example, the output of the path for the example input is

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

Test cases

You can use the javascript snippet to run tests as well.

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

The following hastily assembled (possibly buggy) program will display the worms:

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>

Answer 1

JavaScript (ES6),  261 250  249 bytes

Takes the input list in reverse order. Returns a list of \$[x,y]\$ pairs.

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)

Try it online!

This is essentially a port of the demo snippet.

Answer 2

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}

(not counting the function naming part, f:)

Try it online!

D,:-D:2\6 3 generates the six cardinal directions (1 0;1 1;0 1;-1 0;-1 -1;0 -1)

d::0 is the current direction, used as an index mod 6 in D

m::2/=6 generates the initial worm memory 32 16 8 4 2 1. the bits of each number encode the surroundings (0=visited segment; 1=unvisited). initially m contains only unambiguous surroundings - those in which a single exit is available.

X::(!6),x are the worm's rules. we prepend 0 1 2 3 4 5 to match the intial unambiguous surroundings in m.

{...}/,1 0 apply until convergence the function { } starting with a 1-element list containing 1 0. the list will contain pairs of coordinates visited by the worm.

D 6!d+!6 the six cardinal directions starting from d and going around clockwise

h:*|x last of the argument, i.e. the position of the worm's head

(2*h:*|x)+/:D 6!d+!6 multiply the head's coordinates by 2 and add the cardinal directions. this is our way to represent the segments between points.

+':x add pairs of adjacent visited points - this gives us the representations of segments between them

^(...)?... find out which of the head's surrounding segments haven't been visited yet

p:2/ binary encode and assign to p

m::?m,p append to m and keep the distinct, i.e. append p to m only if p doesn't occur in m

$[...;...;...] if-then-else

c:X m?p find the index of p in m and use it as an index in X. out-of-bounds indexing results in 0N ("null")

$[(~p)|^c:X m?p;x;...] if p is 0 (no exit path) or c is 0N, then return x which will force convergence and stop the loop

x,,h+D 6!d+:c else append the new head to x and repeat