Ce défi vous fera compter les «créatures» dans le jeu de tuiles Palago.

Une créature est une forme fermée qui peut être formée par des tuiles Palago de couleur assortie dans une grille hexagonale.

Le jeu Palago se compose de tuiles comme ceci:

Ces tuiles peuvent être tournées de $120^\circ$ , $240^\circ$ , ou pas du tout, et placées n'importe où sur une grille hexagonale. Par exemple, voici une créature (rouge) qui nécessite 12 tuiles.

Défi

Le but de ce défi est d'écrire un programme qui prend un entier nen entrée et calcule le nombre de créatures (jusqu'à la rotation et la réflexion) qui nécessitent des ntuiles. Le programme devrait être capable de gérer jusqu'à n=10sur TIO . Il s'agit de code-golf , donc le moins d'octets gagne.

Exemples de données

Les valeurs doivent correspondre aux données trouvées dans la section "Nombre de créatures et estimations" du site Web du créateur . À savoir

 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 octets

-63 octets grâce à @Arnauld. Sensationnel.

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

Essayez-le en ligne!

Tout d'abord, respectez Arnauld dont la réponse m'a donné l'inspiration pour creuser plus profondément. J'ai beaucoup essayé d'être original avec mes algorithmes, bien que j'ai intentionnellement changé une partie de mon code pour utiliser les mêmes variables qu'Arnauld afin que le code puisse être plus facilement comparé.

Recherche d'hexagones vides

La recherche de créatures est:

• Initialiser la liste des tuiles avec la tuile 1 à 0,0
• Récursivement:
  • Cherchez un hex vide qui est nécessaire pour terminer la créature
  • Si un hex vide est trouvé
    • Ajoutez chaque type de tuile 0,1,2 à l'hex vide et recurse
  • Si un hex vide n'est pas trouvé
    • Si la créature est de la bonne taille et n'est pas déjà au zoo
      • Augmente le nombre de créatures distinctes trouvées par une
      • Ajoutez toutes les rotations et reflets de la créature au zoo

La recherche d'hexagones vides a révélé une symétrie intéressante. Arnauld a découvert que l'une des six directions pouvait être ignorée, mais en fait trois sur six peuvent être ignorées!

Voici la direction d'origine et la clé de tuile d'Arnauld:

Imaginez que nous commençons à la tuile A de type 1 au point bleu. Il semble que nous devions reprendre en d = 0 et d = 5. Cependant, quelle que soit la tuile placée en d = 0, elle aura certainement une sortie en d = 4, qui visitera le même hex que la tuile A sortant en d = 5. C'est la découverte d'Arnauld, et c'est ce qui m'a fait réfléchir.

Remarquerez que:

• Chaque tuile qui a une sortie en d = 0 a une sortie en d = 5
• Chaque tuile qui a une sortie en d = 2 a une sortie en d = 1

• Chaque tuile qui a une sortie en d = 4 a une sortie en d = 3

• Chaque tuile qui peut être entrée à partir de d = 0 a une sortie dans d = 4

• Chaque tuile qui peut être entrée à partir de d = 2 a une sortie dans d = 0
• Chaque tuile qui peut être entrée à partir de d = 4 a une sortie dans d = 2

Cela signifie que nous devons seulement considérer les directions 0,2,4. Toutes les sorties dans les directions 1,3,5 peuvent être ignorées car les hexs accessibles dans les directions 1,3,5 peuvent à la place être atteints à partir d'un hex adjacent en utilisant les directions 0,2 ou 4.

À quel point cela est cool!?

Directions réétiquetées

J'ai donc réétiqueté les directions et les tuiles comme ceci (image d'Arnauld modifiée):

Nous avons maintenant la relation suivante entre les tuiles, les entrées et les sorties:

    |  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

Les sorties sont donc: d + t == 2? (4-t)% 3: 2-t et 2 * t% 3

Rotations et réflexions hexagonales

Pour les rotations et les réflexions, j'ai décidé d'essayer les coordonnées axiales hexagonales x, y au lieu des coordonnées du cube 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

Dans ce système, la rotation et la réflexion étaient plus simples que ce à quoi je m'attendais:

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

Pour obtenir toutes les combinaisons que j'ai effectuées: pourriture, pourriture, pourriture, réflexion, pourriture, pourriture

Code (480 octets d'origine)

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

Arnauld a gentiment soumis une économie de 63 octets qui a utilisé des astuces qui m'ont pris un certain temps pour envelopper ma tête. Puisqu'il a beaucoup de modifications intéressantes, j'ai pensé mettre son code ci-dessous (j'ai ajouté mes commentaires) afin qu'il puisse être contrasté avec ma 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

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

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$

Comment?

Directions et tuiles

Nous utilisons les codes suivants pour la boussole à 6 directions et les tuiles:

Nous supposons que la créature est bleue.

Connexions

Nous avons besoin d'une table pour savoir quelles parties de la créature doivent être connectées à d'autres tuiles lorsque nous entrons dans une tuile donnée dans une direction donnée:

     |  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

Exemple:

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

Une fois aplati, cela donne:

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

Coordonnées

$x+y+z=0$

Crédits: www.redblobgames.com

Cela facilitera le traitement des rotations et des réflexions lors de la dernière étape de l'algorithme.

Encodage des tuiles

Les tuiles sont stockées dans une liste, sans ordre spécifique. Cela signifie que nous n'avons pas à nous soucier d'une allocation 2D dynamique et que nous pouvons facilement itérer sur les tuiles existantes. L'inconvénient est que, compte tenu des coordonnées spécifiques, nous avons besoin de find()la tuile correspondante dans la liste.

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

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

Algorithme

On commence avec une seule tuile de type $1$$(0,0,0)$$0$

Par conséquent, cette tuile est codée comme [0,0,0,1,1] .

A chaque itération, nous recherchons:

• Tuiles avec des connexions manquantes: dans ce cas, nous essayons successivement de compléter la connexion avec chaque type de tuile.

• Tuiles qui sont déjà connectées mais pour lesquelles de nouvelles connexions doivent être ajoutées car elles ont été atteintes dans une direction différente: dans ce cas, nous mettons à jour le masque de direction (avec un OU au niveau du bit) et forçons une nouvelle itération.

Si toutes les connexions sont valides et que nous avons atteint le nombre de tuiles demandé, nous devons encore tester s'il s'agit d'une nouvelle créature ou simplement d'une version modifiée d'une créature existante:

1. Nous appliquons les transformations suivantes:

   • $(x,y)$$(x,y)$$(y,z)$$(z,x)$ (240 °), et en mettant à jour les types de tuiles en conséquence.

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

2. $(0,0)$

3. Nous trions les tuiles selon leurs coordonnées et types. (Ce tri est traité dans l'ordre lexicographique, ce qui est bien.)

4. Nous contraignons finalement la liste résultante à une chaîne de clés qui peut être comparée avec les autres clés.

5. Nous abandonnons dès qu'une clé connue est mise en correspondance, ou stockons la nouvelle clé et incrémentons le résultat final si aucune des transformations ne conduit à une clé connue.

Commenté

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