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:

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

Optimizer · Accepted Answer · 2015-06-02 10:34:32Z

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

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

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

{ee::+W%}_q~%z%:+:* (19 bytes) Input format: [[1][1 1 1][1 1 1][1 1 1 1 1]] — Dennis, Commented Jun 2, 2015 at 4:32

randomra · Accepted Answer · 2016-08-27 20:38:09Z

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.

Community · Accepted Answer · 2020-06-17 09:04:33Z

4

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered May 31, 2015 at 23:59

Maltysen

25.8k4 gold badges55 silver badges127 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 1, 2015 at 8:47

isaacg

42.1k5 gold badges73 silver badges213 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 1, 2015 at 11:02

Sp3000

61.9k13 gold badges115 silver badges287 bronze badges

Add a comment |

nimi · Accepted Answer · 2015-06-01 18:34:20Z

3

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.

answered Jun 1, 2015 at 18:34

nimi

35.9k4 gold badges34 silver badges99 bronze badges

Add a comment |

Community · Accepted Answer · 2017-04-13 12:39:07Z

2

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

edited Apr 13, 2017 at 12:39

CommunityBot

1

answered Aug 26, 2016 at 19:10

Sherlock9

12.3k1 gold badge30 silver badges68 bronze badges

\$\begingroup\$ Welcome to Python golfing! You can do z and _ or 1 as z==[]or _ when z is a list, using the fact that True==1. Python's function declarations are wordier than Haskell, so it often gives a good payoff to define a single recursive function that does both the inner and outer recursive loops, though I don't know how feasible that is here. \$\endgroup\$
– xnor
Commented Aug 26, 2016 at 19:21
\$\begingroup\$ @xnor "Welcome to Python golfing"? \$\endgroup\$
– Sherlock9
Commented Aug 26, 2016 at 19:23
\$\begingroup\$ Oh, sorry, you do golf in Python. I associate you with Actually. \$\endgroup\$
– xnor
Commented Aug 26, 2016 at 19:28
\$\begingroup\$ @xnor Long, long before I started in Actually, I was golfing in Python. I'm a little miffed that you don't remember :P \$\endgroup\$
– Sherlock9
Commented Aug 26, 2016 at 19:30
\$\begingroup\$ I can't speak for xnor, but I recognize users mainly by their avatar. \$\endgroup\$
– Dennis
Commented Aug 27, 2016 at 2:26

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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)

Reto Koradi · Accepted Answer · 2015-06-01 04:14:55Z

1

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.

edited Jun 1, 2015 at 4:14

answered Jun 1, 2015 at 4:10

Reto Koradi

4,9311 gold badge13 silver badges19 bronze badges

1

\$\begingroup\$ Looks like you're not using m? \$\endgroup\$
– xnor
Commented Jun 1, 2015 at 4:11
\$\begingroup\$ Could have sworn that I deleted it! I remember noticing that I was only using it once, and substituting the only usage. But then I must have missed to actually delete the variable. :( \$\endgroup\$
– Reto Koradi
Commented Jun 1, 2015 at 4:12

Add a comment |

edc65 · Accepted Answer · 2015-06-01 13:24:08Z

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>

Stack Exchange Network

Hook length product

10 Answers 10

CJam, 20 19 bytes

J, 24 bytes

Pyth - 21 bytes

Pyth, 18 bytes

Python 2, 89 88 bytes

Haskell, 68 bytes

Python, 95 91 bytes

R, 174 bytes

Python 2, 135 128 bytes

JavaScript (ES6) 69

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
combinatorics
integer-partitions
or ask your own question.

Hot Network Questions

Hook length product

10 Answers 10

CJam, 20 19 bytes

J, 24 bytes

Pyth - 21 bytes

Pyth, 18 bytes

Python 2, 89 88 bytes

Haskell, 68 bytes

Python, 95 91 bytes

R, 174 bytes

Python 2, 135 128 bytes

JavaScript (ES6) 69

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfmathcombinatoricsinteger-partitions or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
math
combinatorics
integer-partitions
or ask your own question.