Zamów 40 patyczków

15

Mamy 40 drążków o tej samej szerokości, ale różnych wysokościach. Ile jest możliwych ustawień, aby umieścić je obok siebie, aby spojrzeć z prawej strony na 10 drążków, a kiedy spojrzeć z lewej strony, ponownie zobaczymy dokładnie 10 drążków?

Na przykład takie zamówienie to:Przykład zamówienia

Czarne patyki są ukryte, czerwone patyki są widoczne, gdy patrzysz z lewej strony, niebieskie patyki są widoczne, gdy patrzysz z prawej strony, a fioletowe (tj. Najdłuższe) to te, które można zobaczyć z obu stron.

Jako przypadki testowe:

  • Gdybyśmy mieli 3 drążki liczba zamówień, aby zobaczyć 2 z lewej, a 2 z prawej to 2
  • Gdybyśmy mieli 5 drążków liczba zamówień, aby zobaczyć 3 z lewej, a 3 z prawej to 6
  • Gdybyśmy mieli 10 drążków liczba zamówień, aby zobaczyć 4 z lewej, a 4 z prawej to 90720
code-golf combinatorics permutations Kumpel
źródło
13
Możesz uniknąć pytań ze stałym wyjściem, ponieważ optymalna odpowiedź na golfa kodowego prawdopodobnie po prostu wydrukuje wynik bez jego obliczania. Polecam, aby pytanie zawierało kilka zmiennych wejściowych, np. N drążków, tak że K widać je od lewej / prawej, gdzie N i K są liczbami całkowitymi wejściowymi
Sp3000
4
Jeśli zmienisz specyfikację, aby programy pobierały dane wejściowe (nie rozumiem, dlaczego nie - masz już przypadki testowe), możesz pomyśleć o tym, czy chcesz nałożyć limit czasowy na programy.
Sp3000,
1
„Musisz użyć opublikowanego programu do obliczenia przypadku 40/10” powinno być wystarczająco dobrym terminem.
feersum
1
Nie mogę przeoczyć faktu, że 10!/40 = 90720... czy to zbieg okoliczności?
Tim
1
@Tim Jakie znaczenie ma 90720? Kod pocztowy Los Alamitos, Kalifornia ?
Cyfrowa trauma

Odpowiedzi:

8

PARI / GP, 80

f(n,v)=abs(sum(k=1,n-1,binomial(n-1,k)*stirling(k,v-1,1)*stirling(n-k-1,v-1,1)))

Liczba widocznych drążków jest również nazywana liczbami wieżowców , po grze ołówkiem / siatką. Ten kod jest oparty na (tylko nieznacznie zmienionej) formule z OEIS A218531 . Nie znam dużo PARI, ale tak naprawdę nie sądzę, że jest tu dużo golfa.

Przypadki testowe są pokazane na ideone.com . Wynik f(40,10)jest następujący:

192999500979320621703647808413866514749680
Geobity
źródło
1
Jest dobry powód dla tej formuły. Liczba permutacji z vpatyczkami widocznymi z lewej strony to liczba Stirlinga s(n,v). Jeśli najwyższy drążek znajduje się na pozycji k, to drążki widoczne po lewej stronie są drążkami, a drążki widoczne po lewej stronie w permutacji na lewo od k-1wartości po lewej stronie pozycji k. Tak więc, aby mieć vpatyczki widoczne z lewej strony i patyczki widoczne z vprawej strony, można s(k,v-1)dokonać permutacji lewej połowy, s(n-k-1,v-1)permutacji prawej połowy i binomial(n-1,k)podzielić pałeczki na dwie połowy.
xnor
@xnor Podają to wyjaśnienie w dołączonym pliku PDF, ale twoje jest lepiej sformułowane w IMO.
Geobity
Można zapisać 11 bajtów: f(n,v,s=stirling)=abs(sum(k=1,n--,binomial(n,k)*s(k,v-1)*s(n-k,v-1))). Zapisuje sterlingto zmienną do ponownego użycia, pomija ostatni argument, ponieważ 1 jest wartością domyślną i odejmuje 1 od n jeden raz, a nie trzy razy.
Charles
1

Python 3, 259 bajtów

Nie bardzo z tego zadowolony.

import itertools as i
x=input().split()
y,k=x
y=int(y)
c=0
x=list(i.permutations(list(range(1,y+1))))
for s in x:
 t=d=0;l=s[::-1]
 for i in range(y):
  if max(s[:i+1])==s[i]:t+=1
 for i in range(y):
  if max(l[:i+1])==l[i]:d+=1
 if t==d==int(k):c+=1
print(c)

Przykładowe dane wejściowe i wyjściowe:

10 4
90720

Generuje wszystkie możliwe kombinacje podanego zakresu, a następnie przechodzi przez nie, sprawdzając każdą liczbę w nich, aby sprawdzić, czy jest równa maksymalnej liczbie poprzednich liczb. Następnie robi to samo do tyłu, a jeśli liczba do przodu (t) = liczba do tyłu (d) = podany numer widoku (k) jest prawidłowy. Dodaje to do licznika (c) i drukuje to na końcu.

Tim
źródło
0

R 104

function(N,K)sum(sapply(combinat::permn(N),function(x)(z=function(i)sum(cummax(i)==i)==K)(x)&z(rev(x))))

Trochę grałem w golfa:

    function(N,K) {
      all_perm <- combinat::permn(N)
      can_see_K_from_left <- function(i)sum(cummax(i) == i) == K
      can_see_K_from_both <- function(x)can_see_K_from_left(x) &
                                        can_see_K_from_left(rev(x))
      return(sum(sapply(all_perm, can_see_K_from_both)))
    }
flodel
źródło
0

Pyth - 38 36 bajtów

Zasadniczo port odpowiedzi R. Dość wolno, nawet nie można ukończyć 10, 4online.

AGHQLlfqhS<bhT@bTUGlf!-,yTy_TH.pr1hG

Jedyne, czego Pyth nie ma, to cummax i == wektory ponad, ale te zajęły tylko kilka bajtów do wdrożenia.

Wyjaśnienie i dalsza gra w golfa już wkrótce.

Wypróbuj tutaj online .

Maltysen
źródło