Tantangan ini akan membuat Anda menghitung "makhluk" di permainan ubin Palago.

Makhluk adalah segala bentuk tertutup yang dapat dibentuk oleh ubin Palago dengan warna senada dalam kisi heksagonal.

Gim Palago terdiri dari ubin seperti ini:

Ubin ini dapat diputar $120^\circ$ , $240^\circ$ , atau tidak sama sekali dan ditempatkan di mana saja pada kisi heksagonal. Sebagai contoh, di sini adalah makhluk (merah) yang membutuhkan 12 ubin.

Tantangan

Tujuan dari tantangan ini adalah untuk menulis sebuah program yang mengambil bilangan bulat nsebagai input dan menghitung jumlah makhluk (hingga rotasi dan refleksi) yang membutuhkan nubin. Program harus mampu menangani hingga n=10pada TIO . Ini adalah kode-golf , byte paling sedikit menang.

Contoh data

Nilai harus cocok dengan data yang ditemukan di bagian "Jumlah dan Perkiraan Creature" di situs web pembuat . Yaitu

 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 byte terima kasih kepada @Arnauld. Wow.

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

Cobalah online!

Pertama, perhatikan Arnauld yang jawabannya memberi saya inspirasi untuk menggali lebih dalam. Saya telah berusaha keras untuk menjadi orisinal dengan algoritma saya, meskipun saya sengaja mengubah beberapa kode saya untuk menggunakan variabel yang sama dengan Arnauld sehingga kode tersebut dapat lebih mudah dibandingkan.

Mencari heksa kosong

Pencarian makhluk adalah:

• Inisialisasi daftar ubin dengan ubin 1 di 0,0
• Secara rekursif:
  • Cari hex kosong yang dibutuhkan untuk melengkapi makhluk
  • Jika hex kosong ditemukan
    • Tambahkan setiap jenis ubin 0,1,2 ke hex kosong dan berulang
  • Jika hex kosong tidak ditemukan
    • Jika ukuran makhluk benar dan belum ada di kebun binatang
      • Jumlah makhluk berbeda yang ditemukan oleh satu
      • Tambahkan semua rotasi dan refleksi makhluk ke kebun binatang

Pencarian heksa kosong menemukan simetri yang menarik. Arnauld menemukan bahwa salah satu dari enam arah dapat diabaikan, tetapi pada kenyataannya tiga dari enam arah dapat diabaikan!

Berikut ini arahan asli dan kunci ubin Arnauld:

Bayangkan kita mulai dari ubin A tipe 1 di titik biru. Tampaknya kita harus berulang dalam d = 0 dan d = 5. Namun, ubin mana pun yang ditempatkan di d = 0, itu pasti akan memiliki jalan keluar di d = 4, yang akan mengunjungi hex yang sama seperti keluar dari ubin A di d = 5. Itulah penemuan Arnauld, dan itulah yang mulai saya pikirkan.

Perhatikan itu:

• Setiap ubin yang memiliki jalan keluar di d = 0 memiliki jalan keluar di d = 5
• Setiap petak yang memiliki jalan keluar di d = 2 memiliki jalan keluar di d = 1

• Setiap petak yang memiliki jalan keluar di d = 4 memiliki jalan keluar di d = 3

• Setiap petak yang dapat dimasukkan dari d = 0 memiliki jalan keluar di d = 4

• Setiap petak yang dapat dimasukkan dari d = 2 memiliki jalan keluar di d = 0
• Setiap petak yang dapat dimasukkan dari d = 4 memiliki jalan keluar di d = 2

Ini berarti bahwa kita hanya perlu mempertimbangkan arah 0,2,4. Setiap pintu keluar di arah 1,3,5 dapat diabaikan karena heks yang dapat dijangkau dalam arah 1,3,5 malah dapat dicapai dari heks yang berdekatan menggunakan arah 0,2 atau 4.

Betapa kerennya itu!?

Petunjuk Relabelled

Jadi saya menandai ulang arah dan ubin seperti ini (gambar Arnauld diedit):

Sekarang kami memiliki hubungan berikut antara ubin, entri dan keluar:

    |  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

Jadi jalan keluarnya adalah: d + t == 2? (4-t)% 3: 2-t dan 2 * t% 3

Rotasi dan Refleksi Heksagonal

Untuk rotasi dan refleksi, saya memutuskan untuk mencoba koordinat sumbu heksagonal x, y alih-alih koordinat kubus 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

Dalam sistem ini, rotasi dan refleksi lebih sederhana daripada yang saya harapkan:

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

Untuk mendapatkan semua kombinasi yang saya lakukan: membusuk, membusuk, membusuk, memantulkan, membusuk, membusuk

Kode (Asli 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
)

Kode (Arnauld 417 byte)

Arnauld dengan ramah mengajukan penghematan 63 byte yang menggunakan trik yang membutuhkan waktu cukup lama untuk membungkus kepala saya. Karena memiliki banyak pengeditan yang menarik, saya pikir saya akan meletakkan kodenya di bawah ini (saya telah menambahkan komentar saya) sehingga dapat dikontraskan dengan versi saya.

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

$n=1$$n=13$ )

Bagaimana?

Arah dan ubin

Kami menggunakan kode berikut untuk kompas 6 arah dan ubin:

Kami berasumsi bahwa makhluk itu berwarna biru.

Koneksi

Kita membutuhkan sebuah meja untuk mengetahui bagian mana dari makhluk itu yang perlu dihubungkan ke ubin lain ketika kita memasukkan ubin tertentu ke arah yang diberikan:

     |  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

Contoh:

$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

Kumpulan petunjuk yang diperbarui ini pertama kali disandikan ulang sebagai bilangan bulat 5-bit, dan kemudian sebagai karakter ASCII dengan offset tetap sebesar $+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 |  "$"  |  "<"  |  "%"

Setelah diratakan, ini memberi:

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

Koordinat

$x+y+z=0$ :

Kredit: www.redblobgames.com

Ini akan membuatnya lebih mudah untuk memproses rotasi dan refleksi pada langkah terakhir dari algoritma.

Pengkodean ubin

Ubin disimpan dalam daftar, tanpa urutan tertentu. Ini berarti bahwa kita tidak perlu khawatir tentang alokasi 2D yang dinamis dan kita dapat dengan mudah beralih pada ubin yang ada. Kelemahannya adalah bahwa, mengingat koordinat tertentu, kita perlu find()ubin yang sesuai dalam daftar.

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

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

Algoritma

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

Oleh karena itu, ubin ini dikodekan sebagai [0,0,0,1,1].

Pada setiap iterasi, kami mencari:

• Ubin dengan koneksi yang hilang: dalam hal ini, kami mencoba menyelesaikan koneksi dengan setiap jenis ubin secara berurutan.

• Ubin yang sudah terhubung tetapi yang koneksi baru perlu ditambahkan karena mereka telah dicapai dalam arah yang berbeda: dalam hal ini, kami memperbarui topeng arah (dengan bitwise OR) dan memaksa iterasi baru.

Jika semua koneksi valid dan kami telah mencapai jumlah ubin yang diminta, kami masih perlu menguji apakah itu adalah makhluk baru atau hanya versi modifikasi dari yang sudah ada:

1. Kami menerapkan transformasi berikut:

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

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

2. $(0,0)$

3. Kami mengurutkan ubin sesuai dengan koordinat dan jenisnya. (Semacam ini diproses dalam urutan leksikografis, yang baik-baik saja.)

4. Kami akhirnya memaksa daftar yang dihasilkan ke string kunci yang dapat dibandingkan dengan kunci lainnya.

5. Kami membatalkan segera setelah kunci yang diketahui cocok, atau menyimpan kunci baru dan meningkatkan hasil akhir jika tidak ada transformasi yang mengarah ke kunci yang dikenal.

Berkomentar

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