Einführung
"Muhuhuhahahah!" Der verrückte Wissenschaftler lacht. "Du bist in meinem eigenen kleinen Spiel gefangen!"
Vor dir ist eine tödliche Schlangengrube, während hinter dir ein Abgrund ohne Boden ist. Es gibt keinen Ausweg, du steckst fest!
"Zwei Schritte vor dir ist die Schlangengrube, und zwei Schritte hinter dir ist der Abgrund. Aber! Bevor du dich bewegst, MUSST du eine Abfolge von Schritten aufschreiben, vorwärts und rückwärts, und sie mir geben. Aber! Weil ich fühle mich heute ein bisschen böse , ich kann dich dazu bringen, anstelle von jedem Schritt jeden nSchritt zu machen, wo nweniger als deine Sequenzlänge ist!
Wähle jetzt mit Bedacht. "
Was ist die maximale Anzahl von Schritten, die Sie vor Ihrem bevorstehenden Tod unternehmen können?
Aufgabe
Das obige Intro ist eine Wendung in Bezug auf Erdős Diskrepanz-Vermutung , die sich kürzlich als wahr erwiesen hat (wenn Sie mehr darüber verstehen möchten, schauen Sie sich dieses Video von James Grime an - ich habe ihm die Wendungsfrage "gestohlen").
Die Antwort auf das Intro sind 11Schritte, aber ich werde mit einem Beweis nicht zu weit gehen. Die Antwort, wenn der Abstand zwischen Ihnen und den beiden "Gefahren" 3Schritte waren, ist 1160Schritte, obwohl dies noch nicht richtig bestätigt wurde.
Ihre Aufgabe ist es, ein Programm zu erstellen, das die längste Sequenz von Schritten generiert, die Sie für eine größere ausführen können. xDabei xgibt es die Anzahl der Schritte zwischen Ihnen und den beiden "Gefahren". Ihr Programm muss eine Eingabe für xund eine gültige Sequenz dafür ausgeben x.
Für die Zwecke dieser Herausforderung bedeutet dies +einen Schritt vorwärts und -einen Schritt zurück.
Eine Ausgabe für eine Eingabe 2ist also:
+--+-++--++
Welches funktioniert, egal was nder verrückte Wissenschaftler wählt. Für unsere Herausforderung x = 5.
ANMERKUNG: Diese Herausforderung ist kein Betrug dieser Herausforderung oder dieser Herausforderung , da sich meine Herausforderung auf die Ausgabe im Gegensatz zum Code selbst konzentriert - mit anderen Worten, es ist keine Code-Golf-Herausforderung. Darüber hinaus basieren diese Herausforderungen auf einer x = 3bereits festgelegten Obergrenze.
Regeln:
- Ihr gesamtes Programm sollte in Ihre Antwort passen. Wenn es jedoch nicht passt, geben Sie bitte ein zusätzliches Github-Repository oder ähnliches an.
- Sie können sowohl Ihre Antwort als auch Ihr Programm aktualisieren, wenn Sie durch die Optimierung Ihres Codes eine bessere Punktzahl erzielen können. In diesem Fall müssen Sie jedoch alle Angaben in der folgenden Liste aktualisieren.
- In Ihrer Antwort müssen Sie haben:
- Ihr Programm in seiner Gesamtheit oder ein Link zu einem GH-Repository, in dem sich Ihr Code befindet
- Die Anzahl der generierten Schritte - dies ist Ihre endgültige Punktzahl .
- Sie müssen auch eine Online-Version der Sequenz in einem Pastebin oder ähnlichem bereitstellen . Auf diese Weise können wir Ihre Antwort überprüfen.
- Der Zeitpunkt, zu dem Ihr Endstand zuletzt aktualisiert wurde, damit ich Ihren Verlauf nicht überprüfen muss
- Sie dürfen Sequenzen NICHT vorher fest codieren.
- Ihr Programm muss für alle funktionieren
x(woxist die Anzahl der Schritte zwischen Ihnen und dem Pit & Chasm), aber Sie müssen nur die Punktzahl für bereitstellenx = 5.
Die Antwort mit der höchsten Punktzahl gewinnt!
quelle
nSchritt ausgeführt haben, wobeineine beliebige Zahl unter Ihrer Sequenzgröße liegt.x=5würde einen bedeutenden Durchbruch erfordern, der eine Veröffentlichung wert wäre. Bedenken Sie, dass das Maximum von 1160 fürx=3wurde bewiesen , und im Jahr 2014 veröffentlicht und keine weiteren Werte bekannt sind. .Antworten:
Rust, Score = 4997216, Zeit = 2017-07-12 00:18 UTC
Dies verbessert das beste Ergebnis, das ich in der Literatur finden konnte, nämlich 1148805 (Ronan Le Bras, Carla P. Gomes, Bart Selman, Über das Erdős-Diskrepanzproblem , 2014), um den Faktor 4,3.
Ausgabesequenz der Länge 4997216
Quellcode auf GitHub
Laufen
Das Programm akzeptiert die maximale Diskrepanz als Argument (dies ist x - 1 in der Sprache der Challenge, um sich an der allgemeineren mathematischen Konvention auszurichten). Es erzeugt inkrementelle Ausgaben in einem leicht komprimierten Format, das für x = 3 so aussieht :
wobei
addmittels einer Folge von Zeichen an das Ende der aktuellen Sequenz anzuhängen,deleteMittel gewisse Anzahl von Zeichen von dem Ende der aktuellen Sequenz entfernen, undlengthdie Länge der aktuellen Sequenz geltend macht. Dieses Schema vermeidet die Produktion von vielen Gigabyte Zwischenergebnissen, da immer längere Sequenzen entdeckt werden. Sie können das bisher beste Ergebnis mit dem folgenden Python-Programm extrahieren:Wie es funktioniert
Es gibt hier ungefähr tausend Codezeilen, daher ist dies nur eine sehr grobe Übersicht.
Wir beschränken die Suche auf vollständig multiplikative Folgen (solche mit f ( a · b ) = f ( a ) · f ( b )), weil wir uns nur darum kümmern müssen, die Teilsummen für n = 1 und die Teilsummen zu begrenzen Summen für n ≥ 2 erfüllen automatisch die gleiche Schranke.
Definieren Sie für jeden Teilstring f ( i + 1),…, f ( j ) einer teilweise zugewiesenen Zeichenfolge (jedes Element ist also '+', '-' oder unbekannt) die Gefahr + ( i , j ) als zweimal die Anzahl der '+' minus der Länge j - i (der Einfachheit halber lassen wir i so klein wie - x + 2 sein und nehmen an, dass f (- x + 3) = f = f (0) = '+' für dieser Zweck). Definiere Gefahr - ( i , j ) ähnlich. Dann wird die Grenze für Teilsummen für n= 1 ist äquivalent zu der Bedingung , dass , wenn i ≡ j ≡ x (mod 2), Gefahr + ( i , j ) ≤ x - 2 und Gefahr - ( i , j ) ≤ x - 2.
Wir bauen eine inkrementelle Datenstruktur auf, die konstante Zeitabfragen für den Teilstring mit der größten Gefahr mit logarithmischen Zeitaktualisierungen unterstützt. Es funktioniert durch die Zuordnung von vier Werten:
mit jeder Zeichenfolge der Länge 2, jeder anderen Zeichenfolge der Länge 4, jeder vierten Zeichenfolge der Länge 8 und so weiter. Die mit einer längeren Zeichenfolge verknüpften Werte können in konstanter Zeit aus den mit ihren beiden Hälften verknüpften Werten berechnet werden.
Mit dieser Struktur, die um einige Zusatzinformationen ergänzt ist, können wir die Weitergabe von Beschränkungen und die Erkennung von Konflikten bei Teilsequenzen sehr schnell durchführen. Wir verwenden es, um eine CDCL- ähnliche Suche mit Einheitenausbreitung, Entscheidungsebenen und nicht-chronologischem Backtracking (aber vorerst ohne Lernen von Klauseln) für vollständige Sequenzen mit immer größeren Längen durchzuführen.
Bei jedem Suchschritt raten wir nach dem frühesten nicht zugewiesenen Zeichen. Die Heuristik, mit der diese Vermutung erstellt wurde, ist sehr wichtig, um viele Rückverfolgungen zu vermeiden. wir verwenden f (3 · k ) = - f ( k ), f (3 · k + 1) = '+', f (3 · k + 2) = '-'.
Ergebnisse
Die Suchvorgänge mit den Abweichungen 0, 1 und 2 finden sofort die optimalen vollständig multiplikativen Folgen der Länge 0, 9 und 246.
Die Suche nach Diskrepanz 3 bleibt bei 41319 innerhalb von Sekunden hängen, was ziemlich weit von der bekannten optimalen vollständig multiplikativen Sequenz der Länge 127645 entfernt ist, die von Le Bras et al., 2014, gefunden wurde (und einer sehr geringfügig längeren nicht multiplikativen Erweiterung der Länge 130000, die kurz danach gefunden wurde) ), aber viel besser als die bekannteste Sequenz vor der von Länge 17000 .
Die Diskrepanz 4 Suche verbessert die längste Folge mehr oder weniger kontinuierlich für etwa fünf Minuten , bis er bei 4997216. Die besten bisher bekannten Sequenz der Länge 1.148.805 = 9 · 127.645 wurde erweitert von der Diskrepanz 3 - Sequenz klemmt durch jedes Zeichen ersetzen s mit + - - + - ++ - s . Soweit ich das beurteilen kann, sind Sequenzen dieser Länge zu schwer für einen allgemeinen SAT-Löser, um sie direkt zu verbessern (aber vielleicht können Sie, lieber Leser, mich als falsch beweisen!).
Ich gehe davon aus, dass ich meinem Programm eine Art Lernklausel hinzufügen muss, um diese Barrieren zu überwinden.
Die Sequenz als 2187 × 2285-Bitmap
(Klicken Sie hier, um in voller Auflösung anzuzeigen.)
quelle
Haskell , Score = 9020, Zeit = 2017-06-09 00:52 UTC
Probieren Sie es online!
Dies ergibt (9 n - 1 - 1) ⋅11 / 8 für alle n . Hier sind die ersten Ausgaben:
quelle