Saya menemukan urutan ini ketika mengerjakan Evolusi OEIS , tetapi tidak pernah mempostingnya sebagai jawaban. Setelah menulis implementasi referensi di Mathematica, saya pikir ini adalah latihan yang menyenangkan untuk dilakukan sebagai tantangan terpisah, jadi di sini kita mulai.
Mari kita membangun reaktor fisi numerik! Pertimbangkan bilangan bulat positif N
. Sebagai contoh, kita akan melihat 24
. Untuk mendapatkan angka ini, kita harus menemukan jumlah bilangan bulat positif berturut - turut terbesar yang dijumlahkan N
. Dalam hal ini, itu 7 + 8 + 9 = 24
. Jadi kami telah membagi 24
menjadi tiga angka baru. Tapi ini bukan reaktor fisi tanpa reaksi berantai. Jadi mari kita ulangi proses untuk komponen ini secara rekursif:
24
/|\
/ | \
/ | \
7 8 9
/ \ /|\
3 4 / | \
/ \ / | \
1 2 2 3 4
/ \
1 2
Perhatikan bahwa kami menghentikan proses kapan pun nomor tidak dapat didekomposisi menjadi bilangan bulat berurutan yang lebih kecil. Perhatikan juga bahwa kita dapat menulis 9
sebagai 4 + 5
, tetapi 2 + 3 + 4
memiliki lebih banyak komponen. The Fisi jumlah dari N
sekarang didefinisikan sebagai jumlah bilangan bulat yang diperoleh dalam proses ini, termasuk N
dirinya sendiri. Pohon di atas memiliki 13 node, jadi F(24) = 13
.
Urutan ini adalah entri OEIS A256504 .
40 istilah pertama, mulai dari N = 1
, adalah
1, 1, 3, 1, 5, 6, 5, 1, 6, 7, 12, 10, 12, 11, 12, 1, 8, 16, 14, 17, 18, 18,
23, 13, 21, 18, 22, 23, 24, 19, 14, 1, 22, 20, 23, 24, 31, 27, 25, 26
1000 istilah pertama dapat ditemukan di pastebin ini .
Tantangan
Diberikan bilangan bulat positif N
, tentukan angka Fisinya F(N)
. (Jadi, Anda tidak perlu membahas yang 0
terdaftar di OEIS.)
Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).
Ini kode golf, jadi jawaban tersingkat (dalam byte) menang.
Pertanyaan bonus: Dapatkah Anda menemukan properti menarik dari urutan ini?
sumber
Jawaban:
Pyth,
232221 byteIni mendefinisikan fungsi rekursif
y
. Cobalah online: DemonstrasiPenjelasan:
sumber
Fission ,
1328989887797 byteJawaban ini agak lama tidak masuk akal (saya berharap kami memiliki daerah yang dapat dilipat ) ... jangan lupa untuk menggulir melewati ini dan menunjukkan jawaban lain beberapa cinta!
Mengerjakan kode ini adalah yang menginspirasi tantangan ini. Saya ingin menambahkan jawaban dalam Fission ke EOEIS, yang membawa saya ke urutan ini. Namun, sebenarnya mempelajari Fisi dan mengimplementasikan ini membutuhkan waktu beberapa minggu untuk mengerjakannya dan mematikannya. Sementara itu, urutannya benar-benar tumbuh pada saya jadi saya memutuskan untuk memposting tantangan terpisah untuk itu (ditambah, ini tidak akan terlalu jauh di bawah pohon pada EOEIS).
Jadi saya persembahkan kepada Anda, Monstrositas:
Itu mengharapkan bahwa tidak ada baris baru di input, jadi Anda mungkin ingin menyebutnya seperti
echo -n 120 | ./Fission oeis256504.fis
.Tata letak mungkin masih bisa lebih efisien, jadi saya pikir masih ada banyak ruang untuk perbaikan di sini (misalnya, ini berisi
911581461374 spasi).Sebelum kita sampai pada penjelasan, catatan tentang pengujian ini: penerjemah resmi tidak sepenuhnya berfungsi sebagaimana mestinya. a)
Mirror.cpp
tidak dikompilasi pada banyak sistem. Jika Anda mengalami masalah itu, cukup komentari baris yang menyinggung - komponen yang terpengaruh (cermin acak) tidak digunakan dalam kode ini. b) Ada beberapa bug yang dapat menyebabkan perilaku tidak terdefinisi (dan kemungkinan akan untuk program kompleks ini). Anda dapat menerapkan tambalan ini untuk memperbaikinya. Setelah Anda selesai melakukannya, Anda harus dapat mengkompilasi juru bahasaFakta menyenangkan: Program ini menggunakan hampir setiap komponen Fission yang ditawarkan, kecuali untuk
#
(cermin acak),:
(cermin setengah),-
atau|
(cermin polos), dan"
(mode cetak).Apa yang di Bumi?
Peringatan: Ini akan cukup lama ... Saya menganggap Anda benar-benar tertarik pada cara kerja Fission dan bagaimana seseorang dapat memprogramnya. Karena jika tidak, saya tidak yakin bagaimana saya bisa meringkas ini. (Namun, paragraf berikutnya memberikan deskripsi umum bahasa tersebut.)
Fission adalah bahasa pemrograman dua dimensi, di mana data dan aliran kontrol diwakili oleh atom yang bergerak melalui grid. Jika Anda pernah melihat atau menggunakan Marbelous sebelumnya, konsepnya seharusnya tidak asing lagi. Setiap atom memiliki dua sifat bilangan bulat: massa non-negatif dan energi yang berubah-ubah. Jika massa menjadi negatif, atom dikeluarkan dari grid. Dalam kebanyakan kasus, Anda dapat memperlakukan massa sebagai "nilai" atom dan energi sebagai semacam properti meta yang digunakan oleh beberapa komponen untuk menentukan aliran atom (yaitu sebagian besar saklar bergantung pada tanda energi). Saya akan melambangkan atom dengan
(m,E)
, bila perlu. Di awal program, grid dimulai dengan sekelompok(1,0)
atom dari mana pun Anda menempatkan pada empat komponenUDLR
(di mana huruf menunjukkan arah atom bergerak pada awalnya). Papan tersebut kemudian diisi dengan sejumlah komponen yang mengubah massa dan energi atom, mengubah arahnya atau melakukan hal-hal lain yang lebih canggih. Untuk daftar lengkap, lihat halaman esolangs , tetapi saya akan memperkenalkan sebagian besar dari mereka dalam penjelasan ini. Poin penting lainnya (yang digunakan beberapa kali oleh program) adalah bahwa kisi-kisi itu toroidal: sebuah atom yang mengenai salah satu sisi muncul kembali di sisi yang berlawanan, bergerak ke arah yang sama.Saya menulis program di beberapa bagian yang lebih kecil dan mengumpulkannya di bagian akhir, jadi begitulah saya akan menjelaskannya.
atoi
Komponen ini mungkin terlihat agak tidak menarik, tetapi bagus dan sederhana dan memungkinkan saya untuk memperkenalkan banyak konsep penting dari aritmatika dan aliran kontrol Fission. Oleh karena itu, saya akan melalui bagian ini dengan detail yang sangat teliti, sehingga saya dapat mengurangi bagian lain untuk memperkenalkan mekanik Fisi baru dan menunjukkan komponen tingkat yang lebih tinggi yang aliran kontrol detailnya Anda harus dapat mengikuti sendiri.
Fission hanya dapat membaca nilai byte dari karakter individual, bukan seluruh angka. Sementara itu praktik yang dapat diterima di sekitar sini, saya pikir ketika saya berada di sana, saya bisa melakukannya dengan benar dan mem-parsing bilangan bulat aktual di STDIN. Ini
atoi
kodenya:Dua komponen terpenting dalam Fisi adalah reaktor fisi dan fusi. Reaktor fisi adalah salah satu dari
V^<>
(kode di atas menggunakan<
dan>
). Reaktor fisi dapat menyimpan atom (dengan mengirimkannya ke dalam irisan karakter), secara default(2,0)
. Jika sebuah atom mengenai puncak karakter, dua atom baru akan dikirim ke samping. Massa mereka ditentukan dengan membagi massa yang masuk dengan massa yang disimpan (mis. Separuh secara default) - atom yang pergi mendapatkan nilai ini, dan atom yang sedang berjalan mendapatkan sisa massa (yaitu massa yang disimpan dalam fisi) . Kedua atom yang keluar akan memiliki minus energi yang masukenergi yang tersimpan. Ini berarti kita dapat menggunakan reaktor fisi untuk aritmatika - baik untuk pengurangan dan pembagian. Jika reaktor fisi terkena dari situs, atom hanya dipantulkan secara diagonal dan kemudian akan bergerak ke arah puncak karakter.Reaktor fusi adalah salah satu dari
YA{}
(kode di atas menggunakanY
dan{
). Fungsinya mirip: mereka dapat menyimpan atom (default(1,0)
) dan ketika dipukul dari apex dua atom baru akan dikirim ke sisi. Namun, dalam hal ini kedua atom akan identik, selalu mempertahankan energi yang masuk, dan mengalikan massa yang masuk dengan massa yang disimpan. Artinya, secara default, reaktor fusi hanya menduplikasi atom apa pun yang mencapai puncaknya. Ketika dipukul dari samping, reaktor fusi sedikit lebih rumit: atomnya jugadisimpan (terlepas dari memori lainnya) hingga sebuah atom menyentuh sisi yang berlawanan. Ketika itu terjadi, sebuah atom baru dilepaskan ke arah puncak yang massa dan energinya adalah jumlah dari dua atom lama. Jika atom baru mengenai sisi yang sama sebelum atom yang cocok mencapai sisi yang berlawanan, atom lama hanya akan ditimpa. Reaktor fusi dapat digunakan untuk mengimplementasikan penjumlahan dan perkalian.Komponen sederhana lain yang ingin saya hindari adalah
[
dan]
yang mengatur masing-masing arah atom ke kanan dan kiri (terlepas dari arah masuk). Setara vertikal adalahM
(turun) danW
(atas) tetapi mereka tidak digunakan untukatoi
kode.UDLR
juga bertindakWM][
setelah melepaskan atom awal mereka.Pokoknya, mari kita lihat kode di sana. Program dimulai dengan 5 atom:
R
danL
di bagian bawah hanya mendapatkan kenaikan massa mereka (dengan+
) untuk menjadi(10,0)
dan kemudian disimpan dalam fisi dan reaktor fusi, masing-masing. Kami akan menggunakan reaktor ini untuk mengurai input basis-10.L
di sudut kanan atas mendapat massa dikurangi (dengan_
) menjadi(0,0)
dan disimpan di samping reaktor fusiY
. Ini untuk melacak angka yang kita baca - kita akan secara bertahap meningkatkan dan melipatgandakannya ketika kita membaca angka.R
sudut kiri atas massa diatur ke kode karakter0
(48) dengan'0
, kemudian massa dan energi ditukar dengan@
dan akhirnya massa bertambah satu kali dengan+
memberi(1,48)
. Ini kemudian dialihkan dengan cermin diagonal\
dan/
disimpan dalam reaktor fisi. Kami akan menggunakan48
pengurangan untuk mengubah input ASCII menjadi nilai aktual digit. Kami juga harus meningkatkan massa1
untuk menghindari pembagian dengan0
.U
di sudut kiri bawah adalah apa yang sebenarnya membuat semuanya bergerak dan awalnya hanya digunakan untuk aliran kontrol.Setelah diarahkan ke kanan, atom kontrol menyentuh
?
. Ini adalah komponen input. Itu membaca karakter dan mengatur massa atom ke nilai ASCII yang dibaca dan energi0
. Jika kita menekan EOF sebagai gantinya, energi akan disetel ke1
.Atom berlanjut dan kemudian mengenai
%
. Ini adalah sakelar cermin. Untuk energi non-positif, ini bertindak seperti/
cermin. Tetapi untuk energi positif itu bertindak seperti\
(dan juga mengurangi energi dengan 1). Jadi saat kita membaca karakter, atom akan dipantulkan ke atas dan kita dapat memproses karakter. Tetapi ketika kita selesai dengan input, atom akan dipantulkan ke bawah dan kita dapat menerapkan logika berbeda untuk mengambil hasilnya. FYI, komponen yang berlawanan adalah&
.Jadi kita punya atom yang bergerak naik untuk saat ini. Apa yang ingin kita lakukan untuk setiap karakter adalah membaca nilai digitnya, menambahkannya ke total running kami dan kemudian mengalikan total running itu dengan 10 untuk mempersiapkan digit berikutnya.
Atom karakter pertama mengenai reaktor fusi (default)
Y
. Ini membagi atom dan kami menggunakan salinan kiri sebagai atom kontrol untuk kembali ke komponen input dan membaca karakter berikutnya. Salinan yang tepat akan diproses. Pertimbangkan kasus di mana kita telah membaca karakter3
. Atom kita akan seperti itu(51,0)
. Kami bertukar massa dan energi@
, sehingga kami dapat menggunakan pengurangan reaktor fisi berikutnya. Reaktor mengurangi48
energi (tanpa mengubah massa), sehingga reaksinya mengeluarkan dua salinan(0,3)
- energi sekarang sesuai dengan digit yang telah kita baca. Salinan ke atas hanya dibuang dengan;
(komponen yang hanya menghancurkan semua atom yang masuk). Kami akan terus bekerja dengan salinan yang turun. Anda harus mengikuti jalurnya melalui/
dan\
sedikit mirror.The
@
sebelum massa reaktor fusi swap dan energi lagi, seperti yang kita akan menambahkan(3,0)
total kami berjalan diY
. Perhatikan bahwa total yang berjalan itu sendiri akan selalu memiliki0
energi.Sekarang
J
adalah lompatan. Apa yang dilakukannya adalah melompati atom yang masuk ke depan dengan energinya. Jika itu0
, atom terus bergerak lurus. Jika itu1
akan melewati satu sel, jika2
itu akan melewati dua sel dan seterusnya. Energi dihabiskan dalam lompatan, sehingga atom selalu berakhir dengan energi0
. Karena total yang berjalan memang memiliki energi nol, lompatan diabaikan untuk saat ini dan atom diarahkan ke reaktor fusi{
yang melipatgandakan massanya10
. Salinan ke bawah dibuang dengan;
sementara salinan ke atas dimasukkan kembali ke dalamY
reaktor sebagai total berjalan baru.Hal di atas terus berulang (dengan cara pipa yang lucu di mana digit baru sedang diproses sebelum yang sebelumnya dilakukan) sampai kami menekan EOF. Sekarang
%
akan mengirim atom ke bawah. Idenya adalah untuk mengubah atom ini menjadi(0,1)
sekarang sebelum memukul reaktor total yang sedang berjalan sehingga a) total tidak terpengaruh (nol massa) dan b) kita mendapatkan energi1
untuk melompati atom[
. Kita dapat dengan mudah menjaga energi dengan$
, yang meningkatkan energi.Masalahnya adalah bahwa
?
tidak me-reset massa ketika Anda menekan EOF sehingga massa masih akan menjadi karakter terakhir yang dibaca, dan energinya akan menjadi0
(karena%
dikurangi1
kembali ke0
). Jadi kami ingin menyingkirkan massa itu. Untuk melakukan itu kita bertukar massa dan energi dengan@
lagi.Saya perlu untuk memperkenalkan salah satu komponen lagi sebelum menyelesaikan bagian ini:
Z
. Ini pada dasarnya sama dengan%
atau&
. Perbedaannya adalah ia membiarkan atom-atom berenergi positif melewati (sementara mengurangi energi) dan membelokkan atom berenergi positif 90 derajat ke kiri. Kita dapat menggunakan ini untuk menghilangkan energi atom dengan memutarnya terus menerusZ
- segera setelah energi itu hilang, atom akan dibelokkan dan meninggalkan loop. Itulah pola ini:di mana atom akan bergerak ke atas begitu energinya nol. Saya akan menggunakan pola ini dalam satu bentuk atau lainnya beberapa kali di bagian lain dari program ini.
Jadi ketika atom meninggalkan loop kecil ini, itu akan
(1,0)
dan ditukar(0,1)
dengan@
sebelum memukul reaktor fusi untuk melepaskan hasil akhir dari input. Namun, total yang berjalan akan dimatikan dengan faktor 10, karena kami telah secara sementara mengalikannya dengan digit lain.Jadi sekarang dengan energi
1
, atom ini akan melewati[
dan melompat ke dalam/
. Ini membelokkannya ke dalam reaktor fisi yang telah kami siapkan untuk membagi dengan 10 dan memperbaiki multiplikasi asing kami. Sekali lagi, kita membuang satu setengah dengan;
dan menyimpan yang lain sebagai output (di sini diwakili denganO
yang hanya akan mencetak karakter yang sesuai dan menghancurkan atom - dalam program penuh kita tetap menggunakan atom sebagai gantinya).itoa
Tentu saja, kita juga perlu mengubah hasilnya kembali menjadi string dan mencetaknya. Untuk itulah bagian ini dibuat. Ini mengasumsikan bahwa input tidak tiba sebelum centang 10 atau lebih, tetapi dalam program lengkap yang mudah diberikan. Bit ini dapat ditemukan di bagian bawah program lengkap.
Kode ini memperkenalkan komponen Fisi baru yang sangat kuat: tumpukan
K
. Tumpukan awalnya kosong. Ketika sebuah atom dengan energi non-negatif mengenai tumpukan, atom hanya didorong ke tumpukan. Ketika sebuah atom dengan energi negatif mengenai tumpukan, massa dan energinya akan digantikan oleh atom di bagian atas tumpukan (yang karenanya muncul). Jika tumpukan kosong, arah atom terbalik dan energinya menjadi positif (yaitu dikalikan dengan-1
).Oke, kembali ke kode aktual. Gagasan
itoa
snipet adalah berulang kali mengambil inputo modulo 10 untuk menemukan digit berikutnya sementara integer-membagi input dengan 10 untuk iterasi berikutnya. Ini akan menghasilkan semua digit dalam urutan terbalik (dari paling tidak signifikan ke paling signifikan). Untuk memperbaiki urutan, kami mendorong semua digit ke tumpukan dan pada akhirnya mengeluarkannya satu per satu untuk mencetaknya.Bagian atas dari kode melakukan perhitungan digit: the
L
with the pluses memberikan angka 10 yang kita klonkan dan masukkan ke dalam reaktor fisi dan fusi sehingga kita dapat membaginya dan mengalikannya dengan 10. Lingkaran dasarnya dimulai setelah[
di sudut kiri atas . Nilai saat ini dibagi: satu salinan dibagi dengan 10, kemudian dikalikan dengan 10 dan disimpan dalam reaktor fisi, yang kemudian dipukul oleh salinan lain di puncak. Ini menghitungi % 10
sebagaii - ((i/10) * 10)
. Perhatikan juga bahwaA
membagi hasil antara setelah pembagian dan sebelum penggandaan, sehingga kita dapat dimasukkani / 10
ke dalam iterasi berikutnya.The
%
dibatalkan loop sekali variabel iterasi hits 0. Karena ini adalah lebih atau kurang sebuah do-while loop, kode ini akan bahkan bekerja untuk mencetak0
(tanpa menciptakan nol terkemuka sebaliknya). Setelah kami meninggalkan loop, kami ingin mengosongkan tumpukan dan mencetak digit.S
adalah kebalikan dariZ
, jadi itu adalah saklar yang akan membelokkan atom yang masuk dengan energi non-positif 90 derajat ke kanan. Jadi atom benar-benar bergerak dari tepi dariS
lurus ke keK
untuk melepaskan digit (perhatikan~
yang memastikan bahwa atom yang masuk memiliki energi-1
). Digit itu bertambah dengan48
untuk mendapatkan kode ASCII dari karakter digit yang sesuai. TheA
membagi digit untuk mencetak satu salinan dengan!
dan masukkan salinan lainnya kembali keY
reaktor untuk digit berikutnya. Salinan yang dicetak digunakan sebagai pemicu berikutnya untuk tumpukan (perhatikan bahwa cermin juga mengirimkannya ke tepian untuk memukulM
dari kiri).Ketika tumpukan kosong,
K
kehendak mencerminkan atom dan mengubah energinya menjadi+1
, sehingga melewati lurusS
.N
mencetak baris baru (hanya karena rapi :)). Dan kemudian atom berjalanR'0
lagi untuk berakhir di sisiY
. Karena tidak ada atom lebih lanjut di sekitar, ini tidak akan pernah dirilis dan program berakhir.Menghitung Angka Fisi: Kerangka Kerja
Mari kita sampai pada daging sebenarnya dari program ini. Kode ini pada dasarnya adalah port dari implementasi referensi Mathematica saya:
di mana
div
jumlah bilangan bulat di partisi maksimal.Perbedaan utama adalah bahwa kita tidak bisa berurusan dengan nilai setengah bilangan bulat di Fission jadi saya melakukan banyak hal dikalikan dua, dan tidak ada rekursi dalam Fission. Untuk mengatasinya, saya mendorong semua bilangan bulat di partisi dalam antrian untuk diproses nanti. Untuk setiap nomor yang kami proses, kami akan menambah penghitung dengan satu dan setelah antrian kosong, kami akan melepaskan penghitung dan mengirimkannya untuk dicetak. (Antrian,,
Q
berfungsi persis sepertiK
, hanya dalam urutan FIFO.)Berikut ini kerangka kerja untuk konsep ini:
Komponen baru yang paling penting adalah digit. Ini adalah teleporter. Semua teleporter dengan digit yang sama menjadi satu. Ketika sebuah atom mengenai teleporter apa pun, ia akan segera memindahkan teleporter berikutnya dalam grup yang sama, di mana selanjutnya ditentukan dalam urutan kiri-ke-kanan, atas-ke-bawah yang biasa. Ini tidak perlu, tetapi bantu tata letak (dan karenanya bermain golf sedikit). Ada juga
X
yang hanya menduplikasi atom, mengirimkan satu salinan lurus ke depan dan yang lainnya mundur.Sekarang Anda mungkin dapat memilah sebagian besar kerangka kerja sendiri. Pojok kiri atas memiliki antrian nilai yang masih harus diproses dan dirilis satu
n
per satu. Satu salinann
diteleportasi ke bawah karena kita memerlukannya ketika menghitung rentang, salinan lainnya masuk ke blok di bagian atas yang menghitungdiv
(sejauh ini merupakan bagian terbesar dari kode). Setelahdiv
dihitung, duplikat - satu salinan menambah penghitung di sudut kanan atas, yang disimpan diK
. Salinan lainnya diteleportasi ke bawah. Jikadiv
itu1
, kita menangkis ke atas segera dan menggunakannya sebagai pemicu untuk iterasi berikutnya, tanpa enqueuing nilai-nilai baru. Kalau tidak kita gunakandiv
dann
pada bagian di bagian bawah untuk menghasilkan rentang baru (yaitu aliran atom dengan massa yang sesuai yang kemudian dimasukkan ke dalam antrian), dan kemudian lepaskan pemicu baru setelah rentang telah selesai.Setelah antrian kosong, pelatuk akan dipantulkan, melewati langsung
S
dan muncul kembali di sudut kanan atas, di mana ia melepaskan penghitung (hasil akhir) dariA
, yang kemudian diteleportasikan keitoa
via8
.Menghitung Angka Fisi: Tubuh Lingkaran
Jadi yang tersisa hanyalah dua bagian untuk menghitung
div
dan menghasilkan kisaran. Komputasidiv
adalah bagian ini:Anda mungkin sudah cukup melihat sekarang untuk memecahkan masalah ini dengan kesabaran. Rincian tingkat tinggi adalah ini: 12 kolom pertama atau lebih menghasilkan aliran pembagi
2n
. 10 kolom berikutnya menyaring yang tidak memuaskanOddQ@# == IntegerQ[n/#]
. 8 kolom berikutnya menyaring yang tidak memuaskann/# > (# - 1)/2)
. Akhirnya kami mendorong semua pembagi yang valid pada tumpukan, dan setelah selesai kami mengosongkan seluruh tumpukan menjadi reaktor fusi (menimpa semua kecuali pembagi terbesar / terbesar) dan kemudian melepaskan hasilnya, diikuti dengan menghilangkan energinya (yang tidak -zero dari memeriksa ketimpangan).Ada banyak jalan gila di sana yang tidak benar-benar melakukan apa pun. Secara dominan,
\/\/\/\/
kegilaan di atas (5
s juga merupakan bagian dari itu) dan satu jalan di sekitar bawah (yang melewati7
s). Saya harus menambahkan ini untuk menghadapi beberapa kondisi balapan yang tidak menyenangkan. Fisi dapat menggunakan komponen penundaan ...Kode yang menghasilkan rentang baru dari
n
dandiv
adalah ini:Kami pertama kali menghitung
n/div - (div + 1)/2
(keduanya istilah lantai, yang menghasilkan hasil yang sama) dan menyimpan untuk nanti. Kemudian kami menghasilkan rentang daridiv
bawah ke1
dan menambahkan nilai yang tersimpan ke masing-masing.Ada dua pola umum baru dalam kedua hal ini, yang harus saya sebutkan: Satu adalah
SX
atauZX
tekan dari bawah (atau versi yang diputar). Ini adalah cara yang baik untuk menduplikasi atom jika Anda ingin satu salinan berjalan lurus (karena mengarahkan output dari reaktor fusi kadang-kadang bisa rumit). TheS
atauZ
berputar atom ke dalamX
dan kemudian berputar salinan kembali cermin ke arah asli propagasi.Pola lainnya adalah
Jika kita menyimpan nilai apa pun di dalam,
K
kita dapat mengambilnya berulang kali dengan memukulK
dengan energi negatif dari atas. TheA
duplikat nilai kita tertarik dan mengirimkan apa yang menyalin kembali tepat ke stack untuk waktu berikutnya kita membutuhkannya.Yah, itu cukup tebal ... tetapi jika Anda benar-benar berhasil melewati ini, saya harap Anda mendapat gagasan bahwa Fission i͝s̢̘̗̗ ͢i̟nç̮̩r̸̭̬̱͔e̟̹̟̜͟d̙i̠͙͎̖͓̯b̘̠͎̭̰̼l̶̪̙̮̥̮y̠̠͎̺͜ ͚̬̮f̟͞u̱̦̰͍n͍ ̜̠̙t̸̳̩̝o ̫͉̙͠p̯̱̭͙̜͙͞ŕ̮͓̜o̢̙̣̭g̩̼̣̝r̤͍͔̘̟ͅa̪̜͇m̳̭͔̤̞ͅ ͕̺͉̫̀ͅi͜n̳̯̗̳͇̹.̫̞̲̞̜̳
sumber
Now with 100% fewer scrollbars.
jadi katamu .. dan masih akan dilanjutkan ...CJam,
4241 byteTraversal pertama Breadth sederhana dan kondisi berhenti kosong tingkat berikutnya.
Cara kerjanya :
Cobalah online di sini
sumber
Python 3, 112 byte
4 byte disimpan berkat @FryAmTheEggman.
Penjelasan akan datang nanti ...
Fakta bonus: Setiap kekuatan 2 memiliki angka Fisi 1. Ini karena jumlah dari urutan panjang genap selalu merupakan jumlah dari dua angka tengah, yang ganjil, dikalikan dengan setengah panjang urutan, yang merupakan bilangan bulat . Jumlah dari urutan panjang ganjil adalah angka tengah dikalikan dengan panjang urutan, yang ganjil. Jadi karena kekuatan 2 tidak memiliki pembagi ganjil itu hanya dapat dinyatakan sebagai jumlah itu sendiri.
sumber
Python 2,
11110297 byteDapat dibaca:
Tidak terlalu mudah dibaca:
Keduanya 97 byte.
b
adalahn
minus(a-1)th
bilangan segitiga. Jikab % a == 0
, makan
jumlaha
angka berurutan dimulai darib
.sumber
1else
. Hanya solusi kedua yang berfungsi. Tidak sampai Python 3 yangelse
dapat segera mengikuti angka.Python 2, 86
Kurang bermain golf:
Idenya adalah untuk menguji potensi menjalankan bilangan bulat berturut-turut yang dijumlahkan
n
. Proses disimpan langsung secara langsung sebagai setR
daripada melalui titik akhir.Kami memeriksa bagaimana jumlah putaran saat ini dibandingkan dengan jumlah yang diinginkan
n
melalui perbedaannya.f
ke jalankan, menjumlahkan, dan menambahkan 1 untuk node saat ini. Jika prosesnya berjalan{n}
, kami telah mencoba semua jumlah yang tidak sepele, hentikan rekursi dengan menghapusn
terlebih dahulu.Terima kasih kepada Sp3000 untuk menghemat 3 karakter.
sumber
Python 2, 85
Saya sangat bangga dengan jawaban ini karena sudah membutuhkan puluhan detik untuk n = 9, dan 5-10 menit untuk n = 10. Dalam kode golf ini dianggap atribut yang diinginkan dari suatu program.
Ada juga versi hubungan arus pendek yang tidak memakan waktu lama dan menggunakan jumlah byte yang sama:
Ini mungkin lebih cepat, tetapi setidaknya itu melebihi batas rekursi default begitu n berjalan sedikit di atas 40.
Idenya adalah untuk melakukan pencarian brute force untuk angka
a
dand
sedemikian rupa sehinggaa + a+1 + ... + a+d == n
, pada nilai antara 1 dann
. Thef(n,a+d/n,d%n+1)
cabang rekursi loop melalui(a, d)
pasang. Dalam hal kesetaraan terpenuhi, saya berhasil menghindarimap(range(...))
panggilan mahal dengan memecah menjadi hanya dua cabang terlepas dari berapa lama urutannya. Angka-angkaa+1
melaluid
disatukan menjadi satu panggilanf
dengan mengatura
parameter sehingga cara berbeda untuk membagi urutan tidak dapat digunakan.sumber
Haskell,
7669 bytePemakaian:
Bagaimana itu bekerja:
sumber
Retina , 66 byte
Mengambil input dan mencetak output secara unary.
Anda dapat menempatkan setiap baris dalam satu file atau menjalankan kode seperti pada
-s
bendera. Misalnya:Penjelasan:
1
dan mengkonversi sisanya ke1
.Status string sepanjang proses dengan input
11111111111111 (unary 14)
:Banyak terima kasih atas @MartinButtner atas bantuan dalam obrolan!
sumber
CJam (43 byte)
Demo online
Saya yakin bahwa saya kehilangan beberapa trik dengan loop lanjutan, tetapi ini benar-benar mengeksploitasi properti CJam (yang sebelumnya telah mengganggu saya) bahwa di dalam
%
peta hasilnya tetap di stack, dan karenanya dapat diakses menggunakan$
dengan offset negatif.sumber
,
di awal./
dan%
dan beberapa lainnya secara implisit mengubah angka menjadi rentang.,_m*
dapat diganti dengan2m*
. Formula perkembangan aritmatika dapat diganti dengan~,>:Y_,+:+
dan~\,>0\
menjadi!Y
. Akhirnya, jika Anda menggunakan{}#
bukan{}=
, Anda tidak perlu)
setelahnyaX
. Menyatukan semuanya:ri{):X2m*{~,>:Y_,+:+X=}#!Y{~$+}/)}%W=
Pergi, 133 byte
Ini adalah kode golf pertama saya, maaf jika saya melakukan kesalahan.
Ini menggunakan gagasan bahwa "komposisi" fisil juga dapat dilihat sebagai perbedaan antara dua urutan bilangan bulat yang dipesan. Misalnya ambil "komposisi" fisil untuk angka 13. Ini adalah 6,7. Tetapi dapat dilihat sebagai jumlah bilangan bulat 1 ... 7 minus jumlah bilangan bulat 1 ... 5
Ingat rumus dari masa sekolah Gauss, jumlah 1 ... n = (n ^ 2 + n) / 2. Jadi untuk menemukan komposisi bilangan bulat berurutan untuk n yang diberikan, kita juga bisa mengatakan, kita mencari 'titik akhir' p dan q di sepanjang rentang 1 ... n sehingga (p ^ 2 + p) / 2 - ( q ^ 2 + q) / 2 = n. Dalam contoh di atas, kita akan mencari 'titik akhir' 5 dan 7 karena 7 ^ 2 + 7 = 56/2, 5 ^ 2 + 5 = 30/2, 56 / 2-30 / 2 = 28-15 = 13.
Sekarang ada beberapa cara yang mungkin untuk menyusun-menyusun angka, seperti yang dicatat Martin 9 = 2 + 3 + 4 tetapi juga 4 + 5. Tetapi tampaknya jelas bahwa urutan awal "terendah" juga akan menjadi yang terpanjang, karena dibutuhkan lebih banyak jumlah kecil untuk dijumlahkan ke angka besar daripada angka menengah. (Sayangnya saya tidak punya bukti)
Jadi untuk menemukan komposisi 9, uji setiap 'pasangan titik akhir', p dan q, iterasi p dan q secara terpisah dari 0 hingga 9, dan uji jika p ^ p + p / 2 - q ^ 2 + q / 2 = 9. Atau, lebih sederhana, kalikan persamaan dengan 2, untuk menghindari masalah pembagian pembulatan dan menyimpan semua matematika dalam bilangan bulat. Kemudian kita mencari p dan q sedemikian rupa sehingga (p ^ p + p) - (q ^ q + q) = 9 * 2. Pencocokan pertama yang kami temukan adalah titik akhir komposisi Fissile karena, sebagaimana disebutkan, kelompok angka terendah juga akan menjadi yang terpanjang, dan kami mencari dari rendah ke tinggi (0 hingga 9). Kami keluar dari lingkaran segera setelah kami menemukan kecocokan.
Sekarang fungsi rekursif menemukan 'titik akhir fisil' p dan q untuk n yang diberikan, lalu mengingat-sendiri untuk masing-masing 'anak' di pohon dari p ke q. Untuk 9, ia akan menemukan 1 dan 4, (20-2 = 18) maka ia akan memanggil kembali dirinya sendiri pada 2, 3, dan 4, menjumlahkan hasilnya. Untuk angka seperti 4 itu tidak pernah menemukan kecocokan, dan karenanya mengembalikan '1'. Ini mungkin bisa diperpendek tetapi ini seperti program go ketiga saya, dan saya bukan ahli rekursi.
Terima kasih sudah membaca.
sumber
CJam,
403533 byteTerima kasih kepada @Optimizer untuk menyarankan
few
, yang menghemat 2 byte.Cobalah online di juru bahasa CJam .
Bagaimana itu bekerja
sumber
ri{_,:)_few:+W%{1b1$=}=|{F}*}:F~],