Code golf: Distributing the balls (I)

Question

Challenge

In this task you have compute the number of ways we can distribute A balls into B cells with with every cell having at-least one ball.

The inputs A and B are given in a single line separated by a blank,the inputs are terminated by EOF.

You may like to check your solutions here.

Input

0 0
1 0
12 4
6 3
18 17
20 19
15 13
18 9
20 20
17 14
9 2
14 13
18 11

Output

1
0
14676024
540
54420176498688000
23112569077678080000
28332944640000
38528927611574400
2432902008176640000
21785854970880000
510
566658892800
334942064711654400

Constraints

• Every A and B can be distinguishable.
• 0 <= A,B <= 20
• You can use any language of your choice
• Shortest solution wins!

Answer 1

JavaScript (90 93)

function f(a,b){n=m=r=1;for(i=b;i>0;n*=-1){r+=n*m*Math.pow(i,a);m=m*i/(b-i--+1)}return--r}

http://jsfiddle.net/RDGUn/2/

Obviously, any math-based language such as APL will beat me because of syntax verbosity and lack of built-in mathematical constructs :)

Edit Also, I don't have any input-related functionality except parameters passed into the function, not sure how to use standard input with JavaScript...

Edit: Move i-- into m=m* expression; move n*=-1 into for; start r=1 to combine assignments and remove extraneous one on return. (save 3 chars)

Answer 2

Golfscript - 56 50 49 48 41 40 38 37 chars

n%{~),{!}%\{0.@{.@+2$*@)@}/;;]}*)p;}/

Note: this handles multiple lines of input, is fast (1/8 secs to do the test cases), and doesn't break for any legal input.

(The first version was also my first ever Golfscript program; thanks to eBusiness for pointing out several tricks I missed).

In order to make this a useful educational post too, here's an explanation of how it works. We start with the recurrence f(n, k) = k * (f(n-1, k) + f(n-1, k-1)). This can be understood combinatorically as saying that to place n distinguishable balls in k distinguishable buckets such that each bucket contains at least one ball, you pick one of the k buckets for the first ball (k *) and then either it will contain at least one more ball (f(n-1, k)) or it won't (f(n-1, k-1)).

The values resulting from this form a grid; taking n as the row index and k as the column index and indexing both from 0 it starts

1   0   0   0    0    0   0 ...
0   1   0   0    0    0   0 ...
0   1   2   0    0    0   0 ...
0   1   6   6    0    0   0 ...
0   1  14  36   24    0   0 ...
0   1  30 150  240  120   0 ...
0   1  62 540 1560 1800 720 ...
.   .   .   .    .    .   . .
.   .   .   .    .    .   .  .
.   .   .   .    .    .   .   .

So turning to the program,

n%{~ <<STUFF>> }/

splits the input into lines and then for each line evaluates it, putting n and k on the stack, and then calls <<STUFF>>, which is as follows:

),{!}%\{0.@{.@+2$*@)@}/;;]}*)p;

This computes the first k+1 entries of the n+1th row of that grid. Initially the stack is n k.
), gives stack of n [0 1 2 ... k]
{!}% gives stack of n [1 0 0 ... 0] where there are k 0s.
\{ <<MORE STUFF>> }* brings the n to the top and makes it the number of times we execute <<MORE STUFF>>.
Our stack currently is a row of the table: [f(i,0) f(i,1) ... f(i,k)]
0.@ puts a couple of 0s before that array. The first one will be j and the second one will be f(i,j-1).
{ <<FINAL LOOP>> }/ loops through the elements of the array; for each one it puts it on top of the stack and then executes the loop body.
.@+2$*@)@ is boring stack manipulation to take ... j f(i,j-1) f(i,j) and yield ... j*(f(i,j-1)+f(i,j)) j+1 f(i,j)
;;] pops off the left-over k+1 f(i,k) and gathers everything into an array, ready for the next go round the loop.
Finally, when we've generated the nth row of the table,
)p; takes the last element, prints it, and discards the rest of the row.

For posterity, three 38-char solutions on this principle:
n%{~),{!}%\{0.@{.@+@.@*\)@}/;;]}*)p;}/
n%{~),{!}%\{0:x\{x\:x+1$*\)}/;]}*)p;}/
n%{~),{!}%\{0.@{@1$+2$*\@)}/;;]}*)p;}/

Answer 3

Golfscript - 26 chars

Warning: The 12 4 case needs a lot of memory (although not as much as the answer below) and takes a quite a while to run

~:)\?:x,{x+)base(;.&,)=},,

---

Obviously this answer has some problems, but I will leave it here because the comments refer to it and mellamokb's answer is based off it.

Golfscript - 24 chars

Warning: The 12 4 case needs a lot of memory and takes a quite a while to run

~:o)\?,{o)base[0]-,o=},,

Answer 4

J, 40

4 :'|-/x(^~*y!~])i.1x+y'/&.".;._2(1!:1)3 

E.g

4 :'-/((x^~|.@:>:)*y&(!~))i.y'/x:".>{.;:(1!:1)3
15 13
28332944640000

<1sec for all test cases.

Edits

• (52 → 47) Reduce with -/ instead of alternating (1 _1)* (J-B's idea)
• (47 → 53) Noticed multiline input requirement :-/
• (53 → 48) Exploit symmetry of binomials.
• (48 → 48) Make tacit!
• (48 → 41)
• (41 → 40) Squeeze increment+conversion into 1x+

Answer 5

Common Lisp (83)

(defun b (x y)
  (if (= (* x y) 0)
      (if (= (+ x y) 0) 1 0)
      (* y (+ (b (decf x) y) (b x (1- y)))))))

It seems like there should be a shorter way to test the base cases, but nothing occurs to me offhand.

Answer 6

J, 38 to 42

Depending on your strictness preferences about interactive languages and output presentation, take your pick from the J spectre of solutions:

• 38 shortest interactive: 4 :'|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
  Launch jconsole, enter it, then paste the input (end with C-d). You'll notice the output is space-separated (J is a vector language, it performs the computation on the whole input as a whole and returns it as a 1D vector, whose default presentation is on a single line). I consider that ok, the spirit of this problem is computation, not presentation. But if you insist on having newlines instead:
• 39 longer interactive: 4 :'|-/(!&y*^&x)i.1x+y'/&.".;._2(1!:1)3
  Replacing Compose (&) with Under (&.) returns a vector of strings, whose presentation ends up on separate lines.
• 42 batch mode: 4 :'echo|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
  Run from the command line as $ jconsole balls.ijs < balls.in

If you voted this up, you might want to go give Eelvex's solution some credit as well.

Answer 7

GolfScript - 45 38 36 characters

Medium-force dirty implementation recurrence relation (38 36 characters):

n%{~{.2$*{\(.2$f\2$(f+*}{=}if}:f~p}/

The recurrence relation I stole from Peter Taylors solution, it goes like this:

f(x, y) = y * ( f(x-1, y) + f(x-1, y-1) )

With special cases if either variable is 0.

My implementation does not reuse previous results, so each function call branch to two new calls, unless one of the zero cases have been reached. This give a worst case of 2^21-1 function calls which takes 30 seconds on my machine.

Light-force series solution (45 characters):

n%{~.),0\{.4$?3$,@[>.,,]{1\{)*}/}//*\-}/p;;}/

Answer 8

J, 55 characters

(wd@(4 :'(y^x)--/(!&y*^&x)|.i.y')/@".@,&'x');._2(1!:1)3

• Passes current test cases. I think I understand the math...
• j602, console only (wd). Input on stdin, output on stdout.

Bash test script:

jconsole disballs.ijs <<END
12 4
6 3
END

Answer 9

Python 140 Chars

import sys
f=lambda n,k:(n and k and n>=k and k*(f(n-1,k-1)+f(n-1,k)))or(n+k==0 and 1)or 0
for l in sys.stdin:print f(*(map(int,l.split())))

Answer 10

dc, 100 chars

[0q]s5[1q]s6[l2l3>5l3 0>5l2 0=6l2 1-S2l3dS3 1-S3l1xL3s9l1xL2s9+L3*]s1[?z0=5S3S2l1xL3L2+s9fs9l4x]ds4x

Alas, dc doesn't seem to be supported by ideone. There may be a character or two still to squeeze out, but it's bedtime.

Note: this supports multiple lines of input, has sufficient precision to give the correct output even for 20 19 (curse you, Perl, for the time I wasted debugging my solution!), and gives the correct output for 0 0.

Suggestions from Nabb allow shortening at least as far as

[0q]sZ[1q]sI[?z0=ZSkSn[lnlk>Zlk0>Zln0=Iln1-SnlkdSk1-SklFxLks9lFxLns9+Lk*]dsFxfs9l4x]ds4x

at the cost of leaving junk in the register stacks (and thus running out of memory if we compute billions of answers).

Answer 11

Golfscript (28 31 37)

~):$\.($\?:@;?,{@+}%{$base$,\-[0]=},,

Modification to gnibbler's GolfScript solution. I think this is a working solution - tested with [3,2], [4,2], [6,3], and [9,2] with correct answers. (I used $ and @ for variables to tighten up space around the base keyword).

There are two problems with gnibbler's current solution.

1. Checking length after removing [0] does not guarantee a solution, because [1,1,1,1] would be valid for input [4,2], even though all 4 balls are in the same cell (1). So I've modified to check also that all digits are used, i.e., the array contains 1-2, so each cell contains at least one ball.
2. In the case of input [4,2], the base-3 format of numbers 0-27 are less than 4 digits, and the left-most 0's are not included. That means [1,1] is included as a valid solution, even though it is technically actually [0,0,1,1], which means the first two balls are not placed anywhere. I fix by adding 3^3 to every entry (generically k^n-1 to the array of k^n entries) so that the first entries are shifted upward to having at least n-digits in base-k format, and the last entries will automatically be invalid anyway and won't affect the solution (because the second digit will always be 0).

Edit

~:@\?:$,{$+}%{@base(;@,\-,0=},,

`~:@\?:$,{$+@base(;@,\-,0=},,`

Better solution yet! No need to increment, just add to all of the numbers so they start with [1], and no digits will be missing (including the left-padding of 0's) once you decon that first digit. This solution should work and has been tested with same entries above. It's also a lot faster because we aren't incrementing before taking exponent to generate the array (but still suffers from same performance / memory problem for larger input).

Edit: Use gnibbler's idea of moving the addition of $ inside of the filter instead of as an extra step. (save 3 chars).

Answer 12

05AB1E, 19 bytes

#D`ULX.Œʒ€gßĀ}gs_P+

NOTE: It's extremely slow, and already times out for 12 4. It is working as intended, though. Will see if I can come up with an alternative method which works for all test cases in a reasonable time. See below for a much faster version which runs all test cases in less than a second.

Try it online or verify a few more (of the smaller) test cases.

Explanation:

#               # Split the (implicit) input-string by spaces
 D              # Duplicate it
  `             # Push both values to the stack
   U            # Pop and store the second value in variable `X`
    L           # Create a list in the range [1,n] for the first value
     X.Π       # Create a list of all possible ways to divide this list into `X` partitions
                # (including empty sublists, so we'll have to filter them out:)
        ʒ       # Filter this list of lists of partition-lists by:
         €g     #  Get the length of each partition-list
           ß    #  Get the minimum length
            Ā   #  Truthify; 0 remains 0 (falsey); anything else becomes 1 (truthy)
             }g # After the filter, take the length to get the amount left
 s              # Swap so the duplicated input-list is at the top of the stack again
  _             # Check for each value if they're equal to 0 (1 if truthy; 0 if falsey)
   P            # Take the product of the two to check if both input-values are 0
    +           # And add it to the earlier calculated product (edge case for [0,0] = 1)
                # (After which the result is output implicitly)

---

05AB1E, 29 bytes

Here a much faster version which works for all test cases in about 0.5 seconds on TIO:

Î#R`V©LRvyYmX*NÈ·<*+Xy*®y->÷U

Port of @mellamokb's JavaScript answer, so make sure to upvote him!

Try it online or verify all test cases.

Explanation:

Î                    # Push (result=) 0 and the input
 #                   # Split the input by spaces
  R`                 # Push the values to the stack reversed
    V                # Pop and store the first value in variable `Y`
     ©               # Store the second value in variable `®` (without popping)
      LRv            # Loop `y` in the range [`®`,1], with index `N` in the range [0,`®`):
         yYm         #  Calculate `y` to the power `Y`
            X*       #  Multiply it by `X`
                     #  (Note: `X` is 1 before setting it to another value initially)
              NÈ     #  Check if index `N` is even (1 if truthy; 0 if falsey)
                ·<   #  Double it; and decrease it by 1 (1 if truthy; -1 if falseY0
                  *  #  Multiply it to the earlier number
                   + #  And add it to the result
         Xy*         #  Push `X` multiplied by `y`
         ®y->        #  Push `®` - `y` + 1
             ÷       #  Integer divide them
              U      #  Pop and store it as new variable `X`
                     # (output the result at the top of the stack implicitly after the loop)

NOTE: Works for edge case 0 0 in this case (unlike the JavaScript answer I ported this method from), because the L builtin will create a list [0,1].