Catatan, tantangan disalin dari pertanyaan yang diajukan di math.stackexchange .

Baru-baru ini, saya memperoleh keterampilan meniup gelembung. Pada awalnya saya akan meniup gelembung seperti ini:

Tapi kemudian semuanya mulai menjadi aneh:

Setelah beberapa saat, saya meniup beberapa gelembung aneh:

Setelah meniup ratusan, bahkan mungkin ribuan gelembung seperti itu, dahiku tiba-tiba berkerut dengan pertanyaan: Diberi gelembung, berapa banyak cara yang berbeda yang bisa Anda lakukan? Misalnya jika n = 1, hanya ada 1 pengaturan. Jika n = 2, ada 2 pengaturan. Jika n = 3, ada 4 pengaturan. Jika n = 4, ada 9 pengaturan.

Berikut adalah 9 pengaturan dari 4 gelembung:

Setelah meniup semua gelembung yang luar biasa ini, saya memutuskan bahwa saya harus berbagi kesenangan menghitung pengaturan mereka dengan Anda. Jadi, inilah tugas Anda:

Tujuan

Tulis program, fungsi, atau sejenisnya yang menghitung jumlah cara Anda dapat mengatur ngelembung.

Memasukkan

n, jumlah gelembung. n> 0

Keluaran

Jumlah cara Anda dapat mengatur gelembung ini.

Kriteria Menang

Akan sangat keren jika kita bisa meledakkan gelembung di sekitar kode Anda. Semakin kecil Anda membuat kode, semakin mudah melakukannya. Jadi orang yang membuat kode dengan jumlah byte terkecil akan memenangkan kontes.

Informasi tambahan

OEIS

Python 2, 92 87 byte

a=lambda n:n<2or sum((k%d<1)*d*a(d)*a(n-k)for k in range(1,n)for d in range(1,1+k))/~-n

Dalam bahasa Inggris sederhana: untuk menghitung a(n)kami menghitung d*a(d)*a(n-k)untuk setiap pembagi dsetiap bilangan bulat positif klebih kecil dari atau sama dengan n, jumlah semua ini, dan bagi dengan n-1.

Untuk membuatnya berjalan lebih cepat, jalankan di Python 3 (ganti /dengan //dalam fungsi di atas) dan memo:

import functools
a = functools.lru_cache(None)(a)

Jika Anda melakukan ini, itu menghitung a(50) = 425976989835141038353langsung.

GNU Prolog, 98 byte

b(x,0,x).
b(T/H,N,H):-N#=A+B+1,b(H,A,_),b(T,B,J),H@>=J.
c(X,Y):-findall(A,b(A,X,_),L),length(L,Y).

Jawaban ini adalah contoh yang bagus tentang bagaimana Prolog dapat berjuang dengan format I / O yang paling sederhana. Ia bekerja dengan gaya Prolog yang sebenarnya melalui menjelaskan masalah, dan bukan algoritma untuk menyelesaikannya: ia menentukan apa yang dianggap sebagai pengaturan gelembung legal, meminta Prolog untuk menghasilkan semua pengaturan gelembung tersebut, dan kemudian menghitungnya. Generasi mengambil 55 karakter (dua baris pertama dari program). Penghitungan dan I / O mengambil 43 lainnya (baris ketiga, dan baris baru yang memisahkan dua bagian). Saya yakin ini bukan masalah yang diharapkan OP menyebabkan bahasa bergulat dengan I / O! (Catatan: Penyorotan sintaksis Stack Exchange membuat ini lebih sulit untuk dibaca, tidak mudah, jadi saya mematikannya).

Penjelasan

Mari kita mulai dengan versi pseudocode dari program serupa yang sebenarnya tidak berfungsi:

b(Bubbles,Count) if map(b,Bubbles,BubbleCounts)
                and sum(BubbleCounts,InteriorCount)
                and Count is InteriorCount + 1
                and is_sorted(Bubbles).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

Seharusnya cukup jelas cara bkerjanya: kami merepresentasikan gelembung melalui daftar yang diurutkan (yang merupakan implementasi sederhana dari multiset yang menyebabkan multiset yang sama untuk dibandingkan dengan yang sama), dan satu gelembung []memiliki hitungan 1, dengan gelembung yang lebih besar memiliki hitungan sama dengan jumlah total gelembung di dalam ditambah 1. Untuk hitungan 4, program ini akan (jika berhasil) menghasilkan daftar berikut:

[[],[],[],[]]
[[],[],[[]]]
[[],[[],[]]]
[[],[[[]]]]
[[[]],[[]]]
[[[],[],[]]]
[[[],[[]]]]
[[[[],[]]]]
[[[[[]]]]]

Program ini tidak cocok sebagai jawaban karena beberapa alasan, tetapi yang paling mendesak adalah bahwa Prolog sebenarnya tidak memiliki mappredikat (dan menulisnya akan membutuhkan terlalu banyak byte). Jadi alih-alih, kami menulis program lebih seperti ini:

b([], 0).
b([Head|Tail],Count) if b(Head,HeadCount)
                    and b(Tail,TailCount)
                    and Count is HeadCount + TailCount + 1
                    and is_sorted([Head|Tail]).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

Masalah utama lainnya di sini adalah bahwa ia akan masuk ke loop tak terbatas ketika dijalankan, karena cara urutan evaluasi Prolog bekerja. Namun, kita dapat menyelesaikan loop tak terbatas dengan mengatur ulang program sedikit:

b([], 0).
b([Head|Tail],Count) if Count #= HeadCount + TailCount + 1
                    and b(Head,HeadCount)
                    and b(Tail,TailCount)
                    and is_sorted([Head|Tail]).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

Ini mungkin terlihat cukup aneh - kita menambahkan hitungan sebelum kita tahu apa itu - tetapi GNU Prolog #=mampu menangani aritmatika nonkausal semacam itu, dan karena itu adalah baris pertama b, dan HeadCountdan dan TailCountkeduanya harus kurang dari Count(yang dikenal), ini berfungsi sebagai metode membatasi secara alami berapa kali istilah rekursif dapat cocok, dan dengan demikian menyebabkan program selalu berakhir.

Langkah selanjutnya adalah sedikit menurunkan golf ini. Menghapus spasi, menggunakan nama variabel karakter tunggal, menggunakan singkatan seperti :-untuk ifdan ,untuk and, menggunakan setofdaripada listof(memiliki nama yang lebih pendek dan menghasilkan hasil yang sama dalam kasus ini), dan menggunakan sort0(X,X)daripada is_sorted(X)(karena is_sortedsebenarnya bukan fungsi sebenarnya, Saya mengarangnya):

b([],0).
b([H|T],N):-N#=A+B+1,b(H,A),b(T,B),sort0([H|T],[H|T]).
c(X,Y):-setof(A,b(A,X),L),length(L,Y).

Ini cukup singkat, tetapi dimungkinkan untuk melakukan yang lebih baik. Wawasan kunci adalah yang [H|T]benar-benar bertele-tele saat sintaksis daftar berjalan. Seperti yang akan diketahui oleh programmer Lisp, daftar pada dasarnya hanya terbuat dari sel kontra, yang pada dasarnya hanya tupel, dan hampir tidak ada bagian dari program ini yang menggunakan daftar bawaan. Prolog memiliki beberapa sintaks tuple yang sangat pendek (favorit saya adalah A-B, tetapi favorit kedua saya A/B, yang saya gunakan di sini karena menghasilkan output debug yang lebih mudah dibaca dalam kasus ini); dan kita juga dapat memilih karakter tunggal kita sendiri niluntuk bagian akhir daftar, daripada terjebak dengan dua karakter [](saya memilih x, tetapi pada dasarnya apa pun berfungsi). Jadi, bukannya[H|T] , kita bisa menggunakan T/H, dan mendapatkan output darib yang terlihat seperti ini (perhatikan bahwa urutan pengurutan pada tupel sedikit berbeda dari yang ada di daftar, jadi ini tidak dalam urutan yang sama seperti di atas):

x/x/x/x/x
x/x/x/(x/x)
x/(x/x)/(x/x)
x/x/(x/x/x)
x/(x/x/x/x)
x/x/(x/(x/x))
x/(x/x/(x/x))
x/(x/(x/x/x))
x/(x/(x/(x/x)))

Ini agak sulit dibaca daripada daftar bersarang di atas, tetapi itu mungkin; lewati xs, dan tafsirkan /()sebagai gelembung (atau sekadar /gelembung yang merosot tanpa isi, jika tidak ada ()setelahnya), dan elemen-elemen tersebut memiliki korespondensi 1-ke-1 (jika tidak tertata) dengan versi daftar yang ditunjukkan di atas .

Tentu saja, representasi daftar ini, meskipun jauh lebih pendek, memiliki kelemahan utama; itu tidak dibangun ke dalam bahasa, jadi kami tidak dapat menggunakan sort0untuk memeriksa apakah daftar kami diurutkan. sort0bagaimanapun juga cukup verbose, jadi melakukannya dengan tangan bukanlah kerugian besar (pada kenyataannya, melakukannya dengan tangan pada [H|T]daftar representasi datang dengan jumlah byte yang persis sama). Kunci wawasan di sini adalah bahwa program sebagai cek yang ditulis untuk melihat apakah daftar diurutkan, jika ekornya diurutkan, jika yang ekornya diurutkan, dan sebagainya; ada banyak cek berlebihan, dan kita bisa memanfaatkannya. Sebagai gantinya, kami hanya akan memeriksa untuk memastikan bahwa dua elemen pertama dalam urutan (yang memastikan bahwa daftar akan berakhir diurutkan setelah daftar itu sendiri dan semua sufiksnya diperiksa).

Elemen pertama mudah diakses; itu hanya kepala daftar H. Elemen kedua agak sulit diakses, dan mungkin tidak ada. Untungnya, xkurang dari semua tuple yang kami pertimbangkan (melalui operator pembanding umum Prolog @>=), sehingga kami dapat mempertimbangkan "elemen kedua" dari daftar tunggal xdan program akan bekerja dengan baik. Sedangkan untuk benar-benar mengakses elemen kedua, metode tersest adalah menambahkan argumen ketiga (argumen keluar) b, yang kembali xdalam kasus dasar dan Hdalam kasus rekursif; ini berarti bahwa kita dapat mengambil kepala ekor sebagai output dari panggilan rekursif kedua B, dan tentu saja kepala ekor adalah elemen kedua daftar. Jadi bterlihat seperti ini sekarang:

b(x,0,x).
b(T/H,N,H):-N#=A+B+1,b(H,A,_),b(T,B,J),H@>=J.

Kasing dasar cukup sederhana (daftar kosong, kembalikan hitungan 0, "elemen pertama" daftar kosong adalah x). Kasus rekursif dimulai dengan cara yang sama seperti sebelumnya (hanya dengan T/Hnotasi daripada [H|T], dan Hsebagai argumen tambahan); kita mengabaikan argumen tambahan dari panggilan rekursif di kepala, tetapi menyimpannya dalam Jpanggilan rekursif di ekor. Maka yang harus kita lakukan adalah memastikan yang Hlebih besar atau sama denganJ (yaitu "jika daftar memiliki setidaknya dua elemen, yang pertama lebih besar dari atau sama dengan yang kedua) untuk memastikan bahwa daftar akhirnya diurutkan.

Sayangnya, setofcocok jika kita mencoba menggunakan definisi sebelumnya cbersama-sama dengan definisi baru ini b, karena ia memperlakukan parameter yang tidak digunakan dalam cara yang kurang lebih sama dengan SQL GROUP BY, yang sama sekali bukan yang kita inginkan. Anda dapat mengkonfigurasi ulang untuk melakukan apa yang kita inginkan, tetapi konfigurasi ulang itu membutuhkan karakter. Sebagai gantinya, kami menggunakan findall, yang memiliki perilaku default yang lebih nyaman dan hanya dua karakter lebih lama, memberi kami definisi c:

c(X,Y):-findall(A,b(A,X,_),L),length(L,Y).

Dan itu adalah program yang lengkap; hanya menghasilkan pola gelembung, kemudian menghabiskan seluruh byte untuk menghitungnya (kita perlu waktu yang cukup lama findalluntuk mengonversi generator ke daftar, kemudian sayangnya diberi nama secara verbal lengthuntuk memeriksa panjang daftar itu, ditambah pelat ketel untuk deklarasi fungsi).

Mathematica, 68 byte

Saya yakin ini bisa dikalahkan (bahkan di Mathematica) dengan implementasi dari awal, tetapi inilah versi bawaannya:

<<NumericalDifferentialEquationAnalysis`
Last@ButcherTreeCount[#+1]&

ButcherTreeCountadalah 0-diindeks, karenanya [#+1], dan mengembalikan daftar semua nilai hingga argumennya, karenanya Last@. Tetapi sebaliknya itu hanya builtin untuk fungsi ini. Namun, itu membutuhkan memuat paket, yang dilakukan oleh baris pertama.