Saya berjanji, ini akan menjadi tantangan terakhir saya tentang diamong tilings (untuk sementara waktu). Sisi baiknya, tantangan ini tidak ada hubungannya dengan seni ASCII, dan juga bukan golf kode, jadi ini sebenarnya sangat berbeda.
Jadi sebagai pengingat, setiap segi enam dapat diberi judul dengan tiga berlian berbeda:
Sebuah pertanyaan yang menarik untuk ditanyakan adalah berapa banyak tilings ini ada untuk ukuran segi enam yang diberikan. Tampaknya angka-angka ini telah dipelajari dengan cukup teliti dan dapat ditemukan di OEIS A008793 .
Namun, masalahnya menjadi lebih rumit jika kita bertanya berapa banyak tilings yang ada hingga rotasi dan refleksi . Misalnya, untuk panjang sisi N = 2, 20 tilings berikut ada:
____ ____ ____ ____ ____ ____ ____ ____ ____ ____
/\_\_\ /\_\_\ /\_\_\ /\_\_\ /_/\_\ /_/\_\ /\_\_\ /_/\_\ /_/\_\ /_/\_\
/\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\
\/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/
\/_/_/ \/_/_/ \/_/_/ \_\/_/ \/_/_/ \/_/_/ \_\/_/ \_\/_/ \_\/_/ \_\/_/
____ ____ ____ ____ ____ ____ ____ ____ ____ ____
/_/_/\ /\_\_\ /_/\_\ /_/_/\ /_/\_\ /_/\_\ /_/_/\ /_/_/\ /_/_/\ /_/_/\
/\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\
\/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/
\/_/_/ \_\_\/ \_\/_/ \_\/_/ \_\_\/ \_\_\/ \_\/_/ \_\_\/ \_\_\/ \_\_\/
Tetapi banyak dari ini identik di bawah rotasi dan refleksi. Jika kita memperhitungkan simetri ini, hanya tersisa 6 til yang berbeda:
____ ____ ____ ____ ____ ____
/\_\_\ /\_\_\ /\_\_\ /_/\_\ /_/\_\ /_/\_\
/\/\_\_\ /\/_/\_\ /\/_/_/\ /\_\/_/\ /\_\/_/\ /_/\/\_\
\/\/_/_/ \/\_\/_/ \/\_\_\/ \/\_\_\/ \/_/\_\/ \_\/\/_/
\/_/_/ \/_/_/ \/_/_/ \/_/_/ \_\/_/ \_\/_/
2 2 6 6 1 3
di mana angka-angka menunjukkan banyaknya setiap ubin. Perhatikan bahwa untuk hexagon yang lebih besar ada juga tilings dengan multiplisitas 4 dan 12.
Tampaknya jumlah kemiringan hingga simetri telah dipelajari kurang teliti. Entri OEIS A066931 hanya mencantumkan lima istilah:
1, 1, 6, 113, 20174
di mana istilah pertama adalah untuk panjang sisi N = 0
dan istilah terakhir untuk panjang sisi N = 4
.
Saya yakin kita bisa melakukan lebih baik dari itu!
Tugas Anda adalah menghitung jumlah kemiringan untuk panjang sisi tertentu.
Ini adalah kode tercepat . Skor Anda akan menjadi sisi-panjang tertinggi N
yang kode Anda menghasilkan hasil yang benar dalam waktu 30 menit pada mesin saya. Dalam hal seri, saya akan menerima kiriman yang menghasilkan hasil untuk yang N
tercepat.
Seperti biasa, Anda tidak boleh hasil hardcode yang sudah Anda tahu untuk memenangkan tie-breaker. Algoritma yang memecahkan N = 3
harus identik dengan yang memecahkan N = 5
.
Kiriman Anda tidak boleh menggunakan memori lebih dari 4GB. Saya akan memberikan beberapa kelonggaran pada hal ini jika Anda beroperasi mendekati batas itu, tetapi jika Anda secara konsisten di atas batas itu, atau jika Anda melonjak secara signifikan di luar batas itu, saya tidak akan menghitungnya N
untuk pengiriman Anda.
Saya akan menguji semua pengiriman pada mesin Windows 8 saya, jadi pastikan bahasa pilihan Anda tersedia secara bebas di Windows. Satu-satunya pengecualian untuk ini adalah Mathematica (karena saya kebetulan memiliki lisensi untuk itu). Harap sertakan instruksi untuk mengkompilasi / menjalankan kode Anda
Tentu saja, merasa bebas untuk menghitung lebih banyak istilah dalam waktu Anda sendiri (untuk sains, dan bagi orang lain untuk memeriksa angka-angka mereka), tetapi skor jawaban Anda akan ditentukan dalam 30 menit tersebut.
sumber
N = 6
memberikan output lebih dari 10 ^ 12, solusi non-konstruktif hampir pasti diperlukan untuk mencapai sejauh itu.Jawaban:
Aljabar, teori grafik, inversi Möbius, penelitian, dan Jawa
Gugus simetri hexagon adalah kelompok dihedral orde 12, dan dihasilkan oleh rotasi 60 derajat dan cermin membalik diameter. Ini memiliki 16 subkelompok, tetapi beberapa dari mereka berada dalam kelompok konjugasi non-sepele (yang hanya memiliki refleksi memiliki 3 pilihan sumbu), jadi ada 10 simetri yang berbeda secara mendasar yang dapat dimiliki oleh sebuah ubin segi enam:
Jumlah kemiringan intan dari subset kisi segitiga dapat dihitung sebagai penentu , jadi pendekatan awal saya adalah menyiapkan satu determinan untuk masing-masing simetri segi enam, untuk menghitung jumlah kemiringan yang memiliki setidaknya simetri tersebut. ; dan kemudian menggunakan inversi Mbius dalam aljabar kejadian poset mereka (pada dasarnya generalisasi dari prinsip inklusi-eksklusi) untuk menghitung jumlah tilings yang kelompok simetrinya persis masing-masing dari 10 kasus. Namun, beberapa simetri memiliki kondisi tepi yang buruk, jadi saya terpaksa menjumlahkan banyak faktor penentu secara eksponensial. Untungnya, nilai yang didapat
n < 10
memberi saya cukup data untuk dapat mengidentifikasi urutan yang relevan dalam OEIS dan mengumpulkan bentuk tertutup (untuk beberapa nilai "ditutup" yang memungkinkan produk hingga). Ada sedikit diskusi tentang urutan, dan referensi untuk bukti, dalam penulisan resmi yang saya siapkan untuk membenarkan pembaruan urutan OEIS.Setelah penghitungan ganda diatasi, ternyata empat dari sepuluh nilai dibatalkan dengan rapi, jadi kita hanya perlu menghitung enam sisanya dan kemudian melakukan penjumlahan berbobot.
Kode ini membutuhkan waktu kurang dari 30 detik untuk
N=1000
komputer saya.sumber
C
pengantar
Seperti dikomentari oleh David Carraher, cara paling sederhana menganalisis ubin segi enam tampaknya mengambil keuntungan dari isomorfisma dengan Diagram Young 3 dimensi, pada dasarnya x, y persegi diisi dengan bar tinggi bilangan bulat yang z ketinggiannya harus tetap sama atau meningkat sebagai sumbu z didekati.
Saya mulai dengan sebuah algoritma untuk menemukan total yang lebih dapat diterima untuk adaptasi untuk penghitungan simetri daripada algoritma yang dipublikasikan, yang didasarkan pada bias ke salah satu dari tiga sumbu kartesian.
Algoritma
Saya mulai dengan mengisi sel-sel bidang x, y, dan z dengan 1's, sedangkan sisanya berisi nol. Setelah selesai, saya membangun pola lapis demi lapis, dengan setiap lapisan berisi sel-sel yang memiliki jarak manhattan 3D umum dari asal. Sel hanya dapat berisi 1 jika tiga sel di bawahnya juga mengandung 1. jika ada di antara mereka yang mengandung 0, maka sel tersebut harus 0.
Keuntungan membangun pola dengan cara ini adalah bahwa setiap lapisan simetris tentang garis x = y = z. Ini berarti bahwa setiap lapisan dapat diperiksa secara independen untuk simetri.
Pemeriksaan simetri
Simetri padatan adalah sebagai berikut: 3 kali lipat rotasi tentang garis x = y = z -> 3 lipat rotasi tentang pusat segi enam; dan 3 x refleksi tentang 3 bidang yang berisi garis x = y = z dan masing-masing sumbu x, y, z -> refleksi tentang garis-garis melalui sudut-sudut segi enam.
Ini hanya menambah hingga 6 kali lipat simetri. Untuk mendapatkan simetri penuh segi enam, jenis simetri lain harus dipertimbangkan. Setiap padatan (dibangun dari 1's) memiliki padatan komplementer (dibangun dari 0's). Di mana N adalah aneh, padatan komplementer harus berbeda dari padatan asli (karena tidak mungkin bagi mereka untuk memiliki jumlah kubus yang sama). Namun ketika padatan komplementer diputar, akan ditemukan bahwa representasi 2D-nya sebagai ubin berlian identik (kecuali untuk operasi simetri 2 kali lipat) dengan padatan asli. Di mana N adalah genap, adalah mungkin bagi benda padat untuk menjadi terbalik sendiri.
Ini dapat dilihat pada contoh untuk N = 2 dalam pertanyaan. Jika dilihat dari kiri, segi enam pertama tampak seperti kubus padat dengan 8 kubus kecil, sedangkan segi enam terakhir tampak seperti kulit kosong dengan 0 kubus kecil. Jika dilihat dari kanan, kebalikannya benar. Segi 3, 4 dan 5 dan segi enam 16, 17 dan 18 tampak seperti mereka mengandung 2 atau 6 kubus, dan dengan demikian mereka saling melengkapi dalam 3 dimensi. Mereka terkait satu sama lain dalam 2 dimensi dengan operasi simetri 2 kali lipat (rotasi 2 kali lipat, atau refleksi tentang suatu sumbu melalui tepi segi enam.) Di sisi lain segi enam, ke-10, ke-11 dan ke-12 menunjukkan pola 3D yang adalah pelengkap mereka sendiri, dan karena itu memiliki simetri yang lebih tinggi (oleh karena itu ini adalah satu-satunya pola dengan multiplisitas ganjil).
Perhatikan bahwa memiliki (N ^ 3) / 2 kubus adalah kondisi yang diperlukan untuk melengkapi diri sendiri, tetapi secara umum itu bukan kondisi yang memadai jika N> 2. Hasil dari semua ini adalah bahwa untuk N aneh, tilings selalu terjadi berpasangan (N ^ 3) / 2 kubus harus diperiksa dengan cermat.
Kode saat ini (menghasilkan total yang tepat untuk N = 1,2,3,5. Kesalahan seperti yang didiskusikan untuk N = 4.)
Keluaran
Program ini menghasilkan tabel keluaran 8 entri, sesuai dengan 8 simetri padatan. Padatan dapat memiliki salah satu dari 4 simetri sebagai berikut (notasi Schoenflies)
Selain itu, ketika padatan memiliki tepat setengah sel dengan 1 dan setengah dengan 0, ada kemungkinan membalik semua 1 dan 0, kemudian membalikkan koordinat melalui pusat ruang kubus. Inilah yang saya sebut pelengkap diri, tetapi istilah yang lebih matematis akan menjadi "antisimetris sehubungan dengan pusat inversi."
Operasi simetri ini memberikan sumbu rotasi 2 kali lipat dalam ubin segi enam.
Pola yang memiliki simetri ini tercantum dalam kolom terpisah. Mereka hanya terjadi di mana N adalah genap.
Hitungan saya tampaknya sedikit tidak aktif untuk N = 4. Dalam diskusi dengan Peter Taylor, tampaknya saya tidak mendeteksi miring yang hanya memiliki simetri garis melalui tepi segi enam. Ini mungkin karena saya belum menguji komplemen diri (antisimetri) untuk operasi selain (inversi) x (identitas.) Pengujian komplemen mandiri untuk operator (inversi) x (refleksi) dan (inversi) x (rotasi 3 kali lipat ) dapat mengungkap simetri yang hilang. Saya kemudian akan mengharapkan baris pertama data untuk N = 4 terlihat seperti ini (16 lebih sedikit di c1 dan 32 lebih banyak di C1):
Ini akan membuat total sejalan dengan jawaban Peter dan https://oeis.org/A066931/a066931.txt
output saat ini adalah sebagai berikut.
Daftar tugas (diperbarui)
Dilakukan, kurang lebih
Selesai, hasil untuk N aneh setuju dengan data yang dipublikasikan
Ini dapat dilakukan dengan menambahkan kondisi lain ke panggilan rekursi:
if(s1 && m<n*3-2)f(m + 1,e+d,s1)
Ini mengurangi waktu lari untuk N = 5 dari 5 menit menjadi sekitar satu detik. Sebagai hasilnya, baris pertama dari output menjadi total sampah (seperti halnya total keseluruhan) tetapi jika total sudah diketahui dari OEIS, jumlah tiling asimetris dapat disusun kembali, setidaknya untuk N. aneh.Tetapi bahkan untuk N, jumlah padatan asimetris (menurut simetri c3v) yang melengkapi diri sendiri akan hilang. Untuk kasus ini, program terpisah yang didedikasikan untuk padatan dengan tepat (N ** 3) / 2 sel dengan 1 mungkin berguna. Dengan ini tersedia (dan menghitung dengan benar) dimungkinkan untuk mencoba N = 6, tetapi akan membutuhkan waktu lama untuk dijalankan.
Tidak selesai, tabungan diharapkan menjadi marjinal
Selesai, tetapi tampaknya memiliki kelalaian, lihat N = 4.
Penghematan tidak diharapkan menjadi sebesar itu. Menekan angka asimetris menghilangkan sebagian besar dari ini. Satu-satunya refleksi yang diperiksa adalah bidang melalui sumbu y (x dan z dihitung kemudian dengan mengalikan dengan 3.) Angka-angka dengan hanya simetri rotasi dihitung dalam kedua bentuk enansiomernya. Mungkin itu akan berjalan hampir dua kali lebih cepat jika hanya satu yang dihitung.
Menarik tapi mungkin ada pertanyaan lain di situs ini untuk dijelajahi.
sumber