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:
- Weź jako dane wejściowe
N
(liczbę przedmiotów) iM
(liczbę pól), zN
nieujemnymi iM
dodatnimi.N
może być mniejszy niżM
(nawet jeśli zasada nie ma zastosowania w takim przypadku). - Losowo wybierz jedno z możliwych przypisań przedmiotów do skrzynek. Każde zadanie powinno mieć niezerowe prawdopodobieństwo wybrania.
Utwórz reprezentację artystyczną zadania ASCII w następujący sposób:
- Istnieją
M
linie, 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.
- Istnieją
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 N
i 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 = 6
wyniki dwóch egzekucjach programu może być
VVVVVV
@@@@@@
@@ @@@
@ @@
@
lub
VVVVV
@@@ @
@@@ @
@ @ @
@ @ @
@
Podobnie N = 5
, M = 7
moż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.
Odpowiedzi:
Galaretka ,
98 bajtówJest 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
źródło
Mathematica, 68 bajtów
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+M
naM
części dokładnie dodatnie, a następnie odejmuje1
od każdej partycji. To daje nam wszystkie możliwe partycjeN
naM
części nieujemne (któreIntegerPartitions
inaczej 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 staje1000...
sięk
zerami). Przykładowy wynik może wyglądać następująco:źródło
PadRight
że nie wstawiłbyM
zer do zera, jeśliN
<M
.PadRight
brak możliwości umieszczenia go na liście wydłużyłby go znacznie dłużej.PadRight
byłobyIntegerPartitions[#,{#2},0~Range~#]
.Python 2,
7786 bajtówGeneruje 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 .
źródło
Partia, 164 bajty
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:Tak, to
%
łącznie 28 s na drugiej linii.źródło
C, 102 bajty
Pobiera dane wejściowe na standardowe wejście, np .:
Nie wygeneruje każdego wyjścia z jednakowym prawdopodobieństwem, ale jest w stanie wygenerować wszystkie możliwe kombinacje.
Awaria:
Polega na obsłudze przez GCC niezdefiniowanego zachowania
%0s
- zwykle%0
zeruje 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ęcej0
s.źródło
a(b,c){...}
zamiastmain
iscanf
.Python 2,
102999790 bajtówm-1
razy, wybierz losową liczbęx
między0
in
włącznie i odejmij ją od n. Następnie wydrukuj a1
i'0'*x
.Na koniec wydrukuj
1
i resztę0
s. Nie ma jednakowych szans, ale możliwe są wszystkie konfiguracje.(Ponownie wykorzystany kod z niepoprawnej odpowiedzi w języku Python).
źródło
Haskell,
11494 bajtówTrochę 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! )
źródło
REXX, 74 bajty
Wyjście (8 5):
Wyjście (8 5):
źródło
C,
175138 bajtówDzięki @Dave za oszczędność 37 bajtów!
Wypróbuj online!
źródło
calloc
da ci pamięć inicjowaną przez zero (nie musisz sam ustawiać wszystkich zer),strchr
może znaleźć koniec łańcucha, przecinek może łańcuch operacji, unikając potrzeby{}
, ix[0] == *x
. Uważaj też; nie maszmalloc
wystarczającej ilości pamięci, jeśli wszystkie elementy znajdują się w tym samym pudełku.AHK, 66 bajtów
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:
źródło
CJam,
303121 bajtówDane wejściowe to dwie liczby
n m
na stosie. Używa1
znaku kolumny i0
znaku powtarzanego.Wyjaśnienie:
źródło
Röda , 79 bajtów
Wypróbuj online!
Tworzy to tablicę zer i zwiększa je w losowych miejscach.
źródło
PHP, 100 bajtów
Awaria :
Wyjścia dla
m=7
in=5
:Pierwsze wykonanie:
Drugie wykonanie:
Wypróbuj online!
źródło
[,$m,$n]=$argv;
PHP 7.1, aby zapisać kilka znaków. Możesz zastąpić\n
faktycznym podziałem linii, aby zaoszczędzić 1 bajt. możesz użyćfor(;$m-->0;)$a[rand(0,$n-1)].=a;
do zapisania przerw, a$m
i średnika.[,$m,$n]=$argv;$a=array_fill(0,$n,z);for(;$m-->0;)$a[rand()%$n].=a;echo join("\n",$a);
85 bajtów[,$m,$n]=$argv;for(;$m--;)${rand()%$n}.=a;for(;$n--;)echo"z${$n}\n";
67 bajtów.[,$m,$n]=$argv;
na innych golfach kodowych, ale nie byłem w stanie sprawić, by działała ani w moim środowisku deweloperskim, ani na eval.inJavaScript, 105 bajtów
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ę.
źródło
Ruby, 52 bajty
Tworzy anonimową funkcję, która przyjmuje dwie liczby całkowite jako argumenty i zwraca tablicę ciągów:
źródło
Python 2, 81 bajtów
Zwraca listę ciągów.
źródło
JavaScript (ES7), 75 bajtów
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.
źródło
AWK, 78 bajtów
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:
źródło
MATLAB,
10394 bajtyZ formatowaniem
Przykładowe dane wyjściowe
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.
źródło
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)
a=
. W tym przypadku nie można tego zrobić, ponieważ anonimowe funkcje nie mogą zawierać pętli. Ale możesz użyć sztuczki polegającej na włożeniu wszystkiegoeval('...')
. BTW, to zwykle jest uważane za brzydką i złą praktykę w Matlabie, ale tutaj lubimy nadużywanie języków :-)Oktawa ,
6254 bajtyAnonimowa 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!
źródło
TI-Basic,
6362 bajtyTe kryteria znacznie ułatwiły pisanie tego programu.
Przykład I / O:
Wyjaśnienie:
źródło
MATLAB,
736458 bajtówAktualizacja nr 3
Wygląda na to, że potrzebuję sortowania, ponieważ w przeciwnym razie otrzymam ujemne liczby całkowite. Zastąpiłem
disp(sprintf(...))
gofprintf(...)
teraz, więc odpowiedź pozostaje 58 bajtów.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”.Wreszcie zamykam odpowiedź Luisa na oktawę! :RE
Aktualizacja nr 1:
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ę dodatkowyans =
przy pomocy tylko sprintf i nie wiem, czy to dopuszczalne.Kod początkowy:
Dzięki niektórym sugestiom Luisa pozbyłem się pętli w poprzedniej odpowiedzi . Teraz najpierw tworzę pionową tablicę
m
liczb losowych, dodając don
(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:
Uwaga : w oparciu o sugestie zmieniłem tutaj funkcję na funkcję anonimową. W przykładowym wyjściu przypisałem to
a
w celu zademonstrowania. Mam nadzieję, że nie narusza to specyfikacji, ale jeśli tak, proszę dać mi znać, a ja to zmienię.źródło
m
losowych liczb całkowitych, które się sumująn
, ponieważ utknąłem w tej części przez długi czas .. (Wciąż nie mogę dodać więcej niż 2 linków w moich odpowiedziach, więc uwzględnienie tego w komentarzu)Ułożone , 29 bajtów
Wypróbuj online!
Zachowuje się, konstruując tablicę
M
singletonów zawierających'|'
, a następnie dodając'#'
do losowo wybranychN
czasów tablicy .źródło
randin
korzysta z algorytmu Fisher-Yates. (Jest to ten sam algorytm, w którym odpowiedź CJam używa FWIW)Python 2 ,
80 95 8988 bajtówWypróbuj online!
źródło
Węgiel drzewny , 19 bajtów
Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:
źródło