Counting creatures on a hexagonal tiling

Question

This challenge will have you count "creatures" in the tile game Palago.

A creature is any closed shape that can be formed by Palago tiles of matching colour in a hexagonal grid.

The game Palago consists of tiles like this:

These tiles can be rotated \$120^\circ\$, \$240^\circ\$, or not at all and placed anywhere on a hexagonal grid. For example, here is a (red) creature that requires 12 tiles.

Challenge

The goal of this challenge is to write a program that takes an integer n as an input and computes the number of creatures (up to rotation and reflection) that require n tiles. The program should be able to handle up to n=10 on TIO. This is code-golf, so fewest bytes wins.

Example data

The values should match the data found in the "Creature Counts and Estimates" section of the creator's website. Namely

 n | output
---+-------
 1 | 0
 2 | 0
 3 | 1 
 4 | 0
 5 | 1
 6 | 1
 7 | 2
 8 | 2
 9 | 9
10 | 13
11 | 37
12 | 81

Answer 1

JavaScript (Node.js), 480 417 bytes

-63 bytes thanks to @Arnauld. Wow.

n=>(E=(x,y,d,k,h)=>V[k=[x+=1-(d%=3),y+=~d%3+1,d]]?0:(V[k]=1,h=H.find(h=>h[0]==x&h[1]==y))?(d^(t=2-h[2])?E(x,y,t)||E(x,y,h[2]*2):E(x,y,t+2)):[x,y,0],I=c=>c.map(([x,y,t])=>[x-g(0),y-g(1),t],g=p=>Math.min(...c.map(h=>h[p]))).sort(),S=e=>(V={},e=E(0,0,0))?(--n&&H.pop(H.push(e),S(),S(e[2]=1),S(e[2]=2)),++n):n-1||E[I(c=H)]||[0,0,0,++N,0,0].map(r=>E[I(c=c.map(([x,y,t])=>[-x-y,r?y:x,(r?t*2:t+1)%3]))]=1))(H=[[N=0,0,1]])&&N

Try it online!

Firstly, repect to Arnauld whose answer gave me the inspiration to dig deeper. I have tried hard to be original with my algorithms, although I intentionally changed some of my code to use the same variables as Arnauld so that the code could be more easily compared.

Searching for empty hexes

The search for creatures is:

• Initialize list of tiles with tile 1 at 0,0
• Recursively:
  • Search for an empty hex that is needed to complete creature
  • If empty hex found
    • Add each type of tile 0,1,2 to empty hex and recurse
  • If empty hex not found
    • If creature is of correct size and is not already in zoo
      • Increment number of distinct creatures found by one
      • Add all rotations and reflections of creature to zoo

The search for empty hexes uncovered an interesting symmetry. Arnauld discovered that one of the six directions could be ignored, but in fact three out of six can be ignored!

Here is Arnauld's original direction and tile key:

Imagine we start at tile A of type 1 at the blue dot. It seems that we have to recurse out in d=0 and d=5. However, whichever tile is placed in d=0, it will certainly have an exit in d=4, which will visit the same hex as exiting tile A in d=5. That is Arnauld's discovery, and it's what started me thinking.

Notice that:

• Every tile that has an exit in d=0 has an exit in d=5
• Every tile that has an exit in d=2 has an exit in d=1

• Every tile that has an exit in d=4 has an exit in d=3

• Every tile that can be entered from d=0 has an exit in d=4

• Every tile that can be entered from d=2 has an exit in d=0
• Every tile that can be entered from d=4 has an exit in d=2

This means that we only need to consider directions 0,2,4. Any exits in directions 1,3,5 can be ignored because the hexes reachable in directions 1,3,5 can instead be reached from an adjacent hex using directions 0,2 or 4.

How cool is that!?

Relabelled Directions

So I relabel the directions and tiles like this (Arnauld's image edited):

Now we have the following relationship between tiles, entries and exits:

    |  t=0  |  t=1  |  t=2
----+-------+-------+-------
d=0 |  0,2  |  1,2  |    2
d=1 |  0,2  |    0  |  0,1
d=2 |    1  |  1,2  |  0,1

So exits are: d+t==2 ? (4-t)%3 : 2-t and 2*t%3

Hexagonal Rotations and Reflections

For rotations and reflections, I decided to try x,y hexagonal axial coordinates instead of the x,y,z cube coordinates.

-1,2   0,2   1,2   2,2
    0,1   1,1   2,1
 0,0   1,0   2,0   3,0

In this system, the rotation and reflection were simpler than I expected:

120 Rotation:   x=-x-y   y=x   t=(t+1)%3
Reflection:     x=-x-y   y=y   t=(t*2)%3

To get all the combinations I performed : rot,rot,rot,reflect,rot,rot

Code (Original 480 byte)

f=n=>(
    // H:list of filled hexes [x,y,tile] during search for a complete creature
    // N:number of distinct creatures of size n
    // B:record of all orientations of all creatures already found
    H=[[0,0,1]],N=0,B={},

// E: find an empty hex required to complete creature starting in direction d from x,y
    E=(x,y,d,k,h)=>(
        x+=1-d,
        y+=1-(d+1)%3,
        // V: list of visited hexes during this search in E
        V[k=[x,y,d]] ? 
            0
        : (V[k]=1, h=H.find(h=>h[0]==x&&h[1]==y)) ? 
            // this hex is filled, so continue search in 1 or 2 directions
            (d==2-h[2] ? E(x,y,(4-h[2])%3) : (E(x,y,2-h[2]) || E(x,y,h[2]*2%3))) 
        : [x,y,0] // return the empty hex 
    ),

    // I: construct unique identifier for creature c by moving it so x>=0 and y>=0
    I=c=>(
        M=[0,1].map(p=>Math.min(...c.map(h=>h[p]))),
        c.map(([x,y,t])=>[x-M[0],y-M[1],t]).sort()
    ),

    // A: add complete creature c to B
    A=c=>{
        n==1&&!B[I(c)]&&(
            // creature is correct size and is not already in B
            N++,
            [0,0,0,1,0,0].map(
                // Add all rotations and reflections of creature into B
                // '0' marks a rotation, '1' marks a (vertical) reflection
                // rotation:   x=-x-y   y=x   t=(t+1)%3
                // reflection: x=-x-y   y=y   t=(t*2)%3
                r=>B[I(c=c.map(([x,y,t])=>[-x-y,r?y:x,(r?t*2:t+1)%3]))]=1)          
        )
    },

    // S: recursively search for complete creatures starting with hexes H
    S=e=>{
        V={};
        (e=E(0,0,0)) ?
            // e is a required empty hex, so try filling it with tiles 0,1,2
            (--n && (H.push(e),S(),S(e[2]=1),S(e[2]=2),H.pop()), ++n)
        : A(H) // creature is complete, so add it to B
    },

    S(),
    N
)

Code (Arnauld 417 byte)

Arnauld kindly submitted a 63 byte saving that used tricks that took me quite some time to wrap my head around. Since it has many interesting edits, I thought I'd put his code below (I've added my comments) so that it can be contrasted with my version.

f=n=>(
    // E:find an empty hex required to complete creature starting in direction d from x,y
    E=(x,y,d,k,h)=>
      V[k=[x+=1-(d%=3),y+=~d%3+1,d]] ?
        0
      :(V[k]=1,h=H.find(h=>h[0]==x&h[1]==y)) ?
        (d^(t=2-h[2]) ? E(x,y,t) || E(x,y,h[2]*2) : E(x,y,t+2))
      :[x,y,0],

    // I: construct unique identifier for creature c by moving it so x>=0 and y>=0
    I=c=>c.map(([x,y,t])=>[x-g(0),y-g(1),t],g=p=>Math.min(...c.map(h=>h[p]))).sort(),

    // S: recursively search for complete creatures starting with hexes H
    S=e=>
      (V={},e=E(0,0,0)) ?
        (--n&&H.pop(H.push(e),S(),S(e[2]=1),S(e[2]=2)),++n)
      :n-1
        ||E[I(c=H)] 
        // creature is the correct size and has not been seen before
        // so record all rotations and reflections of creature in E[]
        ||[0,0,0,++N,0,0].map(r=>E[I(c=c.map(([x,y,t])=>[-x-y,r?y:x,(r?t*2:t+1)%3]))]=1)
)
// This wonderfully confusing syntax initializes globals and calls S()
(H=[[N=0,0,1]]) && N

Answer 2

JavaScript (Node.js),  578 ... 433  431 bytes

f=(n,T=[B=[N=0,0,0,1,1]])=>!n||T.some(([x,y,q,m])=>B.some((p,d)=>m>>d&1&&((p=x+~-s[d],q=y+~-s[d+2],t=T.find(([X,Y])=>X==p&Y==q))?(q=t[3])&(p=D[d*3+t[4]])^p?t[f(n,T,t[3]|=p),3]=q:0:[0,1,2].map(t=>f(n-1,[...T,[p,q,-p-q,D[d*3+t],t]])))),s="2100122",D=Buffer("160).(9!'8 &$<%"))|n>1||[0,1,2,1,2,0].some((_,d,A)=>B[k=T.map(a=>[(h=n=>Math.min(...T.map(R=a=>a[A[(d+n)%6]]))-R(a))(0),h(3),(x=(a[4]+d*2)%3,d>2)*x?3-x:x]).sort()])?N:B[k]=++N

Try it online! (\$n=1\$ to \$n=13\$)

How?

Directions and tiles

We use the following codes for the 6-direction compass and the tiles:

We assume that the creature is blue.

Connections

We need a table to know which parts of the creature need to be connected to other tiles when we enter a given tile in a given direction:

     |  T=0  |  T=1  |  T=2
-----+-------+-------+-------
 d=0 | 0,4,5 | 1,2,4 |   4
 d=1 | 0,3,5 | 1,2,3 |   3
 d=2 | 0,3,4 |   0   | 0,1,2
 d=3 | 3,4,5 |   5   | 1,2,5
 d=4 |   2   | 2,3,4 | 0,2,5
 d=5 |   1   | 1,3,4 | 0,1,5

Example:

If we enter a tile of type \$1\$ with direction \$5\$, we need to connect in directions \$1\$, \$3\$ and \$4\$:

But the way the tiles are designed, there can't possibly be a single missing connection in a single direction. A consequence of that is that we can ignore one direction entirely and still be able to detect if the path is closed or not. By convention, we are going to ignore direction \$5\$.

     |  T=0  |  T=1  |  T=2
-----+-------+-------+-------
 d=0 |  0,4  | 1,2,4 |   4
 d=1 |  0,3  | 1,2,3 |   3
 d=2 | 0,3,4 |   0   | 0,1,2
 d=3 |  3,4  |   -   |  1,2
 d=4 |   2   | 2,3,4 |  0,2

These updated sets of directions are first re-encoded as 5-bit integers, and then as ASCII characters with a fixed offset of \$+32\$:

     |  T=0  |  T=1  |  T=2              |  T=0  |  T=1  |  T=2
-----+-------+-------+-------       -----+-------+-------+-------
 d=0 |   17  |   22  |   16          d=0 |  "1"  |  "6"  |  "0"
 d=1 |    9  |   14  |    8          d=1 |  ")"  |  "."  |  "("
 d=2 |   25  |    1  |    7    -->   d=2 |  "9"  |  "!"  |  "'"
 d=3 |   24  |    0  |    6          d=3 |  "8"  |  " "  |  "&"
 d=4 |    4  |   28  |    5          d=4 |  "$"  |  "<"  |  "%"

Once flattened, this gives:

D = Buffer("160).(9!'8 &$<%")

Coordinates

To describe the positions of the tiles, we use cube coordinates with \$x+y+z=0\$:

Credits: www.redblobgames.com

It will make it easier to process rotations and reflections in the final step of the algorithm.

Tile encoding

The tiles are stored in a list, with no specific order. It means that we don't have to worry about some dynamic 2D allocation and we can easily iterate on the existing tiles. The downside is that, given specific coordinates, we need to find() the corresponding tile in the list.

Each tile is stored as \$(x, y, z, m, t)\$ where:

• \$(x, y, z)\$ are the cube coordinates of the tile as described above
• \$m\$ is the 5-bit mask of directions that need to be connected
• \$t\$ is its type (\$0\$, \$1\$ or \$2\$)

Algorithm

We start with a single tile of type \$1\$ at \$(0,0,0)\$, with a required connection in direction \$0\$:

Therefore, this tile is encoded as [0,0,0,1,1].

At each iteration, we look for:

• Tiles with missing connections: in this case, we successively try to complete the connection with each type of tile.

• Tiles that are already connected but for which new connections need to be added because they have been reached in a different direction: in this case, we update the direction mask (with a bitwise OR) and force a new iteration.

If all connections are valid and we have reached the requested number of tiles, we still need to test whether it is a new creature or just a modified version of an existing one:

1. We apply the following transformations:

   • We perform the 3 possible rotations by replacing \$(x,y)\$ with \$(x,y)\$ (no rotation), \$(y,z)\$ (120°) or \$(z,x)\$ (240°), and updating the types of the tiles accordingly.

   • We perform the 3 corresponding reflections by replacing \$(x,y)\$ with \$(y,x)\$, \$(z,y)\$ or \$(x,z)\$, and updating the types of the tiles accordingly.

2. For each transformation, we translate all tiles such that the bottom-right corner is always located at \$(0,0)\$. (The signs of the coordinates are inverted in the process, which technically leads to another reflection, but this is harmless.)

3. We sort the tiles according to their coordinates and types. (This sort is processed in lexicographical order, which is fine.)

4. We finally coerce the resulting list to a key string which can be compared with the other keys.

5. We abort as soon as a known key is matched, or store the new key and increment the final result if none of the transformations lead to a known key.

Commented

f = (n, T = [B = [N = 0, 0, 0, 1, 1]]) =>
  // abort if n = 0
  !n ||
  // for each tile in T
  T.some(([x, y, q, m]) =>
    // for d = 0 to d = 4
    B.some((p, d) =>
      // if this tile requires a connection in this direction
      m >> d & 1 && (
        // look for a connected tile t at the corresponding position (p, q)
        (
          p = x + ~-s[d],
          q = y + ~-s[d + 2],
          t = T.find(([X, Y]) => X == p & Y == q)
        ) ?
          // if t exists, make sure that its direction mask is up-to-date
          (q = t[3]) & (p = D[d * 3 + t[4]]) ^ p ?
            // if it's not, update it and force a new iteration
            t[f(n, T, t[3] |= p), 3] = q
          :
            0
        :
          // if t does not exist, try each type of tile at this position
          [0, 1, 2].map(t => f(n - 1, [...T, [p, q, -p - q, D[d * 3 + t], t]]))
      )
    ),
    // s is used to apply (dx, dy)
    s = "2100122",
    // D holds the direction masks for the connections
    D = Buffer("160).(9!'8 &$<%")
  ) |
  // stop here if the above some() was truthy or we have more tiles to add
  n > 1 ||
  // otherwise, apply the transformations
  [0, 1, 2, 1, 2, 0].some((_, d, A) =>
    B[
      // compute the key k
      k =
        // by generating the updated tuples [x, y, type] and sorting them
        T.map(a =>
          [
            // transform the 1st coordinate
            (h = n => Math.min(...T.map(R = a => a[A[(d + n) % 6]])) - R(a))(0),
            // transform the 2nd coordinate
            h(3),
            // update the type
            (x = (a[4] + d * 2) % 3, d > 2) * x ? 3 - x : x
          ]
        ).sort()
    ]
  ) ?
    // if the key was found, just return N
    N
  :
    // if this is a new creature, store its key and increment N
    B[k] = ++N