W tym wyzwaniu będziesz liczyć „stwory” w grze Palago.

Stworzenie to dowolny zamknięty kształt, który można uformować z płytek Palago w tym samym kolorze w sześciokątnej siatce.

Gra Palago składa się z takich płytek:

Płytki te można obracać o $120^\circ$ , $240^\circ$ lub wcale, i umieszczać w dowolnym miejscu na sześciokątnej siatce. Na przykład tutaj jest (czerwone) stworzenie, które wymaga 12 płytek.

Wyzwanie

Celem tego wyzwania jest napisanie programu, który przyjmuje liczbę całkowitą njako dane wejściowe i oblicza liczbę stworzeń (do obrotu i odbicia), które wymagają npłytek. Program powinien być w stanie obsłużyć maksymalnie n=10na TIO . To jest golf golfowy , więc wygrywa najmniej bajtów.

Przykładowe dane

Wartości powinny odpowiadać danym znajdującym się w sekcji „Obliczenia i oszacowania stworów” na stronie internetowej twórcy . Mianowicie

 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 bajtów

-63 bajty dzięki @Arnauld. Łał.

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

Wypróbuj online!

Po pierwsze, uszanuj Arnaulda, którego odpowiedź zainspirowała mnie do głębszego kopania. Starałem się być oryginalny w swoich algorytmach, chociaż celowo zmieniłem część mojego kodu, aby używał tych samych zmiennych, co Arnauld, aby kod był łatwiejszy do porównania.

Wyszukiwanie pustych heksów

Poszukiwanie stworzeń to:

• Zainicjuj listę płytek z płytką 1 o wartości 0,0
• Rekurencyjnie:
  • Wyszukaj pusty heks potrzebny do ukończenia stworzenia
  • Jeśli znaleziono pusty heks
    • Dodaj każdy typ płytki 0,1,2 do pustego heksa i powtórz
  • Jeśli nie znaleziono pustego heksa
    • Jeśli stworzenie ma odpowiedni rozmiar i nie znajduje się już w zoo
      • Przyrost liczby różnych stworzeń znalezionych przez jednego
      • Dodaj wszystkie rotacje i odbicia stworzenia do zoo

Poszukiwanie pustych heksów odkryło interesującą symetrię. Arnauld odkrył, że jeden z sześciu kierunków można zignorować, ale w rzeczywistości trzy z sześciu można zignorować!

Oto oryginalny kierunek i kafelek Arnaulda:

Wyobraźmy sobie, że zaczynamy od płytki A typu 1 w niebieskiej kropce. Wygląda na to, że musimy powtórzyć się d = 0 id = 5. Jednak niezależnie od tego, który kafelek zostanie umieszczony w d = 0, na pewno będzie miał wyjście w d = 4, które odwiedzi ten sam hex, co wyjście z płytki A w d = 5. To odkrycie Arnaulda i to właśnie sprawiło, że zacząłem myśleć.

Zauważ, że:

• Każdy kafelek, który ma wyjście d = 0, ma wyjście id = 5
• Każdy kafelek, który ma wyjście d = 2, ma wyjście id = 1

• Każdy kafelek, który ma wyjście d = 4, ma wyjście id = 3

• Każdy kafelek, który można wprowadzić z d = 0, ma wyjście d = 4

• Każdy kafelek, który można wprowadzić z d = 2, ma wyjście d = 0
• Każdy kafelek, który można wprowadzić z d = 4, ma wyjście d = 2

Oznacza to, że musimy brać pod uwagę tylko kierunki 0,2,4. Wszelkie wyjścia w kierunkach 1,3,5 można zignorować, ponieważ heksy osiągalne w kierunkach 1,3,5 można zamiast tego dotrzeć z sąsiedniego heksa, używając kierunków 0,2 lub 4.

Jakie to jest świetne!?

Przeprojektowane kierunki

Ponownie opisuję wskazówki i kafelki w ten sposób (edytowany obraz Arnaulda):

Teraz mamy następujący związek między kafelkami, wejściami i wyjściami:

    |  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

Wyjścia to: d + t == 2? (4-t)% 3: 2-t i 2 * t% 3

Obroty i odbicia sześciokątne

W przypadku obrotów i odbić postanowiłem wypróbować sześciokątne współrzędne osi x, y zamiast współrzędnych sześcianu 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

W tym systemie rotacja i odbicie były prostsze niż się spodziewałem:

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

Aby uzyskać wszystkie kombinacje, które wykonałem: gnij, gnij, gnij, odbijaj, gnij, gnij

Kod (oryginalny 480 bajtów)

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
)

Kod (bajt Arnauld 417)

Arnauld uprzejmie podał 63-bajtową oszczędność, która wykorzystywała sztuczki, które zajęły mi sporo czasu, aby owinąć głowę. Ponieważ zawiera wiele interesujących zmian, pomyślałem, że umieszczę jego kod poniżej (dodałem swoje komentarze), aby można go było kontrastować z moją wersją.

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 bajtów

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$

W jaki sposób?

Wskazówki i kafelki

Używamy następujących kodów dla 6-kierunkowego kompasu i kafelków:

Zakładamy, że stworzenie jest niebieskie.

Znajomości

Potrzebujemy tabeli, aby wiedzieć, które części stworzenia muszą być połączone z innymi płytkami, gdy wejdziemy na dany kafelek w danym kierunku:

     |  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

Przykład:

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

Po spłaszczeniu daje to:

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

Współrzędne

$x+y+z=0$

Kredyty: www.redblobgames.com

Ułatwi to przetwarzanie obrotów i odbić na ostatnim etapie algorytmu.

Kodowanie kafelków

Kafelki są przechowywane na liście, bez określonej kolejności. Oznacza to, że nie musimy się martwić o dynamiczną alokację 2D i możemy z łatwością iterować na istniejących kafelkach. Minusem jest to, że przy określonych współrzędnych potrzebujemy find()odpowiedniego kafelka na liście.

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

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

Algorytm

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

Dlatego ten kafelek jest zakodowany jako [0,0,0,1,1].

Przy każdej iteracji szukamy:

• Płytki z brakującymi połączeniami: w tym przypadku sukcesywnie próbujemy zakończyć połączenie z każdym rodzajem płytki.

• Kafelki, które są już połączone, ale do których należy dodać nowe połączenia, ponieważ zostały osiągnięte w innym kierunku: w tym przypadku aktualizujemy maskę kierunku (z bitowym OR) i wymuszamy nową iterację.

Jeśli wszystkie połączenia są prawidłowe i osiągnęliśmy żądaną liczbę kafelków, nadal musimy sprawdzić, czy jest to nowe stworzenie, czy tylko zmodyfikowana wersja istniejącego:

1. Stosujemy następujące przekształcenia:

   • $(x,y)$$(x,y)$$(y,z)$ (120 °) lub $(z,x)$ (240 °) i odpowiednio aktualizując typy płytek.

   • Wykonujemy 3 odpowiednie odbicia, zastępując $(x,y)$ z $(y,x)$, $(z,y)$ lub $(x,z)$i odpowiednio aktualizując typy kafelków.

2. Dla każdej transformacji tłumaczymy wszystkie płytki tak, aby zawsze znajdował się w prawym dolnym rogu $(0,0)$. (Znaki współrzędnych są odwracane w procesie, co technicznie prowadzi do kolejnego odbicia, ale jest to nieszkodliwe).

3. Sortujemy płytki według ich współrzędnych i typów. (Ten rodzaj jest przetwarzany w porządku leksykograficznym, co jest w porządku.)

4. W końcu zmuszamy wynikową listę do klucza, który można porównać z innymi kluczami.

5. Przerywamy, gdy tylko dopasowany zostanie znany klucz, lub przechowujemy nowy klucz i zwiększamy końcowy wynik, jeśli żadna z transformacji nie prowadzi do znanego klucza.

Skomentował

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