Basierend auf dieser Math.SE-Frage ; Nummer aus dieser Antwort kopiert . Die Nummer stammt natürlich aus einem Numberphile-Video .
Ihre Aufgabe ist es, die folgende 1350-stellige Primzahl auszugeben:
888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888111111111111111111111111888888111111111111111111111111888888111111811111111118111111888888111118811111111118811111888888111188811111111118881111888888111188811111111118881111888888111888811111111118888111888888111888881111111188888111888888111888888111111888888111888888111888888888888888888111888888111888888888888888888111888888111888888888888888888111888888811188888888888888881118888188811188888888888888881118881188881118888888888888811188881118888111888888888888111888811111888811118888888811118888111111188881111111111111188881111111118888111111111111888811111111111888811111111118888111111111111188881111111188881111111111111118888811118888811111111111111111888881188888111111111111111111118888888811111111111111111111111888888111111111111111111111111118811111111111111111111111111111111111111111111062100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
Optional können Sie Zeilenumbrüche in die Ausgabe einbeziehen.
Regeln
- Das ist kolmogorov-Komplexität , also keine Eingabe.
- Ihr Programm muss innerhalb einer Stunde auf einem Standardcomputer beendet sein - wenn es in der Nähe ist, verwende ich meins zum Testen. Wenn Ihr Programm länger als eine Minute ausgeführt wird oder unter TIO nicht beendet wird, geben Sie bitte die Uhrzeit auf Ihrem Computer an.
- Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes.
code-golf
kolmogorov-complexity
primes
Stephen
quelle
quelle
Antworten:
Jelly ,
7471696866 BytesProbieren Sie es online!
Wie es funktioniert
Das Literal
“©ạ-3ṗÇñ"ỤḍV8żṢ?ḤsMVE[,Ṃƭ"ḞÇsẇʂ(ụFsẠʂẆŀṣ’
ersetzt alle Zeichen durch ihre Codepunkte in Jellys Codepage und interpretiert das Ergebnis als eine (bijektive) Basis-250-Zahl, die die folgende Ganzzahl ergibt.Dann
ḃ19
wandelt diese Nummer bijektive Basis 19, die folgenden Ziffernarray ergibt.Nun
ĖŒṙ
listet die Stellen und führt eine Lauflängen - Decodierung, die folgende Anordnung ergibt.Dann wird
ị⁾81
die Zeichenfolge 81 indiziert , wobei ungerade Zahlen durch das Zeichen 8 und gerade durch das Zeichen 1 ersetzt werden . Anschließend wirds30
das Ergebnis in Blöcke der Länge 30 aufgeteilt. Wenn Sie einen Block pro Zeile anzeigen, sieht das Ergebnis wie folgt aus.Nun,
m0
verkettet die Anordnung der Stücke mit einer umgekehrten Kopie von sich selbst. Anschließend können SieZ
das Ergebnis komprimieren und Zeilen und Spalten transponieren.0
ist ein nicht analysierbarer Nullwert, daher wird das Ergebnis von vorher gedruckt (ohne Zeilenumbrüche) und der Rückgabewert auf 0 gesetzt .62
ist ein weiterer nicht analysierbarer Nullwert, daher wird das Ergebnis von vor ( 0 ) gedruckt und der Rückgabewert auf 62 gesetzt .ȷ446
ist noch ein nicht zu analysierender Nilad. 62 wird gedruckt und der Rückgabewert auf 10 446 gesetzt .Schließlich
‘
erhöht das Ergebnis. Das Endergebnis ( 10 446 + 1 ) wird gedruckt, wenn das Programm beendet ist.quelle
[8, 1]
... Oh, das ist schlau! Ich klaue diesen Trick, ich hoffe es macht dir nichts aus :))) und dann füge ja all das komische 06210..01 Zeug hinzu. nice :)SOGL V0.12 ,
81787573 BytesProbieren Sie es hier aus!
Erläuterung:
quelle
Jelly , 136 Bytes
Probieren Sie es online!
Erklärung (Zahlen gekürzt)
-121 Bytes dank Dennis mit
“...’
Literalen anstelle von normalen Zahlenquelle
“...’
Literale sparen eine Menge Bytes. tio.run/…0;6;2;1;
scheint schrecklich wortreich.Jelly ,
133 8473 BytesProbieren Sie es online! (Fußzeile formatiert die Dezimalzahl mit den Abmessungen, die das Wappen ergeben).
Wie?
Eine lauflängenkodierte Form eines Binärformats auf der linken Seite des Wappens
8
und1
bis zur Zeile vor der ersten,0621
die mit dem0621
Addierten wiedergegeben und dann mit 10 446 multipliziert und inkrementiert wird.quelle
Charcoal ,
10710498968779 BytesProbieren Sie es online! Link zum ausführlichen Code zur Erklärung
quelle
Proton , 368 Bytes
Probieren Sie es online!
quelle
Ruby , 180 Bytes
Probieren Sie es online!
178 Bytes + 2 Bytes für
-Kn
(Erzwingt ASCII-Codierung.)43 meist nicht druckbare Zeichen zwischen den ersten Anführungszeichen. Hexdump:
Wie?
Alle anderen haben eine Lauflängencodierung durchgeführt, deshalb wollte ich etwas anderes ausprobieren.
Die formatierte "Bild" -Version der Primzahl kann in zwei Teile unterteilt werden: ein 30x30-Raster mit 8 und 1 sowie einen zweiten Abschnitt mit meistens Nullen, die fest codiert werden können. Wenn wir uns auf den ersten Teil konzentrieren, stellen wir fest, dass er in der Mitte symmetrisch ist. Wenn wir also die linke Hälfte produzieren können, können wir einfach die Hälfte jeder Zeile mit der Rückseite drucken.
Die Hälfte einer Zeile besteht aus 15 Zeichen. Wenn wir die 8 durch Nullen ersetzen, kann jede Zeile als 15-Bit-Binärzahl interpretiert werden. Praktischerweise ist der Bearbeitungsabstand zwischen den aufeinanderfolgenden Zeilen zum größten Teil gering. Daher habe ich beschlossen, meine Lösung zu implementieren, indem ich die erste Zeile
s
(888888888888888
die gerade 0 wird) speicherte und eine Reihe von Bitumkehroperationen anwandtes
, um das Ergebnis jedes Mal auszudrucken .Da jede Zeile 15 Bit lang ist, habe ich diese Operationen als hexadezimale Ziffern codiert. Wenn die Operation beispielsweise
b
(oder 11) ist, wird Bit 11 umgedreht. Einige Zeilen unterscheiden sich um mehr als ein Bit, sodass eine hexadezimale Zeichenfolge erforderlich ist Ziffern. Wir haben noch ein Bit übrig (f
), damit wir es als Trennzeichen zwischen diesen Zeichenfolgen und als Wert für "do nothing" verwenden können. Beispiel unten (Sie können diese Zeilen in dem Beitrag sehen, auf den in der Frage verwiesen wird):Zu setzen , dass alle zusammen, würden kodieren wir
0123456789ab
, dann mit trennenf
, nichts tun mitf
, dann5
. Dies funktioniert, weil wir.split(?f)
später jede Gruppe von Operationen zeilenweise abrufen werden, was sich nachteilig auswirkt["0123456789ab", "", "5"]
und""
ein No-Op ist.Der Unterschied zwischen den obigen Zeilen 3 und 4 ist bei weitem der längste Satz von Bearbeitungen, und der Bearbeitungsabstand zwischen zwei aufeinanderfolgenden Zeilen beträgt normalerweise 0-2. Daher würde ich sagen, dass diese Codierung relativ kostengünstig ist, obwohl ich mir sicher bin, dass dies möglich ist verbessert werden.
Die gesamte codierte Zeichenfolge hat eine
fff0123456789abff5f6f7ff8f4f3f012fff8bfef7af69df458cf01237bf6af59f48f237f16f045f3f12f0
Größe von 86 Byte, wodurch das gesamte Raster von 30 x 30 erhalten wird. Aber wir sind noch nicht fertig ...Hexadezimale Ziffern können durch 4 Bits (
b
->1100
usw.) dargestellt werden. Dies bedeutet, dass wir die Länge der Zeichenfolge halbieren können , wenn wir bereit sind, die Zeichenfolge 4 Bits gleichzeitig zu codieren, anstatt Bytes zu verwenden. So habe ich es gemacht - der Hexdump zeigt den String in 43 Bytes. Danach müssen Sie nur noch Rubys raffinierten String # unpack withH*
(interpretieren als Hex-String, High Nibble First) verwenden, um den 43-Byte-String auf die 86-Byte-Version zu erweitern, die wir kennen und lieben, und alle Operationen in einer Schleife durchlaufen Bits spiegeln - für unsere gespeicherten Strings
und einer Operationc
tun wirs ^ 2**c.to_i(16)
das entsprechende Bit kippen.Nachdem jeder Satz von Bearbeitungen abgeschlossen ist, füllen wir die resultierende Binärdatei mit 15 Bits auf, schalten alle Nullen auf 8 zurück und drucken das Ergebnis und seine Umkehrung. Wie bereits erwähnt, kann der Teil der Zahl nach dem 30x30-Raster fest codiert werden
puts'0621'+?0*445+?1
.Die endgültig codierte Zeichenfolge kann nicht mit TIO bearbeitet werden. In der TIO-Version werden Escapes verwendet, die zwar noch funktionieren, aber länger sind.
quelle
Python 2 ,
760523329205196 Bytes-237 Bytes dank Stephen. -124 Bytes dank Jonathan Frech.
Probieren Sie es online!
quelle
8
und1
und Kombinieren621
621
. Vielen Dank!CJam,
532412340231210209 BytesProbieren Sie es online
Die Lauflängencodierung wurde von Basis 92 erweitert (Basis 250 führte zu Multibyte-Zeichen, musste also angepasst werden). Wird auch
4341089843357287864910309744850519376
von der Basis 92 aus erweitert und in Binärdaten umgewandelt. Eine 1 bedeutet, dass die Lauflänge zweistellig ist, eine 0 bedeutet, dass es sich um eine Ziffer handelt. Zum Beispiel sind die ersten 4 Stellen der Binärdarstellung 1101, weil die ersten vier Läufe[93,8],[24,1],[6,8],[24,1]
(93 8er, 24er, etc ...) sind.quelle
JavaScript,
454450332207204 Bytes-4 Bytes danke an Stephen. -125 Bytes dank Shaggy und Dom Hastings.
Diese Antwort enthält eine Schiffsladung nicht druckbarer Dateien. Hier ist also ein Hexdump:
quelle
+'1'
da es bereits ein istString
und sein+'0621'
kann+0+621
![...`]
macht mich so wütendJavaScript (ES6),
206205204203198197194 BytesAls ich bei der Arbeit an der Lösung von i cri everytim dabei war , stellte ich fest , dass sie unterschiedlich genug war, um das eigene Posten zu rechtfertigen.
Dies beinhaltet eine Menge nicht druckbarer Dateien zwischen dem
]
und dem. Folgen Sie,
also dem TIO-Link unten, um sie mit Unicode- Escape- Zeichen anzuzeigen (jede Folge von\u
gefolgt von 4 Ziffern zählt als 1 Byte).Probieren Sie es online aus
quelle
MATLAB / Octave ,
319318 BytesDies ist mein erster Versuch bei dieser Herausforderung. Immer noch ein bisschen groß und es gibt wahrscheinlich effizientere Möglichkeiten, dies zu tun, aber ich dachte, ich würde es trotzdem posten, da die Methode interessanter war, als es nur zu komprimieren.
Probieren Sie es online!
Die hier verwendete Methode besteht darin, ein Run-Length-Encoding-Schema zu verwenden.
Wir beginnen mit der ursprünglichen Nummer und zählen die Anzahl der aufeinander folgenden Ziffern. Diese werden im Ergebnis unten als Zählung direkt gefolgt von der Ziffer (aus Gründen der Übersichtlichkeit durch Leerzeichen getrennt) angegeben.
Wenn einer der Werte größer als 95 ist, teilen wir ihn in mehrere Abschnitte von 95 oder weniger auf - dies geschieht nur für die 445 0, die stattdessen vier Sätze von 95 0 und einen Satz von 65 0 ergeben. Wir füllen auch alle Zählungen, die kleiner als 10 sind, mit einer 0 auf, damit alle Elemente drei Zeichen lang sind. Dies ergibt mit den entfernten Leerzeichen:
Im Nachhinein hätte ich diesen Schritt tun können, bevor ich alles zusammengeführt habe, aber du lebst und lernst. Wir machen etwas Kluges, indem wir die Anzahl für jede Gruppe (2 Ziffern) berechnen und 31 addieren. Da alle <96 sind, ist die resultierende Zahl der ASCII-Wert für ein druckbares Zeichen (32 bis 126). Geben Sie uns zählt von:
Nach einigem Umformen in MATLAB, um es für die Dekodierung günstiger zu machen, und dann auch mit Escape-
'
Zeichen''
(ansonsten teilt MATLAB String-Literale dort auf), bleibt uns der clevere String:Das ist die Wurzel des Codes. Im Code ist alles, was ich dann tue, das Array in eine 2D-Zeichenfolge mit 128 Zeichenpaaren umzuformen. Für jedes Paar hat das erste Zeichen 31 subtrahiert, und dann wird das zweite Zeichen so oft angezeigt.
Das Ergebnis ist die ursprüngliche Primzahl:
Bearbeitungen:
quelle
05AB1E , 76 Bytes
Probieren Sie es online!
Habe das von Dennis gestohlen:
Bemerkt, dass es immer zwischen 8 und 1 wechselt, also habe ich die Länge jedes Laufs gezählt (Basis 20):
Fügte alles zusammen und wandelte es in eine Ganzzahl zur Basis 10 um:
Komprimiert es weiter in base-255:
Nachdem Sie das komprimierte Bit erstellt haben, müssen Sie es nur wieder auf das Original zurücksetzen.
Endgültige Ausgabe:
quelle
C (gcc) , 277 Bytes
Ich habe das Gefühl, dass die Saite irgendwie gekürzt werden könnte.
Probieren Sie es online!
quelle
Perl 5 , 307 Bytes
Probieren Sie es online!
quelle
Bubblegum , 88 Bytes
Probieren Sie es online!
quelle
Ruby , 194 Bytes
Der obere Teil ist RLE-codiert, der Rest ist einfach fest codiert.
Probieren Sie es online!
quelle
Kotlin , 339 Bytes
Probieren Sie es online!
quelle
CJam (
10881 Bytes)Online-Demo
Für den Fall, dass die obige Zeichencodierung fehlschlägt, ist sie hier xxd-codiert:
Der anfängliche Lauf von 8s und 1s ist in nur die linke Hälfte aufgeteilt und die Lauflänge ist nur als die Länge der alternierenden Läufe codiert. Läufe von mehr als 24 werden in Läufe von höchstens 24 aufgeteilt, die durch Läufe von 0 getrennt sind, so dass die Längen mit Basis 25 codiert und dann mit Basis 256 codiert werden können, um sie zu komprimieren.
quelle
JavaScript (ES2017), 287 Byte
Verwendet einen etwas anderen Ansatz für die Antwort von @icrieverytim . -10 Bytes dank @Shaggys Vorschlag,
replace
anstelle vonmatch
!quelle
/// 260 Bytes
Probieren Sie es online!
Nichts schrecklich Interessantes, nur etwas Komprimierung.
quelle
Mathematica, 192 Bytes
Siehe: http://reference.wolfram.com/language/ref/Compress.html
quelle
Python 2 ,
191190188 BytesProbieren Sie es online!
Gleiches Prinzip wie meine Antwort hier
quelle