Este desafío hará que cuentes "criaturas" en el juego de fichas Palago.

Una criatura es cualquier forma cerrada que puede estar formada por fichas de Palago de color coincidente en una cuadrícula hexagonal.

El juego Palago consta de fichas como esta:

Estas fichas se pueden rotar , , o no girar en absoluto, y colocarlas en cualquier lugar de una cuadrícula hexagonal. Por ejemplo, aquí hay una criatura (roja) que requiere 12 fichas.$120^\circ$$240^\circ$

Desafío

El objetivo de este desafío es escribir un programa que tome un número entero ncomo entrada y calcule el número de criaturas (hasta la rotación y la reflexión) que requieren nmosaicos. El programa debe ser capaz de manejar hasta n=10el TIO . Este es el código de golf , por lo que gana menos bytes.

Datos de ejemplo

Los valores deben coincidir con los datos encontrados en la sección "Recuentos y estimaciones de criaturas" del sitio web del creador . A saber

 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

Javascript (Node.js) , 480 417 bytes

-63 bytes gracias a @Arnauld. Guau.

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

Pruébalo en línea!

En primer lugar, respeto a Arnauld, cuya respuesta me inspiró a profundizar. He intentado ser original con mis algoritmos, aunque cambié intencionalmente parte de mi código para usar las mismas variables que Arnauld para que el código pudiera compararse más fácilmente.

Buscando hexes vacíos

La búsqueda de criaturas es:

• Inicialice la lista de mosaicos con el mosaico 1 en 0,0
• Recursivamente:
  • Busca un hex vacío que sea necesario para completar la criatura.
  • Si se encuentra un hex vacío
    • Agregue cada tipo de mosaico 0,1,2 para vaciar hex y recurse
  • Si no se encuentra el hex vacío
    • Si la criatura es del tamaño correcto y aún no está en el zoológico
      • Incrementa el número de criaturas distintas encontradas por uno
      • Agrega todas las rotaciones y reflejos de la criatura al zoológico

La búsqueda de hexes vacíos descubrió una simetría interesante. Arnauld descubrió que una de las seis direcciones podría ignorarse, pero de hecho, ¡tres de cada seis pueden ignorarse!

Aquí está la dirección original y la clave de mosaico de Arnauld:

Imagina que comenzamos en el mosaico A del tipo 1 en el punto azul. Parece que tenemos que recurrir en d = 0 yd = 5. Sin embargo, cualquiera que sea la casilla colocada en d = 0, ciertamente tendrá una salida en d = 4, que visitará el mismo hexágono que la ficha A existente en d = 5. Ese es el descubrimiento de Arnauld, y es lo que me hizo pensar.

Darse cuenta de:

• Cada ficha que tiene una salida en d = 0 tiene una salida en d = 5
• Cada ficha que tiene una salida en d = 2 tiene una salida en d = 1

• Cada ficha que tiene una salida en d = 4 tiene una salida en d = 3

• Cada mosaico que se puede ingresar desde d = 0 tiene una salida en d = 4

• Cada mosaico que se puede ingresar desde d = 2 tiene una salida en d = 0
• Cada mosaico que se puede ingresar desde d = 4 tiene una salida en d = 2

Esto significa que solo necesitamos considerar las direcciones 0,2,4. Cualquier salida en las direcciones 1,3,5 se puede ignorar porque los hexes alcanzables en las direcciones 1,3,5 se pueden alcanzar desde un hex adyacente usando las direcciones 0,2 o 4.

¿¡Cuan genial es eso!?

Direcciones reetiquetadas

Así que vuelvo a etiquetar las instrucciones y los mosaicos como este (imagen editada de Arnauld):

Ahora tenemos la siguiente relación entre mosaicos, entradas y salidas:

    |  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

Entonces las salidas son: d + t == 2? (4-t)% 3: 2-t y 2 * t% 3

Rotaciones Hexagonales y Reflexiones

Para rotaciones y reflexiones, decidí probar las coordenadas axiales hexagonales x, y en lugar de las coordenadas del cubo x, y, z.

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

En este sistema, la rotación y la reflexión fueron más simples de lo que esperaba:

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

Para obtener todas las combinaciones que realicé: putrefacción, putrefacción, putrefacción, reflexión, putrefacción, putrefacción

Código (480 bytes original)

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
)

Código (Arnauld 417 byte)

Arnauld presentó amablemente un ahorro de 63 bytes que utilizó trucos que me tomaron bastante tiempo para comprender. Como tiene muchas ediciones interesantes, pensé en poner su código a continuación (agregué mis comentarios) para poder compararlo con mi versión.

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

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

$n=1$$n=13$

¿Cómo?

Direcciones y azulejos

Utilizamos los siguientes códigos para la brújula de 6 direcciones y los mosaicos:

Asumimos que la criatura es azul.

Conexiones

Necesitamos una tabla para saber qué partes de la criatura deben conectarse a otras fichas cuando ingresamos a una ficha dada en una dirección determinada:

     |  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

Ejemplo:

$1$$5$$1$$3$$4$

$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

$+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 |  "$"  |  "<"  |  "%"

Una vez aplanado, esto da:

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

Coordenadas

$x+y+z=0$

Créditos: www.redblobgames.com

Facilitará el procesamiento de rotaciones y reflexiones en el paso final del algoritmo.

Codificación de mosaico

Los mosaicos se almacenan en una lista, sin un orden específico. Significa que no tenemos que preocuparnos por alguna asignación dinámica en 2D y podemos iterar fácilmente en los mosaicos existentes. La desventaja es que, dadas las coordenadas específicas, necesitamos find()el mosaico correspondiente en la lista.

$(x, y, z, m, t)$

• $(x, y, z)$
• $m$
• $t$$0$$1$$2$

Algoritmo

$1$$(0,0,0)$$0$

Por lo tanto, este mosaico está codificado como [0,0,0,1,1].

En cada iteración, buscamos:

• Mosaicos con conexiones faltantes: en este caso, intentamos sucesivamente completar la conexión con cada tipo de mosaico.

• Mosaicos que ya están conectados pero para los cuales se deben agregar nuevas conexiones porque se han alcanzado en una dirección diferente: en este caso, actualizamos la máscara de dirección (con un OR a nivel de bits) y forzamos una nueva iteración.

Si todas las conexiones son válidas y hemos alcanzado el número solicitado de mosaicos, aún debemos probar si es una nueva criatura o simplemente una versión modificada de una existente:

1. Aplicamos las siguientes transformaciones:

   • $(x,y)$$(x,y)$$(y,z)$$(z,x)$

   • $(x,y)$$(y,x)$$(z,y)$$(x,z)$

2. $(0,0)$

3. Clasificamos los mosaicos de acuerdo con sus coordenadas y tipos. (Este tipo se procesa en orden lexicográfico, lo cual está bien).

4. Finalmente coaccionamos la lista resultante a una cadena de clave que se puede comparar con las otras claves.

5. Abortamos tan pronto como una clave conocida coincida, o almacenamos la nueva clave e incrementamos el resultado final si ninguna de las transformaciones conduce a una clave conocida.

Comentado

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