Polystrips adalah subset dari polyomino yang sesuai dengan aturan berikut:
- masing-masing bagian terdiri dari 1 atau lebih sel
- tidak ada sel yang dapat memiliki lebih dari dua tetangga
- sel-sel seharusnya tidak menutup lubang
Polyomino bebas berbeda ketika tidak ada transformasi kaku (terjemahan, rotasi, refleksi atau glide refleksi) dari yang lain (potongan yang dapat diambil dan dibalik). Menerjemahkan, memutar, memantulkan, atau meluncur yang mencerminkan polyomino gratis tidak mengubah bentuknya ( Wikipedia )
Misalnya, ada 30 heptastrip gratis (polistrip dengan panjang 7). Berikut semuanya, dikemas dalam kisi 14x15.
Kredit gambar: Miroslav Vicher
Tujuan
Tulis program / fungsi yang mengambil bilangan bulat positif n
sebagai input dan menghitung n
-polistrip bebas yang berbeda .
n = 1 -> 1 (Satu kotak)
n = 2 -> 1 (Hanya ada satu kemungkinan 2-polystrip yang terbuat dari 2 kotak)
n = 3 -> 2 (Satu terdiri dari 3 kotak bergabung dalam satu garis dan yang lainnya berbentuk L)
n = 4 -> 3 (Satu lurus, satu berbentuk L dan satu berbentuk Z)
. . .
Kasus uji:
n polystrips
1 1
2 1
3 2
4 3
5 7
6 13
7 30
8 64
9 150
10 338
11 794
12 1836
13 4313
14 10067
15 23621
Mencetak gol
Ini kode-golf , jadi kode yang lebih pendek lebih baik. Saya akan sangat menghargai penjelasan rinci tentang algoritma dan kodenya.
Implementasi referensi parsial dalam J
Saya memutuskan untuk menggambarkan setiap bagian dalam format "vektor" dan saya hanya perlu n-2 blok untuk menggambarkan bagian n-polystrip (hanya ada 1 2-polystrip dan dikembalikan secara eksplisit). Blok menggambarkan arah relatif: 0 - tidak ada perubahan; 1 - belok kiri; 2 - belok kanan. Tidak masalah ke arah mana seseorang akan mulai tetapi hanya untuk menunjukkan di mana sel selanjutnya akan diletakkan. Bisa ada jumlah 0s berurutan, tetapi 1s dan 2s selalu tunggal. Implementasi ini parsial, karena tidak memperhitungkan lubang - solusi untuk n> 6 juga menghitung bagian yang berlubang.
sumber
101010
dalam notasi sampel Anda)?Jawaban:
Python 3 ,
480433406364309299295 byteTampak seperti titik yang baik untuk memulai karir PPCG saya (atau tidak?).
Cobalah online!
Suntingan:
D
danX
, dan tweak sedikit di beberapa tempat golf.m
. (Bilangan kompleks benar-benar fitur golfy yang kuat tetapi sering diabaikan; diadaptasi dari solusi xnor untuk tantangan lain )LFR
representasi string menjadi-1,0,1
tupel dan mengorbankan waktu eksekusi untuk jumlah byte byte yang dikurangi (!). Sekarang solusinya secara teoritis benar tetapi batas waktu sebelum menghasilkan hasilnya selama 15.r
. AKHIRNYA DI BAWAH 300 HASIL !!!1j
dapat menempel pada hal lain tanpa membingungkan parser (-2B), dannot
memiliki prioritas yang sangat rendah (-2B).Versi usang (480 byte):
Cobalah online!
Solusi yang tidak digabungkan dengan komentar:
Cobalah online!
Kami tidak membutuhkan ini lagi, dan sekarang dijamin benar untuk ukuran input sewenang-wenang, berkat bilangan kompleks bawaan.m = 999
dipilih karena butuh waktu eksponensial untuk menghitung semuanya, dan sudah butuh ~ 8s untuk menghitungn = 1..15
. Mungkin tidak apa-apa untuk menyimpan 1 byte dengan menggunakan 99 sebagai gantinya.sumber
APL (Dyalog Unicode) ,
7065 byteCobalah online!
Versi program lengkap dari kode di bawah ini, terima kasih kepada Adám.
APL (Dyalog Unicode) , 70 byte
Cobalah online!
Bagaimana itu bekerja
Kode di atas setara dengan definisi berikut:
Ini berfungsi seperti solusi Python, tetapi dalam urutan yang berbeda. Itu
gen
menghapusLFR
-garis panjangn-2
,canonicalize
s setiap strip, mengambil∪
strip nique,test
s setiap strip jika menyentuh sendiri (1 jika tidak menyentuh, 0 sebaliknya), dan menjumlahkan+/
hasil boolean.gen
canonicalize
test
sumber