Betrachten Sie eine binäre Zeichenfolge S
von Länge n
. Indizieren 1
wir von , können wir die Hamming-Entfernungen zwischen S[1..i+1]
und S[n-i..n]
für alle i
in der Reihenfolge von 0
bis berechnen n-1
. Der Hamming-Abstand zwischen zwei Saiten gleicher Länge ist die Anzahl der Positionen, an denen sich die entsprechenden Symbole unterscheiden. Beispielsweise,
S = 01010
gibt
[0, 2, 0, 4, 0].
Dies liegt daran, dass 0
Übereinstimmungen 0
, 01
Hamming-Distanz zwei zu 10
, 010
Übereinstimmungen 010
, 0101
Hamming-Distanz vier zu 1010
und schließlich sich 01010
selbst entsprechen.
Wir interessieren uns jedoch nur für Ausgaben, bei denen der Hamming-Abstand höchstens 1 beträgt. In dieser Aufgabe werden wir also eine Y
angeben, wenn die Hamming-Distanz höchstens eins beträgt, und eine N
andere. Also in unserem obigen Beispiel würden wir bekommen
[Y, N, Y, N, Y]
Definieren Sie f(n)
die Anzahl der verschiedenen Arrays von Y
s und N
s, die Sie erhalten, wenn Sie alle 2^n
verschiedenen möglichen Bitfolgen S
der Länge durchlaufen n
.
Aufgabe
Zum Erhöhen n
ab 1
sollte Ihr Code ausgegeben werden f(n)
.
Beispielantworten
Denn n = 1..24
die richtigen Antworten sind:
1, 1, 2, 4, 6, 8, 14, 18, 27, 36, 52, 65, 93, 113, 150, 188, 241, 279, 377, 427, 540, 632, 768, 870
Wertung
Ihr Code sollte iterieren, nachdem Sie n = 1
die Antwort für jede einzelne n
nacheinander gegeben haben. Ich werde den gesamten Lauf zeitlich festlegen und ihn nach zwei Minuten töten.
Ihre Punktzahl ist die höchste, die n
Sie in dieser Zeit erreichen.
Bei einem Gleichstand gewinnt die erste Antwort.
Wo wird mein Code getestet?
Ich werde Ihren Code auf meinem (etwas alten) Windows 7-Laptop unter Cygwin ausführen. Bitte geben Sie daher jede mögliche Unterstützung, um dies zu vereinfachen.
Mein Laptop hat 8 GB RAM und eine Intel i7 5600U @ 2,6 GHz (Broadwell) -CPU mit 2 Kernen und 4 Threads. Der Befehlssatz umfasst SSE4.2, AVX, AVX2, FMA3 und TSX.
Führende Einträge pro Sprache
- n = 40 in Rust mit CryptoMiniSat von Anders Kaseorg. (In Lubuntu Gast-VM unter Vbox.)
- n = 35 in C ++ unter Verwendung der BuDDy-Bibliothek von Christian Seviers. (In Lubuntu Gast-VM unter Vbox.)
- n = 34 in Clingo von Anders Kaseorg. (In Lubuntu Gast-VM unter Vbox.)
- n = 31 in Rust von Anders Kaseorg.
- n = 29 in Clojure von NikoNyrh.
- n = 29 in C von Bartavelle.
- n = 27 in Haskell von Bartavelle
- n = 24 in Pari / gp von Alephalpha.
- n = 22 in Python 2 + pypy von mir.
- n = 21 in Mathematica von Alephalpha. (Selbst berichtet)
Zukünftige Kopfgelder
Ich werde jetzt eine Prämie von 200 Punkten für jede Antwort geben, die in zwei Minuten auf meinem Computer auf n = 80 steigt .
Antworten:
Rust + CryptoMiniSat , Nr. 41
src/main.rs
Cargo.toml
Wie es funktioniert
Dies führt eine rekursive Suche durch den Baum aller Teilzuweisungen zu Präfixen des Y / N-Arrays durch, wobei bei jedem Schritt mit einem SAT-Solver geprüft wird, ob die aktuelle Teilzuweisung konsistent ist, und wenn nicht, wird die Suche beschnitten. CryptoMiniSat ist aufgrund seiner speziellen Optimierungen für XOR-Klauseln der richtige SAT-Löser für diesen Job.
Die drei Familien von Einschränkungen sind
S i ⊕ S k + i ⊕ D ki , für 1 ≤ k ≤ n - 2, 0 ≤ i ≤ n - k ;
D ki 1 ∨ D ki 2 ∨ ¬ A k , für 1 ≤ k ≤ n - 2, 0 ≤ i 1 < i 2 ≤ n - k ;
¬ D ki 1 ∨ ∨ ¬ D ki n - k - 1∨ A k für 1 ≤ k ≤ n - 2, 0 ≤ i 1 <⋯ < i n - k - 1 ≤ n - k ;
mit der Ausnahme, dass S 0 als eine Optimierung zu falsch gezwungen wird, so dass D k 0 einfach gleich S k ist .
quelle
cargo build
bekomme ich--- stderr CMake Error: Could not create named generator Visual Studio 14 2015 Win64
Rust, n ≈
30 oder31 oder 32Auf meinem Laptop (zwei Kerne, i5-6200U) reicht dies für n = 1, ..., 31 in 53 Sekunden und etwa 2,5 GB Speicher oder für n = 1, ..., 32 in 105 Sekunden und etwa 5 GB der Erinnerung. Kompilieren Sie mit
cargo build --release
und führen Sie es austarget/release/correlations
.src/main.rs
Cargo.toml
Probieren Sie es online!
Ich habe auch eine etwas langsamere Variante mit sehr viel weniger Speicher.
quelle
C ++ mit der BuDDy-Bibliothek
Ein anderer Ansatz: Verwenden Sie eine Binärformel (als binäres Entscheidungsdiagramm ), die die Bits von
S
als Eingabe verwendet und true ist, wenn dies einige feste Werte vonY
oderN
an bestimmten ausgewählten Positionen ergibt . Wenn diese Formel nicht konstant falsch ist, wählen Sie eine freie Position aus und versuchen Sie es mit beidenY
undN
. Wenn keine freie Position vorhanden ist, haben wir einen möglichen Ausgabewert gefunden. Wenn die Formel konstant falsch ist, wird zurückverfolgt.Dies funktioniert relativ vernünftig, da es so wenige mögliche Werte gibt, dass wir oft früh zurückgehen können. Ich habe eine ähnliche Idee mit einem SAT-Solver versucht, aber das war weniger erfolgreich.
Um mit Debian 8 (Jessie) zu kompilieren, installieren Sie
libbdd-dev
und tun Sieg++ -std=c++11 -O3 -o hb hb.cpp -lbdd
. Es kann nützlich sein, das erste Argument aufbdd_init
noch mehr zu erhöhen .quelle
Clingo, Nr.
30 oder 3134Ich war ein wenig überrascht, als ich sah, dass fünf Zeilen Clingo-Code meine Brute-Force-Rust-Lösung überholten und Christians BuDDy-Lösung sehr nahe kamen - es sieht so aus, als würde dies auch mit einem höheren Zeitlimit übertroffen.
corr.lp
corr.sh
quelle
bdd_init
könnte helfen oder die Knotentabelle durch Aufrufenbdd_setmaxincrease
mit einem Wert deutlich über dem Standardwert von 50000 erhöhen. - Verwenden Sie die geänderte Version meines Programms?--configuration=crafty
(jumpy
und erzielentrendy
ähnliche Ergebnisse).Pari / GP , 23
Standardmäßig begrenzt Pari / GP die Stapelgröße auf 8 MB. In der ersten Codezeile wird
default(parisize, "4g")
dieses Limit auf 4 GB festgelegt. Wenn es immer noch einen Stapelüberlauf gibt, können Sie ihn auf 8 GB einstellen.quelle
Clojure, 29 in
7538 Sekunden, 30 in 80 und 31 in 165Die Laufzeit von Intel i7 6700K beträgt weniger als 200 MB.
project.clj (verwendet com.climate / claypoole für Multithreading):
Quellcode:
Als Brute-Force-Lösung durchläuft jeder Thread eine Teilmenge des Bereichs (2 ^ 12 Elemente) und erstellt eine Reihe von ganzzahligen Werten, die auf erkannte Muster hinweisen. Diese werden dann zusammen "unionisiert" und somit die eindeutige Zählung berechnet. Ich hoffe, der Code ist nicht zu knifflig, obwohl er Threading-Makros verwendet . Ich
main
führe den Test einige Male aus, um JVM zum Aufwärmen zu bringen.Update: Wenn Sie nur die Hälfte der ganzen Zahlen durchlaufen, wird aufgrund der Symmetrie dasselbe Ergebnis erzielt. Überspringen Sie auch Zahlen mit einer höheren Bitanzahl in der unteren Hälfte der Zahl, da sie ebenfalls Duplikate erzeugen.
Vorgefertigtes Uberjar ( v1 ) (3,7 MB):
Ergebnisse auf verschiedenen Hardwares, erwartete Laufzeit ist
O(n * 2^n)
?Sie können diesen Single-Thread einfach erstellen und diese Abhängigkeit von Drittanbietern vermeiden, indem Sie den Standard für Folgendes verwenden:
Nun, die eingebaute pmap existiert auch, aber Claypoole hat mehr Funktionen und Abstimmbarkeit.
quelle
Mathematica, n = 19
drücke alt +. abbrechen und das Ergebnis wird gedruckt
quelle
Mathematica, 21
Zum Vergleich Jenny_mathy Antwort gibt
n = 19
auf meinem Computer.Der langsamste Teil ist
Tr@IntegerDigits[#, 2] &
. Es ist eine Schande, dass Mathematica kein eingebautes Hamming-Gewicht hat.Wenn Sie meinen Code testen möchten, können Sie eine kostenlose Testversion von Mathematica herunterladen .
quelle
AC-Version mit eingebautem Popcount
Funktioniert besser mit
clang -O3
, funktioniert aber auch, wenn Sie nur habengcc
.quelle
Haskell, (inoffizielles n = 20)
Dies ist nur der naive Ansatz - bisher ohne Optimierungen. Ich fragte mich, wie gut es gegen andere Sprachen abschneiden würde.
Wie man es benutzt (vorausgesetzt, Sie haben eine Hashell-Plattform) installiert):
approx_corr.hs
(oder einen anderen Namen, ändern Sie die folgenden Schritte entsprechend)ghc approx_corr.hs
approx_corr.exe
n
Code:
quelle
main = putStrLn "Hello World!"
?Data.Bits
Modul könnte nützlich sein. Für Ihre Hauptschleife könnten Sie so etwas wiemain = do maxn <- getmax; t0 <- gettime; loop 1
whereloop n|n==maxn = return ()
und verwendenloop n = do printresult n (f n); t <- gettime; printtime (t-t0); loop (n+1)
.getmax
könnte zum Beispiel verwendengetArgs
, um die Programmargumente zu verwenden.Eine Haskell-Lösung, die popCount und manuell verwaltete Parallelität verwendet
Kompilieren:
ghc -rtsopts -threaded -O2 -fllvm -Wall foo.hs
(Lass fallen
-llvm
wenn es nicht funktioniert)Lauf :
./foo +RTS -N
quelle
-O3
werden und könnte mit schneller sein-O3 -fllvm
...Python 2 + Pypy, n = 22
Hier ist eine wirklich einfache Python-Lösung als eine Art Referenz.
quelle