Produkt o długości haka

27

Młoda schemat jest ułożenie pudełek w lewo-uzasadnione wierszy i kolumn top-uzasadnione. Dla każdego pola wszystkie pola nad nim i po jego lewej stronie są zajęte.

XXXXX
XXX
XXX
X

Długość haczyk pudełka jest liczba pól po jego prawej stronie, w tym samym rzędzie, i poniżej niej w tej samej kolumnie, a także liczyć się raz. Na przykład drugie pudełko ma haczyk o długości 6:

X****
X*X
X*X
X

Oto wszystkie długości haków:

86521
532
421
1

Twoim celem jest obliczenie iloczynu długości haka tutaj 8*6*5*2*1*5*3*2*4*2*1*1 = 115200.

(Przeczytaj o formule długości haka, jeśli jesteś zainteresowany, dlaczego to wyrażenie ma znaczenie.)

Dane wejściowe: zbiór rozmiarów wierszy w postaci liczb takich jak [5,3,3,1]lub jako powtarzający się symbol jednoargumentowy jak [[1,1,1,1,1], [1,1,1], [1,1,1], [1]]lub "XXXXX XXX XXX X". Możesz oczekiwać, że lista zostanie posortowana rosnąco lub malejąco, jak chcesz. Lista będzie niepusta i będzie zawierać wyłącznie dodatnie liczby całkowite.

Wyjście: iloczyn długości haka, który jest dodatnią liczbą całkowitą. Nie martw się o przepełnienie liczb całkowitych lub środowisko wykonawcze.

Wbudowane funkcje specyficzne dla schematów Younga lub partycji całkowitych są niedozwolone.

Przypadki testowe:

[1] 1
[2] 2
[1, 1] 2
[5] 120
[2, 1] 3
[5, 4, 3, 2, 1] 4465125
[5, 3, 3, 1] 115200
[10, 5] 798336000
xnor
źródło

Odpowiedzi:

13

CJam, 20 19 bajtów

{ee::+W%}_q~%z%:+:*

To pobiera unarską listę w stylu CJam w porządku rosnącym. Na przykład:

[[1] [1 1 1] [1 1 1] [1 1 1 1 1]]

daje

115200

Jak to działa

Ta wersja jest dostarczana przez Dennisa i wykorzystuje fakt, że Block ArrayList %nadal działa w CJam: D

{       }_             e# Put this block on stack and make a copy
          q~           e# Read the input and evaluate it to put the array of arrays on stack
            %          e# Use the copy of the block and map the array using that block
 ee                    e# Here we are mapping over each unary array in the input. ee converts
                       e# the array to [index value] pair.
   ::+                 e# Add up each index value pair. Now we have the horizontal half of
                       e# hook length for each row
      W%               e# Reverse the array to make sure the count is for blocks to the right
             z%        e# Transpose and do the same mapping for columns
               :+      e# Now we have all the hook lengths. Flatten the array
                 :*    e# Get the product of all hook lengths.

To jest oryginalna 20 bajtowa wersja

1q~:,Wf%z:ee{:+)*}f/

Pobiera to listę stylów CJam wielkości wierszy w porządku rosnącym. Na przykład:

[1 3 3 5]

daje

115200

Jak to działa

Jeśli spojrzymy na to, długość haka każdego bloku na schemacie Younga jest sumą indeksu tego bloku w jego wierszu i kolumnie, licząc do tyłu. tj. Rozpocznij indeks w każdym rzędzie od prawej strony i zacznij indeks w każdej kolumnie od dołu.

Przyjmujemy dane wejściowe w porządku rosnącym według wielkości wiersza, aby łatwo rozpocząć indeks od dołu w każdej kolumnie. Najpierw otrzymujemy indeks na wiersz i odwracamy go. Następnie dokonujemy transpozycji. Ponieważ pierwotna kolejność wierszy została odwrócona, pobranie indeksu na tym transponowanym diagramie da bezpośrednio indeks od dołu do góry.

Rozszerzenie kodu

1                       e# This serves as the initial term for product of hook lengths
 q~                     e# Read the input and eval it to put an array on stack
   :,                   e# For each row-size (N), get an array of [0..N-1]
     Wf%                e# Reverse each row so that each row becomes [N-1..0]
        z               e# Transpose for the calculation of blocks below each block
         :ee            e# Enumerate each row. Convert it into array of [index value] pairs
            {    }f/    e# Apply this mapping block to each cell of each row
             :+         e# Add the index value pair. Here, index is the blocks below the
                        e# block and value is the blocks to the right of it in the Young diag
               )        e# Increment the sum by 1 to account for the block itself
                *       e# Multiply it with the current holding product, starting with 1

Wypróbuj online tutaj

Optymalizator
źródło
{ee::+W%}_q~%z%:+:*(19 bajtów) Format wejściowy:[[1][1 1 1][1 1 1][1 1 1 1 1]]
Dennis
@Dennis Nice (ab) użycie porządku arity dla %: P
Optimizer
6

J, 24 bajty

*/@,@(1|@-+/\."1++/\)@:>

25 bajtów (z wyjaśnieniem):

*/@,@(+/\."1|@<:@++/\)@:>

Pobiera dane wejściowe jako listę rosnących list jednych cyfr podobnych do przykładu [[1], [1,1,1], [1,1,1], [1,1,1,1,1]].

Stosowanie:

   f=.*/@,@(+/\."1|@<:@++/\)@:>

   f 1;1 1 1;1 1 1;1 1 1 1 1
115200

metoda

  • Utwórz macierz binarną z danych wejściowych
  • Oblicz różnice w obu wymiarach.
  • Dla każdej komórki dodaj dwa wyniki, odejmij 1, weź wartość bezwzględną (aby zamapować pierwotnie zero komórek na 1)
  • Ravel macierz i weź iloczyn liczb.

Wyniki pośrednie wyświetlane na wejściu 1 1 1 1 1;1 1 1;1 1 1;1 (5,3,3,1 in unary)( dotyczy poprzedniej wersji z malejącymi długościami, ale przy użyciu tej samej metody ):

   ]c=.1 1 1 1 1;1 1 1;1 1 1;1
┌─────────┬─────┬─────┬─┐
│1 1 1 1 1│1 1 1│1 1 1│1│
└─────────┴─────┴─────┴─┘

   (>)  c
1 1 1 1 1
1 1 1 0 0
1 1 1 0 0
1 0 0 0 0

   (+/\.@:>)  c
4 3 3 1 1
3 2 2 0 0
2 1 1 0 0
1 0 0 0 0

   (+/\."1@:>)  c
5 4 3 2 1
3 2 1 0 0
3 2 1 0 0
1 0 0 0 0

   ((+/\."1++/\.)@:>)  c
9 7 6 3 2
6 4 3 0 0
5 3 2 0 0
2 0 0 0 0

   ((+/\."1<:@++/\.)@:>)  c
8  6  5  2  1
5  3  2 _1 _1
4  2  1 _1 _1
1 _1 _1 _1 _1

   ((+/\."1|@<:@++/\.)@:>)  c
8 6 5 2 1
5 3 2 1 1
4 2 1 1 1
1 1 1 1 1

   (,@(+/\."1|@<:@++/\.)@:>)  c
8 6 5 2 1 5 3 2 1 1 4 2 1 1 1 1 1 1 1 1

   (*/@,@(+/\."1|@<:@++/\.)@:>)  c
115200

Wersja jawna o tej samej długości:

3 :'*/,|<:(+/\."1++/\)>y'

Wypróbuj online tutaj.

randomra
źródło
4

Pyth - 21 bajtów

Tracę dużo bajtów w obliczeniach pionowych. Skupię się na tym.

*Fs.em+lf>Td>Qkt-bdbQ

Przyjmuje dane wejściowe jak [5, 3, 3, 1].

Wypróbuj tutaj online .

Maltysen
źródło
4

Pyth, 18 bajtów

*Fsm.e+k-bdf>TdQeQ

Pobiera dane wejściowe w kolejności rosnącej, np [1, 3, 3, 5].

Demonstracja.


Alternatywne rozwiązanie, 19 bajtów

*Fs.em+s>Rd<Qk-bdbQ
isaacg
źródło
3

Python 2, 89 88 bajtów

p=j=-1;d={}
for n in input():j+=1;i=0;exec"a=d[i]=d.get(i,j);p*=n-i+j-a;i+=1;"*n
print-p

(Dzięki @xnor za jeden szalony zapis bajtów poprzez połączenie pi j)

d.getWygląda trochę podejrzanie mi, ale poza tym jestem względnie zadowolony z tego. Próbowałem innych metod, takich jak rekurencja i kompresowanie, ale to jedyne, które udało mi się uzyskać poniżej 100.

Pobiera dane wejściowe ze STDIN jako listę w porządku rosnącym, np [1, 3, 3, 5].

Sp3000
źródło
3

Haskell, 68 bajtów

f[]=1
f g@(h:t)=(h+length t)*f[x-1|x<-g,x>1]
p[]=1
p g@(_:t)=f g*p t

Przykład użycia: p [5,4,3,2,1]->4465125

fskanuje od lewej do prawej, mnożąc długość najbardziej wysuniętego haka przez rekurencyjne wywołanie do siebie, w którym każdy element listy wejściowej jest redukowany przez 1(upuszczenie go po osiągnięciu 0). pskanuje od góry do dołu, mnożąc fcałą listę pprzez ogon.

nimi
źródło
2

R, 174 bajtów

Więc ... To rozwiązanie jest dość długie i prawdopodobnie mogłoby być bardziej golfem. Pomyślę o tym !

v=c();d=length;m=matrix(-1,l<-d(a<-scan()),M<-max(a));for(i in 1:l)m[i,(1:a[i])]=c(a[i]:1);for(j in 1:M)m[,j]=m[,j]+c((((p=d(which(m[,j]>0)))-1)):0,rep(0,(l-p)));abs(prod(m))

Nie golfowany:

v=c()          #Empty vector
d=length       #Alias

m=matrix(-1,l<-d(a<-scan()),M<-max(a)) #Builds a matrix full of `-1`

for(i in 1:l)
    m[i,(1:a[i])]=c(a[i]:1) #Replaces each row of the matrix by `n` to 1, `n` being the 
                            #corresponding input : each number is the number of non-empty
                            #cells at its left + itself

for(j in 1:M)
    m[,j]=m[,j]+c((((p=d(which(m[,j]>0)))-1)):0,rep(0,(l-p)))

    #This part calculates the number of "non-empty" (i.e. without `-1` in a column), -1,
    #because the count for the cell itself is already done.
    # Then, it creates a vector of those count, appending 0's at the end if necessary 
    #(this avoids recycling)

abs(prod(m)) #Outputs the absolute value of the product (because of the `-1`'s)
Frédéric
źródło
1

Python 2, 135 128 bajtów

Pobiera listę typów Python ze standardowego wejścia:

r=input()
c=[-1]*r[0]
for a in r:
 for b in range(a):c[b]+=1
s=1
y=0
for a in r:
 for x in range(a):s*=a-x+c[x]-y
 y+=1
print s

Jest to bardzo kanoniczna implementacja, ale jak dotąd nie wymyśliłem nic mądrzejszego. Mam wrażenie, że rozwiązania będą znacznie krótsze, nawet w przypadku „prawdziwych” języków programowania.

Otrzymujemy liczbę pól w każdym rzędzie jako dane wejściowe. To rozwiązanie najpierw liczy liczbę pól w każdej kolumnie, w której jest przechowywany c(w rzeczywistości jest to liczba minus 1, aby uprościć jego użycie w późniejszych obliczeniach). Następnie iteruje wszystkie pola i mnoży długości haczyków. Sama długość haka jest łatwa do obliczenia, gdy masz już liczbę pól w każdym rzędzie i kolumnie.

Reto Koradi
źródło
1
Wygląda na to, że nie używasz m?
xnor
Mógłbym przysiąc, że go usunąłem! Pamiętam, że zauważyłem, że użyłem go tylko raz i zastąpiłem jedyne użycie. Ale potem musiałem przeoczyć tę zmienną. :(
Reto Koradi
1

JavaScript ( ES6 ) 69

Funkcja przyjmująca tablicę liczb całkowitych w porządku rosnącym .

Uruchom fragment kodu, aby przetestować (tylko Firefox)

F=x=>x.map(r=>{for(i=-1;++i<r;p[i]=-~p[i])t*=r-i+~~p[i]},p=[],t=1)&&t

// TEST
out=x=>O.innerHTML += x + '\n';

test=[
 {y:[1], h: 1}
,{y:[2], h: 2}
,{y:[1, 1], h: 2}
,{y:[5], h: 120}
,{y:[2, 1], h: 3}
,{y:[5, 4, 3, 2, 1], h: 4465125}
,{y:[5, 3, 3, 1], h: 115200}
,{y:[10, 5], h: 798336000}
]

test.forEach(t=>{ 
  t.y.reverse(); // put in ascending order
  r=F(t.y);
  out((r==t.h? 'Ok':'Fail')+' Y: ['+t.y+'] Result:'+r+' Check:'+t.h)
})  
<pre id=O></pre>

edc65
źródło
1

Python, 95 91 bajtów

To jest implementacja Pythona odpowiedzi Haskella . Sugestie dotyczące gry w golfa mile widziane.

f=lambda z:z==[]or(z[0]+len(z)-1)*f([i-1for i in z if~-i])
p=lambda z:z==[]or f(z)*p(z[1:])
Sherlock9
źródło
Witamy w golfie Python! Można zrobić z and _ or 1tak z==[]or _, gdy zjest lista, wykorzystując fakt, że True==1. Deklaracje funkcji Pythona są bardziej sformułowane niż Haskell, więc często daje dobrą korzyść w celu zdefiniowania pojedynczej funkcji rekurencyjnej, która wykonuje zarówno wewnętrzną, jak i zewnętrzną pętlę rekurencyjną, chociaż nie wiem, jak to możliwe.
xnor
@xnor „Welcome to Python golfing”?
Sherlock9,
Och, przepraszam, grasz w golfa w Python. Z tobą kojarzę się.
xnor
@xnor Na długo, zanim zacząłem w rzeczywistości, grałem w golfa w Pythonie. Jestem trochę zirytowany, że nie pamiętasz: P
Sherlock9
Nie mogę mówić w imieniu xnor, ale rozpoznaję użytkowników głównie według ich awatarów.
Dennis