Sie haben eine Münze, die 0
oder produziert 1
. Sie vermuten jedoch, dass die Münze voreingenommen ist , was bedeutet, dass die Wahrscheinlichkeit 0
(oder 1
) nicht unbedingt 1/2 beträgt.
Ein bekanntes Verfahren zur "Umwandlung" einer voreingenommenen Münze in eine faire Münze (dh zur Erzielung gleichwahrscheinlicher Ergebnisse), wie von Neumann vorgeschlagen, lautet wie folgt. Produziere (nicht überlappende) Blöcke mit zwei Münzwürfen, bis sich die beiden Werte eines Blocks unterscheiden. und gebe den ersten Wert in diesem Block aus (der zweite Wert würde auch reichen, aber für die Zwecke dieser Herausforderung wählen wir den ersten). Intuitiv 1
kann eher als 0
, aber 01
und 10
wird gleich wahrscheinlich sein.
Zum Beispiel 1110...
würde die Eingabe den ersten Block verwerfen und dann einen 1
aus dem zweiten Block erzeugen , ...
Dieses Verfahren ist teuer , da mehrere Münzwürfe verbraucht werden, um ein einziges Ergebnis zu erzielen.
Die Herausforderung
Nehmen Sie eine endliche Folge von Nullen und Einsen, die Würfe der ursprünglichen Münze darstellen, und erzeugen Sie die maximale Anzahl von Ergebnissen gemäß dem oben beschriebenen Verfahren, bis die gesamte Eingabe verbraucht ist.
Der letzte Block kann unvollständig sein, wenn die Anzahl der Eingabewerte ungerade ist. Beispielsweise 11111
würde die Eingabesequenz kein Ergebnis liefern (die ersten beiden Blöcke haben gleiche Werte und der dritte Block ist unvollständig).
Regeln
Die Eingabe kann eine beliebige nicht negative Anzahl von Werten haben, nicht unbedingt positive oder gerade.
Das Eingabeformat kann sein:
- eine Anordnung von Nullen und Einsen;
- eine Folge von Nullen und Einsen mit einem optionalen Trennzeichen.
Ausgabeformat kann sein:
- eine Folge von Nullen und Einsen mit oder ohne Trennzeichen;
- eine Anordnung von Nullen und Einsen;
- Zeichenfolgen, die eine einzelne Null oder Eins enthalten, durch Zeilenumbrüche getrennt;
- Jedes ähnliche, vernünftige Format, das zu Ihrer Sprache passt.
Code Golf. Wenigste Bytes gewinnt.
Testfälle
Eingabe und Ausgabe werden hier als Zeichenfolgen angenommen.
Input --> Output
'1110' --> '1'
'11000110' --> '01'
'1100011' --> '0'
'00' --> ''
'1' --> ''
'' --> ''
'1101001' --> '0'
'1011101010' --> '1111'
Antworten:
Gelee, 6 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
Retina ,
16 bis14 BytesProbieren Sie es online!
Erläuterung
Das ist ziemlich einfach. Der Code definiert eine einzelne Regex-Ersetzung, die alle (nicht überlappenden) Übereinstimmungen
(.)\1|(.)?.
mit der zweiten erfassten Gruppe ersetzt. Dies kombiniert drei verschiedene Fälle zu einem:Wenn zwei wiederholte Ziffern gleich sind, entfernen wir sie aus der Zeichenfolge (da Gruppe 2 nicht verwendet wird).
Wenn wir ansonsten zwei Zeichen zuordnen können, entfernen Sie das zweite, indem Sie beide durch das erste ersetzen. Wenn dies nicht der Fall ist,
?
wird die Gruppe weggelassen:Dies geschieht nur, wenn ein nicht gepaartes abschließendes Zeichen vorhanden ist, das ebenfalls entfernt wird.
quelle
Labyrinth ,
2112 BytesEin seltenes Beispiel für ein kompaktes Labyrinth-Programm, das auch keine No-Ops enthält.Die|
in der vorherigen Version war völlig unnötig und das Entfernen hat die Größe des Programms massiv reduziert. Tatsächlich schlägt Lab die Netzhaut!Probieren Sie es online!
Das
"
Feld unten links kann auch ein Leerzeichen sein, aber es vereinfacht die Erklärung erheblich, wenn es dort steht.Erläuterung
Das hier ist ein bisschen kniffliger, es wird von Bildern begleitet. Aber zuerst eine kurze Einführung:
Installieren
Das Programm startet oben links
"
, was ein No-Op ist. Dann führen wir durch:Dies belässt den Stapel mit einer einzelnen 0, die für die Zwecke von Labyrinth so gut wie leer ist.
Eingabe lesen und beenden
,
Liest ein Zeichen von der Eingabe und gibt 48 oder 49 für0
bzw.1
und -1 für EOF zurück. Da dies ungleich Null ist, drehen wir uns in die Richtung:
, die die Oberseite des Stapels dupliziert.Das
:
ist in einer Sackgasse, also drehen wir uns um und führen,
noch einmal aus. Nun , wenn die letzte Eingabe EOF ist, dann biegen wir links ab und enden mit@
, sonst rechts wenden wir uns, mit dem Stapel, die wie[a a b]
(woa
,b
sind die beiden Zeichen).Interpretation des Münzwurfs
Wenn wir nicht abgebrochen haben, besteht unser nächster Schritt darin,
$
(bitweises xor) erneut auszuführen . Dies ergibt 0, wenn die Eingabezeichen gleich waren, andernfalls 1. Wir multiplizieren danna
mit diesem Ergebnis und geben entweder 0 odera
. Da sich das*
an einer Kreuzung befindet, bestimmt dieser obere Stapelwert, was als Nächstes geschieht.Im Fall 0 gehen wir geradeaus und führen drei
"
No-Ops aus, bevor wir eine(
Dekrementierung durchführen. Wie beim Setup werden wir gedreht und ausgeführt"*$
, sodass wir bereit sind, weitere Zeichen zu lesen.Andernfalls
a
biegen wir in diesem Fall an der Kreuzung rechts ab, da diesa
positiv ist (48 oder 49)..
gibt das Zeichen aus, lässt den Stapel leer und(
dekrementiert den oberen Bereich des Stapels, wobei eine 0 auf -1 gesetzt wird. Dies bringt uns wieder dazu, nach links abzubiegen,"*$
wie im Setup ausgeführt, und bereit zu sein, weitere Eingaben zu lesen.quelle
(
und.
gibt char 255 (-1 modulo 256) aus. Ab da ist es leider schon falsch: PCJam,
108 BytesTeste es hier.
Erläuterung
Dies ist eine sehr einfache Lösung: Entfernen Sie in jedem Paar alle Instanzen des letzten Zeichens. Wiederholte Ziffern und nicht gepaarte nachfolgende Ziffern werden entfernt, ebenso wie die zweite Ziffer in einem ungleichen Ziffernpaar:
Dies lässt nur die Ziffern, die wir suchen. So berechnet der Code das:
Wenn die Liste am Ende des Programms automatisch ausgedruckt wird, werden die leeren Zeichenfolgen einfach weggelassen.
quelle
Perl,
191817 Bytes@Martin Büttner Retina-Lösung inspirierte zu einem Gewinn von 2 Byte
Beinhaltet +1 für
-p
Führen Sie mit der Eingabe auf STDIN, z
perl -p fair.pl <<< 11000110
fair.pl
:Hier ist nicht viel zu erklären, da es sich um eine (indirekte) Übersetzung der Spezifikation handelt:
(.)\1
Wenn die ersten beiden Ziffern identisch sind, lassen Sie sie fallen.\K.
Ansonsten sind die ersten beiden Ziffern unterschiedlich. Behalte (\K
) den ersten.?\K.
Mit der Ausnahme, dass das erste.
optional ist. Dies ermöglicht eine einzelne Übereinstimmung am Ende der Zeichenfolge, die dann verworfen wird, da der gehaltene Teil leer istquelle
Mathematica, 36
38Bytes-2 nach dem Diebstahl von @ LegionMammal978s Funktion zur Bestimmung, ob eine Liste mit 2 Elementen den Wert {0,1} oder {1,0} hat
Es wird erwartet, dass das Argument eine Liste von ganzen Zahlen ist.
quelle
Hexagony ,
2321 BytesEntfaltet:
Das wird mit einem Fehler beendet aber die Fehlermeldung geht an STDERR.
Probieren Sie es online!
Gemessen an der Anzahl der Spiegel ist es vielleicht gerade noch möglich, sie in Seitenlänge 3 einzubauen, aber ich hatte bisher kein Glück.
Erläuterung
Hier ist das übliche Diagramm, das mit Timwis HexagonyColorer erstellt wurde :
Das Programm verwendet hier nur drei Speicherflanken mit den Bezeichnungen A , B und C (Diagramm mit freundlicher Genehmigung von Timwi's EsotericIDE ):
Die Ausführung beginnt auf blauem Weg. Dies
/
sind nur Spiegel, die den Anweisungszeiger (IP) umleiten. Der eigentliche Code lautet:Das
,
setzt die Kante auf-1
anstelle des Zeichencodes, wenn wir EOF gedrückt haben. Da wir beide Eingänge inkrementieren, ändert sich nichts daran, ob sie gleich sind oder nicht, aber es wird EOF0
.Wir verwenden modulo, um die Gleichheit zu überprüfen, da es entweder
1
oder49
(positiv) für ungleiche Zeichen und0
für gleiche Zeichen ist. Es dient auch als Programmende, da0
die versuchte Division durch Null einen Fehler verursacht , wenn es sich um die von EOF handelt.Das
<
unterscheidet nun Nullen von positiven Ergebnissen. Das Einfache zuerst: Wenn die Zeichen gleich sind, nimmt die IP den roten Pfad._
ist ein Spiegel,\
ist auch ein Spiegel, wird aber ignoriert und>
lenkt die IP so um, dass sie sich um die Kanten wickelt und wieder von oben beginnt. Bei dieser Iteration werden jedoch die Rollen von A , B und C zyklisch vertauscht ( C übernimmt jetzt die Rolle von A usw.).Wenn die Zeichen unterschiedlich sind, wird stattdessen der grüne Pfad verwendet. Das hier ist etwas chaotischer. Es springt zuerst über ein No-Op mit
$
, läuft dann bis zum/
linken Rand, durchläuft dann die vorletzte Zeile von rechts nach links und gibt schließlich den interessanten Teil des Quellcodes am erneut ein{
. Es gibt ein im Wesentlichen lineares Stück Code, das ich in einer Sekunde erklären werde, bevor$
die IP über das springt>
, um die beiden Pfade wieder zusammenzuführen.Hier ist der lineare Code:
Beachten Sie, dass in diesem Fall die Rollen der Kanten für die nächste Iteration ebenfalls zyklisch vertauscht werden, wobei B jedoch die Rolle von A usw. übernimmt .
quelle
Haskell,
714429 BytesExtremes Golfen von Nimi .
quelle
> <> , 11 Bytes
> <> eignet sich ziemlich gut zum Lesen von Char-at-A-Time-Herausforderungen wie folgt :) Probieren Sie es online aus!
Dies alles geschieht in einer Schleife, da der Anweisungszeiger am Ende einer Zeile herumläuft.
quelle
>
oder<
Python, 42 Bytes
Spaß mit Rekursion und bitweisem xor. Nimmt eine Liste von 1 und 0 als Eingabe.
quelle
JavaScript (ES6), 33 Byte
Wie es funktioniert
quelle
Vorspiel , 12 Bytes
Dies setzt einen Interpreter voraus, der Zeichen liest und druckt. Sie können es auch online ausprobieren. Dass aber die Dolmetscher druckt ganze Zahlen, so dass für jeden
0
werden Sie erhalten48
und für jeden1
werden Sie erhalten49
statt (und ein Zeilenvorschub).Erläuterung
Es ist sehr selten, dass Sie in Prelude ein nicht-triviales Programm in einer einzelnen Zeile schreiben können (da Prelude mehr als eine Zeile benötigt, um vollständig zu sein).
quelle
Perl,
2721 BytesByte für die
-n
Flagge hinzugefügt .Prüfung:
Danke an @TonHospel für 6 Bytes!
quelle
say grep$_-chop,/../g
Befunge 93 , 16 Bytes
Ein Einzeiler für Kompaktheit. Getestet mit diesem Online-Interpreter .
Der letzte Teil nutzt die Tatsache, dass das Poppen von einem leeren Befunge-93-Stapel 0 ergibt .
Wenn
a != b
wir durchführenAndernfalls
a == b
führen wir Folgendes aus:quelle
Pyth,
109 BytesAlgorithmus schamlos aus Dennis 'Gelee-Antwort gestohlen .
quelle
Python 2, 48 Bytes
Probieren Sie es online aus
Vielen Dank an Dennis und Vaultah für den Hinweis auf Dinge, die ich verpasst habe
quelle
zip(*[iter(n)]*2)
Mathematica,
4139 BytesWeniger kompliziert und kürzer als die andere Antwort. Die Box ist ein transponierter Charakter.
quelle
JavaScript (ES6), 33 Byte
Langweiliger Hafen der Retina Antwort.
quelle
sed,
3433 bytesPrüfung:
quelle
fold(1)
Befehl in Paare aufzuteilen. Das kam auch bei 34 raus!fold -s2|sed 's+01+0+p;s+10+1+p;d'
fold -s2
entsprichtfold -2
, dass 33 Bytes ... das ist, worauf ich gerade die pure sed-Lösung golfen habe, auch. : Ps/../& /g;s/00\|11\|.\b\| //g
Labyrinth , 31 Bytes
Nicht so kurz und ordentlich wie die Sp3000-Lösung, aber ich dachte, ich würde das trotzdem als einen anderen Ansatz posten:
Erläuterung
Die erste Schleife ist einfach
das liest in zwei Zeichen gleichzeitig (das
"
sind No-Ops). Nach EOF,
wird zurückgegeben-1
, es wird jedoch nur bei jedem zweiten Zeichen auf EOF geprüft. Das bedeutet in jedem Fall, dass der obere Teil des Stapels dann ist-1
und der Wert darunter entweder ein-1
oder ein Zeichencode ist, den wir nicht interessieren, da es sich um einen ungepaarten Münzwurf handelt.Dann
)*
wandelt man das-1
und den Wert darunter in einen einzigen Wert um,0
den wir a) benötigen, um diese beiden Werte zu beseitigen, und b) um die nächste Schleife korrekt einzugeben. Diese nächste Schleife ist einfachDadurch werden alle Werte auf den Zusatzstapel verschoben. Dies ist notwendig, da wir die zuerst gelesenen Paare verarbeiten möchten. Nun die letzte Schleife:
Das
)
erhöht nur einen Dummy-Wert, um sicherzustellen, dass er positiv ist und der Befehlszeiger nach Norden zeigt.{
Zieht über die erste Ziffer des nächsten Paares und:
dupliziert es. Nun, wenn wir mit der Verarbeitung fertig sind, wird dies0
von der Unterseite des Hilfsstapels gewesen sein. Ansonsten ist es entweder48
oder49
. Im Falle einer Null verlassen wir die Schleife und enden an@
, ansonsten dreht sich die IP nach Osten.{
zieht über die andere Ziffer des aktuellen Paares.$
nimmt die XOR zwischen ihnen. Wenn dies 0 ist, dh die beiden gleich sind, bewegt sich die IP einfach weiter nach Süden,;
wirft die Null ab und die IP dreht sich nach Westen in die nächste Iteration. Wenn das XOR war1
, dh sie waren unterschiedlich, dreht sich die IP nach Westen, verwirft das1
mit;
und druckt die erste Ziffer mit.
.quelle
MATL ,
1198 BytesEingabe und Ausgabe sind durch Zeilenumbrüche getrennte Zahlen. Beendet mit einem Fehler (standardmäßig zulässig), wenn alle Eingaben verbraucht wurden.
Probieren Sie es online!
Alter Ansatz, 11 Bytes
Die Eingabe ist eine Zeichenfolge. Die Ausgabe erfolgt durch Zeilenumbrüche getrennte Zahlen.
Probieren Sie es online!
quelle
Ruby, 46 Bytes
Dies trennt
l[0]
,l[1]
undl[2..{end}]
wiea
,b
undc
. Dann wird eine Zeichenfolge mita
ifa!=b
oder''
else erstellt undf[c]
wennc[0]
vorhanden oder''
anderweitig.Ungolfed:
quelle
Brainfuck, 33 Bytes
Im Vergleich zu Java ist dies sehr kompakt, ich habe jedoch Angst vor dem Brainfuck-Golfer-Beantworter. Und Sie können gerne erwähnen, ob es einen Fehler gibt. Angenommen, EOF ist 0, die Eingabe enthält keine ungültigen Eingaben, die Zelle ist anfangs Null und der Zellenwertebereich ist endlich und zyklisch. Es liegt keine andere Annahme vor.
Erläuterung:
Memory Cell Map
Anweisung
quelle
Mathematica, 41 Bytes
Anonyme Funktion, die Listen mit Nullen und Einsen ein- und ausgibt.
quelle
#&@@a
ist 1 Byte kürzer alsa[[1]]
.RuleDelayed
.Transpose
:(Pyth, 10 Bytes
Testsuite
quelle
!q
durchn
und dann den FilterfnFT
durch ersetzennF#
. (hMnF#cz2
; das war die Sache, an die ich gedacht habe, als ich die Herausforderung gesehen habe, aber deine ist nah genug, damit ich sie nicht separat posten kann)1
C 66 Bytes
Vorausgesetzt
sizeof(int) == sizeof(char *)
"clevere" Lösung -
8481 BytesFunktioniert auf Little-Endian-Rechnern mit
short
2 Bytes. Die Eingabe wird als Argument übergeben. Das Programm durchläuft Zeichenpaare und gibt 0 für 0x3130 und 1 für 0x3031 aus. Auf Big-Endian wird das Ergebnis umgekehrt (ersetzen48|c&1
mit ,49^c&1
dies zu beheben).quelle
C 57 Bytes
Wir kopieren versuchsweise ein Zeichen von der Eingabe
p
in das Ergebnisr
, bewegen denr
Zeiger jedoch nur, wenn er vom nächsten Zeichen abweicht. Wenn nicht, werden wir es beim nächsten nicht passenden Paar oderNUL
am Ende mit überschreiben .Testprogramm:
Testausgang:
quelle
Befunge-93 , 40 Bytes
Sie können es hier ausprobieren . Fügen Sie Code in das Feld unter der Schaltfläche "Anzeigen" ein, drücken Sie "Anzeigen", definieren Sie die Eingabe, drücken Sie "Ausführen". Verwenden Sie den "Schritt" -Button, um zu sehen, wie das Programm funktioniert.
quelle
DOS / Windows Batch,
201162 BytesDie Eingabe ist beispielsweise eine durch Leerzeichen getrennte Zeichenfolge
1 0 0 1 1
. Beginnen Sie mit cmd, andernfalls wird der Bildschirm sofort geschlossenquelle
Bienenwachs ,
4535 BytesIch könnte es um 10 Bytes reduzieren - nicht schlecht.
Ich habe eine ganze Reihe von Münzwürfen gelesen , was das Programm ziemlich umfangreich macht. Nur einzelne Ganzzahlen nacheinander zu lesen, würde das Programm kleiner machen - vielleicht um 22 Bytes oder so -, aber auch sehr unpraktisch in der Verwendung.
Beispiele:
Mein Bienenwachs-GitHub-Repository.
Meine Bienenwachsbeispiele auf Rosetta Code.
quelle