Vous avez une pièce qui produit 0
ou 1
. Mais vous soupçonnez que la pièce peut être biaisée , ce qui signifie que la probabilité de 0
(ou 1
) n'est pas nécessairement 1/2.
Une procédure bien connue pour "transformer" une pièce biaisée en une pièce équitable (c'est-à-dire pour obtenir des résultats également probables), telle que proposée par von Neumann, est la suivante. Produisez des blocs (ne se chevauchant pas) de deux lancers de pièces jusqu'à ce que les deux valeurs d'un bloc diffèrent; et affiche la première valeur de ce bloc (la deuxième valeur ferait également l'affaire, mais pour les besoins de ce défi, nous choisissons la première). Intuitivement, 1
peut être plus probable que 0
, mais 01
et 10
sera tout aussi probable.
Par exemple, l’entrée 1110...
jetterait le premier bloc, puis produirait un à 1
partir du deuxième bloc, ...
Cette procédure est coûteuse , car plusieurs lancers de pièces sont consommés pour générer un seul résultat.
Le défi
Prenez une séquence finie de zéros et de uns, représentant les lancers de la pièce d'origine, et produisez le nombre maximum de résultats conformément à la procédure ci-dessus, jusqu'à ce que toutes les entrées soient consommées.
Le dernier bloc peut être incomplet si le nombre de valeurs entrées est impair. Par exemple, la séquence d'entrée ne 11111
donnerait aucun résultat (les deux premiers blocs ont des valeurs égales et le troisième est incomplet).
Règles
L'entrée peut avoir un nombre non négatif de valeurs, pas nécessairement positives ni même.
Le format d'entrée peut être:
- un tableau de zéros et de uns;
- une chaîne de zéros et des uns avec un séparateur facultatif.
Le format de sortie peut être:
- une chaîne de zéros et de uns, avec ou sans séparateurs;
- un tableau de zéros et de uns;
- chaînes contenant un seul zéro ou un, séparées par des nouvelles lignes;
- tout format similaire, raisonnable et adapté à votre langue.
Code de golf. Le moins d'octets gagne.
Cas de test
L'entrée et la sortie sont supposées être des chaînes.
Input --> Output
'1110' --> '1'
'11000110' --> '01'
'1100011' --> '0'
'00' --> ''
'1' --> ''
'' --> ''
'1101001' --> '0'
'1011101010' --> '1111'
Réponses:
Gelée, 6 octets
Essayez-le en ligne!
Comment ça marche
la source
Rétine ,
16 à14 octetsEssayez-le en ligne!
Explication
C'est assez simple. Le code définit une substitution de regex unique remplaçant toutes les correspondances (sans chevauchement) de
(.)\1|(.)?.
quel que soit le deuxième groupe capturé. Cela combine trois cas différents en un seul:Si deux chiffres répétés sont égaux, nous les supprimons de la chaîne (car le groupe 2 n'est pas utilisé).
Sinon, si nous pouvons faire correspondre deux caractères, supprimez le deuxième en les remplaçant par le premier. Si ce n'est pas le cas, le groupe
?
sera omis:Cela ne se produit que s'il existe un caractère de fin non associé, qui est également supprimé.
la source
Labyrinthe ,
2112 octetsUn exemple rare d'un programme Labyrinth compact qui ne comporte pas non plus d'opportunités.La|
version précédente était totalement inutile et sa suppression réduisait considérablement la taille du programme. En fait, Lab bat Retina!Essayez-le en ligne!
Le coin inférieur gauche
"
peut aussi être un espace, mais son utilisation simplifie grandement l'explication.Explication
Celui-ci est un peu plus compliqué, donc il est accompagné d'images. Mais tout d’abord, une introduction rapide:
Installer
Le programme commence en haut à gauche
"
, ce qui est une non-opération. Ensuite, nous effectuons:Cela laisse la pile avec un seul 0, ce qui est presque vide pour les besoins de Labyrinth.
Lecture d'entrée et de terminaison
,
lit un caractère à partir de l'entrée, renvoyant 48 ou 49 pour0
ou1
respectivement, et -1 sur EOF. Comme ceci est différent de zéro, dans les deux cas, nous nous tournons vers le:
qui duplique le haut de la pile.Le
:
est dans une impasse, alors nous nous retournons et exécutons,
une fois de plus. Maintenant , si la dernière entrée était EOF, nous tournons à gauche et se terminent par@
, sinon on tourne à droite, avec la pile ressemblant[a a b]
(oùa
,b
sont les deux caractères).Interprétation du tirage au sort
Si nous ne terminons pas, notre prochain mouvement est d'exécuter à nouveau
$
(bitwise xor). Cela donne 0 si les caractères d'entrée étaient les mêmes, 1 sinon. Nous multiplions ensuitea
avec ce résultat, donnant 0 oua
. Puisque le*
est à une jonction, cette valeur de pile supérieure détermine ce qui se passera ensuite.Dans le cas 0, nous allons tout droit et exécutons trois
"
no-ops avant d'effectuer une(
décrémentation. Comme pour la configuration, cela nous fait tourner et exécuter"*$
, nous laissant prêts à lire plus de caractères.Sinon, dans le
a
cas, on tourne à droite à la jonction puisquea
est positif (48 ou 49)..
sort le caractère, laissant la pile vide, et(
décrémente le haut de la pile, en tournant de 0 à -1. Encore une fois, cela nous fait tourner à gauche, en procédant"*$
comme dans la configuration, nous laissant également prêts à lire plus d’entrées.la source
(
puis.
, en sortie de carbonisation 255 (-1 modulo 256). Donc, c'est déjà faux à partir de là, malheureusement: PCJam,
10 à8 octetsTestez-le ici.
Explication
C'est une solution très simple: dans chaque paire, supprimez toutes les occurrences du dernier caractère. Les chiffres répétés et les derniers chiffres non appariés seront supprimés, de même que le deuxième chiffre de toute paire de chiffres inégaux:
Cela ne laisse que les chiffres que nous recherchons. Voici comment le code calcule ceci:
Lorsque la liste est automatiquement imprimée à la fin du programme, les chaînes vides sont simplement omises.
la source
Perl,
191817 octetsLa solution @Martin Büttner Retina a inspiré un gain de 2 octets
Comprend +1 pour
-p
Exécuter avec l'entrée sur STDIN, par exemple
perl -p fair.pl <<< 11000110
fair.pl
:Pas grand chose à expliquer ici puisqu'il s'agit d'une traduction (indirecte) de la spécification:
(.)\1
Si les 2 premiers chiffres sont identiques, supprimez-les.\K.
Sinon, les deux premiers chiffres sont différents. Gardez (\K
) le premier.?\K.
Sauf que le premier.
est optionnel. Cela permet une seule correspondance à la fin de la chaîne, qui est ensuite rejetée car la partie conservée est vide.la source
Mathematica, 36
38octets-2 après avoir volé la fonction de @ LegionMammal978 pour déterminer si une liste à 2 éléments est {0,1} ou {1,0}
L'argument devrait être une liste d'entiers.
la source
Hexagone ,
2321 octetsDéplié:
Cela se termine par une erreur, mais le message d'erreur passe à STDERR.
Essayez-le en ligne!
À en juger par le nombre de miroirs, il serait peut-être presque possible de l'adapter à la longueur de côté 3, mais je n'ai pas eu de chance jusqu'à présent.
Explication
Voici le diagramme habituel, généré avec HexagonyColorer de Timwi :
Le programme utilise trois bords de mémoire, étiquetés A , B et C ici (avec l' aimable autorisation de diagramme de Timwi EsotericIDE ):
L'exécution commence sur le chemin bleu. Ce ne
/
sont que des miroirs qui redirigent le pointeur d'instruction (IP), le code actuel est le suivant:Le
,
mettra le bord à la-1
place du code du caractère si nous avons atteint EOF. Puisque nous incrémentons les deux entrées, elles ne changent pas si elles sont égales ou non, mais cela transforme EOF en0
.Nous utilisons modulo pour vérifier l'égalité, parce qu'il est soit
1
ou49
(positif) pour les caractères inégaux et0
des caractères égaux. Il sert également de fin du programme, car lorsque nous avons le0
de EOF, la tentative de division par zéro provoquera une erreur.Maintenant, on
<
distingue les zéros des résultats positifs. Le plus simple en premier: si les caractères sont égaux, l’IP prend le chemin rouge._
est un miroir,\
est aussi un miroir mais est ignoré et>
dévie l'adresse IP de telle sorte qu'elle s'enroule autour des bords et recommence du haut. Cependant, sur cette itération, les rôles de A , B et C sont permutés de manière cyclique ( C prend maintenant le rôle de A , etc.).Si les caractères sont différents, le chemin vert est pris à la place. Celui-ci est un peu plus en désordre. Il saute d'abord sur un no-op avec
$
, puis s'enroule/
sur le bord gauche, puis traverse l'avant-dernière ligne de droite à gauche et rentre enfin dans la partie intéressante du code source{
. Il y a un morceau de code essentiellement linéaire, que je vais expliquer dans une seconde, avant que$
l'adresse IP ne saute par dessus>
pour fusionner à nouveau les deux chemins.Voici ce morceau de code linéaire:
Notez que dans ce cas, les rôles des arêtes pour la prochaine itération sont également permutés de manière cyclique, mais B prenant le rôle de A , etc.
la source
Haskell,
714429 octetsGolf extrême par nimi .
la source
> <> , 11 octets
> <> est plutôt bien adapté aux défis de lecture à la fois, comme celui-ci :) Essayez-le en ligne!
Tout cela se passe dans une boucle car le pointeur d'instruction tourne autour une fois qu'il atteint la fin d'une ligne.
la source
>
ou<
Python, 42 octets
Amusez-vous avec la récursivité et le bitor xor. Prend une liste de 1 et de 0 en entrée.
la source
JavaScript (ES6), 33 octets
Comment ça marche
la source
Prélude , 12 octets
Cela suppose un interprète qui lit et imprime les caractères. Vous pouvez en quelque sorte l'essayer en ligne. Mais cet interprète imprime des nombres entiers, donc pour chacun
0
vous obtiendrez48
et pour chacun1
vous obtiendrez à la49
place (et un saut de ligne).Explication
Il est très rare que vous puissiez écrire un programme non trivial sur une seule ligne dans Prelude (car Prelude a besoin de plus d'une ligne pour être complet de Turing).
la source
Perl,
2721 octetsOctet ajouté pour le
-n
drapeau.Tester:
Merci à @TonHospel pour 6 octets!
la source
say grep$_-chop,/../g
Befunge 93 , 16 octets
Une ligne pour la compacité. Testé à l'aide de cet interprète en ligne .
La dernière partie utilise le fait que le fait de sauter d’une pile Befunge-93 vide donne 0 .
Si
a != b
, nous effectuonsSinon, si
a == b
nous effectuons:la source
Pyth,
10 à9 octetsAlgorithme volé sans vergogne de la réponse de Dennis à Jelly .
la source
Python 2, 48 octets
Essayez-le en ligne
Merci à Dennis et vaultah pour avoir signalé des choses qui me manquaient
la source
zip(*[iter(n)]*2)
Mathematica,
4139 octetsMoins compliqué et plus court que l'autre réponse. La boîte est un caractère de transposition.
la source
JavaScript (ES6), 33 octets
Port ennuyeux de la réponse de la rétine.
la source
sed,
3433 octetsTester:
la source
fold(1)
commande pour diviser en paires. Cela est également sorti à 34!fold -s2|sed 's+01+0+p;s+10+1+p;d'
fold -s2
est équivalent àfold -2
, faire que 33 octets ... ce est ce que je viens de jouer au golf la solution pure sed, aussi. : Ps/../& /g;s/00\|11\|.\b\| //g
Labyrinthe , 31 octets
Pas aussi courte et soignée que la solution de Sp3000, mais je pensais poster cela comme une approche différente:
Explication
La première boucle est simplement
qui lit en deux caractères à la fois (les
"
sont no-ops). Après EOF,,
reviendra-1
, mais ne vérifiera que pour EOF tous les deux caractères. Cela signifie que dans tous les cas, le haut de la pile sera alors-1
et la valeur ci-dessous est soit-1
code ou un code de caractère qui ne nous intéresse pas, car il s'agit d'un tirage au sort non apparié.)*
Transforme ensuite-1
les valeurs et la valeur ci-dessous en une seule0
dont nous avons besoin a) pour supprimer ces deux valeurs et b) pour entrer correctement dans la boucle suivante. Cette prochaine boucle est tout simplementCe qui déplace toutes les valeurs sur la pile auxiliaire. Cela est nécessaire car nous voulons commencer à traiter les paires que nous avons lues en premier. Maintenant la dernière boucle:
Le
)
simple incrémente une valeur factice pour s'assurer qu'elle est positive et que le pointeur d'instruction se tourne vers le nord.{
tire sur le premier chiffre de la paire suivante et le:
duplique. Maintenant, lorsque nous aurons terminé le traitement, cela se fera0
du bas de la pile auxiliaire. Sinon, c'est soit48
ou49
. Dans le cas d'un zéro, nous sortons de la boucle et nous terminons le@
, sinon, l'IP tourne à l'est.{
tire sur l'autre chiffre de la paire actuelle.$
prend le XOR entre eux. Si c'est 0, c'est-à-dire que les deux sont égaux, l'adresse IP continue simplement de se déplacer vers le sud,;
ignore le zéro et l'adresse IP se tourne vers l'ouest pour la prochaine itération. Si le XOR était différent1
, c’est-à-dire que l’IP tourne à l’ouest, rejette le1
avec;
et affiche le premier chiffre avec.
.la source
MATL ,
1198 octetsL'entrée et la sortie sont des nombres séparés par des nouvelles lignes. Se termine par une erreur (autorisée par défaut) lorsque toutes les entrées ont été consommées.
Essayez-le en ligne!
Ancienne approche, 11 octets
L'entrée est une chaîne. La sortie est composée de nombres séparés par des nouvelles lignes.
Essayez-le en ligne!
la source
Ruby, 46 octets
Cela sépare
l[0]
,l[1]
etl[2..{end}]
commea
,b
etc
. Ensuite, il crée une chaîne aveca
ifa!=b
ou''
sinon etf[c]
sic[0]
existe ou''
non.Ungolfed:
la source
brainfuck, 33 octets
Comparé à Java, c'est très compact, cependant, j'ai peur du répondeur brainfuck-golfeur. Et n'hésitez pas à mentionner s'il y a un bug. En supposant que EOF soit égal à 0, l'entrée ne contient pas d'entrée non valide, la cellule est initialement égale à zéro et la plage de valeurs de la cellule est finie et cyclique. Aucune autre hypothèse n'est présente.
Explication:
Carte des cellules de mémoire
Instruction
la source
Mathematica, 41 octets
Fonction anonyme qui entre et sort des listes de zéros et de uns.
la source
#&@@a
est 1 octet plus court quea[[1]]
.RuleDelayed
.Transpose
:(Pyth, 10 octets
Suite de tests
la source
!q
parn
puis le filtrefnFT
parnF#
. (hMnF#cz2
; C’était ce à quoi j’avais pensé lorsque j’ai vu le défi, mais le tien est suffisamment proche pour que je ne l’affiche pas séparément)1
C, 66 octets
En supposant
sizeof(int) == sizeof(char *)
solution "intelligente" -
8481 octetsFonctionne sur une machine little-endian en supposant
short
2 octets. L'entrée est passée en argument. Le programme parcourt des paires de caractères et affiche 0 pour 0x3130 et 1 pour 0x3031. Sur big-endian, le résultat sera inversé (remplacez48|c&1
par49^c&1
pour résoudre ce problème).la source
C, 57 octets
Nous copions provisoirement un caractère d’entrée
p
en résultatr
, mais ne faisons avancer ler
pointeur que s’il diffère du caractère suivant. Sinon, nous l'écraserons à la prochaine paire sans correspondance ou avecNUL
à la fin.Programme de test:
Test de sortie:
la source
Befunge-93 , 40 octets
Vous pouvez l' essayer ici . Collez le code dans l’espace sous le bouton "Afficher", appuyez sur "Afficher", définissez la saisie, appuyez sur "Exécuter". Nous utilisons le bouton "step" pour voir comment le programme fonctionne.
la source
Batch DOS / Windows,
201162 octetsL'entrée est une chaîne séparée par un espace, par exemple
1 0 0 1 1
. Commencez à partir de cmd, sinon l'écran se ferme immédiatementla source
cire d'abeille ,
4535 octetsJe pourrais jouer au golf par 10 octets - pas trop mal.
J'ai pris la lecture d'une chaîne complète de lancer de pièces approche , ce qui rend le programme assez volumineux. Le simple fait de lire des entiers un par un rendrait le programme plus petit (environ 22 octets environ), mais aussi très pratique à utiliser.
Exemples:
Mon dépôt GitHub de cire d'abeille.
Mes exemples de cire d'abeille sur Rosetta Code.
la source