Pigeonhole Principle & Code Golf

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

Python 2, 102 99 97 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.)

Answer 7

Haskell, 114 94 bytes

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

Answer 8

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!

Answer 9

CJam, 30 31 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.

Answer 10

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

@#
@#
@
@####
@##

Answer 11

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:

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

Answer 12

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.

Answer 13

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 *

Answer 14

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.

Answer 15

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!

Answer 16

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

Answer 17

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.

Answer 18

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

Answer 19

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.

Answer 20

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.

Answer 21

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:
|##
|###
|##
|##
|###

Answer 22

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!

Answer 23

MATLAB, 73 64 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.

Answer 24

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.

Answer 25

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