Angenommen , wir eine unendliche Matrix definieren M
, auf N^2 -> {0, 1}
(wobei N
beginnt ab , 1
statt 0
) in dieser Art und Weise:
M(1, 1)
=0
.Für jeden
x > 1
,M(x, 1)
=1
wennx
ist Primzahl und0
sonst.Für jeden
y > 1
,M(1, y)
= dery
th Begriff in derThue-Morse sequence
.Für jeden
x, y > 1
,M(x, y)
=M(x, y-1) + M(x-1, y) mod 2
.
Der obere linke 16x16
Abschnitt dieser Matrix sieht wie folgt aus (wobei x
es sich um Zeilen und y
Spalten handelt):
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1
1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0
0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1
0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1
1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1
0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0
1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1
0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0
0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1
0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1
0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1
Ihre Aufgabe ist es, ein Programm zu erstellen, das den Wert eines beliebigen Eintrags in dieser Matrix so genau wie möglich auswertet.
Ihr Programm nimmt zwei ganze Zahlen x
und y
gibt sie in einer beliebigen Form als Eingabe ein und gibt sie zurück M(x, y)
, entweder 0
oder 1
.
Ihr Code kann in einer beliebigen Sprache geschrieben sein, darf jedoch 64 Kilobyte (65.536 Bytes) Quellcodegröße oder 2 MB (2.097.152 Bytes) Gesamtspeicherauslastung nicht überschreiten. Ihr Programm muss mit leerem Speicher beginnen (dh es kann keine Daten von einer anderen Stelle laden) und muss für jede Eingabe unabhängig ausgeführt werden (d. H., Es darf keine gemeinsamen Daten für mehrere Durchläufe speichern). Ihr Programm muss außerdem in der Lage sein, alle Einträge im oberen linken 8192x8192
Quadrat in angemessener Zeit auszuwerten .
Das Programm, das die meisten Einträge im oberen linken 8192 x 8192
Quadrat richtig auswertet, wird der Gewinner sein, wobei ein kürzerer Code als Auslöser fungiert.
quelle
Antworten:
J -
4238 charZiemlich schnell, 100% genau und innerhalb der Speicherbeschränkungen.
Die Strategie ist wie folgt: Wir werden aufeinanderfolgende Antidiagonalen dieser Matrix berechnen, ein paarweises XOR ausführen, um sich entlang zu bewegen, und die aktuellen Thue-Morse- und Prim-Bits an den Enden addieren. Wir ziehen dann die gewünschte Ziffer aus der Antidiagonale, wenn wir dort ankommen.
Erklärung durch Explosion:
Die Verwendung dieses Verbs gilt
x m y
für M (x, y) wie in der Frage angegeben. Wom
ist das Verb?Um Tastatureingaben zu sparen, versuchen wir nicht festzustellen, ob wir noch mehr Prim- oder Thue-Morse-Bits benötigen. Wir berechnen daher die gesamte Antidiagonale, um das gewünschte Bit zu erhalten. Läuft allerdings
8192 m 8192
noch in weniger als 0,07 s und ca. 100 KiB auf meinem bescheidenen Laptop.quelle
Mathematica - 100% Genauigkeit,
223193189 BytesHier ist eine lesbare Version:
Ich berechne im Grunde entlang von Diagonalen der Konstanten vor
x+y
.Eigenschaften:
O(x*y)
.f[8192,8192]
dauert etwa 400 Sekunden. Ich nehme an, es gibt Raum für Verbesserungen (RotateLeft
könnte vielleicht die innere Schleife ersetzen).Es wird nur ein Array mit bis zu
max(x,y)
Zwischenergebnissen im Speicher verwendet. Es ist also nicht erforderlich, mehr als 32 KB (unter der Annahme von 32-Bit-Ganzzahlen) für den Algorithmus selbst zu verwenden (und unabhängig davon, was Mathematica verwendet). Tatsächlich verwendet Mathematica 31M für sich auf meinem System, dies funktioniert jedoch problemlos:quelle
O(x*y)
times, aber die Gesamtausführungszeit erhöht sich schneller. Ich bin mir nicht ganz sicher, was passiert. Wenn mich ein Mathematica-Guru aufklären könnte, welche Operation in der Schleife nichtO(1)
hilfreich ist , wäre das sehr hilfreich! :) (nun,PrimeQ
undTotal@IntegerDigits
nicht, aber ich habe sie von AnfangO(y)
O(x)
Matlab: 100% Genauigkeit, 120 Zeichen, unzumutbare Ausführungszeit
Benutzen:
quelle
M(8192, 8192)
ich es nicht ertragen.Python, 192 Zeichen
100% Genauigkeit, berechnet M (8192,8192) in ~ 10 Sekunden auf meiner Maschine.
quelle
Haskell - 261 Bytes - 100% - 1 MB - Ich glaube nicht, dass es bald enden wird
Dauert ungefähr 10 Sekunden für
m 16 16
mit-O2
, aber wie ich es trotzdem geschrieben habe, kann ich es trotz dieses Problems zeigen:Vielleicht kann ein guter Haskeller es optimieren?
quelle
f p|p=not|0<1=id
besser sein. Versuchen Sie auch,morse = False : concat $ iterate [True] (\a -> a ++ map not a)
für erhöhte Faulheit zu verwenden. Ich frage mich, wie sich das auf die Leistung auswirkt.True
nach0<1
undFalse
nach Golf spielen0>1
.Perl, 137
Nicht um zu 'gewinnen' :-), aber da es hier noch kein Perl gibt und Code trotzdem geschrieben wurde, ist es hier.
Dauert beim Aufruf einige Sekunden
print f(8192,8192)
und speichert eine einzelne Zeile der Matrix im Speicher (Array mit 8192 Ganzzahlen (Skalaren)). Der gesamte Perl-Prozess ist ungefähr 3,5 MB groß. Ich habe versucht, es mit String anstelle von Array zu machen (entweder mit Regexps oder Zugriff mit Substr), nimmt weniger Speicher in Anspruch und kann weiter golfen werden, läuft aber viel langsamer.Eingerückt:
quelle
Haskell, 223
Dies hat eine schnelle Laufzeit (5,7 Sekunden mit
-O3
). Speicher wurde noch nicht überprüft, sollte aber linear sein.Dies verwendet den hier zuvor gezeigten Diagonalalgorithmus.
Was die Geschwindigkeit betrifft, sind nur der Diagonal-Algorithmus
-O3
und der|foldr seq(0>1)s=0<1
Guard von Bedeutung, der die Liste streng macht. alles andere ist eher ineffizient implementiert - die Prüfung der Primzahlen erfolgt durch Prüfung aller kleineren Zahlen auf Division, die Elemente der Morsefolge werden ständig neu berechnet. aber es ist trotzdem schnell genug :-).quelle