Este desafio fará você contar "criaturas" no jogo de azulejos Palago.

Uma criatura é qualquer forma fechada que possa ser formada por peças Palago de cores correspondentes em uma grade hexagonal.

O jogo Palago consiste em peças como esta:

Esses ladrilhos podem ser girados , ou, de maneira alguma, e colocados em qualquer lugar em uma grade hexagonal. Por exemplo, aqui está uma criatura (vermelha) que requer 12 peças.$120^\circ$$240^\circ$

Desafio

O objetivo desse desafio é escrever um programa que use um número inteiro ncomo entrada e calcule o número de criaturas (até rotação e reflexão) que requerem nblocos. O programa deve ser capaz de lidar com até n=10na TIO . Isso é código-golfe , e o menor número de bytes vence.

Dados de exemplo

Os valores devem corresponder aos dados encontrados na seção "Estimativas e contagens de criaturas" do site do criador . Nomeadamente

 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 graças a @Arnauld. Uau.

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

Experimente online!

Em primeiro lugar, respeite Arnauld, cuja resposta me deu a inspiração para aprofundar. Eu tentei ser original com meus algoritmos, apesar de ter intencionalmente alterado parte do meu código para usar as mesmas variáveis ​​que Arnauld, para que o código pudesse ser comparado com mais facilidade.

Procurando por hexágonos vazios

A busca por criaturas é:

• Inicialize a lista de blocos com o bloco 1 em 0,0
• Recursivamente:
  • Procure por um hexadecimal vazio necessário para completar a criatura
  • Se hexadecimal vazio encontrado
    • Adicione cada tipo de bloco 0,1,2 ao hexadecimal vazio e recorra
  • Se hexadecimal vazio não encontrado
    • Se a criatura for do tamanho correto e ainda não estiver no zoológico
      • Número de incremento de criaturas distintas encontradas por um
      • Adicione todas as rotações e reflexos da criatura ao zoo

A busca por hexágonos vazios revelou uma simetria interessante. Arnauld descobriu que uma das seis direções poderia ser ignorada, mas na verdade três em cada seis podem ser ignoradas!

Aqui está a chave e a direção originais de Arnauld:

Imagine que começamos no bloco A do tipo 1 no ponto azul. Parece que precisamos recuar em d = 0 ed = 5. No entanto, qualquer que seja o bloco colocado em d = 0, certamente terá uma saída em d = 4, que visitará o mesmo hexadecimal que sair do bloco A em d = 5. Essa é a descoberta de Arnauld, e foi o que me fez pensar.

Notar que:

• Todo bloco que tem uma saída em d = 0 tem uma saída em d = 5
• Todo bloco que tem uma saída em d = 2 tem uma saída em d = 1

• Todo bloco que tem uma saída em d = 4 tem uma saída em d = 3

• Todo bloco que pode ser inserido de d = 0 tem uma saída em d = 4

• Todo bloco que pode ser inserido de d = 2 tem uma saída em d = 0
• Todo bloco que pode ser inserido de d = 4 tem uma saída em d = 2

Isso significa que precisamos apenas considerar as direções 0,2,4. Quaisquer saídas nas direções 1,3,5 podem ser ignoradas porque os hexágonos alcançáveis ​​nas direções 1,3,5 podem ser alcançados a partir de um hexadecimal adjacente usando as direções 0,2 ou 4.

Quão legal é isso!?

Direções rotuladas

Então, eu rotulo novamente as direções e os blocos assim (imagem de Arnauld editada):

Agora, temos a seguinte relação entre blocos, entradas e saídas:

    |  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

Então, as saídas são: d + t == 2? (4-t)% 3: 2-t e 2 * t% 3

Rotações hexagonais e reflexões

Para rotações e reflexões, decidi tentar coordenadas axiais hexagonais x, y em vez das coordenadas do 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

Nesse sistema, a rotação e a reflexão eram mais simples do que eu esperava:

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

Para obter todas as combinações que realizei: apodrecer, apodrecer, apodrecer, refletir, apodrecer, apodrecer

Código (480 bytes originais)

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

Arnauld gentilmente enviou uma economia de 63 bytes que usou truques que levaram algum tempo para entender. Como ele tem muitas edições interessantes, pensei em colocar o código abaixo (adicionei meus comentários) para que ele possa ser contrastado com a minha versão.

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$

Quão?

Direções e peças

Usamos os seguintes códigos para a bússola de 6 direções e os ladrilhos:

Assumimos que a criatura é azul.

Conexões

Precisamos de uma tabela para saber quais partes da criatura precisam ser conectadas a outras peças quando inserimos uma determinada peça em uma determinada direção:

     |  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

Exemplo:

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

Uma vez achatado, isso fornece:

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

Coordenadas

$x+y+z=0$

Créditos: www.redblobgames.com

Isso facilitará o processamento de rotações e reflexões na etapa final do algoritmo.

Codificação de bloco

Os blocos são armazenados em uma lista, sem ordem específica. Isso significa que não precisamos nos preocupar com alguma alocação dinâmica em 2D e podemos iterar facilmente nos blocos existentes. A desvantagem é que, dadas coordenadas específicas, precisamos find()do bloco correspondente na lista.

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

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

Algoritmo

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

Portanto, esse bloco é codificado como [0,0,0,1,1].

Em cada iteração, procuramos:

• Ladrilhos com conexões ausentes: nesse caso, tentamos sucessivamente concluir a conexão com cada tipo de ladrilho.

• Ladrilhos que já estão conectados, mas para os quais novas conexões precisam ser adicionadas porque foram alcançadas em uma direção diferente: nesse caso, atualizamos a máscara de direção (com um OR bit a bit) e forçamos uma nova iteração.

Se todas as conexões são válidas e atingimos o número solicitado de peças, ainda precisamos testar se é uma nova criatura ou apenas uma versão modificada de uma existente:

1. Aplicamos as seguintes transformações:

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

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

2. $(0,0)$

3. Classificamos os blocos de acordo com suas coordenadas e tipos. (Essa classificação é processada em ordem lexicográfica, o que é aceitável.)

4. Finalmente, coagimos a lista resultante a uma cadeia de chaves que pode ser comparada com as outras chaves.

5. Abortamos assim que uma chave conhecida é correspondida ou armazenamos a nova chave e incrementamos o resultado final se nenhuma das transformações levar a uma chave conhecida.

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