Le principe du pigeonhole stipule que
Si N articles sont placés dans M cases, avec N > M , alors au moins une case doit contenir plus d'un article.
Pour beaucoup, ce principe a un statut spécial par rapport à d'autres propositions mathématiques. Comme l'a écrit EW Dijkstra ,
Il est entouré d'une mystique. Les preuves qui l'utilisent sont souvent considérées comme quelque chose de spécial, quelque chose de particulièrement ingénieux.
Le défi
Le but de ce défi est d'illustrer le principe du pigeonnier à l'aide de représentations artistiques ASCII. Plus précisément:
- Prendre en entrée
N
(nombre d'articles) etM
(nombre de cases), avecN
non négatif etM
positif.N
peut être inférieur àM
(même si le principe ne s'applique pas dans ce cas). - Sélectionnez au hasard l'une des affectations possibles des éléments aux boîtes. Chaque affectation doit avoir une probabilité non nulle d'être sélectionnée.
Produisez une représentation artistique ASCII de l'affectation comme suit:
- Il y a des
M
lignes, chacune correspondant à une case. - Chaque ligne commence par un caractère non blanc, tel que
|
. - Après ce caractère se trouve un autre caractère non blanc, tel que
#
, répété autant de fois qu'il y a d'éléments dans cette case.
- Il y a des
Considérons par exemple N = 8
, M = 5
. Si le assigment sélectionné des articles à des boîtes est 4
, 1
, 0
, 3
, 0
, la représentation est
|####
|#
|
|###
|
Une exécution différente (entraînant une affectation différente) du même programme pourrait donner
|#
|##
|#
|#
|###
Il y a une certaine flexibilité concernant la représentation; voir ci-dessous.
Règles spécifiques
Le code devrait théoriquement s'exécuter pour toutes les valeurs de N
et M
. En pratique, il peut être limité par la taille de la mémoire ou les limitations du type de données.
Étant donné que l'observation du résultat n'est pas suffisante pour déterminer si toutes les affectations ont une probabilité non nulle , chaque soumission doit expliquer comment le code y parvient, si ce n'est évident.
Les variations de représentation suivantes sont autorisées:
- N'importe quelle paire de caractères différents non blancs peut être choisie. Ils doivent être cohérents d'une exécution à l'autre du programme.
- Les rotations de 90 degrés de la représentation sont acceptables. Encore une fois, le choix doit être cohérent.
- Les espaces de fin ou de début sont autorisés.
A titre d'exemple avec un format de représentation différent, car N = 15
, M = 6
les résultats de deux exécutions du programme pourraient être
VVVVVV
@@@@@@
@@ @@@
@ @@
@
ou
VVVVV
@@@ @
@@@ @
@ @ @
@ @ @
@
De même, N = 5
, M = 7
pourrait donner, en utilisant une autre variante de la représentation,
*
* * * *
UUUUUUU
ou
*** **
UUUUUUU
ou
*
* *
* *
UUUUUUU
Notez comment le principe n'est pas applicable dans ce cas, car N
< M
.
Règles générales
Les programmes ou fonctions sont autorisés, dans n'importe quel langage de programmation . Les failles standard sont interdites.
L'entrée peut être prise par tout moyen raisonnable ; et avec n'importe quel format, comme un tableau de deux nombres ou deux chaînes différentes.
Les moyens et le format de sortie sont également flexibles. Par exemple, la sortie peut être une liste de chaînes ou une chaîne avec des retours à la ligne; renvoyé comme argument de sortie de fonction ou affiché dans STDOUT. Dans ce dernier cas, il n'est pas nécessaire de s'inquiéter du retour à la ligne causé par une largeur d'affichage limitée.
Le code le plus court en octets gagne.
Réponses:
Gelée ,
98 octetsIl s'agit d'un lien dyadique qui prend M comme argument de gauche et N comme argument de droite. La sortie est un tableau d'entiers, où 0 représente les pigeons et 1 représente les trous.
Essayez-le en ligne!
Comment ça marche
la source
Mathematica, 68 octets
Une fonction sans nom qui prend deux arguments entiers, le nombre de cases, suivi du nombre d'éléments.
Il calcule d'abord toutes les partitions possibles de
N+M
enM
parties exactement positives, et soustrait ensuite1
de chaque partition. Cela nous donne toutes les partitions possibles deN
enM
parties non négatives (quiIntegerPartitions
ne généreraient pas autrement). Choisissez ensuite une partition aléatoire et mélangez-la. Cela garantit que toutes les partitions ordonnées possibles avec des zéros sont autorisées. Enfin, convertissez chaque bac de la partition en une ligne de sortie en augmentant 10 à la puissance correspondante (de sorte que chaque ligne devient1000...
avec desk
zéros). Un exemple de sortie pourrait ressembler à ceci:la source
PadRight
je ne remplirais pas lesM
zéros siN
<M
.PadRight
la non-listabilité le rendrait beaucoup plus long.PadRight
seraitIntegerPartitions[#,{#2},0~Range~#]
.Python 2,
7786 octetsGénère un nombre dans [0, n], imprime autant d'éléments et le soustrait de n. Il le fait m fois.
Cela rend très improbable que quelque chose arrive dans la dernière case, mais la question demandait seulement que chaque sortie soit possible , pas aussi probable .
la source
Lot, 164 octets
Je pense que 7
%
signes consécutifs pourraient être un nouveau record personnel! Remarque: cela produit une sortie étrange si jamais il affecte plus de 9 éléments à la même case; si c'est un problème, alors pour 180 octets:Oui, c'est 28
%
s au total sur la deuxième ligne.la source
C, 102 octets
Prend des informations sur stdin, par exemple:
Ne génère pas chaque sortie avec une probabilité égale, mais est capable de générer toutes les combinaisons possibles.
Panne:
S'appuie sur la gestion par GCC du comportement indéfini de
%0s
- normalement%0
va mettre à zéro un entier ou un flottant, mais il ne peut que remplir (jamais tronquer), donc il n'est pas possible d'imprimer un blanc. Mais le comportement pour les chaînes n'est pas défini, et GCC a décidé de le mettre à zéro de la même manière, donc ce zéro-pad est une chaîne vide pour pouvoir écrire zéro ou plusieurs0
s.la source
a(b,c){...}
au lieu demain
etscanf
.Python 2,
102999790 octetsm-1
fois, choisissez un montant aléatoirex
entre0
etn
, inclus et soustrayez-le de n. Imprimez ensuite un1
et'0'*x
.Enfin, l'imprimé
1
et le reste de l'0
art. Pas du tout des chances égales, mais toutes les configurations sont possibles.(Code réutilisé de la réponse Python cassée.)
la source
Haskell,
11494 octetsUn peu d'une approche de force brute: génère une liste infinie de nombres aléatoires, prend n nombres du début de la liste, les résume et vérifie s'ils sont égaux à m. Sinon, retirez le premier élément de la liste et recommencez.
Essayez-le en ligne!
Remarque: 73 octets sans l'importation
EDIT: Sauvegardé quelques octets avec l'astuce 10 ^ ( Essayez la nouvelle version en ligne! )
la source
REXX, 74 octets
Sortie (8 5):
Sortie (8 5):
la source
C,
175138 octetsMerci à @Dave pour avoir économisé 37 octets!
Essayez-le en ligne!
la source
calloc
vous donnera une mémoire initialisée à 0 (pas besoin de définir tous les 0 vous-même),strchr
peut trouver la fin d'une chaîne, des opérations de chaîne de virgule peuvent être évitées{}
, etx[0] == *x
. Attention aussi; vous n'avez pasmalloc
assez de mémoire si tous les éléments sont dans la même boîte.AHK, 66 octets
J'ai suivi le même principe que orlp en utilisant des nombres aléatoires de 0 à N, puis en le soustrayant de N. Malheureusement, je n'ai pas pu enregistrer d'octets en utilisant 10 ^ r en raison du fonctionnement de la fonction d'envoi. Hélas et alack. Voici quelques sorties pour n = 8, m = 5:
la source
CJam,
303121 octetsL'entrée est deux nombres
n m
sur la pile. Utilise1
le caractère de colonne et0
le caractère répété.Explication:
la source
Röda , 79 octets
Essayez-le en ligne!
Cela crée un tableau de zéros et les incrémente à des endroits aléatoires.
la source
PHP, 100 octets
Panne :
Sorties pour
m=7
etn=5
:Première exécution:
Deuxième exécution:
Essayez-le en ligne!
la source
[,$m,$n]=$argv;
partir de PHP 7.1 pour enregistrer quelques caractères. Vous pouvez remplacer\n
par un saut de ligne réel pour économiser 1 octet. vous pouvez utiliserfor(;$m-->0;)$a[rand(0,$n-1)].=a;
pour enregistrer les pauses, un$m
et un point-virgule.[,$m,$n]=$argv;$a=array_fill(0,$n,z);for(;$m-->0;)$a[rand()%$n].=a;echo join("\n",$a);
85 octets[,$m,$n]=$argv;for(;$m--;)${rand()%$n}.=a;for(;$n--;)echo"z${$n}\n";
67 octets.[,$m,$n]=$argv;
sur d'autres golfs de code mais je n'ai pas pu le faire fonctionner ni dans mon environnement de développement ni sur eval.inJavaScript, 105 octets
Essayez-le en ligne!
En raison de la méthode d'attribution des lignes, cela aura tendance à se placer davantage vers le bas, bien qu'il y ait une petite chance que le haut en obtienne.
la source
Rubis, 52 octets
Crée une fonction anonyme qui prend deux entiers comme arguments et renvoie un tableau de chaînes:
la source
Python 2, 81 octets
Renvoie une liste de chaînes.
la source
Javascript (ES7), 75 octets
Je pensais que j'étais intelligent pour avoir trouvé les pouvoirs de l'idée 10 seulement pour réaliser que la plupart des réponses utilisaient déjà cela.
la source
AWK, 78 octets
Prend 2 arguments, d'abord le nombre d'éléments, puis le nombre de boîtes. Commence en amorçant le générateur de nombres aléatoires de sorte que chaque exécution est différente. Construit ensuite simplement des chaînes dans un tableau, Exemple d'utilisation:
la source
MATLAB,
10394 octetsAvec formatage
Exemple de sortie
Il y a des espaces blancs à la fin puisque chaque entrée de tableau est affichée avec un onglet entre eux, mais cela devrait être acceptable selon les spécifications.
Cela me semble être une implémentation très simpliste, donc je suis sûr que cela pourrait être amélioré.
Merci à @Luis Mendo pour ses suggestions.
la source
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=
. Dans ce cas, vous ne pouvez pas faire cela, en principe, car les fonctions anonymes ne peuvent pas contenir de boucles. Mais vous pourriez utiliser l'astuce de tout mettre dedanseval('...')
. BTW, c'est normalement considéré comme une mauvaise et mauvaise pratique dans Matlab, mais ici nous aimons abuser des langues :-)Octave ,
6254 octetsFonction anonyme qui prend deux nombres et génère un tableau 2D de caractères avec
>
des boîtes et*
des objets. Tous les résultats sont également probables.Essayez-le en ligne!
la source
TI-Basic,
6362 octetsCes critères ont rendu ce programme beaucoup plus facile à écrire.
Exemple d'E / S:
Explication:
la source
MATLAB,
736458 octetsMise à jour # 3
J'ai besoin du tri, semble-t-il, car sinon j'obtiens des entiers négatifs. J'ai remplacé
disp(sprintf(...))
parfprintf(...)
maintenant, cependant, donc la réponse reste 58 octets.Mise à jour # 2:
J'ai réalisé que je n'avais pas besoin de trier le tableau, et en fait, le tri réduirait en fait la moyenne des nombres dans le tableau. J'ai donc supprimé la
sort(...)
partie. Notez que la sortie reste la même, donc je ne mets pas à jour la "sortie d'échantillon".Enfin, en terminant sur la réponse Octave de Luis! :RÉ
Mise à jour # 1:
Au lieu de convertir en chaîne, j'affiche simplement les nombres directement. Je pourrais réduire à 58 octets, en supprimant le
disp(...)
, mais ensuite j'obtiens le supplémentans =
avec juste sprintf, et je ne sais pas si c'est acceptable.Code initial:
Grâce à quelques suggestions de Luis , je me suis débarrassé de la boucle dans ma réponse précédente . Maintenant, je crée d'abord un tableau vertical de
m
nombres aléatoires totalisantn
(diff([0;sort(randi(n,m-1,1));n])
), puis les utilise comme exposants de 10, les convertis en chaîne, les justifie à gauche et les affiche.Je pourrais techniquement me débarrasser de la disp (...) pour économiser encore 6 octets, mais ensuite un "ans" s'imprime ce qui peut violer les spécifications. Il peut également y avoir un moyen de les changer en chaîne et de justifier à gauche pour obtenir le format de fin souhaité, donc je suis ouvert aux suggestions.
Exemple de sortie:
Remarque : J'ai changé ma fonction en fonction anonyme ici, sur la base de suggestions. Dans l'exemple de sortie, j'ai attribué cela à
a
afin de démontrer. J'espère que cela ne viole pas les spécifications, mais si c'est le cas, faites-le moi savoir et je le changerai.la source
m
des entiers aléatoires qui s'additionnentn
, car je suis resté coincé sur cette partie pendant un long moment .. (Je ne peux toujours pas ajouter plus de 2 liens dans mes réponses, donc l'inclure dans un commentaire)Empilé , 29 octets
Essayez-le en ligne!
Se comporte en construisant un tableau de
M
singletons contenant'|'
, puis en ajoutant'#'
à un tableau choisi au hasardN
.la source
randin
utilise l'algorithme Fisher-Yates en interne. (C'est le même algorithme que la réponse CJam utilise FWIW)Python 2 ,
80 95 8988 octetsEssayez-le en ligne!
la source
Fusain , 19 octets
Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:
la source