Es gibt 40 Möglichkeiten, wie ein gerichteter Hamilton-Pfad in einem 3 × 3-Raster angeordnet werden kann:
Diese Grafik ( danke Sp3000! ) Zeigt nur die 20 ungerichteten Pfade. Überquere jede farbige Linie in beide Richtungen für die 40 gerichteten Pfade.
Herausforderung
Schreiben Sie unter Verwendung von ausschließlich druckbarem ASCII ein 3 × 3-Zeichenraster, z.
ABC
DEF
GHI
Wenn jeder der 40 gerichteten Pfade als 40 einzeilige Programme mit 9 Zeichen aus diesem Raster gelesen wird, ist es das Ziel, dass jedes Programm eine eindeutige Ganzzahl von 1 bis 40 ausgibt. Dies für alle 40 Pfade zu tun, erscheint schwierig und unwahrscheinlich. Sie müssen es also nur für so viele Pfade wie möglich zum Laufen bringen.
Die Einsendung, deren 40 Pfadprogramme die deutlichsten Zahlen von 1 bis 40 ausgeben, wird der Gewinner sein. Tiebreaker geht auf die frühere Vorlage.
Pfadprogramme, bei denen ein Fehler auftritt oder die keine Ganzzahl von 1 bis 40 ausgeben, oder die eine Ganzzahl ausgeben, die bereits von einem anderen Pfadprogramm behandelt wurde, werden nicht gezählt. Speziell:
- Programme, die beim Kompilieren, Ausführen oder Beenden fehlerhaft sind, werden nicht gezählt. Warnungen sind in Ordnung.
- Programme, die keine Ganzzahl von 1 bis 40 ausgeben oder etwas leicht Missgebildetes ausgeben, wie z. B.
-35
oder,35 36
werden nicht gezählt. - Programme, für deren Ausgabe Benutzereingaben erforderlich sind, werden nicht gezählt.
- Programme, die niemals enden, werden nicht gezählt.
- Von nun an werden Programme, die nicht deterministisch sind, nicht mehr gezählt.
- Andernfalls werden gültige Programme, die eine Ganzzahl von 1 bis 40 ausgeben, die bereits von einem anderen gültigen Programm ausgegeben wurden, nicht gezählt. (Das erste Programm wird gezählt.)
- Nur Programme, die ganzzahlige Darstellungen von Zahlen von 1 bis 40 (einschließlich) ausgeben, werden auf Ihre Gesamtsumme angerechnet. Die Zahlen werden voraussichtlich in der üblichen sein
1
,2
, ...,39
,40
Form, sofern dies nicht die Norm für Ihre Sprache ist. (Eine nachgestellte Zeile in der Ausgabe ist in Ordnung.) - Welche Zahlen Ihre Programme ausgeben und in welcher Reihenfolge sie sich befinden, spielt keine Rolle. Nur die Anzahl der verschiedenen Ganzzahlen aus gültigen Programmen ist von Bedeutung.
Alle Pfadprogramme müssen in derselben Sprache ausgeführt werden. Die "Programme" können jedoch Funktionen (ohne erforderliche Argumente) oder REPL- Befehle sowie vollständige Programme sein, die ihre Ziel-Ganzzahl ausgeben oder zurückgeben. Sie können Funktionen, REPL-Befehle und vollständige Programme mischen und abgleichen.
Ihre 9 druckbaren ASCII-Zeichen müssen nicht eindeutig sein.
Beispiel
Wenn dein 3 × 3 Raster wäre
ABC
DEF
GHI
und Ihre 40 Programme und Ausgaben sahen so aus
ABCFEDGHI -> 26
ABCFIHEDG -> 90
ABCFIHGDE -> 2
ABEDGHIFC -> syntax error
ADEBCFIHG -> prints 40 but then errors
ADGHEBCFI -> 6
ADGHIFCBE -> 6
ADGHIFEBC -> 6
CBADEFIHG -> runtime error
CBADGHEFI -> 3
CBADGHIFE -> 4
CFEBADGHI -> -32
CFIHEBADG -> 38.0
CFIHGDABE -> "36"
EDABCFIHG -> 33
EFCBADGHI -> no output
EHGDABCFI -> compilation error
EHIFCBADG -> 8
GDABCFEHI -> 22
GHEDABCFI -> 41
IHGDEFCBA -> 0
GDEHIFCBA -> '9'
EDGHIFCBA -> +10
CFIHGDEBA -> 11
GHIFCBEDA -> error
IFCBEHGDA -> error
EBCFIHGDA -> prints 23 but then loops infinitely
CBEFIHGDA -> randomly prints either 24 or 44
GHIFEDABC -> error
IFEHGDABC -> 30
EFIHGDABC -> 39
IHGDABEFC -> 7
GDABEHIFC -> 29
EBADGHIFC -> -1
GHIFCBADE -> 26
IHGDABCFE -> 1
IFCBADGHE -> error
GDABCFIHE -> no output
IHEFCBADG -> no output
IFCBADEHG -> "quack"
Ihre Punktzahl wäre 14, da es 14 verschiedene Ganzzahlen von 1 bis 40 gibt, die gültig ausgegeben werden, nämlich 26 2 6 3 4 33 8 22 11 30 39 7 29 1
.
quelle
123654789
Antworten:
PARI / GP - 24
PARI / GP ignoriert Leerzeichen zwischen Ziffern, so dass
1 8 2
beispielsweise als behandelt wird182
. Dasselbe könnte für Perl funktionieren, indem die Leerzeichen durch Unterstriche ersetzt werden. Ich habe nicht den gesamten Suchraum ausgeschöpft, daher gibt es möglicherweise bessere Kandidaten.Ein Programm kann als gp
gp -q -f program.gp
oder interaktiv in der Repl eingegeben werden.Ausgabe
Alle bis auf 4 Werte liegen innerhalb des erforderlichen Bereichs mit 12 doppelten Einträgen.
Aktualisieren
Ich bin mit dem Knirschen fertig, es gibt sechs verschiedene 23er und nur eine 24er (wie von Zeilen gelesen):
Das Programm, das ich für das Knirschen verwendete, ist unten. PARI / GP verfügt nur über eingeschränkte Funktionen zur Verarbeitung von Zeichenfolgen. Behandeln Sie daher hauptsächlich Char-Arrays (auch bekannt als
Vecsmall
). Die Betreiber getestet sind+
,-
,*
,\
(Boden div)%
,;
(Ausdruck Separator, im Wesentlichen verwirft alles , bevor es), und(Raum, wie oben beschrieben). Der Exponentenoperator
^
könnte ebenfalls hinzugefügt werden, wird jedoch zu langsam, um ausführlich getestet zu werden.quelle
Toter Fisch , 18
Dies war tatsächlich die erste Sprache, die ich ausprobierte, bevor ich über Infix-Operatoren nachdachte. Ich poste es jetzt wegen der schieren Komik der Idee, dass Deadfish für etwas nützlich sein könnte.
Für diejenigen, die Deadfish nicht kennen,
i
ist Inkrement,s
ist Quadrat undo
wird ausgegeben, wobei der Akkumulator bei 0 beginnt (es gibt auch eine vierte Anweisungd
zur Dekrementierung, die hier nicht verwendet wird). Die Tatsache, dass wir kein automatisches Drucken haben und verwenden müssen,o
ist ein großer Nachteil, aber überraschenderweise macht Deadfish diesbezüglich nicht allzu schrecklich. Es stellt sich heraus, dass die optimale Platzierung des Ausgabeoperators in der Mitte liegt.quelle
Python REPL und viele mehr,
2223Wichtigste Beobachtung: Wenn Sie das Raster wie ein Schachbrettmuster einfärben, wechselt der Pfad zwischen den Rasterfarben und beginnt und endet mit derselben Farbe.
Immer noch brachial zum Besseren zwingen.Das Ausprobieren+*%
(und auch**
bei Sprachen, bei denen^
es um Potenzierung geht) ist leider nicht besser gelaufen. Ich habe auch versucht, bitweise Operatoren einzuwerfen, und nur^
(xor) schien ein wenig zu helfen, aber die Suche dauerte zu lange, sodass ich aufgegeben habe.quelle
6+7*5%6%4
,6+7*4%6%5
und6+8*4%6%5
( von links nach rechts, von oben nach unten), und sonst nichts.+
und-
in den Ecken / in der Mitte zuzulassen ? Da es sich sowohl um unäre als auch um binäre Operatoren handelt, sollte dies dennoch zu allen gültigen Ausdrücken führen. Es ist unwahrscheinlich, dass es zu einer besseren Lösung führt, aber es erweitert zumindest den Suchraum. Hmm, eigentlich könnte es ein Problem sein, weil Sie mit Folgen von Operatoren enden könnten.J, 15
Dies gibt nur gültige Zahlen aus, aber viele sind Duplikate. Die eindeutigen Werte sind
17 11 16 28 31 23 13 10 21 33 18 24 22 29 27
. Sie können definitiv bessere Ergebnisse erzielen, indem Sie die Operatoren und die beteiligten ganzen Zahlen ändern.quelle
Yes
.> <>, 36 *
Wenn du Glück hast!
Da für die Abfrage kein deterministischer Code erforderlich ist, müssen wir nur beweisen, dass es möglich (auch wenn unwahrscheinlich) ist, 36 Zahlen zurückzugeben, und wir sind fertig.Es war gut, solange es dauerte, denke ich.(Für diejenigen, die nicht mit> <> vertraut sind, finden Sie hier eine großartige Einführung. )
Ich habe mich für die Anweisung "x" in> <> entschieden, die die Richtung der Anweisungszeiger nach dem Zufallsprinzip nach oben, unten, links oder rechts ändert. Da unser Code nur aus einer Zeile besteht, können wir die Fälle nur betrachten, wenn sie nach rechts oder links gehen. Wenn der Zeiger nach oben oder unten geht, wird nur die Anweisung "x" erneut getroffen.
Die Anweisung "n" fügt die Nummer oben im Stapel ein und druckt sie aus. Wenn der Stapel jedoch leer ist und nichts zu öffnen ist, wird ein Fehler ausgegeben.
Die "l" -Anweisung schiebt einfach die Länge des Stapels auf den Stapel (und glücklicherweise sendet sie keinen Fehler, wenn der Stapel leer ist), also zum Beispiel, wenn der Stapel leer wäre und "l" aufgerufen würde würde 0 auf den Stapel schieben. Wenn wir jetzt wieder "l" aufrufen würden, würde der Stapel, da er ein Element (0) hat, 1 an die Spitze des Stapels schieben, und dies würde bedeuten, dass sich zwei Dinge auf dem Stapel befinden würden, und das würde bedeuten, dass Wenn wir noch einmal "l" rufen würden, würden wir 2 auf den Stapel schieben usw. Wir können also "l" verwenden, um eine beliebige Zahl auf den Stapel zu schieben, wie oben gezeigt.
Das ";" Anweisung beendet das Programm.
Die Idee bei der Verwendung von "x" ist, dass beispielsweise nur ein "x" im Code vorhanden ist (wobei A, B, C, D Anweisungen sind):
Das Programm würde A, dann B, dann C ausführen, und bei Erreichen von "x" hätten wir zwei Möglichkeiten: Der Code geht entweder weiter nach rechts und drückt das ";" und verlässt oder es geht nach links und führt C, dann B, dann A, dann D aus und verlässt erst dann. Wenn unser Code also ein "x" enthält, erhält das Programm zwei mögliche Programmabläufe, aus denen wir das am besten geeignete Programm auswählen können.
Wenn es zwei oder mehr "x" gibt, erhalten wir unendlich viele mögliche Programmabläufe.
Unser Code hat fünf "x", außerdem befindet sich jedes von ihnen in einer "Startzelle" der Hamilton-Pfade, was bedeutet, dass jedes einzelne Programm mit einem "x" beginnt und jedes Programm die folgende Struktur hat:
Wobei A, B, C, D zu {gehören; , n, l, l} Dies bedeutet, dass es nur 12 eindeutige Programme gibt. Da wir außerdem immer mit einem "x" beginnen, können wir uns den Fall ansehen, wenn das Programm nach links geht, sodass symmetrische Programme auch als gleich angesehen werden können. Bis zur Symmetrie gibt es nur 6 verschiedene mögliche Programme. Nur 4 davon kommen in den Programmen vor, die als Hamilton-Pfade generiert wurden:
Schauen wir uns das erste Programm "xnxlxlx; x" an. Wenn wir beim ersten Schritt nach rechts gehen, drücken wir den Druckbefehl, der einen Fehler auslöst, da wir nichts auf dem Stapel haben. Wenn wir nach links gehen, drücken wir den Befehl zum Beenden des Programms. Daher können wir von diesen Programmen keine Zahlen ausgeben .
Das zweite Programm, "xlxnxlx; x", ist viel hoffnungsvoller, da beim Beginnen eine Null auf den Stapel gelegt wird. Wenn wir dann beim nächsten "x" nach links gehen, erhält unser Stapel eine Eins Wenn wir wieder nach rechts gehen, haben wir eine 2, die wir dann drucken können und die wir fortsetzen können, um das Programm zu beenden. Wir können beobachten, dass wir tatsächlich jede gerade Zahl drucken können , da wir im "xlx" -Teil am Anfang eine Anzahl von willkürlichen Größen erreichen können, indem wir eine bestimmte Anzahl von Malen nach rechts, nach links und wieder nach rechts gehen.
Ähnlich ist zu sehen, dass das dritte Programm xnxlx; xlx eine beliebige ungerade Zahl ausgeben kann , indem es am Anfang nach links geht und dann die Routine "xlx" nur dieses Mal nach links, dann nach rechts und dann nach links wiederholt.
Und das vierte Programm ist im Wesentlichen dasselbe wie das zweite Programm und kann eine beliebige gerade Zahl ausgeben .
Für die benötigten Programme haben wir also:
Das sind 4 Programme, die keine Zahlen ausgeben können, 20, die eine gerade Zahl ausgeben können, 16, die eine ungerade Zahl ausgeben können. Da es genau 20 gerade Zahlen und mindestens 16 ungerade Zahlen im Bereich von 1 bis 40 gibt, besteht mit einer bestimmten Wahrscheinlichkeit die Möglichkeit, dass von diesem Codeblock 36 verschiedene Zahlen im Bereich von 1 bis 40 ausgegeben werden.
quelle
GolfScript, 8
Derzeit die Lösung mit der höchsten Punktzahl. : PWar schön, solange es dauerte.Programme
quelle
0)1#2#3(4
bei 15. Schöne Symmetrie auch.CJam, 14
Nachfolgend die Arbeitsprogramme:
Die generierten Werte sind: [1, 3, 4, 11, 13, 14, 20, 21, 22, 23, 24, 30, 31, 33]
quelle
dc (20)
32 Ausgänge, davon 20 unterschiedliche (mit einem gekennzeichnet
$
)2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 16, 20, 22, 24, 25, 32, 34, 40
quelle