# Pigeonhole Principle & Code Golf

The pigeonhole principle states that

If N items are put into M boxes, with N > M, then at least one box must contain more than one item.

For many, this principle has a special status compared to other mathematical enouncements. As E.W. Dijkstra wrote,

It is surrounded by some mystique. Proofs using it are often regarded as something special, something particularly ingenious.

## The challenge

The purpose of this challenge is to illustrate the pigeonhole principle using ASCII art representations. Specifically:

1. Take as input N (number of items) and M (number of boxes), with N non-negative and M positive. N may be smaller than M (even if the principle does not apply in that case).
2. Randomly select one of the possible assignments of items to boxes. Each assignment should have a non-zero probability of being picked.
3. Produce an ASCII art representation of the assignment as follows:

• There are M lines, each corresponding to a box.
• Each line starts with a non-whitespace character, such as |.
• Following that character is another non-whitespace character, such as #, repeated as many times as there are items in that box.

Consider for example N = 8, M = 5. If the selected assigment of items to boxes is 4, 1, 0, 3, 0, the representation is

|####
|#
|
|###
|


A different run (resulting in a different assignment) of the same program could give

|#
|##
|#
|#
|###


There is some flexibility regarding the representation; see below.

## Specific rules

The code should theoretically run for any values of N and M. In practice it may be restricted by memory size or data type limitations.

Since observing the output is not sufficient to determine if all assignments have non-zero probability, each submission should explain how the code achieves that, if not obvious.

The following representation variations are allowed:

• Any pair of different, non-whitespace characters can be chosen. They must be consistent across program executions.
• 90-degree rotations of the representation are acceptable. Again, the choice must be consistent.
• Trailing or leading whitespace is allowed.

As an example with a different representation format, for N = 15, M = 6 the results of two executions of the program could be

VVVVVV
@@@@@@
@@ @@@
@  @@
@


or

VVVVV
@@@ @
@@@ @
@ @ @
@ @ @
@


Likewise, N = 5, M = 7 could give, using another variation of the representation,

  *
* * * *
UUUUUUU


or

 *** **
UUUUUUU


or

   *
*  *
*  *
UUUUUUU


Note how the principle is not applicable in this case, because N <M.

## General rules

Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

Input can be taken by any reasonable means; and with any format, such as an array of two numbers or two different strings.

Output means and format are also flexible. For example, the output can be a list of strings or a string with newlines; returned as function output argument or displayed in STDOUT. In the latter case it is not necessary to worry about line wrapping caused by limited display width.

Shortest code in bytes wins.

• It actually took me until now to get the title... – Martin Ender Apr 2 '17 at 19:21
• @MartinEnder Is it that "pigeonhole principle" has more characters than "code golf", or is there some other joke? – dorukayhan Apr 3 '17 at 22:59
• @dorukayhan In a standard browser, look at the text slightly above the question title... – Luis Mendo Apr 3 '17 at 23:08

# Jelly, 9 8 bytes

=þṗX¥S⁵*


This is a dyadic link that takes M as its left and N as its right argument. Output is an array of integers, where 0 represents pigeons and 1 represents holes.

Try it online!

### How it works

=þṗX¥S⁵*  Main link. Left argument: m. Right argument: n

¥     Combine the two links to the left into a dyadic chain and call it
with arguments m and n.
ṗ        Compute the n-th Cartesian power of [1, ..., m], i.e., generate all
vectors of length n that consist of elements of [1, ..., m].
X       Pseudo-randomly choose one of those vectors with a uniform distribution.
=þ        Equal table; for each k in [1, ..., m] and each vector to the right,
compare the elements of the vector with k. Group the results by the
vectors, yielding a 2D Boolean matrix.
R    Range; map 1 to [1], 0 to [].
S   Take the sum of all columns.
⁵* Raise 10 to the resulting powers.


## Mathematica, 68 bytes

Print/@(10^RandomSample@RandomChoice[IntegerPartitions[+##,{#}]-1])&


An unnamed function that takes two integer arguments, the number of boxes, followed by the number of items.

It first computes all possible partitions of N+M into exactly M positive parts, and subtracts 1 from each partition afterwards. This gives us all possible partitions of N into M non-negative parts (which IntegerPartitions wouldn't generate otherwise). Then pick a random partition and shuffle it. This guarantees all possible ordered partitions with zeros are allowed. Finally, convert each bin of the partition to an output line by raising 10 to the corresponding power (such that each line becomes 1000... with k zeros). An example output might look like:

100
10000
1
10
10

• I believe PadRight wouldn't pad to M zeros if N < M. – LegionMammal978 Apr 2 '17 at 17:39
• @LegionMammal978 Thanks, managed to fix it at the same byte count. – Martin Ender Apr 2 '17 at 18:29
• ...I'm honestly impressed. I was about to do a similar solution, but PadRight's non-listability would make it much longer. – LegionMammal978 Apr 2 '17 at 19:29
• @LegionMammal978 Another way to avoid PadRight would be IntegerPartitions[#,{#2},0~Range~#]. – Martin Ender Apr 2 '17 at 19:31
• No buitltin? I'm surprised... :D But nice answer. I just need to figure out how it works first :P – HyperNeutrino Apr 3 '17 at 6:25

# Python 2, 77 86 bytes

from random import*
n,m=input()
exec'c=randint(0,n);n-=c;print 10**c;'*~-m
print 10**n


Generates a number in [0, n], prints that many items and substracts it from n. It does this m times.

This makes it very unlikely anything makes it to the last box, but the question only asked that every output be possible, not equally likely.

## Batch, 164 bytes

@for /l %%i in (1,1,%1)do @set h%%i=1
@for /l %%j in (1,1,%2)do @call set/ab=%%random%%%%%%%1+1&call set/ah%%b%%*=10
@for /l %%i in (1,1,%1)do @call echo %%h%%i%%


I think 7 consecutive % signs might be a new personal best! Note: this produces odd output should it ever assign more than 9 items to the same box; if that's a problem, then for 180 bytes:

@for /l %%i in (1,1,%1)do @set h%%i=1
@for /l %%j in (1,1,%2)do @call set/ab=%%random%%%%%%%1+1&call call set h%%b%%=%%%%h%%b%%%%%%0
@for /l %%i in (1,1,%1)do @call echo %%h%%i%%


Yes, that's 28 %s in total on the second line.

# C, 102 bytes

n,m;main(x){srand(time(0));for(scanf("%d %d",&n,&m);m--;n-=x)printf("|%0*s\n",x=m?rand()%(n+1):n,"");}


Takes input on stdin, e.g.:

echo "5 4" | ./pigeonhole


Won't generate each output with equal probability, but is capable of generating all possible combinations.

### Breakdown:

n,m;
main(x){
srand(time(0));             // Seed random number generator
for(scanf("%d %d",&n,&m);   // Parse input values into n and m
m--;                    // Loop through each bucket (count down)
n-=x)                   // Subtract number assigned to bucket from total
printf(                 // Output a formatted string using padding
"|%0*s\n",          // (turns out %0s will actually zero-pad a string!)
x=m?rand()%(n+1):n, // Calculate a number of items for this bucket
"");
}


Relies on GCC's handling of the undefined behaviour of %0s — normally %0 will zero-pad an integer or float, but it can only pad (never truncate), so it's not possible to print a blank. But the behaviour for strings isn't defined, and GCC decided to make it zero-pad the same way, so this zero-pads an empty string to be able to write zero-or-more 0s.

• Since functions are allowed, you could cut off a few characters by using a(b,c){...} instead of main and scanf. – Kevin Apr 3 '17 at 14:17

# Python 2, 1029997 90 bytes

m-1 times, chose a random amount x between 0 and n, inclusive and subtract it from n. Then print a 1 and '0'*x.

Finally, print 1 and the rest of 0s. Not at all equal chances, but all configurations are possible.

from random import*
n,m=input()
exec'x=randrange(n+1);n-=x;print 10**x;'*(m-1)
print 10**n


(Reused code from the broken Python answer.)

• I think this answer should've been a suggestion on my answer as it's literally the same answer with a small bug fix. – orlp Apr 2 '17 at 19:15
• @orlp If you look at the history of this answer, it just became that in the latest version. If I would have made it like this initially, I would have posted it as a comment instead. – L3viathan Apr 2 '17 at 19:17
• Ah then it's fine, the way it looked (and that you wrote 'reused code') made it look differently than it is. Sorry. – orlp Apr 2 '17 at 19:19
• @orlp No problem. Yours is working now and shorter than mine anyways, I can also delete this answer if you feel that it is too close to yours, I don't mind, just wanted to clarify that I didn't just copy-paste your answer. – L3viathan Apr 2 '17 at 19:21

import System.Random
n#m=map(10^).take m.until((==n).sum.take m)tail.randomRs(0,m)<$>newStdGen  A bit of a brute force approach: Generates an infinite list of random numbers, takes n numbers of the start of the list, sums them up, and checks if they're equal to m. If not, take the first element off the list and repeat. Try it online! Note: 73 bytes without the import EDIT: Saved some bytes with the 10^ trick (Try the new version online!) ## REXX, 74 bytes arg n m m=m-1 o.=@ do n a=random(m) o.a=o.a||# end do a=0 to m say o.a end  Output (8 5): @# @### @ @# @###  Output (8 5): @# @# @ @#### @##  # C, 175 138 bytes Thanks to @Dave for saving 37 bytes! i;f(n,m){char**l=calloc(m,8);for(i=0;i<m;)l[i]=calloc(n+1,1),*l[i++]=124;for(i=n+1;--i;)*strchr(l[rand()%m],0)=35;for(;i<m;)puts(l[i++]);}  Try it online! • Hi, a few things which could help you reduce this: calloc will give you 0-initialised memory (no need to set all the 0s yourself), strchr can find the end of a string, comma can chain operations, avoiding the need for {}, and x[0] == *x. Also watch out; you're not mallocing enough memory if all the items are in the same box. – Dave Apr 3 '17 at 11:17 # AHK, 66 bytes 2-=1 Loop,%2%{ Random,r,0,%1% Send,|{# %r%}n 1-=r } Send,|{# %1%}  I followed the same principal that orlp did using random numbers from 0 to N and then subtracting it from N. Unfortunately, I couldn't save bytes by using 10^r because of the way the Send function works. Alas and alack. Here are some outputs for n=8, m=5: |## |##### |## |## |# |## |## |# |##### | |### |# |# |## | |### |### | |### | | | |# | | | |# |### | |#####  ## CJam, 3031 21 bytes :B1a*:C\{CBmrAt.*}*N*  Input is two numbers n m on the stack. Uses 1 for the column character and 0 for the repeated character. Explanation: :B e# Store m in B (without deleting it from the stack) 1a e# Push 1 and wrap it in an array: [1] * e# Repeat the array m times :C e# Store this array in C (without deleting) \{ e# Do n times: CBmrAt e# Create an array of 1s with a random element replaced with 10. .* e# Vectorized multiplication: multiply the respective elements in the arrays. e# Effectively, we multiply a random value in the array by 10 (and add a 0 to the end). }* e# End loop. N* e# Join with newlines.  # Röda, 79 bytes f n,m{a=[0]*m i=0{{n-- a[i%m]++}if randomBoolean i++}while[n>0] a|[|.."#"*_]}  Try it online! This creates an array of zeroes and increments them at random places. # PHP, 100 bytes list($z,$m,$n)=$argv;$a=array_fill(0,$n,z);while($m>0){$a[rand(0,$n-1)].=a;$m--;}echo join("\n",$a);


Breakdown :

list($z,$m,$n)=$argv;     // assigns the input vars to $m and$n
$a=array_fill(0,$n,z);    // creates an array $a of$n elements containing 'z'
while($m>0){ // randomly populate array$a
$a[rand(0,$n-1)].=a;  //
$m--; // } // echo join("\n",$a);       // output $a contents separated by a new line  Outputs for m=7 and n=5 : First execution : za zaa za za zaa  Second execution : za zaa zaaa z za  Try it online! • You could use [,$m,$n]=$argv; from PHP 7.1 to save a few chars. You can replace \n with an actual line break to save 1 byte. you can use for(;$m-->0;)$a[rand(0,$n-1)].=a; to save the breaks, a $m and a semicolon. [,$m,$n]=$argv;$a=array_fill(0,$n,z);for(;$m-->0;)$a[rand()%$n].=a;echo join("\n",$a); 85 byte – Christoph Apr 4 '17 at 13:09 • This golfs down even further [,$m,$n]=$argv;for(;$m--;)${rand()%$n}.=a;for(;$n--;)echo"z${$n}\n"; 67 byte. – Christoph Apr 4 '17 at 13:22
• @Christoph I saw the notation [,$m,$n]=$argv; on other code-golfs but wasn't able to make it work either in my dev environment or on eval.in – roberto06 Apr 4 '17 at 14:03 • try it here: sandbox.onlinephpfunctions.com/code/…. – Christoph Apr 5 '17 at 6:37 • Nice. I think you can post your snippet as an answer since it differs quite a lot from mine ;) – roberto06 Apr 5 '17 at 7:15 # JavaScript, 105 bytes x=>y=>{s=[];for(;x>1;y-=t)s[--x]="|"+"#".repeat(t=Math.random()*(y+1)|0);s[0]="|"+"#".repeat(y);return s}  Try it online! Due to the method of assigning the rows, this will tend to place more towards the bottom, although there is a small chance that the top will get some. # Ruby, 52 bytes ->(n,m){r=Array.new(m){?|};n.times{r[rand m]+=?#};r}  Creates an anonymous function which takes two integers as arguments and returns an array of Strings: >> puts ->(n,m){r=Array.new(m){?|};n.times{r[rand m]+=?#};r}.call 7,5 |# |# |## |## |#  ## Python 2, 81 bytes from random import* def f(n,m):l=['#']*m;exec('l[randrange(m)]+="o";'*n);return l  Returns a list of strings. ## Javascript (ES7), 75 bytes (N,M)=>{for(r='';M;M--,N-=x=~~(Math.random()*(N+1)),r+=10**x+ );return r}  I thought I was clever for coming up with the powers of 10 idea only to realize that most answers were already using that. ## AWK, 78 bytes {srand();for(;n++;)c[k]=c[k=int($2*rand())]"#"}END{for(;j<$2;)print"|"c[j++]}  Takes 2 arguments, first the number of items, then the number of boxes. Starts by seeding the random number generator so each run is different. Then simply builds up strings in an array, Example usage: awk '{srand();for(;n++;)c[k]=c[k=int($2*rand())]"#"}END{for(;j<\$2;)print"|"c[j++]}' <<< "12 5"

Example output:
|##
|###
|##
|##
|###


## MATLAB, 103 94 bytes

function a(m,n)
d=@(p)disp(char([1,~(1:p)]+48));for i=1:m-1;p=randi([0,n]);d(p);n=n-p;end;d(n)


### With Formatting

function a(m,n)
for i=1:m-1
d=@(p)disp(char([1,~(1:p)]+48));  % inline function for displaying
p=randi([0,n]);              % picking a random number b/w 0 and n
d(p);                        % '1' represents the box/pigeonhole, with '0's denoting entries
n=n-p;
end
d(n);                            % writing the remaining entries/zeros


### Sample Output

>> a(4,7)
10
10000
10
10


There are trailing whitespaces since each array entry is displayed with a tab between them, but this should be acceptable as per specs.

This seems like a very simplistic implementation to me, so I'm sure this could be improved.

Thanks to @Luis Mendo for suggestions.

• You can save quite a few bytes defining the display statement as an anonymous function, to avoid writing it twice: d=@(p)disp(char([1,~(1:p)]+48));for i=1:m-1;p=randi([0,n]);d(p);n=n-p;end;d(n) – Luis Mendo Apr 5 '17 at 17:45
• @LuisMendo Thanks for the suggestion, I'll update. Can I also define my actual function the same way, eg. a=@(m,n)... since that will also reduce the number of bytes. How do people generally remove/shorten the "function name(args)" in MATLAB code-golf answers? – Krostd Apr 5 '17 at 23:50
• Yes, you could also use an anoymous function as the answer. You can even skip the a=. In this case you can't do that, in principle, because anonymous functions can't contain loops. But you could use the trick of putting everything into eval('...'). BTW, that's normally considered ugly and bad practice in Matlab, but here we like abusing languages :-) – Luis Mendo Apr 6 '17 at 0:00
• Hmm.. I'll update based on your suggestion and think some more about it and see if I can avoid the loop, though that seems unlikely. I can think of a logic that could do that, but not sure how to implement it.. I'm thinking of defining a number 10^n, and finding m numbers which are all powers of 10, and then just printing them out. It'll be exactly the same output as I have now.. :D Any suggestions? Feel free to post it as another answer. – Krostd Apr 6 '17 at 0:04
• I meant m factors (not just any numbers) – Krostd Apr 6 '17 at 0:20

# Octave, 62 54 bytes

@(n,m)strcat(62,(sum(randi(m,1,n)==(1:m)',2)>=1:n)*42)


Anonymous function that takes two numbers and outputs a 2D array of chars with > for boxes and * for objects. All results are equally likely.

Try it online!

# TI-Basic, 63 62 bytes

Prompt N,M
For(A,1,M
N→B
If M-A
randInt(0,N→B
":→Str0
For(C,1,B
Ans+"X→Str0
End
Disp Ans
N-B→N
End


Each assignment should have a non-zero probability of being picked.

This criteria made this program much easier to write.

Example I/O:

prgmPIDGEON
N=?5
M=?2
:XXXX
:X


Explanation:

Prompt N,M     # 5 bytes, input number of items, number of boxes
For(A,1,M      # 7 bytes, for each box
N→B            # 4 bytes, on last box, make sure the sum is met by adding N items
If M-A         # 5 bytes, if not last box
randInt(0,N→B  # 8 bytes, add random number of items from 0 to N to box A
":→Str0        # 6 bytes, first character
For(C,1,B      # 7 bytes, add B items to the box
Ans+"X→Str0    # 8 bytes
End            # 2 bytes
Disp Ans       # 3 bytes, print this box
N-B→N          # 6 bytes, subtract the items used in this box
End            # 1 byte, move on to next box


## MATLAB, 7364 58 bytes

### Update#3

I do need the sorting, it seems, since otherwise I get negative integers. I did replace disp(sprintf(...)) with fprintf(...) now, though, so the answer remains 58 bytes.

@(m,n)fprintf('%i\n',10.^diff([0;sort(randi(n,m-1,1));n]))


### Update#2:

I realized I didn't need to sort the array, and in fact sorting would actually reduce the average of numbers in the array. So I deleted the sort(...) part. Note that the output remains the same, so I am not updating the "sample output".

@(m,n)disp(sprintf('%i\n',10.^diff([0;randi(n,m-1,1);n])))


Finally closing in on the Octave answer by Luis! :D

### Update#1:

@(m,n)disp(sprintf('%i\n',10.^diff([0;sort(randi(n,m-1,1));n])))


Instead of converting to string, I just display numbers directly. I could reduce to 58 bytes, by removing the disp(...), but then I get the extra ans = with just sprintf, and don't know if that's acceptable.

### Initial code:

@(m,n)disp(strjust(num2str(10.^diff([0;sort(randi(n,m-1,1));n])),'left'))


Thanks to some suggestions by Luis, I got rid of the loop in my previous answer. Now I first create a vertical array of m random numbers adding up to n (diff([0;sort(randi(n,m-1,1));n])), then use them as exponents of 10, convert them to a string, left-justify them, and display them.

I could technically get rid of the disp(...) to save another 6 bytes, but then an "ans" gets printed which may violate specs. There may also be a way around to changing them to string and left-justifying to get the desired end format, so I'm open to suggestions.

### Sample output:

>> a=@(m,n)disp(strjust(num2str(10.^diff([0;sort(randi(n,m-1,1));n])),'left'));
>> a(4,6)
1000
10
100
1


Note: I have changed my function to an anonymous function here, based on suggestions. In the sample output, I have assigned that to a in order to demonstrate. I hope this does not violate specs, but if it does please let me know and I will change it.

• I just realized the top answer uses the same logic of 10^.. For what it's worth, and if it matters, I didn't use that as a reference for my answer.. (but dang, someone beat me to it! :P) – Krostd Apr 6 '17 at 1:50
• Also wanted to note credit to this answer for the idea of creating m random integers that add up to n, since I was stuck on that part for a long while.. (Still can't add more than 2 links in my answers, so including it in a comment) – Krostd Apr 6 '17 at 9:53

# Stacked, 29 bytes

('|')\rep\[:randin'#'push@.]*


Try it online!

Behaves by constructing an array of M singletons containing '|', then adding '#' to a randomly chosen array N times.

• Nice! And so all results are equally likely, right? – Luis Mendo Apr 7 '17 at 0:10
• @LuisMendo it should be, since randin uses the Fisher-Yates algorithm internally. (This is the same algorithm that the CJam answer uses FWIW) – Conor O'Brien Apr 7 '17 at 0:12

# Python 2, 80 95 89 88 bytes

from random import*
n,m=input()
while m:x=randint(0,n);print'1'+'0'*[n,x][m>1];m-=1;n-=x


Try it online!

• Added 15 Bytes: Previous edit was a bit flawed, some piegons were left out.
• Saved 6 Bytes: replaced if else by [n,x][m>1]
• Saved 1 Byte: import *

# Charcoal, 19 bytes

≔ＥＮ⟦⟧θＦＮ⊞‽θ#Ｅθ⁺|⪫ιω


Try it online! Link is to verbose version of code. Explanation:

  Ｎ                 Input M
Ｅ                  Map over implicit range
⟦⟧               Empty array
≔    θ              Assign resulting nested array to q

Ｎ            Input N
Ｆ             Loop over implicit range
θ         Nested array q
‽          Random element
#        Literal string
⊞           Append to array

θ      Nested array q
Ｅ       Map over array
ι  Current element
ω Empty string
⪫   Join
|    Literal string
⁺     Concatenate
Implicitly print on separate lines
`