Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!
share|improve this question
    
Are there time limits? –  user475 Mar 28 '11 at 13:56
    
@Tim Nordenfur:Updated :-) –  Quixotic Mar 28 '11 at 13:59
    
That link is invalid for me. –  mellamokb Mar 28 '11 at 14:54
3  
@Debanjan I don't like the idea of pasting questions from SPOJ here. People submit their code for competing there and it would be unfair to them. –  fR0DDY Mar 29 '11 at 5:58
1  
@Debanjan, I see your reference and raise you Mathworld (eqn. 5 says that S(n,0) is 1 if n=0 and 0 otherwise). If you want I can find a reference for the stronger statement that Stirling2 is in the associative subgroup of the exponential Riordan group. –  Peter Taylor Mar 30 '11 at 14:42

11 Answers 11

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;}/

share|improve this answer
1  
Pretty good for a beginner, there is a few possible small scale reductions, immediately I find [0] -> 1,, the space after zip can just be removed, and the other space can be removed if you just store in an operator instead of k. I haven't stepped through your code yet, but I suspect you might get away with just using a value without putting it in an array in some of the spots. –  eBusiness Mar 30 '11 at 1:38
1  
+1,I don't understand Golfscript but this looks sufficiently fast,and yet very short. –  Quixotic Mar 30 '11 at 15:23
    
@eBusiness and @Peter Taylor:On a different note .. how much you guys rate Golfscript on the scale of easy to learn? –  Quixotic Mar 30 '11 at 15:26
    
@Debanjan, depends on what you already know. It's a functional stack-based language. I've used a functional languages before (SML - plus I've written functional-style code in OO languages), and I've used stack-based languages before (Java bytecode assembled with Jasmin, PostScript), so the only real hurdle I face is learning what operators are available. If you only know languages from the Algol family (C, Java, etc) then you'll have three hurdles to jump at once. –  Peter Taylor Mar 30 '11 at 16:00
    
@Debanjan - It's much easier than it looks, you can start writing code almost immediately, but of course it takes some time to learn all the little tricks. –  eBusiness Mar 30 '11 at 17:59

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)

share|improve this answer
    
You could use the spidermonkey shell - it at least has readline and print. I don't know what others here use. –  Jesse Millikan Mar 28 '11 at 22:05
    
@Jesse: Interesting. I'm going to lose anyway lol. –  mellamokb Mar 29 '11 at 3:11
    
prompt and alert are JavaScript's "standard" io, as they're the typical blocking io calls, despite the fact that you'd never typically use blocking io with JavaScript. –  zzzzBov Mar 30 '11 at 18:10

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+
share|improve this answer
1  
Hey! That was my idea! O:-) –  J B Mar 30 '11 at 11:03
    
Ok, I'll steal that 1x+ then, but that only buys me back 1 character, whereas you took 5! –  J B Mar 30 '11 at 15:20

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.

share|improve this answer

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.

share|improve this answer
    
You need an Under &. for it to work properly on interactive mode. –  Eelvex Mar 30 '11 at 15:16
    
@Eelvex you must have a different interpretation of "properly". I start jconsole, paste code, paste input, C-d, and receive the output. No under needed. What's yours? –  J B Mar 30 '11 at 15:19
    
Our codes combined: 4 :'|-/(!&y*^&x)i.1x+y'/&.".;._2(1!:1)3. 39 chars. –  Eelvex Mar 30 '11 at 15:20
    
Without echo or Under I get the output in one line only (instead of multiple lines). –  Eelvex Mar 30 '11 at 15:21
    
@Eelvex indeed, but that's not explicitely forbidden. –  J B Mar 30 '11 at 15:24

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;;}/
share|improve this answer

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
share|improve this answer
    
What does that j6xx's wd do? –  J B Mar 29 '11 at 4:39
    
I really meant j602... I'm guessing it's in j601 also. It's defined as echo, which is defined as 0 0&$@(1!:2&2). I'm not sure what that means, but it does something like pretty-print rank 1 items with a line break. (I'm just now noticing that uses 2 rather than 4... I think it still goes to stdout in console mode, at least.) –  Jesse Millikan Mar 29 '11 at 4:44
    
I'm having trouble running this code. Do I just type it into the console? –  mellamokb Mar 29 '11 at 12:38
    
@mellamokb I've using something like the test script above, with the program saved as disballs.ijs and the correct path to j602/bin/jconsole. –  Jesse Millikan Mar 29 '11 at 14:23
    
@Jesse: I'm running this on windows. I get << was unexpected at this time. Sorry I'm new to J input, I always used it in console mode. –  mellamokb Mar 29 '11 at 15:31

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=},,
share|improve this answer
2  
I can't figure how you came up with that code, not only will this method run out of memory for large inputs, I also can't figure what the increment operators are good for. That you actually hit the target for 6 3 seems to be nothing but luck. –  eBusiness Mar 29 '11 at 1:21
5  
+1 for the clown ~:o) –  mellamokb Mar 29 '11 at 3:11
2  
I don't understand Golfscript but as you said and I agree your approach is too slow. –  Quixotic Mar 29 '11 at 7:21
3  
@mellamokb, good on you for working out how it was supposed to work :) It only took 2 extra chars to fix that bug. Now we are in the murky area where the shortest code may be correct but not practical. Code-golf is riddled with insanely inefficient answers but microseconds vs seconds usually doesn't matter. This one is an extreme case (lots of memory too). Debanjan has indicated that the answers need to be faster, but this site is not SPOJ, this question is tagged code-golf –  gnibbler Mar 29 '11 at 22:59
1  
@gnibbler, 0 0 should produce 1; 0 k for any other k should produce 0; n 1 for n > 0 should produce 1. –  Peter Taylor Mar 30 '11 at 5:55

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())))
share|improve this answer

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

share|improve this answer
    
Registers are always single characters (you can use any character, which will make the code more readable), so l11 is parsed as l1 1 (you can use K as a single character token for 0 if you aren't going to change precision anyway). You can change the input loop to ?[...?z1=4]. You can inline the macro in register 1. And you can probably save heaps more characters in general, but I'll wait for it to be shorter to comprehend it. –  Nabb Mar 31 '11 at 12:17
    
@Nabb, ah, I didn't read the man page carefully enough. I'm only using 8 or 9 registers, so I didn't run into the consequences of my misunderstanding. Thanks. –  Peter Taylor Mar 31 '11 at 12:21

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

share|improve this answer
    
Breaks on input 0 0. –  Peter Taylor Mar 29 '11 at 20:44
    
Also appears to handle only one line of input. –  Peter Taylor Mar 29 '11 at 22:09
    
And breaks on n 1 for any n, causes it to hang. hmm.. –  mellamokb Mar 29 '11 at 23:10
1  
converting numbers to base 1 will do that :) –  gnibbler Mar 29 '11 at 23:26
    
@gnibbler: Do you have any suggestions? Will I just need to throw in some if statements at the beginning to catch those cases? Seems like I'll lose a lot of ground that way. –  mellamokb Mar 31 '11 at 13:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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