-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
n=10TIO”. - jeśli jest to wymaganie dotyczące szybkości wykonywania, zamiast kodu golfowego należy użyć code-challenge , który odnosi się do zadania optymalizacji bajtów.