Cel

Celem tego wyzwania jest stworzenie funkcji, nktóra oblicza liczbę sposobów podziału n X 1siatki na trójkąty, w których wszystkie wierzchołki trójkątów znajdują się w punktach siatki.

Przykład

Na przykład istnieje 14 sposobów podziału siatki 2 x 1, więc f(2) = 14za pomocą następujących partycji, w których partycje mają odpowiednio 2, 2, 2, 2, 4 i 2 różne orientacje.

Punktacja

To jest golf golfowy , więc wygrywa najkrótszy kod.

05AB1E , 13 bajtów

·LÉœÙεÅγo;P}O

Port odpowiedzi galaretki @Bubbler .

Bardzo wolny ze względu na wbudowane permutacje.

Wypróbuj online lub sprawdź pierwsze cztery dane wejściowe .

Wyjaśnienie:

·                # Double the (implicit) input
 L               # Create a list in the range [1, doubled_input]
  É              # Check for each if they're odd (1 if truthy, 0 is falsey)
                 # We now have a list of n 0s and n 1s (n being the input)
   œ             # Get all permutations of that list
    Ù            # Only leave the unique permutations
     ε     }     # Map each permutation to:
      Åγ         #  Run-length encode the current value (short for `γ€g`)
        o        #  Take 2 to the power for each
         ;       #  Halve each
          P      #  Take the product of the mapped permutation
            O    # Sum all mapped values together (and output implicitly)

Haskell , 60 55 54 52 bajtów

Po narysowaniu i zaprogramowaniu wielu przykładów przyszło mi do głowy, że jest to to samo, co problem wież:

Na szachownicy $(n+1) \times (n+1)$ ile jest sposobów, aby wieża mogła przejść od $(0,0)$ do $(n,n)$ po prostu przesuwając w prawo $+(1,0)$ lub w górę $+(0,1)$ ?

$1 \times n$

Dzięki @PeterTaylor za -6 bajtów i @PostLeftGarfHunter za -2 bajty!

b 0=1
b 1=2
b n=div((10*n-6)*b(n-1)-9*(n-2)*b(n-2))n

Wypróbuj online!

Haskell , 42 bajty

0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n

Wypróbuj online!

Dość bezpośrednia implementacja, która powtarza ponad 2 zmienne.

Oto, w jaki sposób możemy uzyskać to rozwiązanie. Zacznij od kodu implementującego bezpośrednią rekurencyjną formułę:

54 bajty

0%0=1
a%b=sum$map(a%)[0..b-1]++map(b%)[0..a-1]
f n=n%n

Wypróbuj online!

Korzystanie interpretację gawron ruch flawr jest , a%bto liczba ścieżek uzyskać wieżę od (a,b)celu (0,0), przy użyciu jedynie przesuwa spadek współrzędnych. Pierwszy ruch albo maleje, aalbo malejeb , pozostawiając ten sam drugi, stąd formuła rekurencyjna.

49 bajtów

a?b=sum$map(a%)[0..b-1]
0%0=1
a%b=a?b+b?a
f n=n%n

Wypróbuj online!

Możemy uniknąć powtórzeń map(a%)[0..b-1]++map(b%)[0..a-1], zauważając, że dwie połówki są takie same ai bzamieniły się. Wywołanie pomocnicze a?bliczy ścieżki, w których zmniejsza się pierwszy ruch a, a więc b?aliczy te, w których zmniejsza się pierwszy ruch b. Są one ogólnie różne i dodają się do a%b.

Podsumowanie a?bmożna również napisać w formie listy a?b=sum[a%i|i<-[0..b-1]].

42 bajty

0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n

Wypróbuj online!

Wreszcie pozbywamy się %i po prostu piszemy rekursję pod względem ?zastępowaniaa%i ją a?i+i?aw wywołaniu rekurencyjnym.

Nowy przypadek podstawowy powoduje, że ?daje to wynik podwójny ?w porównaniu z wersją 49-bajtową, ponieważ z 0?0=1, mielibyśmy 0%0=0?0+0?0=2. Pozwala to na użycie funkcji Definiuj f n=n?nbez zmniejszania o połowę tego, co chcielibyśmy zrobić w innym przypadku.

CJam (24 bajty)

{2,*e!{e`0f=:(1b2\#}%1b}

Demo online

Wykorzystuje to podejście Bubblera do sumowania przez permutacjen zer i njedynek.

Sekcja

{         e# Define a block
  2,*     e#   Given input n, create an array of n 0s and n 1s
  e!      e#   Generate all permutations of that array
  {       e#   Map:
    e`    e#     Run-length encode
    0f=:( e#     Extract just the lengths and decrement them
    1b    e#     Sum
    2\#   e#     Raise 2 to the power of that sum
  }%
  1b      e#  Sum the mapped values
}

Alternatywne podejście (28 bajtów)

{_1aa{_2$,f{j}@@,f{j}+1b}2j}

Demo online

Sekcja

Wszystkie trójkąty mają jedną poziomą krawędź i dwie krawędzie, które łączą poziome linie. Oznacz nie-poziome krawędzie krotką ich dwóch współrzędnych x i posortuj leksykograficznie. Zatem pierwsza krawędź to(0,0) , ostatnia krawędź jest (n,n), a dwie kolejne krawędzie różnią się dokładnie w jednej z dwóch pozycji. To zapewnia prostą rekurencję, którą zaimplementowałem za pomocą zapamiętanego operatora rekurencji j:

{            e# Define a block
  _          e#   Duplicate the argument to get n n
  1aa        e#   Base case for recursion: 0 0 => 1
  {          e#   Recursive body taking args a b
    _2$,f{j} e#     Recurse on 0 b up to a-1 b
    @@,f{j}  e#     Recurse on a 0 up to a b-1
    +1b      e#     Combine and sum
  }2j        e#   Memoised recursion with 2 args
}

Uwaga

Nie po raz pierwszy chciałem fj być wspierany w CJam. Tutaj sprowadziłoby to również wynik do 24 bajtów. Być może powinienem spróbować napisać łatkę ...

Galaretka , ₁₅ 14 bajtów

Ø.xŒ!QŒɠ€’§2*S

Wypróbuj online!

-1 bajt na podstawie komentarza Petera Taylora.

Wykorzystuje ilustrację flawr bezpośrednio , zamiast wynikowej formuły.

Jak to działa

Ø.xŒ!QŒɠ€’§2*S    Main link (monad). Input: positive integer N.
Ø.x               Make an array containing N zeros and ones
   Œ!Q            All unique permutations
      Œɠ€         Run-length encode on each permutation
         ’§       Decrement and sum each
           2*S    Raise to power of 2 and sum

Wybierz każdą możliwą trasę na kwadratowej siatce. Liczba sposobów przesuwania jednostek L w jednym kierunku, jak na wieży 2**(L-1). Zastosuj to do każdej trasy i zsumuj liczbę sposobów przemierzania każdej trasy.

Węgiel drzewny , 44 31 bajtów

przekreślone 44 jest nadal regularne 44

Ｆ⊕θ«≔⟦⟧ηＦ⊕θ⊞ηΣ∨⁺ηＥυ§λκ¹⊞υη»Ｉ⊟⊟υ

Wypróbuj online! Objaśnienie: Działa poprzez obliczenie liczby sposobów podziału trapezu o przeciwnych długościach boków m,nna trójkąty, które wszystkie leżą na przesunięciach liczb całkowitych. Jest to po prostu ogólny przypadek prostokąta wielkości nw pytaniu. Liczba partycji jest podawana rekurencyjnie jako suma liczb partycji dla wszystkich stron m,0..n-1i n,0..m-1. Jest to równoważne z uogólnionym problemem wież , OEIS A035002 . Kod po prostu oblicza liczbę partycji roboczych od 0,0góry do n,nstosując uprzednio obliczonych wartości, jak to idzie.

Ｆ⊕θ«

Pętla nad rzędami 0..n.

≔⟦⟧η

Zacznij od pustego rzędu.

Ｆ⊕θ

Pętlę nad kolumnami w rzędzie 0..n.

⊞ηΣ∨⁺ηＥυ§λκ¹

Weź dotychczasowy wiersz i wartości z poprzednich wierszy w bieżącej kolumnie i dodaj sumę do bieżącego wiersza. Jeśli jednak nie ma żadnych wartości, zamień 1zamiast sumy.

⊞υη»

Dodaj gotowy wiersz do listy dotychczasowych wierszy.

Ｉ⊟⊟υ

Podaj obliczoną wartość końcową.

JavaScript (ES6),  45 44  42 bajtów

Wykorzystuje rekurencyjną formułę znalezioną przez Petera Taylora i flawr .

f=n=>n<2?n+1:(10-6/n)*f(--n)+9/~n*f(--n)*n

Wypróbuj online!

Pari / GP , 43 bajty

Według OEIS funkcją generującą tę sekwencję jest

n->Vec(sqrt((1-x)/(1-9*x)+O(x^n++))+1)[n]/2

Wypróbuj online!

Python 3 , 51 bajtów

lambda n:-~n*(n<2)or(10-6/n)*f(n-1)-(9-18/n)*f(n-2)

Wypróbuj online!

Port of flawr odpowiedzi