9
\$\begingroup\$

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 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.

endless self-avoiding walks


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
\$\endgroup\$
9
  • 1
    \$\begingroup\$ It should work for any n given arbitrary RAM and time. \$\endgroup\$ Apr 26 '20 at 4:17
  • 1
    \$\begingroup\$ Hmm... A self-avoiding walk takes social distancing to the next level! \$\endgroup\$ Apr 26 '20 at 5:38
  • 1
    \$\begingroup\$ Mathy titles are scary. You'd probably get more views if it was talking about a drunk man trying to find pubs he has not already visited by repeating the same walk over and over. :-p (I'm saying that tongue-in-cheek, but there's some truth in there...) \$\endgroup\$
    – Arnauld
    Apr 26 '20 at 15:20
  • 4
    \$\begingroup\$ Rebranded just for you, @Arnauld! \$\endgroup\$ Apr 26 '20 at 18:27
  • 1
    \$\begingroup\$ This is on OEIS as oeis.org/A334398. \$\endgroup\$ Aug 28 '20 at 17:02
8
\$\begingroup\$

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()
\$\endgroup\$
1
  • 2
    \$\begingroup\$ The same day you answered this question, this entry was made oeis.org/A334398. I think you should be credited for these numbers and any other entries in OEIS by Mr. Kagey \$\endgroup\$
    – ZaMoC
    Aug 27 '20 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.