Zasada szuflady mówi, że

Jeśli N przedmiotów zostanie umieszczonych w skrzynkach M , gdzie N > M , to co najmniej jedno pudełko musi zawierać więcej niż jeden przedmiot.

Dla wielu ta zasada ma szczególny status w porównaniu do innych wypowiedzi matematycznych. Jak napisał EW Dijkstra ,

Otacza go jakaś tajemnica. Dowody używania tego są często uważane za coś wyjątkowego, coś szczególnie genialnego.

Wyzwanie

Celem tego wyzwania jest zilustrowanie zasady szuflady przy użyciu reprezentacji artystycznych ASCII. Konkretnie:

1. Weź jako dane wejściowe N(liczbę przedmiotów) i M(liczbę pól), z Nnieujemnymi i Mdodatnimi. Nmoże być mniejszy niż M(nawet jeśli zasada nie ma zastosowania w takim przypadku).
2. Losowo wybierz jedno z możliwych przypisań przedmiotów do skrzynek. Każde zadanie powinno mieć niezerowe prawdopodobieństwo wybrania.

3. Utwórz reprezentację artystyczną zadania ASCII w następujący sposób:

   • Istnieją Mlinie, każda odpowiadająca pudełku.
   • Każda linia zaczyna się od znaku spacji, na przykład |.
   • Po tym znaku znajduje się inny znak niebiałej spacji, taki jak #powtórzony tyle razy, ile jest elementów w tym polu.

Rozważmy na przykład N = 8, M = 5. Jeśli wybrany assigment elementów do pudełka jest 4, 1, 0, 3, 0, reprezentacja jest

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

Może to dać inny przebieg (skutkujący innym przypisaniem) tego samego programu

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

Istnieje pewna elastyczność w zakresie reprezentacji; patrz poniżej.

Szczegółowe zasady

Kod powinien teoretycznie działać na żadnej wartości z Ni M. W praktyce może być ograniczony wielkością pamięci lub ograniczeniami typu danych.

Ponieważ obserwacja wyniku nie jest wystarczająca do ustalenia, czy wszystkie przypisania mają niezerowe prawdopodobieństwo , każde przesłanie powinno wyjaśnić, w jaki sposób kod to osiąga, jeśli nie jest to oczywiste.

Dozwolone są następujące warianty reprezentacji :

• Można wybrać dowolną parę różnych, niebiałych znaków. Muszą być spójne we wszystkich wykonaniach programu.
• Dopuszczalne są obroty o 90 stopni. Ponownie wybór musi być spójny.
• Dozwolone są końcowe lub wiodące białe znaki.

Jako przykład z innego formatu reprezentacji, dla N = 15, M = 6wyniki dwóch egzekucjach programu może być

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

lub

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

Podobnie N = 5, M = 7może dawać, stosując kolejną wersję reprezentacji

  *
* * * *
UUUUUUU

lub

 *** **
UUUUUUU

lub

   *
*  *
*  * 
UUUUUUU

Zwróć uwagę, że zasada nie ma zastosowania w tym przypadku, ponieważ N< M.

Główne zasady

Programy lub funkcje są dozwolone w dowolnym języku programowania . Standardowe luki są zabronione.

Dane wejściowe można przyjmować dowolnymi rozsądnymi środkami ; i w dowolnym formacie, takim jak tablica dwóch liczb lub dwóch różnych ciągów.

Środki wyjściowe i format są również elastyczne. Na przykład wynikiem może być lista ciągów lub ciąg znaków z nowymi liniami; zwrócone jako argument wyjściowy funkcji lub wyświetlone w STDOUT. W tym drugim przypadku nie trzeba martwić się o zawijanie linii spowodowane ograniczoną szerokością wyświetlacza.

Najkrótszy kod w bajtach wygrywa.

Galaretka , 9 8 bajtów

=þṗX¥S⁵*

Jest to ogniwo diademowe, które przyjmuje M za lewy, a N za prawy argument. Dane wyjściowe to tablica liczb całkowitych, gdzie 0 oznacza gołębie, a 1 oznacza dziury.

Wypróbuj online!

Jak to działa

=þṗ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 bajtów

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

Nienazwana funkcja, która przyjmuje dwa argumenty liczb całkowitych, liczbę pól, a następnie liczbę elementów.

Najpierw oblicza wszystkie możliwe partycje N+Mna Mczęści dokładnie dodatnie, a następnie odejmuje 1od każdej partycji. To daje nam wszystkie możliwe partycje Nna Mczęści nieujemne (które IntegerPartitionsinaczej by nie wygenerowały). Następnie wybierz losową partycję i potasuj ją. To gwarantuje, że wszystkie możliwe uporządkowane partycje z zerami są dozwolone. Na koniec przekonwertuj każdy przedział partycji na linię wyjściową, podnosząc 10 do odpowiedniej mocy (tak, że każda linia staje 1000...się kzerami). Przykładowy wynik może wyglądać następująco:

100
10000
1
10
10

Python 2, 77 86 bajtów

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

Generuje liczbę w [0, n], drukuje tyle elementów i odejmuje ją od n. Robi to m razy.

To sprawia, że ​​jest bardzo mało prawdopodobne, aby cokolwiek dotarło do ostatniego pola, ale pytanie tylko zadawało, aby każde wyjście było możliwe , jednakowo mało prawdopodobne .

Partia, 164 bajty

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

Myślę, że 7 kolejnych %znaków może być nowym osobistym rekordem! Uwaga: generuje to nieparzyste dane wyjściowe, jeśli kiedykolwiek przypisze więcej niż 9 elementów do tego samego pudełka; jeśli to problem, to dla 180 bajtów:

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

Tak, to %łącznie 28 s na drugiej linii.

C, 102 bajty

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

Pobiera dane wejściowe na standardowe wejście, np .:

echo "5 4" | ./pigeonhole

Nie wygeneruje każdego wyjścia z jednakowym prawdopodobieństwem, ale jest w stanie wygenerować wszystkie możliwe kombinacje.

Awaria:

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

Polega na obsłudze przez GCC niezdefiniowanego zachowania %0s- zwykle %0zeruje liczbę całkowitą lub liczbę zmiennoprzecinkową, ale może tylko padać (nigdy nie obcinać), więc nie można wydrukować pustego miejsca. Ale zachowanie ciągów nie jest zdefiniowane, a GCC zdecydowało, aby wstawiać zero-pad w ten sam sposób, więc to zerowanie wstawia pusty ciąg, aby móc pisać zero lub więcej 0s.

Python 2, 102 99 97 90 bajtów

m-1razy, wybierz losową liczbę xmiędzy 0i nwłącznie i odejmij ją od n. Następnie wydrukuj a 1i '0'*x.

Na koniec wydrukuj 1i resztę 0s. Nie ma jednakowych szans, ale możliwe są wszystkie konfiguracje.

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

(Ponownie wykorzystany kod z niepoprawnej odpowiedzi w języku Python).

Haskell, 114 94 bajtów

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

Trochę brutalnej siły: generuje nieskończoną listę liczb losowych, bierze n liczb na początku listy, sumuje je i sprawdza, czy są równe m. Jeśli nie, usuń pierwszy element z listy i powtórz.

Wypróbuj online!

Uwaga: 73 bajty bez importu

EDYCJA: Zapisano niektóre bajty za pomocą sztuczki 10 ^ ( Wypróbuj nową wersję online! )

REXX, 74 bajty

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

Wyjście (8 5):

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

Wyjście (8 5):

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

C, 175 138 bajtów

Dzięki @Dave za oszczędność 37 bajtów!

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++]);}

Wypróbuj online!

AHK, 66 bajtów

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

Postępowałem zgodnie z tą samą zasadą, co orlp, używając liczb losowych od 0 do N, a następnie odejmując ją od N. Niestety nie mogłem zapisać bajtów przy użyciu 10 ^ r ze względu na sposób działania funkcji Send. Niestety i niestety. Oto kilka wyników dla n = 8, m = 5:

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

CJam, 30 31 21 bajtów

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

Dane wejściowe to dwie liczby n mna stosie. Używa 1znaku kolumny i 0znaku powtarzanego.

Wyjaśnienie:

: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 bajtów

f n,m{a=[0]*m
i=0{{n--
a[i%m]++}if randomBoolean
i++}while[n>0]
a|[`|`.."#"*_]}

Wypróbuj online!

Tworzy to tablicę zer i zwiększa je w losowych miejscach.

PHP, 100 bajtów

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

Awaria :

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

Wyjścia dla m=7i n=5:

Pierwsze wykonanie:

za
zaa
za
za
zaa

Drugie wykonanie:

za
zaa
zaaa
z
za

Wypróbuj online!

JavaScript, 105 bajtów

x=>y=>{s=[];for(;x>1;y-=t)s[--x]="|"+"#".repeat(t=Math.random()*(y+1)|0);s[0]="|"+"#".repeat(y);return s}

Wypróbuj online!

Ze względu na metodę przypisywania rzędów będzie to miało tendencję do umieszczania większej liczby w dolnej części, chociaż istnieje niewielka szansa, że ​​góra zdobędzie trochę.

Ruby, 52 bajty

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

Tworzy anonimową funkcję, która przyjmuje dwie liczby całkowite jako argumenty i zwraca tablicę ciągów:

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

Python 2, 81 bajtów

from random import*
def f(n,m):l=['#']*m;exec('l[randrange(m)]+="o";'*n);return l

Zwraca listę ciągów.

JavaScript (ES7), 75 bajtów

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

Pomyślałem, że jestem sprytny, gdy wpadłem na pomysł 10 mocy, by zdać sobie sprawę, że większość odpowiedzi już tego używała.

AWK, 78 bajtów

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

Przyjmuje 2 argumenty, najpierw liczbę elementów, a następnie liczbę pól. Zaczyna się od uruchomienia generatora liczb losowych, aby każdy przebieg był inny. Następnie po prostu buduje ciągi w tablicy, przykład użycia:

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 bajty

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)

Z formatowaniem

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

Przykładowe dane wyjściowe

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

Są spacje końcowe, ponieważ każda pozycja tablicy jest wyświetlana z tabulatorem między nimi, ale powinno to być dopuszczalne zgodnie ze specyfikacją.

Wydaje mi się to bardzo uproszczoną implementacją, więc jestem pewien, że można to poprawić.

Dzięki @Luis Mendo za sugestie.

Oktawa , 62 54 bajty

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

Anonimowa funkcja, która pobiera dwie liczby i generuje tablicę 2D znaków >dla pól i *obiektów. Wszystkie wyniki są równie prawdopodobne.

Wypróbuj online!

TI-Basic, 63 62 bajty

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

Każde zadanie powinno mieć niezerowe prawdopodobieństwo wybrania.

Te kryteria znacznie ułatwiły pisanie tego programu.

Przykład I / O:

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

Wyjaśnienie:

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 bajtów

Aktualizacja nr 3

Wygląda na to, że potrzebuję sortowania, ponieważ w przeciwnym razie otrzymam ujemne liczby całkowite. Zastąpiłem disp(sprintf(...))go fprintf(...)teraz, więc odpowiedź pozostaje 58 bajtów.

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

Aktualizacja nr 2:

Uświadomiłem sobie, że nie muszę sortować tablicy, a w rzeczywistości sortowanie zmniejszyłoby średnią liczb w tablicy. Więc usunąłem sort(...)część. Zauważ, że dane wyjściowe pozostają takie same, więc nie aktualizuję „próbki wyjściowej”.

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

Wreszcie zamykam odpowiedź Luisa na oktawę! :RE

Aktualizacja nr 1:

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

Zamiast konwertować na ciąg, po prostu wyświetlam liczby bezpośrednio. Mógłbym zredukować do 58 bajtów, usuwając disp(...), ale potem dostaję dodatkowy ans =przy pomocy tylko sprintf i nie wiem, czy to dopuszczalne.

Kod początkowy:

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

Dzięki niektórym sugestiom Luisa pozbyłem się pętli w poprzedniej odpowiedzi . Teraz najpierw tworzę pionową tablicę mliczb losowych, dodając do n( diff([0;sort(randi(n,m-1,1));n])), a następnie używam ich jako wykładników liczby 10, przekształcam je w ciąg znaków, wyrównuję do lewej i wyświetlam.

Mógłbym technicznie pozbyć się disp (...), aby zapisać kolejne 6 bajtów, ale wtedy drukowany jest „ans”, który może naruszać specyfikację. Może być również sposób na zmianę ich na ciąg i justowanie w lewo, aby uzyskać pożądany format końcowy, więc jestem otwarty na sugestie.

Przykładowe dane wyjściowe:

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

Uwaga : w oparciu o sugestie zmieniłem tutaj funkcję na funkcję anonimową. W przykładowym wyjściu przypisałem toaw celu zademonstrowania. Mam nadzieję, że nie narusza to specyfikacji, ale jeśli tak, proszę dać mi znać, a ja to zmienię.

Ułożone , 29 bajtów

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

Wypróbuj online!

Zachowuje się, konstruując tablicę Msingletonów zawierających '|', a następnie dodając '#'do losowo wybranych Nczasów tablicy .

Python 2 , 80 95 89 88 bajtów

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

Wypróbuj online!

• Dodano 15 bajtów: poprzednia edycja była nieco wadliwa, niektóre piegony zostały pominięte.
• Zapisano 6 bajtów: zastąpione, jeśli inaczej, przez [n, x] [m> 1]
• Zapisano 1 bajt: import *

Węgiel drzewny , 19 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

  Ｎ                 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