Neulich ging unser Team in einen Fluchtraum. Eines der Rätsel bestand aus einer Platine mit sechs mechanischen Schaltern, bei denen Sie die richtige Kombination von Ein und Aus finden mussten, um eine Box zu entsperren.
-v-v-v-
-v-v-v-
Als Entwickler haben wir beschlossen, dass es effizienter ist, jede einzelne der 2 ^ 6 = 64-Kombinationen auszuprobieren, als das Rätsel tatsächlich zu lösen. Also haben wir einen armen Kerl beauftragt, eine Binärzählung durchzuführen:
-v-v-v-
-v-v-v-
-v-v-v-
-v-v-^-
-v-v-v-
-v-^-v-
-v-v-v-
-v-^-^-
und so weiter.
Die Herausforderung
Schreiben Sie ein Programm, das, wenn die Schalter wie oben formatiert sind, alle Kombinationen von Ein und Aus in beliebiger Reihenfolge generiert.
Sie können entweder ein vollständiges Programm oder eine Funktion schreiben. Daher kann Ihr Programm Eingaben entweder über stdin, eine Datei oder als einzelnes Zeichenfolgenargument aufnehmen und die Ausgabe entweder zurückgeben oder ausdrucken. Wenn zurückgegeben, kann die Ausgabe in einer Liste / Array / etc sein. eher als eine einzelne Zeichenfolge. Wenn es sich bei der Ausgabe um eine einzelne Zeichenfolge handelt, sollten die Boards durch Zeilenumbrüche getrennt werden (abschließende Zeilenumbrüche sind zulässig.)
Die Eingabezeichenfolgen entsprechen dem regulären Ausdruck r'((-v)+-)(\n(-v)+-)*'
und stellen eine Karte dar, bei der alle Schalter ausgeschaltet sind. Dies bedeutet, dass kein Null-Fall vorliegt und die Schalter linksbündig ausgerichtet sind. Jede Zeile verfügt möglicherweise nicht über die gleiche Anzahl von Schaltern.
Jede Ausgangskarte sollte genau dasselbe Format wie die Eingabe haben, mit der Ausnahme, dass die vs nach Bedarf durch ^ ersetzt werden können. Die Ausgangskarten können durch beliebig viele Zeilenumbrüche getrennt werden.
Da die Laufzeit in Bezug auf die Anzahl der Schalter natürlich 0 (2 ^ n) beträgt, wird Ihr Code in keiner Anordnung an mehr als 10 Schaltern getestet.
Das ist Code-Golf, also gewinnt der kürzeste Code in der Anzahl der Bytes.
Beispiel für Ein- und Ausgänge
Eingang:
-v-
Mögliche Ausgabe:
-v-
-^-
Eingang:
-v-
-v-
Mögliche Ausgabe:
-^-
-^-
-^-
-v-
-v-
-^-
-v-
-v-
Da es äußerst mühsam ist, Ihre Antwort auf eine größere Anzahl von Schaltern zu überprüfen, finden Sie hier ein Python-Skript als Tool zur Überprüfung der Integrität. (Ich habe ein aktuell auskommentiertes Snippet eingefügt, um die erwartete Ausgabe aus einer bestimmten Eingabedatei zu generieren, falls Sie mehr Testfälle wünschen.) Leider ist es in Bezug auf Eingabe und Ausgabe einiges weniger flexibel als die Spezifikation. Legen Sie die Eingabezeichenfolge in eine Datei mit dem Namen 'input' und die durch Zeilenumbrüche getrennte Ausgabe (sorry, keine Listenformatierung) in eine Datei mit dem Namen 'output' im selben Verzeichnis und führen Sie sie aus python3 sanitycheck.py
.
quelle
Antworten:
Haskell ,
25242317 BytesProbieren Sie es online!
-1 Byte dank @ H.PWiz
-1 Byte danke an @nimi
Gibt eine Liste von Zeichenfolgen zurück. Das TIO hat 2 zusätzliche Bytes für die Funktionsdeklaration - ich habe gesehen, dass andere Leute es ausgeschaltet haben, als sie die Funktion ohne Punkte geschrieben haben, also mache ich dasselbe, sofern nicht anders angegeben.
Vorherige Antwort (25 Bytes)
Die Erklärungen beziehen sich alle auf die vorherige Antwort, die fast auf die gleiche Weise funktioniert, mit der Ausnahme, dass ich die Definition von eingefügt habe
g
. Die Art und Weiseg
funktioniert , ist jetzt von lexikalischen Vergleich mit Ersatz^v
fürv
und halten alles andere gleich.Interessanterweise funktioniert dies für beliebige Telefonzentralen:
Erklärung (kurz)
Erklärung (lang)
mapM
ist eine ziemlich beängstigende Funktion für diejenigen, die Haskell nicht kennen. Aber es ist in diesem Zusammenhang nicht schwer zu verstehen.String
Ich habe es auf seine Definition für Listen spezialisiert, indem ich es auf s wirken ließ (die in Haskell Listen von Zeichen sind). In diesem Zusammenhang lautet die Typensignatur alsoEs ist sogar noch spezialisierter auf meine Verwendung -
a
undb
beidesChar
-, so dass wir die Typensignatur als sehen könnenSchauen wir uns kurz an, was
g
passiert, bevor wir erklären, wie esmapM
funktioniert.g
Verwendet Pattern Matching, um dasChar 'v'
in den String umzuwandeln"v^"
. alles andere wird in eine Singleton-Zeichenfolge konvertiert (denken Sie daran, dass Zeichenfolgen nur Listen vonChar
s sind, sodass wirx
eine Singleton-Liste einfügen können). Beim Testen mit dem REPL stellen wir fest, dass dies der Fall istBeachten Sie, dass
g
es den richtigen Typ hat, um ein Argument vonmapM
(nicht überraschend!) Zu sein.Wir werden untersuchen, wie es
mapM
funktioniert, indem wir esg
und das Argument gebenals Eingabe.
mapM
erste karteng
über dieString
und da s nachg
konvertiert , gibt uns dies eine liste vonChar
Strings
Strings
Dies ist zwar der richtige Ausgabetyp,
mapM
leistet jedoch etwas mehr. Sie können sich das so vorstellen, als würden Sie alleString
s bilden, die Sie aus dieser Liste erstellen könnten, wenn Sie aus jedem einen einzelnen Charakter auswählen müsstenString
( müssten.Für das erste Element haben Sie also keine andere Wahl, als das auszuwählen
Char '-'
. Für das zweite Element können Sie wählen zwischen'v'
und'^'
usw. .Es entspricht ungefähr diesem Python-Code:
Abgesehen davon, dass Haskell zwischen
Char
s undString
s trennt , wenn er das setztChar
s in eine Liste setzt, es nicht brauchtjoin
.Die endgültige Ausgabe ist also
wie gewünscht.
quelle
mapM
arbeitete für diese Herausforderung, hatte ich anfangs formulierte es so ,sequence . map g
aber das kann kompakt ausgedrückt werden alsmapM id . map g
ich sah , und dann konnte ich nurmapM g
=='v'
für>'-'
Perl 6 , 32 Bytes
Probieren Sie es online!
.comb
teilt die Zeichenfolge in Zeichen auf.».&{...}
Ordnet die Zeichen entsprechend der Funktion zwischen den geschweiften Klammern zu.$_, ('^' if /v/)
erzeugt eine Liste von Alternativen für jedes Zeichen. Hatv
nur eine Alternative:^
.[X~]
Reduziert diese Liste mit dem produktübergreifenden Operator für die Verkettung von ZeichenfolgenX~
.quelle
Gelee , 7 Bytes
Probieren Sie es online!
Die Ausgabe ist eine Liste von Jelly-Strings.
Erläuterung:
quelle
Perl 5 , 29 Bytes
Probieren Sie es online!
Meine erste Einreichung!
Normalerweise übermitteln Perl 5-Golfer Programme anstelle von Funktionen, um zu vermeiden, dass diese
sub{}
mindestens enthalten sein müssen. Aber sie haben hinzuzufügensay
,say␠
,say for
odersay for␠
im Austausch.Durch den Unteransatz könnte ich verkürzen
zu
Die Erklärung ist ganz einfach. Perl 5 verfügt über einen eingebauten
glob
Operator, der ein Shell-ähnliches Glob-Muster akzeptiert, mit dem Listen mit Dateinamen (z. B.foo*.txt
) oder Listen mit Zeichenfolgen (z{a,b,c}
. B. ) erstellt werden können. Der Haken ist, dass die Newline geflüchtet werden muss, was ich mitquotemeta
(as\Q
) getan habe .quelle
K (NGN / k) ,
2725 BytesProbieren Sie es online!
"^"/"v"\
ersetzen"v"
mit"^"
x,'
Reißverschluss mit den Originalbuchstaben(,/,/:\:)/
kartesisches Produkt vorbei?
uniqquelle
APL (Dyalog Classic) ,
21 1715 BytesProbieren Sie es online!
ähnlich wie bei meiner k-Lösung
gibt ein n-dimensionales Array von Strings zurück (n = Anzahl der Schalter)
in einfacher zu erklärender Form:
⊃(∘.,⌿ ⊢ ∪¨ 'v'⎕r'^')
'v'⎕r'^'
Ersetzev
s durch^
s⊢ ∪¨
... Gewerkschaften mit jedem der ursprünglichen Charaktere. Es ist ein Vektor von Zeichenfolgen der Länge 1 oder 2∘.,⌿
kartesische Produktreduktion⊃
offenbarenum zur vollgolfversion zu gelangen folgen wir dem muster
f⌿ A g¨ B
->A f.g B
:∘.,⌿ ⊢ ∪¨ 'v'⎕r'^'
->⊢ ∘.,.∪ 'v'⎕r'^'
Als Nebeneffekt werden die Klammern nicht mehr benötigt
quelle
J , 42 Bytes
Probieren Sie es online!
Erläuterung
Nehmen lassen
als unser beispieleingang.
('v^' {~ 2 #:@i.@^ 1 #. e.&'v')
Erstellt alle möglichen Kombinationen nur der Schalter, wobei das Eingabeformat ignoriert wird. für unser Beispiel ergibt es:1 #. e.&'v'
zählt die Anzahl vonv
s in der Eingabe.2 #:@i.@^
erhöht 2 auf diese Potenz, erzeugt die ganzen Zahlen von 0 bis zu dieser Zahli.
und konvertiert sie in binäre Zahlen#:
'v^' {~
wechselt zu Binärziffern zuv
und^
]`('v' I.@e.~ [)`[}"1
ändert der ursprüngliche Eingang, beschrieben in dem vorhergehenden Schritt (dh alle möglichen für jede Zeile des Ergebnisses einer Kopie davon produziertv
/^
Kombinationen). In jeder Kopie wird diev
der ursprünglichen Eingabe durch eine mögliche Folge vonv
/ ersetzt^
.quelle
Java,
202197189191 BytesJa, es ist eine vergleichsweise wörtliche Sprache, aber das halte ich für klassisches Golfen:
Ich dachte, dass ein "einfacher" Weg, mit den Zeilenumbrüchen umzugehen, die notwendig sind, um ein korrektes Layout zu erreichen, darin besteht, das ursprüngliche Eingabezeichen-Array tatsächlich wiederzuverwenden und es nur an den entsprechenden Stellen mit
'v'
s und'^'
s zu füllen .Aktualisierung:
Es stellte sich heraus, dass das Nichtspeichern der Positionen das Löschen der
int
Variablendeklarationen und des Arrays ermöglicht (auf Kosten der Überprüfung jeder Position des Arrays, ob sie ein enthält)v
oder^
), wodurch 5 Bytes eingespart werden.Weitere 8 Bytes werden durch die Berechnung der Obergrenze eingespart
(1<<numberOfSwitches)
kompakter .Entsprechend der im Kommentar genannten Regel sollte die Funktionsdeklaration gezählt werden, also ist es jetzt ein Lambda ...
quelle
String generate(String s) {...}
) in Ihre Byteanzahl aufnehmen müssen. Hier ist eine feste / Lambda-Version für 191 Bytes . Ich habe ein bisschen Golf gespielt, um 3 Bytes zu sparen{ function body }
relevant sein sollte, weil es keine Rolle spielt, ob Sie es in eine Funktion setzen, die iststatic
oder nicht, und natürlich kann man es in einen Lambda-Ausdruck umwandeln , wenn die Deklaration für die Punktzahl zählt. Aber das ist es, was jetzt gemacht wird, danke, dass du darauf hingewiesen hast.d=94
). 2. Initialisiereni
Sie, wenn Sie es deklarieren. 3. Verwenden Siei++<m
anstelle eines separaten Inkrements (Sie müssen den Inhalt der Schleife an einer Stelle ändern, dies verursacht jedoch keine Kosten). 4. Kannst du damit durchkommen(i&1<<j++)>0
? 5. Ich glaube nicht, dass du das{}
für die innerefor
Schleife brauchst . 6. Sie können ersetzena[k]==d||a[k]==u
mita[k]>45
, denke ich. 7. Gehen Sie mitj=k=0
. All das sollte 19Byte entfernen.{}
notwendig sind, aber ich kann einen anderen Blick darauf werfen. Dasa[k]>45
mag jedoch ein ordentlicher Trick sein. Zugegeben, ich habe dies nur geschrieben, um einige Zeit damit zu verschwenden, auf den Beginn eines Meetings zu warten (daher der Klassenname - das war beabsichtigt ;-)), aber vielleicht werde ich es mir noch einmal ansehen - auf jeden Fall danke!J ,
41 4024 BytesProbieren Sie es online!
quelle
{
. obwohl ich denke,[:>@,@{<@(,'^'$~'v'=])"0
wäre etwas fairer, da "jede ausgangskarte genau das gleiche format wie der eingang haben sollte" und der eingang nicht umrahmt ist.Python 2 , 87 Bytes
Probieren Sie es online!
Ein nicht-regulärer Ansatz.
quelle
C (GCC) ,
75 7470 Bytes-5 Byte dank @ceilingcat
Probieren Sie es online!
setzt
s
voraus, dass die Speicherpunkte beschreibbar sindquelle
Python 3.8 (Vorabversion) ,
129 117 116 110106 Bytes-10 Bytes dank @Chas Brown
Probieren Sie es online!
quelle
C (gcc) , 102 Bytes
Probieren Sie es online!
quelle
K4 , 44 Bytes
Lösung:
Beispiele:
Erläuterung:
Vor-Ort-Austausch von
"^"
. Anzahl der Schalterkombinationen ermitteln (zB 2 ^ n), binär hochzählen, Schalter ersetzen ...quelle
R , 116 Bytes
Probieren Sie es online!
Funktion, die einen Vektor von durch Zeilenumbrüche getrennten Karten zurückgibt
quelle
"[<-"
!JavaScript, 88 Bytes
Probieren Sie es online!
quelle
n>>=1
->n/=2
Retina 0.8.2 , 29 Bytes
Probieren Sie es online! Erläuterung:
Ändern Sie die Zeilenumbrüche in
;
s und diev
s in#
Marker.Ersetzen Sie das
#
s nacheinander von links nach rechts.Ändern Sie jede Zeile in zwei Zeilen, eine mit dem
#
Ersetzten durch av
, eine mit dem Ersetzten durch a^
.Ändern Sie das
;
s zurück in Zeilenumbrüche und platzieren Sie die Ergebnisse auseinander.quelle
Perl 5
-0
, 51 BytesProbieren Sie es online!
quelle
-n
hätte ich die Notwendigkeit von$_=<>;
JavaScript (Node.js) ,
80 7368 BytesProbieren Sie es online!
quelle
Python 3 - Konstrukt, 203 Bytes
Probieren Sie es online!
Erster Versuch, nicht sehr klein, aber funktioniert. In Python gibt es keinen Ersatz für elegante Saiten ...
Die erste Schleife erstellt eine Zuordnung von Zeilen zu Bitindizes, dh für jede Zeile wird der Index des ersten Bits in einem Bitzähler gespeichert. Dies wird zum Indizieren des Bitzählers in der nächsten Schleife verwendet.
Die zweite Schleife führt einen Binärzähler aus, extrahiert die Bits für jede Zeile und Iteration und fügt sie zusammen. Nachdem Sie alles zusammengefügt haben, wird es mithilfe der Zeichenfolgenersetzung wieder in das Switch-Map-Format übersetzt.
Ich denke, es gibt eine elegantere Möglichkeit, die Eingabezeichenfolge wiederzuverwenden, anstatt sie immer wieder neu zu erstellen.
Edit: Inspiriert von der Antwort in Python 3.8 ist hier eine viel kürzere Ersetzungsversion
Python 3 - ersetzen, 123 Bytes
Probieren Sie es online!
quelle
Ruby , 64 Bytes
Gibt ein Array zurück. Erhält Zahlen von1 zu 2v (woher v ist die Anzahl der "v" in der Eingabe) und Kippschalter basierend auf der v niedrigstwertige Bits. Dies ermöglicht es uns, ein Byte über Iteration von zu speichern0 zu 2v- 1 , weil der v niedrigstwertige Bits in 2v sind alle null.
Gibt in Ruby
i[j]
dasj
dritte Biti
ab dem niedrigstwertigen Bit zurück, auch bekannt als(i>>j)&1
.Probieren Sie es online!
quelle
Kohle , 28 Bytes
Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:
quelle
PHP , 93 Bytes
Probieren Sie es online!
Standalone-Programm, Eingabe über Kommandozeile.
Schleifen Sie die Anzahl der möglichen Permutationen der Eingabezeichenfolge basierend auf der Anzahl der
v
. Ersetzen Sie1
beim Hochzählen in der Binärdatei jede Binärdatei durch a^
und jede Binärdatei0
durch av
in der Eingabezeichenfolge.quelle