El principio del casillero establece que

Si N elementos se colocan en cuadros M , con N > M , entonces al menos un cuadro debe contener más de un elemento.

Para muchos, este principio tiene un estado especial en comparación con otros enunciados matemáticos. Como EW Dijkstra escribió :

Está rodeado de alguna mística. Las pruebas que lo utilizan a menudo se consideran algo especial, algo particularmente ingenioso.

El reto

El propósito de este desafío es ilustrar el principio del casillero utilizando representaciones artísticas ASCII. Específicamente:

1. Tomar como entrada N(número de elementos) y M(número de cuadros), con Nno negativo y Mpositivo. Npuede ser menor que M(incluso si el principio no se aplica en ese caso).
2. Seleccione aleatoriamente una de las posibles asignaciones de elementos a cuadros. Cada tarea debe tener una probabilidad distinta de cero de ser elegida.

3. Produzca una representación artística ASCII de la tarea de la siguiente manera:

   • Hay Mlíneas, cada una correspondiente a un cuadro.
   • Cada línea comienza con un carácter que no es un espacio en blanco, como |.
   • Después de ese carácter hay otro carácter que no es un espacio en blanco, por ejemplo #, repetido tantas veces como haya elementos en ese cuadro.

Consideremos, por ejemplo N = 8, M = 5. Si el assigment seleccionada de artículos a las cajas se 4, 1, 0, 3, 0, la representación es

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

Una ejecución diferente (que resulta en una asignación diferente) del mismo programa podría dar

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

Hay cierta flexibilidad con respecto a la representación; vea abajo.

Reglas específicas

El código debería ejecutarse teóricamente para cualquier valor de Ny M. En la práctica, puede estar restringido por el tamaño de la memoria o las limitaciones del tipo de datos.

Dado que observar el resultado no es suficiente para determinar si todas las asignaciones tienen una probabilidad distinta de cero , cada envío debe explicar cómo el código logra eso, si no es obvio.

Se permiten las siguientes variaciones de representación :

• Se puede elegir cualquier par de caracteres diferentes que no sean espacios en blanco. Deben ser consistentes en todas las ejecuciones del programa.
• Las rotaciones de 90 grados de la representación son aceptables. Nuevamente, la elección debe ser consistente.
• Se permite el espacio en blanco al final o al final.

Como ejemplo con un formato de representación diferente, para N = 15, M = 6los resultados de dos ejecuciones del programa podrían ser

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

o

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

Del mismo modo, N = 5, M = 7podría dar, utilizando otra variación de la representación,

  *
* * * *
UUUUUUU

o

 *** **
UUUUUUU

o

   *
*  *
*  * 
UUUUUUU

Tenga en cuenta que el principio no es aplicable en este caso, porque N< M.

Reglas generales

Se permiten programas o funciones , en cualquier lenguaje de programación . Las lagunas estándar están prohibidas.

La entrada puede tomarse por cualquier medio razonable ; y con cualquier formato, como una matriz de dos números o dos cadenas diferentes.

Los medios de salida y el formato también son flexibles. Por ejemplo, la salida puede ser una lista de cadenas o una cadena con líneas nuevas; devuelto como argumento de salida de función o mostrado en STDOUT. En este último caso, no es necesario preocuparse por el ajuste de línea causado por el ancho limitado de la pantalla.

El código más corto en bytes gana.

Gelatina , 9 8 bytes

=þṗX¥S⁵*

Este es un enlace diádico que toma M como su argumento izquierdo y N como su argumento derecho. La salida es una matriz de enteros, donde 0 representa palomas y 1 representa agujeros.

Pruébalo en línea!

Cómo funciona

=þṗ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])&

Una función sin nombre que toma dos argumentos enteros, el número de cuadros, seguido del número de elementos.

Primero calcula todas las particiones posibles N+Men Mpartes exactamente positivas, y luego resta 1de cada partición. Esto nos da todas las particiones posibles Nen Mpartes no negativas (que de IntegerPartitionsotro modo no se generarían). Luego elige una partición aleatoria y barajala. Esto garantiza que todas las particiones ordenadas posibles con ceros estén permitidas. Finalmente, convierta cada bin de la partición en una línea de salida elevando 10 a la potencia correspondiente (de modo que cada línea se convierta 1000...en kceros). Un resultado de ejemplo podría verse así:

100
10000
1
10
10

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

Genera un número en [0, n], imprime esa cantidad de elementos y lo resta de n. Hace esto m veces.

Esto hace que sea muy poco probable que algo llegue al último cuadro, pero la pregunta solo pedía que cada salida fuera posible , no igualmente probable .

Lote, 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%%

¡Creo que 7 %signos consecutivos podrían ser una nueva mejor marca personal! Nota: esto produce resultados impares si alguna vez asigna más de 9 elementos al mismo cuadro; si eso es un problema, entonces para 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%%

Sí, eso es 28 %s en total en la segunda línea.

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,"");}

Toma entrada en stdin, por ejemplo:

echo "5 4" | ./pigeonhole

No generará cada salida con la misma probabilidad, pero es capaz de generar todas las combinaciones posibles.

Descompostura:

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
            "");
}

Se basa en el manejo de GCC del comportamiento indefinido de %0s: normalmente %0rellenará a cero un número entero o flotante, pero solo puede rellenar (nunca truncar), por lo que no es posible imprimir un espacio en blanco. Pero el comportamiento de las cadenas no está definido, y GCC decidió convertirlo en cero-pad de la misma manera, por lo que este cero-rellena una cadena vacía para poder escribir cero o más 0s.

Python 2, 102 99 97 90 bytes

m-1veces, elija una cantidad aleatoria xentre 0e n, inclusive y reste de n. A continuación, imprimir una 1y '0'*x.

Finalmente, imprimir 1y el resto del 0s. No todas las posibilidades, pero todas las configuraciones son posibles.

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

(Código reutilizado de la respuesta rota de Python).

Haskell, 114 94 bytes

import System.Random
n#m=map(10^).take m.until((==n).sum.take m)tail.randomRs(0,m)<$>newStdGen

Un enfoque de fuerza bruta: genera una lista infinita de números aleatorios, toma n números del comienzo de la lista, los resume y comprueba si son iguales a m. Si no, quite el primer elemento de la lista y repita.

Pruébalo en línea!

Nota: 73 bytes sin importar

EDITAR: guardó algunos bytes con el truco 10 ^ (¡ Pruebe la nueva versión en línea! )

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

Salida (8 5):

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

Salida (8 5):

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

C, 175 138 bytes

¡Gracias a @Dave por guardar 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++]);}

Pruébalo en línea!

AHK, 66 bytes

2-=1
Loop,%2%{
Random,r,0,%1%
Send,|{# %r%}`n
1-=r
}
Send,|{# %1%}

Seguí el mismo principio que orlp usando números aleatorios de 0 a N y luego restando de N. Desafortunadamente, no pude guardar bytes usando 10 ^ r debido a la forma en que funciona la función Enviar. Por desgracia y flojo. Aquí hay algunas salidas para n = 8, m = 5:

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

CJam, 30 31 21 bytes

:B1a*:C\{CBmrAt.*}*N*

La entrada es dos números n men la pila. Usos 1para el carácter de columna y 0para el carácter repetido.

Explicación:

: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|[`|`.."#"*_]}

Pruébalo en línea!

Esto crea una matriz de ceros y los incrementa en lugares aleatorios.

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

Descompostura :

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

Salidas para m=7y n=5:

Primera ejecución:

za
zaa
za
za
zaa

Segunda ejecución:

za
zaa
zaaa
z
za

Pruébalo en línea!

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}

Pruébalo en línea!

Debido al método de asignación de las filas, esto tenderá a colocar más hacia abajo, aunque existe una pequeña posibilidad de que la parte superior obtenga algo.

Ruby, 52 bytes

->(n,m){r=Array.new(m){?|};n.times{r[rand m]+=?#};r}

Crea una función anónima que toma dos enteros como argumentos y devuelve una matriz de cadenas:

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

Devuelve una lista de cadenas.

Javascript (ES7), 75 bytes

(N,M)=>{for(r='';M;M--,N-=x=~~(Math.random()*(N+1)),r+=10**x+`
`);return r}

Pensé que era inteligente para proponer los poderes de la idea 10 solo para darme cuenta de que la mayoría de las respuestas ya estaban usando eso.

AWK, 78 bytes

{srand();for(;n++;)c[k]=c[k=int($2*rand())]"#"}END{for(;j<$2;)print"|"c[j++]}

Toma 2 argumentos, primero el número de elementos, luego el número de cajas. Comienza por sembrar el generador de números aleatorios para que cada ejecución sea diferente. Luego, simplemente crea cadenas en una matriz, Ejemplo de uso:

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)

Con formato

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

Salida de muestra

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

Hay espacios en blanco finales ya que cada entrada de matriz se muestra con una pestaña entre ellos, pero esto debería ser aceptable según las especificaciones.

Esto me parece una implementación muy simplista, así que estoy seguro de que esto podría mejorarse.

Gracias a @Luis Mendo por sus sugerencias.

Octava , 62 54 bytes

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

Función anónima que toma dos números y genera una matriz 2D de caracteres con >cuadros y * objetos. Todos los resultados son igualmente probables.

Pruébalo en línea!

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

Cada tarea debe tener una probabilidad distinta de cero de ser elegida.

Este criterio hizo que este programa fuera mucho más fácil de escribir.

Ejemplo de E / S:

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

Explicación:

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, 73 64 58 bytes

Actualización n. ° 3

Parece que necesito la clasificación, ya que de lo contrario obtengo enteros negativos. Sin embargo, reemplacé disp(sprintf(...))con fprintf(...)ahora, por lo que la respuesta sigue siendo 58 bytes.

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

Actualización n. ° 2:

Me di cuenta de que no necesitaba ordenar la matriz, y de hecho la clasificación reduciría el promedio de números en la matriz. Entonces borré la sort(...)parte. Tenga en cuenta que la salida sigue siendo la misma, por lo que no estoy actualizando la "salida de muestra".

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

¡Finalmente acercándome a la respuesta de Octave de Luis! :RE

Actualización n. ° 1:

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

En lugar de convertir a cadena, solo visualizo números directamente. Podría reducir a 58 bytes, quitando el disp(...), pero luego obtengo el extra ans =con solo sprintf, y no sé si eso es aceptable.

Código inicial:

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

Gracias a algunas sugerencias de Luis , me libré del bucle en mi respuesta anterior . Ahora primero creo una matriz vertical de mnúmeros aleatorios que suman n(diff([0;sort(randi(n,m-1,1));n]) ), luego los uso como exponentes de 10, los convierto en una cadena, los justifico a la izquierda y los visualizo.

Técnicamente podría deshacerme del disp (...) para guardar otros 6 bytes, pero luego se imprime un "ans" que puede violar las especificaciones. También puede haber una forma de cambiarlos a cadena y justificar a la izquierda para obtener el formato final deseado, por lo que estoy abierto a sugerencias.

Salida de muestra:

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

Nota : He cambiado mi función a una función anónima aquí, basada en sugerencias. En el resultado de la muestra, lo he asignado aafin de demostrar. Espero que esto no viole las especificaciones, pero si lo hace, hágamelo saber y lo cambiaré.

Apilado , 29 bytes

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

Pruébalo en línea!

Se comporta construyendo una matriz de Msingletons que contienen '|', y luego sumando '#'a una matriz elegida aleatoriamente N.

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

Pruébalo en línea!

• Se agregaron 15 bytes: la edición anterior fue un poco defectuosa, algunos piegons quedaron fuera.
• Guardado 6 bytes: reemplazado si no por [n, x] [m> 1]
• 1 byte guardado: importación *

Carbón , 19 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

  Ｎ                 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