Angka fisil

47

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 24menjadi 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 9sebagai 4 + 5, tetapi 2 + 3 + 4memiliki lebih banyak komponen. The Fisi jumlah dari Nsekarang didefinisikan sebagai jumlah bilangan bulat yang diperoleh dalam proses ini, termasuk Ndirinya 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 0terdaftar 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?

Martin Ender
sumber
Saya perhatikan bahwa OEIS tampaknya memiliki kesalahan pada n = 34: mulai dari n = 32, ia (saat ini) mendaftar 1, 22, 22, 23, 24, 31, daripada 1, 22, 20, 23, 24, 31.
mathmandan
1
@mathmandan tangkapan bagus, saya mungkin akan mengusulkan koreksi (bersama dengan diagram pertama).
Martin Ender
Tantangan terkait: codegolf.stackexchange.com/questions/5703/… (dan pertanyaan yang sama tentang math.SE: math.stackexchange.com/questions/139842/… )
Ilmari Karonen
@mathmandan FYI, saya telah memperbaiki urutan dan contohnya sekarang, dan juga menambahkan implementasi referensi saya dan ketentuan 10k pertama.
Martin Ender
Kelihatan bagus! Terima kasih untuk pekerjaan anda!
mathmandan

Jawaban:

16

Pyth, 23 22 21 byte

Lh&lJfqbsT.:tUb)syMeJ

Ini mendefinisikan fungsi rekursif y. Cobalah online: Demonstrasi

Penjelasan:

L                      define a function y(b): return ...
            tUb          the list [1, 2, ..., b-1]
          .:   )         generate all consecutive sub-sequences
     f                   filter for sub-sequences T, which satisfy:
      qbsT                   b == sum(T)
    J                    and store them in J

                         return 
   lJ                        len(J)
  &                        and (if len(J) == 0 then 0 else ...)
                    eJ       last element of J (=longest sub-sequence) 
                  yM         recursive calls for all these numbers
                 s           sum
 h                         incremented by one (counting the current node)
Jakube
sumber
52

Fission , 1328 989 887 797 byte

Jawaban 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:

 R'0@+\
/  Y@</ /[@ Y]_L
[? % \  / \ J
   \$@  [Z/;[{+++++++++L
UR+++++++++>/;
9\   ;    7A9
SQS  {+L  /$     \/\/\/\/\/   5/ @  [~ &@[S\/ \  D /8/
~4X /A@[  %5                   /; &    K  } [S//~KSA /
  3    \  A$@S  S\/  \/\/\/   \/>\ /S]@A  /  \ { +X
W7           X  X    /> \      +\ A\ /   \ /6~@/ \/
        /   ~A\;     +;\      /@
    ZX [K    / {/  / @  @ }  \ X @
       \AS   </      \V /    }SZS S/
         X   ;;@\   /;X  /> \ ; X X
 ;       \@+  >/ }$S SZS\+;    //\V
           / \\  /\; X X @  @  \~K{
           \0X /     /~/V\V /   0W//
    \        Z      [K \  //\
W       /MJ $$\\ /\7\A  /;7/\/ /
       4}K~@\ &]    @\  3/\
 /     \{   }$A/1 2  }Y~K <\
[{/\  ;@\@  /   \@<+@^   1;}++@S68
@\ <\    2        ;   \    /
$  ;}++ +++++++L
%@A{/
M  \@+>/
~     @
SNR'0YK
  \  A!/

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 911 581 461 374 spasi).

Sebelum kita sampai pada penjelasan, catatan tentang pengujian ini: penerjemah resmi tidak sepenuhnya berfungsi sebagaimana mestinya. a) Mirror.cpptidak 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 bahasa

g++ -g --std=c++11 *.cpp -o Fission

Fakta 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 komponen UDLR(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 atoikodenya:

     ;
 R'0@+\
/  Y@</ /[@ Y]_L
[? % \  / \ J 
   \$@  [Z/;[{+++++++++L
UR+++++++++>/;
           O

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 menggunakan Ydan {). 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 adalah M(turun) dan W(atas) tetapi mereka tidak digunakan untuk atoikode. UDLRjuga bertindak WM][setelah melepaskan atom awal mereka.

Pokoknya, mari kita lihat kode di sana. Program dimulai dengan 5 atom:

  • The Rdan Ldi 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.
  • Yang Ldi sudut kanan atas mendapat massa dikurangi (dengan _) menjadi (0,0)dan disimpan di samping reaktor fusi Y. Ini untuk melacak angka yang kita baca - kita akan secara bertahap meningkatkan dan melipatgandakannya ketika kita membaca angka.
  • Di Rsudut kiri atas massa diatur ke kode karakter 0(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 menggunakan 48pengurangan untuk mengubah input ASCII menjadi nilai aktual digit. Kami juga harus meningkatkan massa 1untuk menghindari pembagian dengan 0.
  • Akhirnya, Udi 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 energi 0. Jika kita menekan EOF sebagai gantinya, energi akan disetel ke 1.

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 karakter 3. Atom kita akan seperti itu (51,0). Kami bertukar massa dan energi @, sehingga kami dapat menggunakan pengurangan reaktor fisi berikutnya. Reaktor mengurangi 48energi (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 di Y. Perhatikan bahwa total yang berjalan itu sendiri akan selalu memiliki 0energi.

Sekarang Jadalah lompatan. Apa yang dilakukannya adalah melompati atom yang masuk ke depan dengan energinya. Jika itu 0, atom terus bergerak lurus. Jika itu 1akan melewati satu sel, jika 2itu akan melewati dua sel dan seterusnya. Energi dihabiskan dalam lompatan, sehingga atom selalu berakhir dengan energi 0. Karena total yang berjalan memang memiliki energi nol, lompatan diabaikan untuk saat ini dan atom diarahkan ke reaktor fusi {yang melipatgandakan massanya 10. Salinan ke bawah dibuang dengan ;sementara salinan ke atas dimasukkan kembali ke dalam Yreaktor 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 energi 1untuk 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 menjadi 0(karena %dikurangi 1kembali ke 0). 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 menerus Z- segera setelah energi itu hilang, atom akan dibelokkan dan meninggalkan loop. Itulah pola ini:

/ \
[Z/

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 dengan Oyang hanya akan mencetak karakter yang sesuai dan menghancurkan atom - dalam program penuh kita tetap menggunakan atom sebagai gantinya).

itoa

           /     \
input ->  [{/\  ;@
          @\ <\   
          $  ;}++ +++++++L
          %@A{/
          M  \@+>/
          ~     @
          SNR'0YK
            \  A!/

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 itoasnipet 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 Lwith 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 menghitung i % 10sebagai i - ((i/10) * 10). Perhatikan juga bahwa Amembagi hasil antara setelah pembagian dan sebelum penggandaan, sehingga kita dapat dimasukkan i / 10ke 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 mencetak 0(tanpa menciptakan nol terkemuka sebaliknya). Setelah kami meninggalkan loop, kami ingin mengosongkan tumpukan dan mencetak digit. Sadalah kebalikan dari Z, 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 dari Slurus ke ke Kuntuk melepaskan digit (perhatikan ~yang memastikan bahwa atom yang masuk memiliki energi -1). Digit itu bertambah dengan 48untuk mendapatkan kode ASCII dari karakter digit yang sesuai. The Amembagi digit untuk mencetak satu salinan dengan!dan masukkan salinan lainnya kembali ke Yreaktor untuk digit berikutnya. Salinan yang dicetak digunakan sebagai pemicu berikutnya untuk tumpukan (perhatikan bahwa cermin juga mengirimkannya ke tepian untuk memukul Mdari kiri).

Ketika tumpukan kosong, Kkehendak mencerminkan atom dan mengubah energinya menjadi +1, sehingga melewati lurus S. Nmencetak baris baru (hanya karena rapi :)). Dan kemudian atom berjalan R'0lagi untuk berakhir di sisi Y. 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:

fission[n_] := If[
  (div = 
    SelectFirst[
      Reverse@Divisors[2 n], 
      (OddQ@# == IntegerQ[n/#] 
       && n/# > (# - 1)/2) &
    ]
  ) == 1,
  1,
  1 + Total[fission /@ (Range@div + n/div - (div + 1)/2)]
]

di mana divjumlah 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,, Qberfungsi persis seperti K, hanya dalam urutan FIFO.)

Berikut ini kerangka kerja untuk konsep ini:

                      +--- input goes in here
                      v 

                     SQS ---> compute div from n          D /8/
                     ~4X               |                /~KSA /
                       3               +----------->    { +X
initial trigger ---> W                               6~@/ \/
                              4                   
                     W        ^                     /
                              |              3
                     ^     generate range    |
                     |     from n and div  <-+----- S6
                     |         -then-      
                     +---- release new trigger

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 Xyang 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 nper satu. Satu salinan nditeleportasi ke bawah karena kita memerlukannya ketika menghitung rentang, salinan lainnya masuk ke blok di bagian atas yang menghitung div(sejauh ini merupakan bagian terbesar dari kode). Setelah divdihitung, duplikat - satu salinan menambah penghitung di sudut kanan atas, yang disimpan di K. Salinan lainnya diteleportasi ke bawah. Jika divitu 1, kita menangkis ke atas segera dan menggunakannya sebagai pemicu untuk iterasi berikutnya, tanpa enqueuing nilai-nilai baru. Kalau tidak kita gunakan divdann 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 Sdan muncul kembali di sudut kanan atas, di mana ia melepaskan penghitung (hasil akhir) dari A, yang kemudian diteleportasikan ke itoavia 8.

Menghitung Angka Fisi: Tubuh Lingkaran

Jadi yang tersisa hanyalah dua bagian untuk menghitung divdan menghasilkan kisaran. Komputasi divadalah bagian ini:

 ;    
 {+L  /$     \/\/\/\/\/   5/ @  [~ &@[S\/ \
/A@[  %5                   /; &    K  } [S/
   \  A$@S  S\/  \/\/\/   \/>\ /S]@A  /  \ 
         X  X    /> \      +\ A\ /   \ /
    /   ~A\;     +;\      /@
ZX [K    / {/  / @  @ }  \ X @
   \AS   </      \V /    }SZS S/
     X   ;;@\   /;X  /> \ ; X X
     \@+  >/ }$S SZS\+;    //\V
       / \\  /\; X X @  @  \~K{
       \0X /     /~/V\V /   0W//
\        Z      [K \  //\
           \ /\7\A  /;7/\/

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 memuaskan OddQ@# == IntegerQ[n/#]. 8 kolom berikutnya menyaring yang tidak memuaskan n/# > (# - 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 ( 5s juga merupakan bagian dari itu) dan satu jalan di sekitar bawah (yang melewati 7s). Saya harus menambahkan ini untuk menghadapi beberapa kondisi balapan yang tidak menyenangkan. Fisi dapat menggunakan komponen penundaan ...

Kode yang menghasilkan rentang baru dari ndan divadalah ini:

 /MJ $$\
4}K~@\ &]    @\  3/\
\{   }$A/1 2  }Y~K <\
 \@  /   \@<+@^   1;}++@
  2        ;   \    /

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 dari divbawah ke 1dan menambahkan nilai yang tersimpan ke masing-masing.

Ada dua pola umum baru dalam kedua hal ini, yang harus saya sebutkan: Satu adalah SXatau ZXtekan 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). The Satau Zberputar atom ke dalam Xdan kemudian berputar salinan kembali cermin ke arah asli propagasi.

Pola lainnya adalah

[K
\A --> output

Jika kita menyimpan nilai apa pun di dalam, Kkita dapat mengambilnya berulang kali dengan memukul Kdengan energi negatif dari atas. The Aduplikat 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̳̯̗̳͇̹.̫̞̲̞̜̳

Martin Ender
sumber
1
Now with 100% fewer scrollbars.jadi katamu .. dan masih akan dilanjutkan ...
Pengoptimal
13
Masih lebih mudah dibaca daripada kebanyakan kode pengembang junior kami.
corsiKa
Sebagai pencipta Fission, bahkan saya belum menulis program sebesar itu! Saya terkesan! Penjelasan Anda sangat spektakuler dan pasti bisa berfungsi sebagai tutorial untuk bahasa tersebut.
C0deH4cker
Juga, baris terakhir dari jawaban Anda agak terlihat seperti program Fission;)
C0deH4cker
12

CJam, 42 41 byte

ri]{_{:X,:)_few:+W%{1bX=}=}%{,(},e_}h]e_,

Traversal pertama Breadth sederhana dan kondisi berhenti kosong tingkat berikutnya.

Cara kerjanya :

ri]                                       e# This represents the root of the fissile tree
   {                               }h     e# Now we run a do-while loop
    _{                    }%              e# Copy the nodes at the current level and map them
                                          e# via this code block to get next level nodes
      :X,:)                               e# Store the node value in X and get array [1..X]
           _few                           e# Copy the array and get continuous slices of
                                          e# length 1 through X from the array [1..X]
               :+W%                       e# Right now, we have an array of array with each
                                          e# array containing slice of same length. We join
                                          e# those arrays and reverse them to get slices of
                                          e# higher length in front of lower lengths
                   {1bX=}=                e# Choose the first slice whose sum is same as X
                                          e# The reversal above makes sure that we give
                                          e# preference to slice of higher length in case of
                                          e# multiple slices add up to X
                            {,(},         e# Filter out slices of length 1 which basically
                                          e# mean that the current node cannot be split up
                                 e_       e# Join all slices in a single array. This is our
                                          e# next level in the Fissile tree. If this is empty
                                          e# it means that all no further node can be
                                          e# decomposed. In an {}h do-while loop, this fact
                                          e# itself becomes the stopping condition for the
                                          e# loop
                                     ]e_, e# Wrap all levels in an array. Flatten the array
                                          e# and take its length

Cobalah online di sini

Pengoptimal
sumber
Ini mungkin bisa di-golf hingga sekitar 35 byte. Saya mencoba mencari tahu caranya ..
Pengoptimal
10

Python 3, 112 byte

def f(n,c=0):
 d=n-c;s=(n-d*~-d/2)/d
 return(s%1or s<1)and f(n,c+1)or+(d<2)or-~sum(f(int(s)+i)for i in range(d))

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.

randomra
sumber
2 + 3 + 4 + 5 = 14 yang tidak aneh. Argumen Anda untuk deret panjang genap harus diubah menjadi "jumlah deret panjang genap adalah jumlah dari dua angka tengah, yang ganjil, dikalikan dengan setengah panjangnya". Sisa pernyataan Anda tidak terpengaruh.
Bruno Le Floch
@BrunoLeFloch Terima kasih! Dikoreksi.
randomra
Bukankah seharusnya judul Anda mencerminkan perbaikan? yaitu <strike> 117 </strike> <strike> 113 </strike> 112
corsiKa
@corsiKa Saya biasanya hanya melakukan itu untuk peningkatan besar. Akan ada terlalu banyak nomor yang dicoret.
randomra
8

Python 2, 111 102 97 byte

Dapat dibaca:

def f(n,c=0):a=n-c;b=n-a*~-a/2;return 1/a or-~sum(map(f,range(b/a,b/a+a)))if b>b%a<1else f(n,c+1)

Tidak terlalu mudah dibaca:

def f(n,a=0):b=n-a*~-a/2;return b>0and(f(n,a+1)or b%a<1and(1/a or-~sum(map(f,range(b/a,b/a+a)))))

Keduanya 97 byte.

badalah nminus (a-1)thbilangan segitiga. Jika b % a == 0, maka njumlah aangka berurutan dimulai dari b.

Sp3000
sumber
8
Saya dulu menganggap Python sebagai bahasa yang bisa dibaca sampai saya bergabung dengan PPCG.
Alex A.
Saya pikir Anda perlu meningkatkan definisi Anda yang dapat dibaca ..: P
Optimizer
Python 2 tidak memungkinkan 1else. Hanya solusi kedua yang berfungsi. Tidak sampai Python 3 yang elsedapat segera mengikuti angka.
mbomb007
@ mbomb007 Setahu saya ini bekerja dengan baik dari 2.7.8 dan seterusnya
Sp3000
Ok, saya menggunakan 2.7.2.
mbomb007
7

Python 2, 86

f=lambda n,R={1}:n-sum(R)and f(n,R^{[min(R),max(R)+1][n>sum(R)]})or-~sum(map(f,R-{n}))

Kurang bermain golf:

def f(n,R={1}):
    d=sum(R)-n
    if d==0:return (sum(map(f,R-{n}))
    if d<0:return f(n,R|{max(R)+1})
    if d>0:return f(n,R-{min(R)})

Idenya adalah untuk menguji potensi menjalankan bilangan bulat berturut-turut yang dijumlahkan n. Proses disimpan langsung secara langsung sebagai set Rdaripada melalui titik akhir.

Kami memeriksa bagaimana jumlah putaran saat ini dibandingkan dengan jumlah yang diinginkan nmelalui perbedaannya.

  • Jika jumlahnya terlalu besar, kami memotong elemen terkecil dalam proses.
  • Jika jumlahnya terlalu kecil, kami memperpanjang proses dengan membuat maksnya lebih besar sebesar 1.
  • Jika jumlahnya benar, kita berulang, memetakan fke jalankan, menjumlahkan, dan menambahkan 1 untuk node saat ini. Jika prosesnya berjalan {n}, kami telah mencoba semua jumlah yang tidak sepele, hentikan rekursi dengan menghapus nterlebih dahulu.

Terima kasih kepada Sp3000 untuk menghemat 3 karakter.

Tidak
sumber
7

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.

f=lambda n,a=1,d=1:a/n or[f(a)+f(n-a,1+1%d*a)+1/d,f(n,a+d/n,d%n+1)][2*n!=-~d*(2*a+d)]

Ada juga versi hubungan arus pendek yang tidak memakan waktu lama dan menggunakan jumlah byte yang sama:

f=lambda n,a=1,d=1:a/n or~d*(2*a+d)+n*2and f(n,a+d/n,d%n+1)or f(a)+f(n-a,1+1%d*a)+1/d 

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 adan dsedemikian rupa sehingga a + a+1 + ... + a+d == n, pada nilai antara 1 dan n. The f(n,a+d/n,d%n+1)cabang rekursi loop melalui (a, d)pasang. Dalam hal kesetaraan terpenuhi, saya berhasil menghindari map(range(...))panggilan mahal dengan memecah menjadi hanya dua cabang terlepas dari berapa lama urutannya. Angka-angka a+1melalui ddisatukan menjadi satu panggilan fdengan mengatur aparameter sehingga cara berbeda untuk membagi urutan tidak dapat digunakan.

feersum
sumber
Bagaimana cara kerjanya?
xnor
"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 sebagai atribut yang diinginkan dari suatu program." Memberi +1 hanya untuk itu.
Soham Chowdhury
6

Haskell, 76 69 byte

f x=head$[1+sum(map f[y..z])|y<-[1..x-1],z<-[y..x],sum[y..z]==x]++[1]

Pemakaian:

*Main> map f [1..40]
[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]

Bagaimana itu bekerja:

[  [y..z] |y<-[1..x-1],z<-[y..x],sum[y..z]==x]

           make a list of lists with all consecutive integers (at least 2 elements)
           that sum up to x, sorted by lowest number, e.g. 9 -> [[2,3,4],[4,5]].

1+sum(map f[...]) 

           recursively calculate the Fission Number for each list

[...]++[1]

           always append the 1 to the list of Fission Numbers.

head

           take the first element, which is either the Fission Number of the
           longest list or if there's no list, the 1 appended in the step before.  
nimi
sumber
3

Retina , 66 byte

^|$
,
(`,(1+?)(?=(?<1>1\1)+\D)
$0;
+)`,(1*);1\1
,$1,1$1;
^,|1

.
1

Mengambil input dan mencetak output secara unary.

Anda dapat menempatkan setiap baris dalam satu file atau menjalankan kode seperti pada -sbendera. Misalnya:

> echo -n 1111111|retina -s fission
11111

Penjelasan:

  • Kami menyimpan daftar nomor yang dipisahkan koma untuk dibagikan.
  • Untuk setiap angka, kami mengambil nilai awal terkecil yang dapat membuat pemisahan yang valid dan membatasi dari yang lain dengan titik koma.
  • Jika ada tanda titik koma di dalam bilangan, kami mengubahnya menjadi koma dan membatasi bagian berikutnya yang berukuran tepat (panjang elemen sebelumnya + 1).
  • Kami ulangi langkah 2 dan 3 hingga perubahan terjadi.
  • Kami mendapatkan koma untuk setiap daun dan titik koma untuk setiap simpul bagian dalam ditambah koma tambahan karena kami mulai dengan dua koma. Jadi kami menghapus koma dan bagian angka ' 1dan mengkonversi sisanya ke 1.

Status string sepanjang proses dengan input 11111111111111 (unary 14):

,11111111111111,
,11;111111111111,
,11,1;11,1111,11;111;,
,11,1,11;,1111,11,1;11;;,
,11,1,11;,1111,11,1,11;;;,
,,;,,,,;;;,
11111111111

Banyak terima kasih atas @MartinButtner atas bantuan dalam obrolan!

randomra
sumber
3

CJam (43 byte)

qi,{):X),_m*{{_)*2/}/-X=}=~\,>0\{~$+}/)}%W=

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.

Peter Taylor
sumber
Saya akan melihat lebih dekat besok, tetapi untuk permulaan Anda tidak perlu ,di awal. /dan %dan beberapa lainnya secara implisit mengubah angka menjadi rentang.
Martin Ender
,_m*dapat diganti dengan 2m*. Formula perkembangan aritmatika dapat diganti dengan ~,>:Y_,+:+dan ~\,>0\ menjadi !Y. Akhirnya, jika Anda menggunakan {}#bukan {}=, Anda tidak perlu )setelahnya X. Menyatukan semuanya:ri{):X2m*{~,>:Y_,+:+X=}#!Y{~$+}/)}%W=
Dennis
2

Pergi, 133 byte

func 算(n int)int{Σ:=1;for i:=0;i<n;i++{for j:=0;j<n;j++{if i*i+i-j*j-j==2*n{for k:=j+1;k<=i;k++{Σ+=算(k)};j,i=n,n}}};return Σ}

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

  A: 1 2 3 4 5 6 7  sum = 28
  B: 1 2 3 4 5      sum = 15 
A-B:           6 7  sum = 13, which is also 28-15 = 13

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.

jangan cerah
sumber
Kerja bagus! Tapi mengapa fungsi Unicode / nama variabel. Itu biaya byte yang tidak perlu dan tentunya Anda bisa saja menggunakan beberapa huruf normal?
Martin Ender
Terima kasih atas komentar baiknya. Tapi saya bertanya pada diri sendiri, mengapa tidak menghitung karakter alih-alih byte :)
don bright
Karena itulah aturan baku di sekitar sini. :) Alasan kita biasanya menghitung byte dan bukan karakter karena jika tidak ini terjadi , yang sedikit menyenangkan untuk semua pihak yang terlibat. ;) (Yang mengatakan, setiap penulis tantangan adalah bebas untuk menentukan penghitungan oleh karakter bukan byte, tapi saya secara khusus tidak).
Martin Ender
1

CJam, 40 35 33 byte

ri{__,f-_few:+{1b1$=}=|{F}*}:F~],

Terima kasih kepada @Optimizer untuk menyarankan few, yang menghemat 2 byte.

Cobalah online di juru bahasa CJam .

Bagaimana itu bekerja

ri      e# Read an integer from STDIN.
{       e# Define function F(X):
  _     e# Push X.
  _,    e# Push [0 ... X-1].
  f-    e# Subract each from X. Pushes Y := [X ... 1].
  _few  e# Push all overlapping slices of Y of length in Y.
  :+    e# Consolidate the slices of different lenghts in a single array.
  {     e# Find the first slice S such that...
    1b  e#   the sum of its elements...
    1$= e#   equals X.
  }=    e#   Since Y is in descending order, the first matching slice is also the longest.
  |     e# Set union with [X]. This adds X to the beginning of the S if S != [X].
  {F}*  e# Execute F for each element of S except the first (X).
}:F     e#
~       e# Execute F for the input.
],      e# Count the integers on the stack.
Dennis
sumber
Jika Anda menggabungkan paruh pertama saya dengan babak kedua Anda, Anda mendapatkan 34:ri{_,:)_few:+W%{1b1$=}=|{F}*}:F~],
Pengoptimal
@Optimizer: Bagus. Itu memungkinkan peningkatan tambahan. Terima kasih!
Dennis