Hook length product

Question

A Young diagram is an arrangement of boxes in left-justified rows and top-justified columns. For each box, all the spaces above it and to its left are occupied.

XXXXX
XXX
XXX
X

The hook length of a box is the number of boxes to its right in its row, and below it in its column, also counting itself once. For example, the second box has a hook length of 6:

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

Here are all the hook lengths:

86521
532
421
1

Your goal is compute the product of the hook lengths, here 8*6*5*2*1*5*3*2*4*2*1*1 = 115200.

(Read about the hook length formula if you're interested in why this expression matters.)

Input: A collection of row-sizes as numbers like [5,3,3,1] or as a repeated unary symbol like [[1,1,1,1,1], [1,1,1], [1,1,1], [1]] or "XXXXX XXX XXX X". You can expect the list to be sorted ascending or descending, as you wish. The list will be non-empty and only contain positive integers.

Output: The product of hook lengths, which is a positive integer. Don't worry about integer overflows or runtime.

Built-ins dealing specifically with Young diagrams or integer partitions are not allowed.

Test cases:

[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

Answer 1

CJam, 20 19 bytes

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

This takes in CJam style unary list in an ascending order. For example:

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

gives

115200

How it works

This version is provided by Dennis and it uses the fact that a Block ArrayList % still works in 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.

---

This is the original 20 bytes version

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

This takes in a CJam style list of row-sizes in an ascending order. For example:

[1 3 3 5]

gives

115200

How it works

If we look at it, hook length of each block in a Young block diagram is the sum of the index of that block in its row and column, counting backwards. i.e. Start the index in each row from right side and start the index in each column from bottom.

We take the input in ascending order of row-size in order to easily start the index from bottom in each column. First, we get the index per row and reverse it. Then we transpose. Since the original row order was reversed, taking index in this transposed diagram will directly give the bottom to top index.

Code expansion

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

Try it online here

Answer 2

J, 24 bytes

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

25 bytes (with explanation):

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

Takes input as list of ascending lists of unary digits similar to the example [[1], [1,1,1], [1,1,1], [1,1,1,1,1]].

Usage:

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

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

Method

• Create a binary matrix from the input
• Compute the running differences in both dimensions.
• For each cell add the two results, subtract 1, take the absolute value (to map the originally zero cells to 1)
• Ravel the matrix and take the product of the numbers.

Intermediate results shown on the input 1 1 1 1 1;1 1 1;1 1 1;1 (5,3,3,1 in unary) (this is for a previous version with descending lengths but using the same method):

   ]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

Same length explicit version:

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

Try it online here.

Answer 3

Pyth - 21 bytes

I'm losing a lot of bytes in the vertical calculation. Gonna focus on golfing that.

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

Takes input like [5, 3, 3, 1].

Try it here online.

Answer 4

Pyth, 18 bytes

*Fsm.e+k-bdf>TdQeQ

Takes input in ascending order, like [1, 3, 3, 5].

Demonstration.

---

Alternate solution, 19 bytes

*Fs.em+s>Rd<Qk-bdbQ

Answer 5

Python 2, 89 88 bytes

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

(Thanks to @xnor for one insane byte save by combining p and j)

The d.get looks a little suspicious to me, but otherwise I'm relatively happy with this. I tried some other approaches, like recursion and zipping, but this is the only one I managed to get under 100.

Takes input from STDIN as a list in ascending order, e.g. [1, 3, 3, 5].

Answer 6

Haskell, 68 bytes

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

Usage example: p [5,4,3,2,1] -> 4465125

f scans from left to right by multiplying the length of outmost hook with a recursive call to itself where each element of the input list is reduced by 1 (dropping it when reaching 0). p scans from top to bottom by multiplying f of the whole list with p of the tail.

Answer 7

R, 174 bytes

So... This solution is quite long and could probably be more golfed. I'll think about it !

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

Ungolfed :

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)

Answer 8

Python 2, 135 128 bytes

This takes a Python type list from stdin:

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

This is a very canonical implementation, but I haven't come up with anything much smarter so far. I have a feeling that there will be much shorter solutions even with "real" programming languages.

We get the number of boxes in each row as input. This solution first counts the number of boxes in each column, which is stored in c (it's actually the count minus 1 to simplify its usage in the later calculation). Then it iterates over all boxes, and multiplies the hook lengths. The hook length itself is trivial to calculate once you have the count of boxes in each row and column.

Answer 9

JavaScript (ES6) 69

A function taking an array of integers in ascending order.

Run the snippet to test (Firefox only)

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>

Answer 10

Python, 95 91 bytes

This is a Python implementation of nimi's Haskell answer. Golfing suggestions welcome.

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