Bracket Zahlen bieten eine einfache Möglichkeit , große natürliche Zahlen auszudrücken nur linke Klammer, Raum verwenden und rechte Klammer ( [ ]).
Eine Klammer-Nummer ist definiert als eine Folge von einem oder mehreren Paaren übereinstimmender Klammern, die [...]als Chunks bezeichnet werden und durch null oder mehr Leerzeichen von ihren Nachbarn getrennt sind.
Die Anzahl der Leerzeichen zwischen jedem Block definiert die Hyperoperation zwischen ihnen. Keine Leerzeichen bedeuten Addition, 1 Leerzeichen bedeutet Multiplikation, 2 Leerzeichen bedeuten Exponentiation, 3 Leerzeichen bedeuten Tetration und so weiter. Hyperoperationen höherer Ordnung haben Vorrang, daher erfolgt die Tetration vor der Exponentiation, die Exponentiation vor der Multiplikation usw. Sie sind auch rechtsassoziativ und werden wie a^b^cfolgt berechnet a^(b^c). (Ist a^b*caber immer noch (a^b)*c.)
Jeder Block kann entweder leer sein ( []) oder eine andere Klammernummer enthalten. Leere Blöcke haben den Wert 0. Nicht leere Blöcke haben den Wert ihrer enthaltenen Klammernummer plus 1.
Beispiele: ( ^^ist Tetration, ^^^ist Pentation )
[[]]hat den Wert 1, da 0 ([]) um 1 erhöht wird[[[]]]hat den Wert 2, tut dies aber auch,[[]][[]]da die beiden ([[]]) hinzugefügt werden[[[]]] [[[[]]] [[[[]]]]][[[]]]hat den Wert 20 = (2 * ((2 ^ 3) +1)) + 2[[[]]] [[[[]]]]hat den Wert 65536 = 2 ^^^ 3 = 2 ^^ (2 ^^ 2) = 2 ^^ 4 == 2 ^^ (2 ^^ (2 ^^ 2))[[[[]]]] [[[]]] [[]]hat den Wert 7625597484987 = 3 ^^^ (2 ^^^ 1) = 3 ^^^ 2 = 3 ^^ 3 = 3 ^ (3 ^^ 3)
In gültigen Klammernummern:
- Es wird niemals führende oder nachfolgende Leerzeichen geben.
- Es wird immer mindestens ein Paar passender Klammern geben.
- Alle linken Klammern haben eine passende rechte Klammer.
- Ein Leerzeichen wird niemals direkt rechts
[oder links von angezeigt]. - Der Wert ist immer eine nicht negative ganze Zahl.
Herausforderung
Beachten Sie, dass es für eine Klammernummer viele Formulare geben kann, die denselben Wert angeben. [[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]und [[[]]] [[[[]]]]beide stellen 16 dar, aber das letztere ist viel kürzer.
Ihre Herausforderung besteht darin, einen Algorithmus zu schreiben, der versucht, die kürzeste Klammer für einen bestimmten Wert zu finden. Ich glaube zum Beispiel, dass der kürzeste Weg, 16 darzustellen, bei 17 Zeichen als ist [[[]]] [[[[]]]].
Wertung (aktualisiert)
Sei S die Menge von ganzen Zahlen von 1 bis 256 (einschließlich) sowie die folgenden zehn Werte:
8191 13071 524287 2147483647 1449565302 1746268229 126528612 778085967 1553783038 997599288
(Die ersten 4 sind Mersenne-Primzahlen, der Rest ist zufällig.)
Die Einreichung, die für alles in S den kürzesten Satz von Klammernummern generiert, gewinnt. Ihre Punktzahl ist die Summe der Längen Ihrer Klammerzahlen für alle Werte in S (kleiner ist besser).
Bitte reichen Sie mit Ihrem Code eine Liste Ihrer Klammernummern für alle S ein , die genaue Reihenfolge ist nicht sonderlich wichtig. z.B:
1=[[]]
2=[[[]]]
3=[[[[]]]]
...
2147483647=[...]
...
(Ich weiß, dass dies nicht die optimale Bewertungsmethode ist, aber ich bin nicht dafür eingerichtet, eine Reihe von zufälligen heuristischen Tests für jede Einreichung durchzuführen. Entschuldigung :()
Regeln
- Sie können nicht alle Halter Nummern neben den trivialen inkrementalen Lösungen codieren (
[], [[]], [[[]]], ...). Ihr Programm muss eigentlich nach möglichst kurzen Darstellungen suchen. (Obwohl die Ergebnisse möglicherweise nicht optimal sind.) - Ihr Algorithmus sollte für alle nicht negativen ganzen Zahlen unter 2.147.483.648 (2 ^ 31) funktionieren. Sie können sich nicht speziell auf die Werte in S konzentrieren .
- Für eine bestimmte Eingabe sollte Ihr Algorithmus auf einem anständigen modernen Computer (~ 2,5 GHz Prozessor, ~ 6 GB RAM) in höchstens 10 Minuten ausgeführt werden.
- Bei der (scheinbar) seltenen Chance auf ein Unentschieden gewinnt die am höchsten gewählte Einreichung.
- Wenn Sie eine andere Lösung kopieren oder ohne Namensnennung überarbeiten, werden Sie disqualifiziert.
quelle
Antworten:
Python 11455b
Bei dieser Lösung wird eher gierig nach Wegen gesucht, Primzahlen aufzuschlüsseln, als nach einem erschöpfenden Ansatz. Ich brauche 9875b für 1-256 im Vergleich zu 8181 für Martins wahrscheinlich optimale Lösung in diesem Raum.
Eine größere Tabelle mit Multiplikations- und Exponentationsergebnissen führt zu leichten Verbesserungen in den größeren Testfällen. Die Lösung unten dauerte ungefähr 7 Minuten. Das Erhöhen der Laufzeit über 30 Minuten hinaus hat nur minimale Auswirkungen auf die Ausgabe.
Ich hatte wie Martin ein Problem mit der Vorrangstellung. Meine Lösung zur Einschränkung der Betriebsauswahl ist möglicherweise nicht optimal.
Ausgabe:
quelle
Mathematica
Hinweis: Dieser Algorithmus wird niemals in der Lage sein, die größeren Testzahlen zu erreichen. Ich würde einen wesentlich anderen Ansatz brauchen, also lasse ich es einfach so, wie es für andere ist, um ihre niedrigeren Zahlen zu überprüfen. Sie können diese Einsendung für ungültig halten.
Hier ist ein Anfang für die ersten 256 Nummern (die anderen wurden hinzugefügt, nachdem ich angefangen habe, und ich muss wahrscheinlich eine separate Lösung für diese finden)
Die Gesamtlänge der ersten 256 Ziffern beträgt 7963 Zeichen. Ich weiß nicht, ob das optimal ist.
Ohne Berücksichtigung der Addition wurden die Ergebnisse für 8191 und 13071 in wenigen Sekunden und 524387 in wenigen Minuten ermittelt
bei 164 Zeichen zusammen.
Hier ist der Code:
Ich habe eine erschöpfende Suche bis zur Potenzierung durchgeführt. Es gibt keine Tetration oder Operationen höherer Ordnung. Ich habe die Operationen höherer Ordnung nur manuell ausprobiert und es gibt nur eine Handvoll Kombinationen, die tatsächlich Zahlen unter 2 31 ergeben .
Edit: Meine vorherige Lösung hat sich nicht um den Vorrang gekümmert, sie hat nur die Dinge zusammengeschmissen.
Jetzt denke ich , mein neuer Code behebt das,aber keine der ersten 256 Nummern hat sich geändert, noch 8191 (was vorher gültig war, habe ich überprüft) ... und es ist zu spät für mich, jetzt zu sagen, ob mein Code es tatsächlich behoben hat . Ich werde morgen noch einen Blick darauf werfen und eine Erklärung hinzufügen, denn jetzt, mit der Präzedenzprüfung, ist es etwas kompliziert (hoffentlich sollte es aber die Suchzeit verkürzen).Edit: Okay, es gab einige Bugs wie erwartet. Ich glaube, ich habe es jetzt behoben und die Gesamtlänge von 1 - 256 auf 7963 erhöht . Ich bin mir nicht sicher, ob dies länger optimal ist, da es möglich sein könnte, kürzere Lösungen aus suboptimalen Teilen zu finden, wenn sie Operationen höherer Ordnung ermöglichen. Eine Erklärung folgt, wenn es mir gelingt, den Code ein wenig aufzuräumen.
quelle
Python 9219b
Dies ist mein zweiter Eintrag. Ich habe bei Null angefangen und versucht, die Daten neu anzuordnen, einschließlich der Verwendung des Blist-Pakets für sortierte Listen und Wörter sowie einiger neuer Ansätze für die Suche nach großen Lösungen. Ich denke ich habe ein Optimum von 1-256. Durch die Erhöhung der Laufzeit von 30 auf 4 m konnten die großen Testfälle um ca. 30 Byte verkürzt werden.
Ausgabe:
7944b für 1-256
1275b für die großen Fälle
quelle