Diketahui bahwa seseorang yang berada di grid di bawah pengaruh alkohol memiliki peluang yang sama untuk pergi ke arah yang tersedia. Namun, pernyataan yang masuk akal ini tidak berlaku di ranah pemabuk yang sangat kecil , yang perilakunya sangat banyak seolah-olah mereka mengambil setiap jalur yang tersedia sekaligus, dan kemungkinan jalur yang mereka ambil dapat saling mengganggu. Tugas Anda adalah menampilkan posisi yang memungkinkan pemabuk kuantum setelah n
langkah-langkah tersebut.
Spesifikasi
Pemabuk yang bersangkutan menempati kotak persegi, dan dapat dianggap sebagai otomat seluler 3-negara menggunakan lingkungan Von Neumann (berbentuk-tambah) yang mengikuti aturan sederhana ini:
Empty
pergi keAwake
jika berdekatan dengan tepat satuAwake
, dan sebaliknya pergi keEmpty
Awake
pergi keSleeping
Sleeping
pergi keSleeping
Keadaan awal papan adalah satu Awake
dikelilingi oleh bidang tak terbatas Empty
s.
Tantangan
Dengan bilangan bulat negatif n
, buat representasi ASCII dari pemabuk setelah n
langkah-langkah. Setiap negara harus diwakili oleh karakter yang berbeda, dan solusi harus menyatakan karakter mana yang berarti negara mana. Jika Anda menggunakan spasi untuk Empty
, Anda tidak perlu menyertakan runnya di akhir baris.
Ini kode-golf , jadi jawaban tersingkat menang. Celah standar berlaku, spasi spasi jejak terdepan dan jejak diizinkan, output array string / 2d char diizinkan, dll.
Contohnya
Contoh-contoh ini digunakan untuk
Empty
, @
untuk Awake
, dan #
untuk Sleeping
.
n=0
@
n = 1
@
@#@
@
n = 2
@
#
@###@
#
@
n = 3
@
@#@
@ # @
@#####@
@ # @
@#@
@
n=6
@
#
@###@
@#@
@ ### @
#@# # #@#
@###########@
#@# # #@#
@ ### @
@#@
@###@
#
@
n=10
@
#
@###@
@#@
###
# # #
#######
# ### #
@ ## ### ## @
#@# ### # ### #@#
@###################@
#@# ### # ### #@#
@ ## ### ## @
# ### #
#######
# # #
###
@#@
@###@
#
@
Catatan Menarik
Dengan mencari urutan jumlah sel yang ditempati di OEIS, saya menemukan bahwa pemabuk kuantum adalah isomorfik dengan urutan tusuk gigi yang jauh lebih banyak dipelajari . Jika Anda bisa memasukkan pengetahuan itu ke dalam golf yang lebih baik, saya akan terkesan.
sumber
n=10
sudah benar? Saya sudah mencoba beberapa pendekatan dan mereka semua mendapatkan jawaban yang sama (salah), jadi saya hanya ingin memastikan. Terlihat agak aneh tapi saya tidak tahu.Jawaban:
Bahasa Wolfram (Mathematica) ,
9291 byteTantangan sempurna untuk menggunakan bawaan Matematika
CellularAutomaton
!Cobalah online!
Kosong = 0, Sedar = 1, Tidur = 2
Animasi 256 iterasi pertama (putih = kosong, abu-abu = bangun, hitam = tidur):
Penjelasan
Jalankan
CellularAutomaton
dengan spesifikasi ...Terapkan aturan totalistik 3 warna 7049487784884, dengan lingkungan Von Neumann ...
Di papan tulis dengan 1 tunggal di tengah, dengan latar belakang 0s ...
Ulangi
<input>
kali ({j#}
dievaluasi ke{{{#}}}
). Array secara otomatis mengembang jika sel di luar perbatasan tidak sama dengan latar belakangAturan ini berasal dari angka dasar-3
220221220221220221220221220
, yang berarti "ubah semua1
atau2
menjadi2
, dan ubah0
menjadi1
jika dan hanya jika ada angka ganjil1
s di sekitarnya."Cetak array.
Semi-bukti "aneh
1
s 'setara dengan' tepat satu1
'":Pertimbangkan kisi piksel 5x5 ini. Putih adalah sel
0
atau2
(piksel non-bangun), dan abu-abu adalah1
sel.Jika sebuah
1
sel dihasilkan sekitar tiga0
sel, maka kisi-kisi harus terlihat seperti ini: ia memiliki tiga1
s yang disusun dalam bentuk-U (atau versi yang dirotasi) sebagai berikut:Karena kemiripan otomatis dari otomat seluler ini, pola apa pun yang muncul dalam otomat seluler harus muncul pada diagonal (melalui induksi). Namun, pola ini tidak simetris secara diagonal. yaitu tidak dapat terjadi pada diagonal dan tidak dapat muncul di mana saja pada otomat seluler.
Sedar / Tidur adalah setara
Perhatikan bahwa
0
sel tidak dapat dikelilingi oleh tepat satu atau tiga2
sel dan sel istirahat0
, karena itu akan menyiratkan bahwa beberapa langkah sebelumnya, sel memiliki tetangga satu atau tiga1
sel - dan harus telah berubah menjadi1
sudah (kontradiksi). Oleh karena itu, boleh saja mengabaikan perbedaan antara1
dan2
dan menyatakan 'ubah semua1
menjadi1
, dan0
menjadi1
jika dan hanya jika negara itu memiliki jumlah ganjil dari tetangga yang bukan nol.'Otomat seluler yang dihasilkan memang identik dengan aslinya, satu-satunya perbedaan adalah tidak ada perbedaan antara pemabuk "terjaga" dan "tertidur". Pola ini dijelaskan dalam OEIS A169707 .
Cobalah online!
Perbandingan berdampingan dari 16 iterasi pertama:
Menambahkan dua iterasi berurutan memberikan hasil yang mengikuti spesifikasi tantangan (94 byte):
Cobalah online!
sumber
Python 2 , 192 byte
Cobalah online!
-17 byte terima kasih kepada Tn. Xcoder
-9 byte menggunakan format output Jonathan
-11 byte terima kasih kepada Lynn
-3 byte terima kasih kepada ovs
sumber
exec
simpanan 9 byte, dan…for k in 0,1,2,3for…
menyimpan satu lagi: Tautann=[C+k for k in-1j,1j,-1,1for C in c]
menghemat satu byte lagi!X+Y*1jin
itu sesuatu yang saya pikir tidak mungkin: PC,
360354343319Baris baru setelah non-
#define
baris hanya untuk presentasi di sini, sehingga tidak dihitung. Saya menyertakan fungsi wrapper, jadi −6 (313) jika fungsi tersebut tidak dihitung dan Anda menganggapn
berasal dari tempat lain.q(10)
output:Gunakan
untuk kosong,
"
untuk tidur, dan!
untuk bangun.Ini berfungsi seperti ini:
A(i,b,e)
adalah "∀i∈ [b, e).",B(b,e)
adalah "∀r∈ [b, e) .∀c∈ [b, e)."Perhatikan bahwa setelah n generasi, papan adalah 2 n + 1 persegi.
Karena simetri papan, ini hanya perlu mensimulasikan kuadran kanan bawah, jadi kami mengalokasikan n + 1 matriks persegi dengan 1 baris & kolom padding untuk pencarian tetangga nanti (jadi n + 2).
Mengalokasikan dengan
calloc
memungkinkan kita secara bersamaan mengalikan lebar dengan ketinggian dan menghapus papan untuk0
(kosong).Saat mencari sel dengan koordinatnya (
C
danD
), ia menggunakan nilai absolut dari baris dan kolom (W
) untuk secara otomatis mencerminkan koordinat.Papan disimpan sebagai array pasang bilangan bulat yang mewakili generasi saat ini dan sebelumnya. Bilangan bulat yang dimaksud adalah
char
agar kita dapat menghindarisizeof
.Generasi yang paling sering dicari (dengan tes tetangga) adalah generasi yang lalu, sehingga ditempatkan pada indeks 0 pada pasangan sehingga dapat diakses dengan
*
.Pada setiap generasi (
g
), generasi saat ini disalin dari generasi sebelumnya menggunakanB
loop, kemudian generasi baru dihasilkan dari yang lama.Setiap sel direpresentasikan menggunakan
0
untuk kosong,1
untuk bangun, dan2
untuk tidur. Menghitung tetangga awalnya perhitungan jumlah bit yang ditetapkan dalam 4 bit sel yang rendah ketika 4 tetangga digeser & ATAU bersama-sama sebagai flag (N
), gunakan16
untuk tidur. Tetapi dengan pengamatan bahwa jumlah ganjil tetangga setara dengan tepat 1 tetangga, kita dapat menyimpan beberapa karakter hanya menggunakan topeng dengan 1.Pada akhirnya, papan dicetak penuh dengan mengulangi kuadran kanan bawah menggunakan trik koordinat nilai absolut yang sama, dikurangi bantalan sehingga kami tidak mencetak lapisan luar pada papan. Ini juga mengapa
B
loop menyertakan braket keriting pembuka, karena kami memiliki pernyataan baris baru ekstra di loop luar.Kode ASCII dengan mudah memetakan 0 + 32 (kosong) ke spasi, 2 + 32 (tidur) ke
"
, dan 1 + 32 (bangun) ke!
.Secara keseluruhan saya pikir ini adalah golf yang bisa dibaca karena struktur masalah yang bagus.
sumber
putchar(10)
denganputs("")
&~
bukan NAND, maksud saya kadang-kadang saya berpikir!(a &~ b)
dalam hala NAND (NOT b)
, meskipun dalam hal ini logika!
tidak sama dengan bitwise~
karena kita bergantung pada0
atau1
hasil!
.MATL , 39 byte
Ini menampilkan
Empty
sebagai(ruang)
Awake
sebagai#
Sleeping
sebagai!
.Cobalah online! Anda juga dapat melihat pola tumbuh dalam seni ASCII, atau secara grafis (kode yang dimodifikasi).
Penjelasan
Kode menggunakan bilangan kompleks
0
,1
,j
untuk mewakili tiga negara: kosong, bangun, tidur masing-masing.sumber
Befunge,
384304 byteCobalah online!
Masalah dengan mencoba mengimplementasikan hal semacam ini di Befunge adalah ukuran memori yang terbatas (2000 byte untuk data dan kode). Jadi saya harus menggunakan algoritma yang menghitung karakter yang benar untuk setiap koordinat yang diberikan tanpa referensi ke perhitungan sebelumnya. Mencapai ini dengan secara rekursif melihat ke masa lalu di semua jalur yang mungkin pemabuk mungkin ikuti untuk mencapai titik itu.
Sayangnya ini bukan solusi efisien tertentu. Ini bekerja, tetapi ini sangat lambat, dan itu menjadi lambat secara eksponensial semakin besar nilai n . Jadi sementara itu berpotensi dapat bekerja untuk n hingga sekitar 127 (batas sel memori 7-bit Befunge), dalam praktiknya Anda pasti akan kehilangan minat menunggu hasilnya. Pada TIO, itu akan mencapai batas waktu 60 detik pada sesuatu yang lebih tinggi dari sekitar 6 (paling-paling). Kompiler akan melakukan jauh lebih baik, tetapi bahkan Anda mungkin tidak ingin pergi jauh lebih tinggi dari 10.
Namun, saya pikir itu layak diajukan karena itu sebenarnya demonstrasi yang cukup bagus dari "fungsi" rekursif di Befunge.
sumber
Python 2 , 214 byte
Cobalah online!
Penjelasan
Penggunaan
0
untukempty
,1
untuksleeping
dan2
untukawake
. Mencetak daftar karakter dua dimensi (string satu-panjang).Menentukan fungsi yang mengambil bilangan bulat non-negatif
n
. Berhasil memajukan automaton seluler sampai keadaan yang diinginkan tercapai. Akhirnya, konversi antara nilai integer internal dan karakter aktual diterapkan.sumber
Lua ,
251242239238 byte-8 byte dengan menyederhanakan inisialisasi array dengan mengorbankan beberapa spasi tambahan terkemuka.
-1 byte dengan mengubah
c=i==2+...and print(s)
menjadic=i~=2+...or print(s)
.-3 byte dengan membangun string lengkap terlebih dahulu dan mencetak sekali di akhir.
-1 byte terima kasih kepada Jonathan Frech dengan menulis ulang
or(g(...)==1 and
sebagaior(1==g(...)and
.Cobalah online!
Kosong = Spasi
Terjaga =
1
Tidur =
0
Mengambil input dari baris perintah dan mencetak ke stdout.
Dengan menyatakan status sebagai
false
/nil
,1
dan secara0
internal, mendeteksi "kosong" tidak memerlukan kode apa pun dan pemeriksaan "tepat sekali bangun" dapat dilakukan hanya dengan tambahan.sumber
or(g(...)==1 and
bisaor(1==g(...)and
.APL (Dyalog) , 38 byte
Cobalah online!
-4 Terima kasih kepada Adám .
-8 Terima kasih kepada ngn .
sumber
Jelly ,
3929 byteCobalah online!
Penggunaan
0
,1
dan2
untuk bangun dan tidur kosong. Footer di tautan mengonversi ini menjadi,
@
dan#
.ṬŒḄ
bukanḤḶ=¹
.-
bukan1N
. Juga membuat¤
tidak perlu.S
bukan+/
.Ḃ+Ḃ+
bukan%3=1+=1Ḥ$+
. Sekarang digunakan2
untuk tidur, bukan3
.Penjelasan datang ...
sumber
APL (Dyalog Classic) , 38 byte
Cobalah online!
berdasarkan solusi Erik the Outgolfer
⍪1
adalah matriks 1x1 yang berisi 1⎕
masukan yang telah dievaluasi( )⍣⎕
terapkan itu berkali-kali(⌽0,⍉)⍣4
mengelilingi dengan 0s, yaitu 4 kali lakukan: transpose (⍉
), tambahkan 0s di sebelah kiri (0,
), mundur secara horizontal (⌽
)g←3+/0,,∘0
sebuah fungsi yang menjumlahkan tiga kali lipat horisontal, sebut sajag
⍉∘g∘⍉
sebuah fungsi yang menjumlahkan tiga kali lipat vertikal - yangg
berada di bawah transposisi2 | ⍉∘g∘⍉ + g←3+/0,,∘0
jumlah dari kedua jumlah modulo 2⌈
semakin besar antara itu dan ...2∘∧
LCM dari 2 dan matriks asli - ini mengubah 1s menjadi 2s, sambil mempertahankan 0s dan 2ssumber
Perl 5 , 192 +1 (
-n
) = 193 byteCobalah online!
Menggunakan 0 untuk kosong, 1 untuk bangun, dan 2 untuk tidur.
sumber
Ruby ,
164153 byteCobalah online!
Gunakan "" untuk Kosong, "@" untuk Sedarlah, dan "#" untuk Tidur (seperti dalam contoh). Saya bisa menghemat 6 byte dengan menggunakan angka saja, saya kira, tetapi terlihat lebih baik seperti ini.
sumber
Pip ,
6961 byte60 byte kode, +1 untuk
-l
bendera.Dibawa
n
sebagai argumen baris perintah. Penggunaan0
untuk kosong,1
untuk bangun, dan2
untuk tidur. (Untuk mendapatkan seni ASCII yang lebih bagus seperti pada contoh tantangan, ganti finaly
dengan" @#"@y
.)Cobalah online!
Penjelasan
Mempersiapkan:
Loop utama:
di mana fungsi tubuh adalah:
Setelah loop, kami cukup cetak otomatis
y
. The-l
bendera berarti bahwa daftar bersarang dicetak dengan menggabungkan isi dari setiap baris dan memisahkan baris dengan baris baru.sumber
Java (OpenJDK 8) , 220 byte
Cobalah online!
Catatan: array yang dikembalikan berisi perbatasan atau
'\0'
karakter. Karena pesawat seharusnya tak terbatas, hanya non-perbatasan yang digunakan.Pemetaan karakter:
(spasi)
=
0
Menghemat
sumber
@
centang saya , dan Anda menemukan kuncinya! Bagus. Thechar
-Cast adalah pengawasan keseluruhan dari saya.Python,
199192 byteKode ini berjalan di kedua Python 2 dan Python 3, tetapi menggunakan perpustakaan Numpy pihak ke-3 yang populer untuk melakukan penanganan array.
print(f(6))
outputJika Anda ingin mencetak lebih cantik, Anda dapat menyebutnya dengan cara ini:
yang dicetak menggunakan karakter yang sama seperti yang diberikan dalam pertanyaan.
sumber
[e]ach state should be represented by a different character
(saya menafsirkancharacter
sebagai karakter ASCII yang sebenarnya, daripada integer).