Uwaga: wyzwanie skopiowane z pytania zadanego na math.stackexchange .

Niedawno zdobyłem sporo umiejętności w dmuchaniu baniek. Na początku wysadzałbym takie bąbelki:

Ale potem zaczęło się robić dziwnie:

Po jakimś czasie dmuchałem dziwnymi bąbelkami:

Po wysadzeniu setek, a może nawet tysięcy takich bąbelków, moje czoło nagle zmarszczyło się pytaniem: Biorąc pod uwagę n bąbelków, ile różnych sposobów możesz je ułożyć? Na przykład, jeśli n = 1, istnieje tylko 1 układ. Jeśli n = 2, istnieją 2 układy. Jeśli n = 3, istnieją 4 ustawienia. Jeśli n = 4, istnieje 9 układów.

Oto 9 układów 4 bąbelków:

Po wysadzeniu wszystkich tych cudownych baniek postanowiłem podzielić się z tobą radością liczenia ich ustaleń. Oto twoje zadanie:

Cel

Napisz program, funkcję lub podobny, który zlicza liczbę sposobów ułożenia nbąbelków.

Wkład

n, liczba bąbelków. n> 0

Wydajność

Liczba sposobów ułożenia tych bąbelków.

Zwycięskie kryteria

Byłoby naprawdę fajnie, gdybyśmy mogli dmuchnąć bańkę wokół twojego kodu. Im mniejszy kod, tym łatwiej będzie to zrobić. Tak więc osoba, która stworzy kod z najmniejszą liczbą bajtów, wygra konkurs.

Informacje dodatkowe

OEIS

Python 2, 92 87 bajtów

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

Mówiąc prościej: aby obliczyć a(n), obliczamy d*a(d)*a(n-k)dla każdego dzielnika dkażdej dodatniej liczby całkowitej kmniejszej lub równej n, sumujemy je wszystkie i dzielimy przez n-1.

Aby działać szybciej, prowadzony w Pythonie 3 (zamiast /ze //w powyższej funkcji) i memoize:

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

Jeśli to zrobisz, oblicza się a(50) = 425976989835141038353natychmiast.

GNU Prolog, 98 bajtów

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).

Ta odpowiedź jest doskonałym przykładem tego, jak Prolog może zmagać się z nawet najprostszymi formatami We / Wy. Działa w prawdziwym stylu Prolog, opisując problem, a nie algorytm do jego rozwiązania: określa, co liczy się jako legalne ustawienie bąbelków, prosi Prolog o wygenerowanie wszystkich tych układów bąbelków, a następnie je zlicza. Generacja zajmuje 55 znaków (pierwsze dwa wiersze programu). Liczenie i operacje we / wy zajmują pozostałe 43 (trzecią linię i nową linię oddzielającą dwie części). Założę się, że to nie jest problem, którego OP spodziewał się, że języki będą miały problemy z I / O! (Uwaga: Podświetlanie składni Stack Exchange sprawia, że ​​jest to trudniejsze do odczytania, a nie łatwiejsze, więc go wyłączyłem).

Wyjaśnienie

Zacznijmy od pseudokodu podobnego programu, który tak naprawdę nie działa:

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).

Powinno być dość jasne, jak to bdziała: reprezentujemy bąbelki za pomocą posortowanych list (które są prostą implementacją multiset, które powodują, że równe multisety są równe), a pojedynczy bąbel []ma liczbę 1, a większy bąbel ma liczbę równa całkowitej liczbie bąbelków w środku plus 1. Dla liczby 4 program ten (jeśli zadziałałby) wygenerowałby następujące listy:

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

Ten program nie nadaje się jako odpowiedź z kilku powodów, ale najbardziej naglące jest to, że Prolog tak naprawdę nie ma mappredykatu (a napisanie go zajęłoby zbyt wiele bajtów). Zamiast tego piszemy program bardziej w ten sposób:

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).

Innym poważnym problemem jest to, że po uruchomieniu przechodzi w nieskończoną pętlę, ze względu na sposób działania kolejności oceny Prologa. Możemy jednak rozwiązać nieskończoną pętlę, zmieniając nieco program:

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).

To może wyglądać dość dziwnie - dodajemy razem liczniki przed wiemy, czym one są - ale GNU Prolog użytkownika #=jest w stanie obsługiwać tego rodzaju noncausal arytmetyki, a ponieważ jest to pierwsza linia b, a HeadCounti TailCountmusi być zarówno mniej niż Count(co jest znane), służy jako metoda naturalnego ograniczenia liczby dopasowań terminu rekurencyjnego, a tym samym powoduje, że program zawsze się kończy.

Następnym krokiem jest odrobina golfa. Usuwanie białych znaków, używanie jednoznakowych nazw zmiennych, używanie skrótów takich jak :-for ifi ,for and, używanie setofzamiast listof(ma krótszą nazwę i daje te same wyniki w tym przypadku) i używanie sort0(X,X)zamiast is_sorted(X)(ponieważ is_sortedtak naprawdę nie jest rzeczywistą funkcją, Zrobiłem to):

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).

Jest to dość krótkie, ale można zrobić lepiej. Kluczowy wgląd jest taki, że [H|T]jest bardzo gadatliwy, gdy idą składnie list. Jak dowiedzą się programiści Lisp, lista jest po prostu zbudowana z komórek minusowych, które są w zasadzie krotkami i prawie żadna część tego programu nie używa wbudowanych list. Prolog ma kilka bardzo krótkich składni krotek (moim ulubionym jest A-B, ale moim drugim ulubionym jest A/B, którego tu używam, ponieważ w tym przypadku daje łatwiejszy do odczytania wynik debugowania); i możemy również wybrać nasz pojedynczy znak nilna końcu listy, zamiast utknąć w tym znaku [](wybrałem x, ale w zasadzie wszystko działa). Zamiast tego [H|T]możemy użyć T/Hi uzyskać dane wyjścioweb wygląda to tak (zauważ, że kolejność sortowania w krotkach jest nieco inna niż w przypadku list, więc nie są one w takiej samej kolejności jak powyżej):

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)))

Jest to trudniejsze do odczytania niż listy zagnieżdżone powyżej, ale jest możliwe; mentalnie pomiń xs i interpretuj /()jako bąbelek (lub po prostu /jako zwyrodniały bąbelek bez zawartości, jeśli nie ma ()go po nim), a elementy mają korespondencję 1 do 1 (jeśli nieuporządkowana) z wersją listy pokazaną powyżej .

Oczywiście reprezentacja tej listy, mimo że jest znacznie krótsza, ma poważną wadę; nie jest wbudowany w język, więc nie możemy sort0sprawdzić, czy nasza lista jest posortowana. sort0i tak jest dość gadatliwy, więc robienie tego ręcznie nie jest wielką stratą (w rzeczywistości robienie tego ręcznie na [H|T]reprezentacji listy ma dokładnie taką samą liczbę bajtów). Kluczowym spostrzeżeniem jest to, że program w formie pisemnej sprawdza, czy lista jest posortowana, czy jej ogon jest posortowany, czy jego ogon jest posortowany i tak dalej; istnieje wiele zbędnych czeków i możemy to wykorzystać. Zamiast tego sprawdzimy tylko, czy pierwsze dwa elementy są w porządku (co gwarantuje, że lista zostanie posortowana po sprawdzeniu samej listy i wszystkich jej sufiksów).

Pierwszy element jest łatwo dostępny; to tylko początek listy H. Dostęp do drugiego elementu jest jednak trudniejszy i może nie istnieć. Na szczęście xjest to mniej niż wszystkie krotki, które bierzemy pod uwagę (za pomocą uogólnionego operatora porównania Prolog @>=), więc możemy rozważyć „drugi element” listy singletonów xi program będzie działał dobrze. Jeśli chodzi o faktyczny dostęp do drugiego elementu, najkrótszą metodą jest dodanie trzeciego argumentu (argument wyjściowy) b, który zwraca się xw przypadku podstawowym i Hprzypadku rekurencyjnym; oznacza to, że możemy chwycić głowę ogona za wynik drugiego wywołania rekurencyjnego B, i oczywiście głowa ogona jest drugim elementem listy. Tak bwygląda teraz:

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

Przypadek podstawowy jest dość prosty (pusta lista, zwraca liczbę 0, „pierwszym elementem” pustej listy jest x). Przypadek rekurencyjny rozpoczyna się tak samo jak poprzednio (tylko z T/Hnotacją zamiast [H|T], i Hjako dodatkowy argument wyjściowy); pomijamy dodatkowy argument wywołania rekurencyjnego na głowie, ale przechowujemy go w Jrekurencyjnym wywołaniu na ogonie. Następnie wszystko, co musimy zrobić, to upewnić się, że Hjest większa lub równa J(tj. „Jeśli lista zawiera co najmniej dwa elementy, pierwszy jest większy lub równy drugiemu), aby mieć pewność, że lista zostanie posortowana.

Niestety, setofpasuje, jeśli spróbujemy użyć poprzedniej definicji cwraz z nową definicją b, ponieważ traktuje niewykorzystane parametry w mniej więcej taki sam sposób jak SQL GROUP BY, co nie jest tym, czego chcemy. Możliwa jest ponowna konfiguracja w celu wykonania tego, co chcemy, ale ta rekonfiguracja kosztuje znaki. Zamiast tego używamy findall, który ma wygodniejsze domyślne zachowanie i ma tylko dwa znaki dłużej, co daje nam następującą definicję c:

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

I to jest kompletny program; zwięźle generuj wzorce bąbelków, a findallnastępnie zliczaj je na liczenie bajtów (potrzebujemy dość długiego czasu, aby przekonwertować generator na listę, a następnie niestety nazwami pełnymi, lengthaby sprawdzić długość tej listy, plus płytkę kotłową do deklaracji funkcji).

Mathematica, 68 bajtów

Założę się, że można to pokonać (nawet w Mathematica) za pomocą implementacji od zera, ale oto wbudowana wersja:

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

ButcherTreeCountjest indeksowane 0, stąd [#+1]i zwraca listę wszystkich wartości aż do argumentu, stąd Last@. Ale w przeciwnym razie jest to tylko wbudowana funkcja. Wymaga to jednak załadowania pakietu, co robi pierwsza linia.