Infinite Snake game

Question

Infinite Snake is just like the video game Snake, except for that the snake is infinitely long, there are no items to eat, and the Snake needs to move in a repeating n-step move pattern (e.g. right, up, right, up, right, down). The only constraint is that you can't crash back into yourself.

Challenge

Your goal is to write code that counts the number of valid move patterns of length n, where two patterns are considered the same if you can get from one to the other through a series of rotations, reflections, and reversals.

This is a code-golf challenge, so the shortest code in bytes wins.

---

Origin

This sequence is based on the On-Line Encyclopedia of Integer Sequence's lastest "nice" sequence, A334322.

Number of endless self-avoiding walks of length n for the square lattice.

An "endless self-avoiding walk" (i.e., valid move pattern) is defined in the paper Endless self-avoiding walks by Nathan Clisby on the arXiv. Roughly speaking, an \$n\$-step self-avoiding walk (in the usual sense) is called endless if you can concatenate it with itself head-to-tail an infinite number of times and remain self-avoiding.

Example

For example, Figure 2.1 in the paper gives an example of an endless self-avoiding walk (of length six) on the left and a non-example on the right.

---

Small test cases

f(1) = 1:
---->

f(2) = 2:
---->----> and ---->
                   |
                   v

f(3) = 3:
---->---->---->, ---->---->, and ---->     
                          |          |
                          v          v---->

f(4) = 7:
---->---->---->---->, ---->---->---->, ---->---->     ,
                                    |           |
                                    v           v---->

---->---->, ---->    ^, ---->     , and ---->     .
         |      |    |      |               |
         v      v---->      v---->          v
         |                       |          |
         v                       v          v---->

More small values:

 f(5) =   16
 f(6) =   39
 f(7) =   96
 f(8) =  245
 f(9) =  631
f(10) = 1642

Answer 1

JavaScript (ES6), 240 bytes

Returns the \$n\$-th term of the sequence.

f=(n,p=[],s=[])=>n?[-1,0,1,2].map(d=>f(n-1,[...p,[d%2,~-d%2]],s))|N:N=[...p,...p].every(o=([h,v])=>o[[n+=h,y+=v]]^=1,y=0)&&s.every(P=>(g=j=>!j||P.reverse().some(([h,v],i)=>(j&4?h:-h)-p[i][j&1]|(j&2?v:-v)-p[i][~j&1])&g(j-.5))(8))?s.push(p):N

Try it online!

A334322 (133 bytes)

This is a version where the tests on symmetries of the square and reversals of the path have been removed. So, it generates A334322 instead.

This is just meant as a verification of the main algorithm.

f=(n,p=[],s=[])=>n?[-1,0,1,2].map(d=>f(n-1,[...p,[d%2,~-d%2]],s))|N:N=[...p,...p].every(o=([h,v])=>o[[n+=h,y+=v]]^=1,y=0)?s.push(p):N

Try it online!

Commented

Main algorithm

This is the main algorithm, which generates A334322.

f = (               // f is a recursive function taking:
  n,                //   n = input
  p = [],           //   p[] = current path as a list of (dx, dy)
  s = []            //   s[] = array of solutions
) =>                //
  n ?               // if n is not equal to 0:
    [-1, 0, 1, 2]   //   list of directions
    .map(d =>       //   for each direction d:
      f(            //     do a recursive call:
        n - 1,      //       decrement n
        [           //       new path:
          ...p,     //         copy all previous entries
          [         //         add a new pair (dx, dy):
            d % 2,  //           with dx = d mod 2
            ~-d % 2 //           and dy = (d - 1) mod 2
          ]         //           (NB: sign of mod = sign of dividend)
        ],          //       end of new path
        s           //       pass s[] unchanged
      )             //     end of recursive call
    ) | N           //   end of map(); yield N
  :                 // else:
    N =             //   update N:
      [...p, ...p]  //     append the path to itself
      .every(o =    //     o is an object used to store the positions
        ([h, v]) => //     for each (h, v) = (dx, dy):
        o[[         //       update o for the new position:
          n += h,   //         add dx to n
          y += v    //         add dy to y
        ]] ^= 1,    //       if a position was already visited, this XOR gives 0
        y = 0       //       start with y = 0 (we already have n = 0)
      ) ?           //     end of every(); if the path is self-avoiding:
        s.push(p)   //       push it into s[]
      :             //     else:
        N           //       leave N unchanged (see the note below)

Note: The first iteration always leads to a valid straight path. Because of that, \$N\$ is guaranteed to be defined when we encounter an invalid path for the first time. (Otherwise, this N = N could be a problem, as \$N\$ is not explicitly defined anywhere else.)

Additional tests

Below are the additional tests that are performed to detect symmetries of the square and reversals of the path.

There are \$16\$ different tests whose parameters depend on the bits of a counter \$j\$ going from \$8\$ to \$0\$. We subtract \$1/2\$ from \$j\$ between each iteration so that each set of parameters is tested twice: once with the path \$P[\:]\$ reversed and once with \$P[\:]\$ put back in the original order.

s.every(P =>             // for each previous path P[] in s[]:
  ( g = j =>             //   g is a recursive function taking a counter j:
    !j ||                //     success if j = 0
    P.reverse()          //     otherwise, reverse P[]
    .some(([h, v], i) => //     for each (h, v) at position i in P[]:
      (j & 4 ? h : -h)   //       compare either h or -h with
      - p[i][j & 1] |    //       either p[i][0] or p[i][1]
      (j & 2 ? v : -v)   //       compare either v or -v with
      - p[i][~j & 1]     //       the other component of p[i]
    ) &                  //     end of some()
    g(j - .5)            //     do a recursive call with j - 1/2
  )(8)                   //   initial call to g with j = 8
)                        // end of every()