Ich habe eine kurbelbetätigte Spieluhr, die eine Serie von vier Noten spielen kann. Wenn ich die Kurbel drehe, zupft sie eine von vier Saiten, abhängig von der Position der Kurbel und der Drehrichtung. Wenn die Kurbel genau nach Norden gedreht wird, sieht die Box (mit den Saiten 1 bis 4) folgendermaßen aus:
1 | 2
|
O
4 3
Von dort aus kann ich die Kurbel im Uhrzeigersinn drehen, um die Saite 2 zu zupfen und die Kurbel nach Osten zu richten:
1 2
O---
4 3
Alternativ hätte ich auch die Kurbel von Norden gegen den Uhrzeigersinn drehen können, um die erste Saite zu spielen und mit einer nach Westen weisenden Kurbel zu enden:
1 2
---O
4 3
Zu jeder Zeit kann die Box dann eine von zwei Noten spielen: die nächste verfügbare Note im Uhrzeigersinn oder die nächste Note gegen den Uhrzeigersinn.
Herausforderung
Ihre Herausforderung besteht darin, ein Programm oder eine Funktion zu schreiben, die eine nicht leere Folge von Notenwerten (dh Ziffern 1
bis 4
) akzeptiert, und festzustellen, ob es jemals möglich ist, diese Notenfolge auf der Spieluhr abzuspielen. Produzieren Sie ein wahres oder falsches Ergebnis, um die Spielbarkeit oder Nichtspielbarkeit der Eingabe anzuzeigen.
Einige Notizen:
Die Eingabe macht keine Annahmen über die anfängliche Startposition. Die Eingaben
214
(von Osten ausgehend und streng gegen den Uhrzeigersinn bewegend) und234
(von Norden ausgehend und streng im Uhrzeigersinn bewegend) und beide sind gültig.Die Kurbel kann sich nach jeder Note frei in beide Richtungen bewegen. Eine Reihe derselben Note ist möglich (zB
33333
), indem man sich über eine Saite vor und zurück bewegt. Die Serie1221441
ist perfekt spielbar (von Westen aus zwei Schritte im Uhrzeigersinn, dann drei Schritte gegen den Uhrzeigersinn und dann zwei Schritte im Uhrzeigersinn).
Proben
Einige true
Fälle:
1
1234
1221
3333
143332
22234
2234
22214
1221441
41233
Einige false
Fälle:
13 (note 3 is never available after note 1)
1224 (after `122`, the crank must be north, so 4 is not playable)
121 (after `12` the crank is east; 1 is not playable)
12221 (as above, after `1222` the crank is east)
43221
quelle
Antworten:
Pyth,
3027 BytesHier ist die Idee:
Die Kurbel befindet sich immer in einer halben Ganzzahlposition
c
. Bei jedem Schritt spiegeln wir esn
durch Setzen über eine ganzzahlige Positionsnote widerc = 2*n-c
. Wennn
gültig,c
ändert sich um ± 1 mod 8. Wennn
ungültig,c
ändert sich um ± 3 mod 8. Wir reduzieren die Eingabe kumulativ, um alle Werte von zu erfassenc
, und prüfen dann, ob alle Noten gültig waren. Wir machen das für jeden Startwert vonc
, weil er kürzer ist als nur die, die an die erste Note angrenzen.Formatiert:
Testsuite .
quelle
CJam,
3431 BytesHab das auf meinem Handy gemacht, deshalb muss ich später eine Erklärung abgeben.Die Ausgabe ist nicht leer, wenn die Wahrheit stimmt.Versuchen Sie es online | Testsuite
Erläuterung
Der neue Code verschiebt das Layout ein wenig:
Gerade Zahlen entsprechen Saitenpositionen und ungerade Zahlen entsprechen Kurbelpositionen.
Folgendes passiert:
Der Stapel wird dann am Ende automatisch gedruckt. Mögliche Endpositionen befinden sich im Ausgang, z. B. für den Eingang ist
1
der Ausgang31
, dh die Kurbel kann nach links oder oben zeigen.Wenn nur CJam Filter mit extra Parameter hätte ...
Bearbeiten: Vorübergehendes Zurücksetzen, während ich mich davon überzeugt habe, dass dieses 29-Byte-Format funktioniert:
quelle
Haskell,
93 8887 BytesDies wird zu einer anonymen Funktion ausgewertet, die eine Zeichenfolge akzeptiert und einen Booleschen Wert zurückgibt. Testsuite hier.
Erläuterung
Die Idee ist, dass das Lambda auf der rechten Seite eine Zahl
a
zuordnet[[a,a+1],[a+1,a]]
, die zwei möglichen "Bewegungen", die die Kurbel über diese Zahl führen, gemäß dem folgenden Diagramm:In der anonymen Hauptfunktion wird zunächst
mapM((...).read.pure)
jedes Zeichen in eine Ganzzahl konvertiert, das obige Lambda darauf angewendet und einer der beiden Züge ausgewählt, wobei die Liste aller resultierenden Zugsequenzen zurückgegeben wird. Dann prüfen wir, ob eine dieser Sequenzen die Eigenschaft hat, dass die zweite Nummer jeder Bewegung der ersten Nummer der nächsten Modulo 4 entspricht, was bedeutet, dass es sich um eine physikalisch mögliche Sequenz handelt. Dazu verschieben wirzip
jede Sequenz mit ihrertail
, überprüfen die Bedingung fürall
die Paare und prüfen , ob dieany
Sequenz den Wert ergibtTrue
.quelle
Netzhaut, 50 Bytes
Ich denke das funktioniert?
Probieren Sie es hier aus.
quelle
Retina ,
127109 BytesDies druckt
0
oder1
entsprechend.Probieren Sie es online! (Dies ist eine leicht modifizierte Version, die alle Übereinstimmungen in der Eingabe markiert, anstatt
0
oder zu drucken1
.)Ich habe versucht, einen eleganten Algorithmus zu entwickeln, aber meine ersten Versuche waren nicht in der Lage, das Backtracking zu umgehen ... und das Backtracking zu implementieren, ist ärgerlich ... also habe ich eine Sprache verwendet, die das Backtracking für mich ausführt, bei der ich nur a codieren muss gültige Lösung. Leider ist die Kodierung ziemlich ausführlich und ziemlich überflüssig ... Ich bin sicher, dass dies verkürzt werden kann.
Während ich versuche, etwas besseres herauszufinden, ist hier eine etwas besser lesbare Version, wenn jemand herausfinden möchte, wie das funktioniert:
Und hier ist ein Hinweis:
quelle
MATL ,
5755 BytesHierbei wird die aktuelle Version (10.2.1) verwendet , die älter als diese Herausforderung ist.
BEARBEITEN (17. Januar 2017): Aufgrund von Änderungen in der Sprache
v
muss durch&v
undtL3$)
durch ersetzt werdenY)
(außerdem könnten einige andere Verbesserungen vorgenommen werden). Der folgende Link enthält diese beiden ÄnderungenProbieren Sie es online!
Erläuterung
Dies basiert auf zwei meiner Lieblingswerkzeuge für Codegolf: Brute Force und Convolution .
Der Code legt den Weg durch die Kurbel in Bezug auf den Koordinaten folgen
0.5
,1.5
usw. Jede Zahl gibt die Position der Kurbel zwischen den Noten. Der Code erstellt zunächst ein Pfadarray mit allen möglichen Pfaden, die mit der ersten Note der Eingabezeichenfolge beginnen. Jeder Pfad ist eine Spalte in diesem Array. Dies ist die Brute-Force- Komponente.Aus diesem Pfadarray wird ein Notenarray erhalten, bei dem jede Spalte eine realisierbare Folge von gespielten Noten ist. Wenn Sie sich beispielsweise von einer Position
0.5
zur1.5
nächsten bewegen , wird eine Note erzeugt1
. Dies besteht darin, den Durchschnitt zwischen Positionen zu bilden und dann eine Modulo-4-Operation anzuwenden. Der laufende Durchschnitt entlang jeder Spalte wird mit einer 2D- Faltung erstellt .Schließlich prüft das Programm, ob eine Spalte des Notenarrays mit der Eingabe übereinstimmt.
quelle
Pyth, 43
Test Suite
Dies ist wahrscheinlich sehr golffähig und auch nicht der optimale Algorithmus für das Golfen (ich erwarte, dass die Aufzählung aller Pfade kürzer sein wird?) ... Wie auch immer, wenn Sie einen Fehler mit dem Algorithmus finden, lassen Sie es mich bitte wissen, ich denke, es sollte funktionieren, aber ich habe mich vorher geirrt!
Ich erkläre meinen Algorithmus anhand der Beispieleingabe von
1221
. Dieses Programm bildet zunächst die Ziffern gegen ihre Nachfolger, etwa so:[[1,2],[2,2],[2,1]]
. Dann wird es ihre Differenzen mod4
(Pyth wird das Ergebnis , das das Vorzeichen des rechten Arguments übereinstimmt%
, so dass diese immer positiv ist):[3,0,1]
. Dann werden die Ergebnisse aufgeteilt auf0
und haben2
von jedem von ihnen abgezogen:[[1],[-1]]
.Nachdem das Setup abgeschlossen ist, erstellen wir eine Liste von
[-1,1,-1...]
und deren Negation[1,-1,...]
, die beide dieselbe Länge haben wie das resultierende Array von zuvor. Führen Sie dann für jede dieser Listen eine Zwischensubtraktion zwischen den Elementen der Liste und der im vorherigen Schritt erstellten Liste durch. Wenn dann eines der Ergebnisse nur leere Listen enthält, geben wir true aus.quelle
1221221
und bekommen1221441
?1221221
ist falsch und1221441
gibt insgesamt wahr, aber wenn ich verstehe, möchten Sie das Ergebnis nach diesem Schritt im Algorithmus? Wenn das der Fall ist, gibt es: von[3, 0, 1, 3, 0, 1]
bis[[3], [1, 3], [1]]
und[3, 0, 1, 1, 0, 3]
bis[[3], [1, 1], [3]]
. Lassen Sie mich wissen, wenn Sie etwas anderes erklärt haben möchten :)[[1], [-1, 1], [-1]]
und[[1], [-1, -1], [1]]
von hier aus können Sie sehen, dass die erste Liste keine Listen enthält, die sich abwechseln-1
und1
die andere Liste das Endergebnis liefert. Der Algorithmus ist ein bisschen stumpf, aber er ordnet Richtungsänderungen0
und Richtungen wie folgt zu.+/-1
Dann wird überprüft, ob keine Sprünge gemacht werden und die Richtungen sinnvoll sind.Matlab,
279180 BytesEine ziemlich faule Lösung, aber die kürzeste, die ich finden konnte. Ich habe eine spezielle Matrix erstellt: Wenn Sie den Zustand des Zupfers und die letzte zu zupfende Zeichenfolge codieren, wird ein Vektor zurückgegeben, der die neue Position des Zupfers codiert und angibt, ob der vorherige Zupfvorgang überhaupt möglich war. Jetzt durchlaufen wir alle Noten von den zwei möglichen Startpositionen und prüfen, ob eine davon zu einer spielbaren Melodie führt. Kann wahrscheinlich viel mehr golfen werden.
Erweiterte und erläuterte Quelle:
quelle
ES6,
104100 BytesBearbeiten: 4 Bytes dank @DigitalTrauma gespeichert.
Dies ist eine vollständige Neufassung, da mein bisheriger Ansatz fehlerhaft war.
Ich beginne damit, dass ich alle Ziffernreihen auf 1 oder 2 reduziere, je nachdem, ob der Lauf eine gerade oder eine ungerade Zahl enthält. Ich suche dann nach allen illegalen Kombinationen:
13|24|31|42
(gegenüberliegende Seiten)3[24]{2}1
wie3221
und3441
sind illegal4xx2
,1xx3
und2xx4
wox
ist eine der fehlenden Ziffern(.).\1
wie Dinge121
illegal sind (111
wurde auf früher reduziert1
)Wenn es keine illegalen Paare oder "Tripel" gibt, ist die gesamte Kette legal (der Beweis durch Induktion bleibt als Übung, da es hier spät in der Nacht ist).
Ich habe versucht,
3[24]{2}1|1[24]{2}3
mit einer negativen Lookahead-Behauptung zu vereinfachen , aber es stellte sich heraus, dass dies länger war.quelle
f("1122") => true
@DigitalTraumaf("1221221")
die Antwort falsch ist, also muss ich überdenken.[24][24]
,(2|4)\1
aber nicht ausreichend getestet. Das tut mir leid.[24][24]
zu[24]{2}
?JavaScript (ES6), 80 Byte
Erläuterung
i%4
ist die aktuelle Kurbelposition:Eingerückt und kommentiert
Prüfung
quelle
|
das in diesem Fall funktioniert?(x.map(...),v)
. Es funktioniert, weil das Array, das von dermap
Rückgabe umgewandelt wird, auf0
und0|v == v
.Lua ,
146 142 108 162 159 149 144 135 132 118113 BytesGibt true oder false bei einer Zahlenfolge zwischen 1 und 4 zurück. (Verarbeitet keine Daten oder Zahlen außerhalb des Bereichs.)
Verfolgt einfach, was die letzte Bewegung war und prüft, ob diese Bewegung eine Umkehrung der letzten Bewegung ist (IE, 121 oder 12221) oder ob die Bewegungsentfernung mehr als möglich ist.
EDIT 1 :
6 Bytes gespeichert. Ich habe vergessen, dass
if (int) then
true zurückgegeben wird, wenn int nicht null ist.Somit:
ändert sich zu:
Auch durch Restrukturierung ein paar Bytes gespart.
EDIT 2 :
Ich finde das langsam heraus. Ich habe die Dokumentation hier gelesen: http://www.lua.org/pil/ Und eine der nützlicheren Seiten zum Golfen ist http://www.lua.org/pil/3.3.html
Dies ist insbesondere sehr hilfreich:
Dies bedeutet für mich, dass ich meine Deklaration für q ( die ursprünglich auf 0 gesetzt war ) entfernen kann, da sie so lange als "falsch" betrachtet wird, bis sie gesetzt wird. Dadurch spare ich ein paar Bytes mehr.
Eine andere erwähnenswerte Sache, die ich nicht benutze, ist, wenn Sie Werte in Lua tauschen möchten, können Sie einfach
a,b=b,a
auf eine temporäre Variable verzichten.EDIT 3
Durch eine clevere Rekonstruktion und eine neue Funktion habe ich den Byte-Countdown um 9 erhöht.
Bester Modus zum Empfangen von Eingaben
Wenn Sie eine Liste mit Zahlen einlesen und nacheinander mit ihnen arbeiten müssen, können Sie Folgendes verwenden:
Im Vergleich zu Ihrer Alternative mit string: sub sehen Sie den Wert für Golf (oder allgemeine Verwendung):
Restrukturierungsfunktionen oder Strings
Zweitens, wenn Sie mehrere Deklarationen in einer Zeile haben und einer der Werte eine Funktion ist oder wenn Sie eine Bedingung haben, in der Sie eine Zahl mit dem Ergebnis einer Funktion wie dieser vergleichen:
Wenn Sie es so umstrukturieren, dass die schließenden Klammern das letzte Zeichen in der Bedingung oder Deklaration sind, können Sie ein Zeichen wie das folgende ausschneiden:
Rückgabebedingungen, die True oder False anstelle von 'True' oder 'False' entsprechen
Ich fand einen halb amüsanten Weg, um meinen Byte-Count noch weiter zu reduzieren. Wenn Sie true oder false zurückgeben müssen, können Sie eine Anweisung zurückgeben, die true oder false entspricht und weniger Zeichen als "true" oder "false" enthält.
Vergleichen Sie zum Beispiel:
Zu:
quelle
121
sollte falsch ausgeben.MATL, 49 Bytes (nicht konkurrierende 1 )
1. Die Antwort (ab) verwendet die weniger strenge Indizierung neuerer Versionen von MATL und hätte zum Zeitpunkt der Veröffentlichung dieser Herausforderung nicht funktioniert.
Probieren Sie es online! .
Ich habe diese Herausforderung beim Best of PPCG 2016 gesehen und festgestellt , dass dies meinen Lieblingsoperator verwenden kann :
Oder
diff
in MATLAB / Octave (ich werde die MATLAB / Octave-Terminologie in meiner Erklärung frei verwenden, da sie für Menschen leichter zu lesen ist). Dieser Befehl berechnet die elementweise Differenz in einem Vektor oder in diesem Fall in einem Zeichenarray.Für dieses Problem weisen die Unterschiede ein interessantes Muster auf. Beachten Sie, dass
Für das Differenzmuster (vorerst ohne Berücksichtigung des
1-4
Übergangs) bedeutet dies, dassIch implementierte dies, indem ich für jedes Array die erste Null fand. Ich trimme die Null heraus und multipliziere alle Elemente danach mit
-1
. Das bedeutet für das Endergebnis, dass alle Elemente müssen das gleiche Vorzeichen haben. Natürlich gibt es das kleine Problem des-3
Gleichmachens+1
und des2
generellen Verbots. Ich habe das gelöst, indem ich die Mengenvereinigung des Ergebnisses mit genommen[1 -3]
und überprüft habe, ob diese Größe 2 hat (dh, keine unzulässigen Elemente sind durch die Vereinigung in die Menge eingegangen). Wiederholen Sie diesen[-1 3]
Vorgang für und prüfen Sie, ob einer der beiden (oder beide im Fall einer Eingabe mit einer Länge) wahr ist.quelle
M
, das letzte Mal, als ich es ausprobiert habe, hat es anders funktioniert als erwartet, also habe ich es vorerst einfach ignoriert. Ist es richtig zu sagen, dass es sein muss,3M
weil ich dann die Eingabe von not)
, not:
but ofq
(Überspringen,w
da es keine normale Funktion ist) bekomme ?w
wird übersprungen, da dies keine normale Funktion ist. Normale Funktionen, die keine Eingaben benötigen, werden ebenfalls übersprungenPython (3.5)
160151150 BytesEine rekursive Lösung
Ungolfed ohne Lambda
Ich drehe den ganzen Kasten anstelle der Kurbel. Die Kurbelposition liegt zwischen dem ersten und dem zweiten Zeichen der c-Zeichenfolge. Ich muss alle Startpositionen der Kurbel testen.
Trick verwenden, um die Saite zu drehen
Die übliche Art, einen String in python (
s[i:]+s[:i]
) zu drehen, muss sowohl index als auch string wiederholen. In diesem Fall dupliziere ich die Zeichenfolge und schneide die ersten Zeichen ab.Testfälle
quelle
3"[i:]) for
.Python 2 , 65 Bytes
Probieren Sie es online!
quelle
JavaScript (ES2015),
1109515 Bytes von Neil gespeichert! Originalversion ungolfed:
Tests: https://jsbin.com/cuqicajuko/1/edit?js,console
quelle
(s,d)=>(h=s[0],t=s.slice(1),g=t[0],!g||(d?g==h?p(t,-d):g%4==(h-d)%4&&p(t,d):p(s,1)||p(s,-1)))
Turing-Maschinencode, 395 Bytes
Probieren Sie es online!
Dies ist im Grunde ein staatlicher Ansatz:
a
,b
,c
, Undd
ist „unentschieden states“ , die erst am Anfang auftretenN
,E
,S
, UndW
sind die "beschlossen Staaten", offenbar für stehendeN
orth,E
ast,S
outh undW
est.quelle
Thue, 203 Bytes
Ich kann mir nicht vorstellen, wie ich weiter Golf spielen kann.
Wenn die Notenfolge möglich ist, wird die Endrichtung ausgegeben, andernfalls ist die Ausgabe leer.
quelle
Prolog (SWI) , 117 Bytes
Definiert ein Prädikat
p
, das bei abspielbaren Eingaben (als Liste von Ganzzahlen angegeben) erfolgreich ist und bei nicht abspielbaren Eingaben fehlschlägt. Probieren Sie es online!Erläuterung
a
Definiert eine Nachbarschaftsbeziehung zwischen NoteN
und KurbelpositionP
. Wir definieren die Position p zwischen den Noten p und p + 1 . Somit ist eine Position benachbart zu notierenN
iffN
(P=N
); oderN=1,P=4
); oder!
) und die Position ist gleichN-1
(P is N-1
).m
Nimmt eine Liste von Noten und versucht, eine Liste von Positionen zu generieren, die diese Noten spielen.A
Wird die Note gerade gespielt? Wird die Note gerade gespieltB
?X
ist die aktuelle Kurbelposition,Y
ist die nächste Kurbelposition. Ein Zug ist gültig, wenna(A,X)
).a(B,X)
).a(B,Y)
). undX\=Y
).Wenn all dies zutrifft, rekursieren Sie. Wenn wir eine Note erfolgreich gefunden haben (
m([_],_)
), kann die Notenfolge abgespielt werden.Für diese Frage ist es uns nur wichtig, ob eine Abfolge von Bewegungen vorhanden ist. Daher definieren wir, dass die generierte Liste der Kurbelpositionen
p
aufgerufenm
und verworfen wird.Sehen Sie eine ungolfed Version und überprüfen Sie alle Testfälle hier .
quelle