15
\$\begingroup\$

We have 40 sticks of same widths but different heights. How many arrangements are there possible to put them next to each other so that when we look from right we see 10 sticks and when we look from left we again see exactly 10 sticks?

For example such an ordering is:An example ordering

Black sticks are hidden, red sticks are the ones you can see when you look from left, the blue sticks are the ones you can see when you look from right and purple one(i.e. the longest one) is the one that can be see seen from both sides.

As test cases:

  • If we had 3 sticks number of orderings to see 2 from left and 2 from right is 2
  • If we had 5 sticks number of orderings to see 3 from left and 3 from right is 6
  • If we had 10 sticks number of orderings to see 4 from left and 4 from right is 90720
\$\endgroup\$
6
  • 13
    \$\begingroup\$ You might want to avoid questions with a fixed output because the optimal code-golf answer will probably just print the result without calculating it. I'd recommend making the question have a few variable inputs, eg N sticks such that you see K of them from left/right, where N and K are input integers \$\endgroup\$ – Sp3000 May 12 '15 at 7:18
  • 4
    \$\begingroup\$ If you do change the spec so that programs take in input (I don't see why not - you already have the test cases), you might want to think about whether or not you want to put a time limit on programs. \$\endgroup\$ – Sp3000 May 12 '15 at 7:24
  • 1
    \$\begingroup\$ "Must use your posted program to calculate the 40/10 case" should be a good enough time limit. \$\endgroup\$ – feersum May 12 '15 at 8:50
  • 1
    \$\begingroup\$ I can't get over the fact that 10!/40 = 90720... is that coincidence? \$\endgroup\$ – Tim May 12 '15 at 15:48
  • 1
    \$\begingroup\$ @Tim Whats the significance of 90720? Zip code for Los Alamitos, CA? \$\endgroup\$ – Digital Trauma May 12 '15 at 18:16
8
\$\begingroup\$

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

The number of visible sticks is also called Skyscraper Numbers, after the pencil/grid game. This code is based on (only slightly altered) the formula from OEIS A218531. I don't know much PARI, but I really don't think there's much to golf out here.

Test cases are all shown at ideone.com. The result for f(40,10) is:

192999500979320621703647808413866514749680
\$\endgroup\$
3
  • 1
    \$\begingroup\$ There's a nice reason for the formula. The number of permutations with v left-visible sticks is the Stirling number s(n,v). If the tallest stick is at position k, then the left-visible sticks are that stick and the left-visible sticks in the sub-permutation to the left of k-1 values left of position k. So, to have v left-visible sticks and v right-visible sticks, one has s(k,v-1) choices to permute the left half, s(n-k-1,v-1) to permute the right half, and binomial(n-1,k) choices to split sticks into the two halves. \$\endgroup\$ – xnor May 12 '15 at 22:32
  • \$\begingroup\$ @xnor They give basically that explanation in the linked PDF, but yours is worded much better IMO. \$\endgroup\$ – Geobits May 12 '15 at 23:01
  • \$\begingroup\$ You can save 11 bytes: f(n,v,s=stirling)=abs(sum(k=1,n--,binomial(n,k)*s(k,v-1)*s(n-k,v-1))). This saves sterling to a variable for reuse, leaves off its last argument, since 1 is the default, and subtracts 1 from n once rather than three times. \$\endgroup\$ – Charles Sep 27 '16 at 7:43
1
\$\begingroup\$

Python 3, 259 bytes

Not very happy with this.

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)

Example input and output:

10 4
90720

It generates all the possible combinations of the provided range, and then loops through them, checking each number in them to see if it equal to the maximum of the previous numbers. It then does the same backwards, and if the count forwards (t) = the count backwards (d) = the given view number (k) it's a valid one. It adds this to a counter (c) and prints that at the end.

\$\endgroup\$
0
\$\begingroup\$

R, 104

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

De-golfed a little:

    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)))
    }
\$\endgroup\$
0
\$\begingroup\$

Pyth - 38 36 bytes

Basically a port of the R answer. Pretty slow, can't even complete 10, 4 online.

AGHQLlfqhS<bhT@bTUGlf!-,yTy_TH.pr1hG

The only things Pyth doesn't have are cummax and the == over vectors, but those only took a few bytes to implement.

Explanation and further golfing coming soon.

Try it here online.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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