Einführung
Nehmen wir für einen Moment an, dass die Vipern und die Klippe nur zwei statt drei Schritte entfernt sind.
o
---
Hsss! |
';;' ___ /_\ ___ _
|
Sie sind leider ein Gefangener eines sadistischen Folterers. Sie müssen in jeder Kurve einen Schritt nach links oder rechts machen. Wenn Sie dies nicht tun, werden Sie sofort erschossen. Sie können Ihre Schritte im Voraus planen, aber sobald Sie den ersten Schritt getan haben, können Sie Ihren Plan nicht mehr ändern. (Und auch nicht trödeln; sie werden dich erschießen.)
Plötzlich kommt eine gute Idee in den Sinn ...
Ah! Ich kann einfach abwechselnd nach rechts und links gehen! Schritt nach rechts, Schritt nach links, Schritt nach rechts, Schritt nach links und so weiter ...
Ah ah ah, nicht so schnell. Wie gesagt, der Folterer ist sadistisch. Sie können wählen, ob Sie jeden Schritt, jeden zweiten Schritt oder jeden dritten Schritt und so weiter machen. Wenn Sie also naiv die Reihenfolge wählen RLRLRL...
, können Sie gezwungen werden, jeden zweiten Schritt zu machen, der mit beginnt LL
. Oh oh! Du wurdest von Vipern gebissen! Die Dunkelheit überflutet dich und alles andere verschwindet ...
Eigentlich nein, du bist noch nicht tot. Sie müssen sich noch Ihren Plan ausdenken. Nachdem Sie ein paar Minuten darüber nachgedacht haben, stellen Sie fest, dass Sie zum Scheitern verurteilt sind. Es gibt keine Möglichkeit, eine Reihe von Schritten zu planen, die Ihr Überleben garantieren. Das Beste, was Sie sich einfallen lassen können, ist RLLRLRRLLRR
. 1 Elf sichere Schritte und nicht mehr. Wenn der zwölfte Schritt ist R
, veranlasst der Folterer Sie, jeden Schritt auszuführen, und die letzten drei Schritte schicken Sie von der Klippe. Wenn der zwölfte Schritt ist L
, wird der Folterer Sie veranlassen, jeden dritten Schritt zu machen ( LRLL
), was Sie direkt in die Brut der Vipern und ihrer tödlichen Bisse bringt.
Sie wählen R
als zwölften Schritt, in der Hoffnung, Ihren Tod so lange wie möglich zu verzögern. Wenn der Wind in Ihren Ohren brüllt, wundern Sie sich…
Was wäre, wenn ich drei Schritte hätte?
Spoiler Alarm!
Du würdest immer noch sterben. Wie sich herausstellt, gibt es unabhängig von der Anzahl der Schritte einen Punkt, an dem Ihr Folterer eine Reihe von Schritten ausführen kann, um sicherzustellen, dass Sie Ihrem tödlichen Schicksal begegnen. 2 Wenn die Vipern und die Klippe drei Schritte entfernt sind, können Sie insgesamt 1160 sichere Schritte ausführen, und wenn sie vier Schritte entfernt sind, gibt es mindestens 13.000 sichere Schritte! 3
Die Herausforderung
Geben Sie bei einer einzelnen Ganzzahl n < 13000
eine Folge n
sicherer Schritte aus, vorausgesetzt, die Klippe und die Viper sind vier Schritte entfernt.
Regeln
- Kann entweder ein vollständiges Programm oder eine Funktion sein.
- Die Eingabe kann über STDIN oder ein Äquivalent oder als Funktionsargument erfolgen.
- Output müssen zwei verschiedene Zeichen (die sein kann
+/-
,R/L
,1/0
, etc.). - Beliebige Leerzeichen in der Ausgabe spielen keine Rolle.
- Das Hardcodieren einer Lösung ist nicht zulässig. Das würde diese Herausforderung trivialisieren.
- Ihr Programm sollte (theoretisch) in angemessener Zeit beendet sein. Wie in,
n=13000
könnte wie ein Monat dauern, aber es sollte nicht mehr als tausend Jahre dauern. Das heißt, keine rohe Gewalt. (Nun, zumindest versuchen Sie es zu vermeiden.) - Lebensbonus: Geben Sie eine Reihe von
2000
sicheren Schritten. Wenn Sie dies tun, wird der Folterer von Ihrer Hartnäckigkeit, Ausdauer und Voraussicht so beeindruckt sein, dass er Sie am Leben lässt. Diesmal. (Behandeln Sie diese Sequenz als Binärzahl und geben Sie das Dezimaläquivalent für die Überprüfung an. Dies dient zur Belohnung von Antworten, die schnell abgeschlossen werden, da die Beantwortung sehr lange dauern kann.) - Punktzahl: Bytes , sofern Sie sich nicht für den Bonus qualifizieren - multiplizieren Sie mit 0,75 .
1 Es gibt eine gute Erklärung für dieses Problem und eine "Lösung" durch einen der Stars von Numberphile, James Grime, auf seinem YouTube-Kanal hier: https://www.youtube.com/watch?v=pFHsrCNtJu4 .
2 Diese 80 Jahre alte Vermutung, bekannt als Erdos 'Diskrepanzproblem, wurde erst kürzlich von Terence Tao bewiesen. Hier ist ein sehr schöner Artikel im Quanta Magazine dazu: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .
3 Quelle: Ein SAT-Angriff auf die Erdos-Diskrepanz-Vermutung von Boris Konev und Alexei Lisitsa. Abgerufen von hier: http://arxiv.org/pdf/1402.2184v2.pdf .
quelle
n=13000
, werden die ersten 2000 Anweisungen davon einen Bonus gewinnen? Scheint sinnlos, also hast du wahrscheinlich etwas anderes gemeint?n=13000
innerhalb eines Jahres, vielleicht zehn, damit umzugehen. Wirst du einen Monat wartenn=2000
? Wahrscheinlich nicht. Und wenn ja , dann haben Sie den Bonus trotzdem verdient.Antworten:
Java, 915 × 0,75 = 686,25
Die Eingabe wird als Befehlszeilenargument verwendet.
Dabei werden fast alle Möglichkeiten ausprobiert (die einzige Einschränkung besteht darin, dass die ersten 8 Schritte nur innerhalb von -1..1 ablaufen sollten). Dabei wird Schritt für Schritt mithilfe einer magischen Voodoo-Heuristik ausgewählt, welchen Weg Sie zuerst ausprobieren möchten.
Es löst 2000 und sogar 4000 innerhalb von 1 Sekunde auf meinem (ziemlich schnellen) Computer. Benötigt mehr RAM für größere Zahlen; Die größte Eingabe, die ich innerhalb von 8 GB gelöst habe, ist 5023 und es dauerte etwa 30 Sekunden.
Dezimale Darstellung der Lösung für 2000 Schritte, wie für den Bonus erforderlich:
Anhängen ,
Yb
um es in CJam zu konvertieren , um binäre zurück.Über die Heuristik: Erstens gibt es ein Muster, das ich verwende: Alle 9 Schritte versuchen, die ersten 9 zu wiederholen, außer bei jedem (9 * x) -ten Schritt wird versucht, den x-ten Schritt zu wiederholen. Dies ist inspiriert von der Lösung, die ich heruntergeladen und in meiner Python-Antwort verwendet (fest codiert) habe.
Ich behalte im Auge, wie oft ich von dem Muster abgewichen bin und wie oft ich eine "Kante" erreicht habe (1 Schritt nach dem Sterben). Die heuristische Funktion ist im Grunde eine gewichtete Kombination dieser beiden Zahlen und der Anzahl der bisher ausgeführten Schritte.
Die Heuristik könnte weiter optimiert werden, um die Geschwindigkeit zu verbessern, und es gibt verschiedene Möglichkeiten, einen Zufallsfaktor hinzuzufügen.
Tatsächlich habe ich gerade über multiplikative Funktionen in Bezug auf dieses Problem gelesen, und es sieht so aus, als ob dies eine signifikante Verbesserung darstellen kann (TODO: Implementiere dies später).
Ungolfed und kommentiert:
quelle
Python 2, 236 Bytes
Dies ist für eine Brute-Force-ish-Methode ziemlich schnell und dauert nur einige Sekunden für n = 223, aber viel länger für n> = 224.
Erläuterung: Verfolgen Sie eine Liste von Zeichenfolgen-Listenpaaren (s, u), wobei die Liste u so ist, dass u [i] die aktuelle Position ist, nachdem Sie jedem i-ten Schritt in der Zeichenfolge gefolgt sind. Versuchen Sie, für jede Zeichenfolge in der Liste "L" oder "R" hinzuzufügen, und ändern Sie dann die Werte in der Liste, die sich überschneiden. (Wenn die resultierende Zeichenfolge die Länge 10 hat, addieren oder subtrahieren Sie 1 von den Positionen 1, 2, 5 und 10, je nachdem, in welche Richtung Sie sich bewegt haben). Wenn Sie 3 oder -3 überschreiten, werfen Sie das neue Paar weg, andernfalls behalten Sie es in der Liste. Die längsten Saiten bleiben am Ende erhalten. Wenn Sie eine Zeichenfolge mit der Länge n haben, geben Sie sie zurück.
quelle
//
gewundert , weil ich nicht wusste, dass das in Python 2Python 2, 729 Bytes
Ich denke, dies ist auch für den Bonus qualifiziert, wenn die Idee darin besteht, "schnell beendete Antworten zu belohnen".
Dies ist jedoch eine hartkodierte Antwort, die nicht im Sinne der Herausforderung ist (obwohl dies nicht ausdrücklich verboten war, als ich sie schrieb).
quelle