Bei dieser Herausforderung musst du "Kreaturen" im Kachelspiel Palago zählen.

Eine Kreatur ist jede geschlossene Form, die durch farblich passende Palago-Kacheln in einem sechseckigen Raster geformt werden kann.

Das Spiel Palago besteht aus folgenden Teilen:

Diese Kacheln können um $120^\circ$ , oder gar nicht gedreht und an einer beliebigen Stelle in einem sechseckigen Raster platziert werden. Zum Beispiel ist hier eine (rote) Kreatur, die 12 Steine ​​benötigt.$240^\circ$

Herausforderung

Ziel dieser Herausforderung ist es, ein Programm zu schreiben, das eine Ganzzahl nals Eingabe verwendet und die Anzahl der Kreaturen (bis zur Drehung und Reflexion) berechnet, für die nKacheln erforderlich sind. Das Programm sollte in der Lage sein zu handhaben bis zu n=10auf TIO . Das ist Code-Golf , also gewinnen die wenigsten Bytes.

Beispieldaten

Die Werte sollten mit den Daten im Abschnitt "Creature Counts and Estimates" auf der Website des Erstellers übereinstimmen . Nämlich

 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 Byte

-63 Bytes dank @Arnauld. Beeindruckend.

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

Probieren Sie es online!

Erstens ein Dank an Arnauld, dessen Antwort mir die Inspiration gab, tiefer zu graben. Ich habe mich sehr bemüht, mit meinen Algorithmen originell zu sein, obwohl ich absichtlich einen Teil meines Codes geändert habe, um dieselben Variablen wie Arnauld zu verwenden, damit der Code einfacher verglichen werden kann.

Suche nach leeren Feldern

Die Suche nach Kreaturen ist:

• Initialisieren Sie die Liste der Kacheln mit Kachel 1 auf 0,0
• Rekursiv:
  • Suche nach einem leeren Hexfeld, das zur Vollendung der Kreatur benötigt wird
  • Wenn ein leeres Hex gefunden wurde
    • Füge jede Art von Plättchen 0,1,2 hinzu, um das Feld zu leeren und den Fluch zu wiederholen
  • Wird kein leeres Hex gefunden
    • Wenn die Kreatur die richtige Größe hat und noch nicht im Zoo ist
      • Erhöhen Sie die Anzahl der verschiedenen Kreaturen, die von einer gefunden wurden
      • Fügen Sie dem Zoo alle Rotationen und Reflexionen der Kreatur hinzu

Die Suche nach leeren Feldern ergab eine interessante Symmetrie. Arnauld entdeckte, dass eine der sechs Richtungen ignoriert werden kann, aber tatsächlich können drei von sechs ignoriert werden!

Hier ist Arnauld's ursprüngliche Richtung und der Kachelschlüssel:

Stellen Sie sich vor, wir beginnen bei Kachel A vom Typ 1 am blauen Punkt. Es scheint, dass wir in d = 0 und d = 5 rekursieren müssen. Unabhängig davon, welches Plättchen in d = 0 platziert ist, wird es mit Sicherheit einen Ausgang in d = 4 haben, der dasselbe Feld wie der Ausgang in A in d = 5 aufsucht. Das ist Arnauld's Entdeckung und es hat mich zum Nachdenken gebracht.

Beachte das:

• Jedes Plättchen mit einem Ausgang in d = 0 hat einen Ausgang in d = 5
• Jedes Plättchen mit einem Ausgang in d = 2 hat einen Ausgang in d = 1

• Jedes Plättchen mit einem Ausgang in d = 4 hat einen Ausgang in d = 3

• Jede Kachel, die von d = 0 eingegeben werden kann, hat einen Ausgang in d = 4

• Jede Kachel, die von d = 2 eingegeben werden kann, hat einen Ausgang in d = 0
• Jedes Plättchen, das von d = 4 eingegeben werden kann, hat einen Ausgang in d = 2

Dies bedeutet, dass wir nur die Richtungen 0,2,4 berücksichtigen müssen. Alle Ausgänge in den Richtungen 1,3,5 können ignoriert werden, da die in den Richtungen 1,3,5 erreichbaren Felder stattdessen von einem benachbarten Feld aus mit den Richtungen 0,2 oder 4 erreicht werden können.

Wie cool ist das!?

Relabelled Richtungen

Also beschrifte ich die Richtungen und Kacheln wie folgt neu (Arnauld's Bild bearbeitet):

Jetzt haben wir die folgende Beziehung zwischen Kacheln, Ein- und Ausgängen:

    |  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

Ausgänge sind also: d + t == 2? (4-t)% 3: 2-t und 2 * t% 3

Sechseckige Rotationen und Reflexionen

Für Rotationen und Reflexionen habe ich mich entschieden, die hexagonalen Achsenkoordinaten x, y anstelle der Würfelkoordinaten x, y, z zu verwenden.

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

In diesem System waren die Rotation und Reflektion einfacher als ich erwartet hatte:

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

Um alle Kombinationen zu erhalten, die ich durchgeführt habe: rot, rot, rot, reflektieren, rot, rot

Code (ursprünglich 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 übermittelte freundlicherweise eine 63-Byte-Speicherung, die Tricks verwendete, die mich einige Zeit gekostet haben, um meinen Kopf herumzuwickeln. Da es viele interessante Änderungen gibt, dachte ich, ich würde seinen Code unten einfügen (ich habe meine Kommentare hinzugefügt), damit er meiner Version gegenübergestellt werden kann.

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 Byte

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

Probieren Sie es online! ( $n=1$$n=13$

Wie?

Richtungen und Fliesen

Wir verwenden die folgenden Codes für den 6-Richtungs-Kompass und die Kacheln:

Wir nehmen an, dass die Kreatur blau ist.

Anschlüsse

Wir brauchen eine Tabelle, um zu wissen, welche Teile der Kreatur mit anderen Plättchen verbunden werden müssen, wenn wir ein bestimmtes Plättchen in eine bestimmte Richtung betreten:

     |  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

Beispiel:

Wenn wir ein Plättchen vom Typ $1$ mit der Richtung $5$ eingeben , müssen wir in den Richtungen $1$ , $3$ und $4$ :

Aber so wie die Fliesen gestaltet sind, kann es unmöglich eine einzige fehlende Verbindung in einer einzigen Richtung geben. Dies hat zur Folge, dass wir eine Richtung vollständig ignorieren und trotzdem erkennen können, ob der Pfad geschlossen ist oder nicht. Konventionell werden wir die Richtung ignorieren$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

Diese aktualisierten Richtungssätze werden zuerst als 5-Bit-Ganzzahlen und dann als ASCII-Zeichen mit einem festen Versatz von + neu codiert$+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 |  "$"  |  "<"  |  "%"

Einmal abgeflacht, ergibt dies:

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

Koordinaten

$x+y+z=0$

Credits: www.redblobgames.com

Dies erleichtert die Verarbeitung von Rotationen und Reflexionen im letzten Schritt des Algorithmus.

Kachelkodierung

Die Kacheln werden in einer Liste ohne bestimmte Reihenfolge gespeichert. Dies bedeutet, dass wir uns nicht um eine dynamische 2D-Zuordnung kümmern müssen und die vorhandenen Kacheln problemlos iterieren können. Der Nachteil ist, dass wir bei bestimmten Koordinaten dies tun müssenfind() die entsprechende Kachel in der Liste .

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

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

Algorithmus

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

Daher wird diese Kachel als codiert [0,0,0,1,1].

Bei jeder Iteration suchen wir nach:

• Fliesen mit fehlenden Verbindungen: In diesem Fall versuchen wir nacheinander, die Verbindung für jeden Fliesentyp herzustellen.

• Kacheln, die bereits verbunden sind, für die jedoch neue Verbindungen hinzugefügt werden müssen, weil sie in einer anderen Richtung erreicht wurden: In diesem Fall aktualisieren wir die Richtungsmaske (mit einem bitweisen ODER) und erzwingen eine neue Iteration.

Wenn alle Verbindungen gültig sind und wir die angeforderte Anzahl von Kacheln erreicht haben, müssen wir noch testen, ob es sich um eine neue Kreatur oder nur um eine modifizierte Version einer vorhandenen handelt:

1. Wir wenden folgende Transformationen an:

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

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

2. $(0,0)$

3. Wir sortieren die Kacheln nach ihren Koordinaten und Typen. (Diese Sortierung wird in lexikografischer Reihenfolge verarbeitet, was in Ordnung ist.)

4. Wir zwingen schließlich die resultierende Liste zu einer Schlüsselkette, die mit den anderen Tasten verglichen werden können.

5. Wir brechen ab, sobald ein bekannter Schlüssel gefunden wurde, oder speichern den neuen Schlüssel und erhöhen das Endergebnis, wenn keine der Transformationen zu einem bekannten Schlüssel führt.

Kommentiert

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