Podział siatki na trójkąty


18

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 Przegrody 2 x 1 których partycje mają odpowiednio 2, 2, 2, 2, 4 i 2 różne orientacje.

Punktacja

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


10
Niektóre dodatkowe przypadki testowe byłyby korzystne, dzięki czemu możemy zweryfikować poprawność naszych zgłoszeń.
AdmBorkBork

8
Możesz podać trójkąty nie zdegenerowane .
Arnauld

1
Dokonałem edycji sekwencji OEIS A051708, aby odzwierciedlić tę interpretację.
Peter Kagey

Odpowiedzi:


2

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)

19

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)×(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×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!


Znalazłem sekwencję OEIS, wyszukując kilka pierwszych wartości. Ładne wyjaśnienie, dlaczego pasuje. Czy chcesz go edytować, aby dodać komentarz na temat tej alternatywnej interpretacji kombinatorycznej? Jeśli nie, mógłbym.
Peter Taylor

BTW musisz dostosować indeksowanie, ponieważ tutaj jest poprawna odpowiedź A051708(n+1). Więc opublikowałem pierwszą poprawną odpowiedź :-P
Peter Taylor

Rozumiem, że wieża przesuwa mapę do trójkątów, dzięki czemu trójkąty z górną i dolną krawędzią odpowiadają ruchom w górę czy w prawo?
Neil

@PeterTaylor Damn, dzięki za zwrócenie uwagi na mój błąd :)
flawr

5
@ Neil Dodałem graficzne objaśnienie.
flawr

8

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%ia?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.


Twoje 49-bajtowe rozwiązanie wykorzystuje tę samą rekurencję, co moja odpowiedź, ale jeszcze nie wymyśliłem 42-bajtowej. Wyjaśnienie byłoby miłe.
Peter Taylor

Myślę, że zastosowałem to samo podejście w jednym z moich wcześniejszych programów: Pomysł polega na generowaniu (lub zliczaniu) wszystkich partycji poprzez generowanie nie poziomych linii od prawej do lewej. Zaczynasz od pionowej linii. Następnie możesz powtórzyć: weź jeden z końcowych węzłów poprzedniej linii i połącz go z węzłem na przeciwległej linii poziomej, która jest bardziej na lewo od wszystkich poprzednich węzłów na tej linii.
wada

Operator a%bzlicza liczbę partycji za pomocą węzłów 0,1,...,aw górnym wierszu i węzłów w 0,1,..,bdolnym wierszu. Operator a?bliczy liczbę sposobów dodania nowej linii z górnego węzła, ajeśli dolny węzeł bjest już w użyciu. (Możesz połączyć się aze wszystkimi węzłami [0,1,...,b-1], ale musisz powtórzyć dla każdego z nich.)
flawr

@ flawr, to 49-bajtowy, który rozumiem. Jest to ?42-bajtowy, którego nie znam, a szczególnie ciekawe jest to, że nie jest symetryczny.
Peter Taylor

@PeterTaylor Przepraszam za zamieszanie, jakoś pomieszałem oba rozwiązania. Myślę, że dość łatwo możemy przekształcić te dwa rozwiązania w siebie nawzajem: w pierwszym kroku możemy zastąpić map...zrozumienie listy, w drugim kroku po prostu wprowadzamy definicję %:a?b=sum$map(a%)[0..b-1], a%b=a?b+b?a a?b=sum[a%i|i<-[0..b-1]], a%b=a?b+b?a a?b=sum[a?i+i?a|i<-[0..b-1]]
wada

7

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


Tak, pokonałem cię o 10 sekund, nie sądzę, żebym kiedykolwiek był tak blisko :)
flawr

@ flawr, zastanawiałem się nad opublikowaniem, zanim napisałem sekcję, ale pomyślałem, że mam czas, aby szybko to znokautować. Potem zobaczyłem „Nowa odpowiedź”, więc usunąłem częściowo napisane fragmenty, opublikowałem i zredagowałem.
Peter Taylor

1
Dzięki za -5 bajtów btw: D
flawr

4

Galaretka , 15 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.


Niezłe podejście. Kiedy przeniosłem go do CJam, krótsze było zmniejszenie długości, sumy, a następnie podniesienie 2 do sumy; zamiast podnosić 2 do długości, zmniejszając je o połowę, a następnie mnożąc. Nie wiem, czy może to uratować bajt.
Peter Taylor

3

Węgiel drzewny , 44 31 bajtów

przekreślone 44 jest nadal regularne 44

F⊕θ«≔⟦⟧ηF⊕θ⊞ηΣ∨⁺ηEυ§λκ¹⊞υη»I⊟⊟υ

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.

F⊕θ«

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

≔⟦⟧η

Zacznij od pustego rzędu.

F⊕θ

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

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

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.

I⊟⊟υ

Podaj obliczoną wartość końcową.



2

Pari / GP , 43 bajty

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

12)(1-x1-9x+1)

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

Wypróbuj online!


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.