Der Hamming-Abstand zwischen zwei gleich langen Saiten ist die Anzahl der Positionen, an denen sich die entsprechenden Symbole unterscheiden.
Sei P
eine binäre Zeichenfolge der Länge n
und T
eine binäre Zeichenfolge der Länge 2n-1
. Wir können die n
Hamming-Abstände zwischen P
und jedem n
Teilstring T
in der Reihenfolge von links nach rechts berechnen und sie in ein Array (oder eine Liste) einfügen .
Beispiel Hamming-Distanzsequenz
Lass P = 101
und T = 01100
. Die Reihenfolge der Hamming-Entfernungen, die Sie von diesem Paar erhalten, ist 2,2,1
.
Aufgabe
Berücksichtigen Sie zum Erhöhen n
ab n=1
alle möglichen Paare von binären Zeichenfolgen P
mit Länge n
und T
Länge 2n-1
. Es gibt 2**(n+2n-1)
solche Paare und damit viele Sequenzen von Hamming-Entfernungen. Viele dieser Sequenzen sind jedoch identisch. Die Aufgabe besteht darin, herauszufinden, wie viele für jeden unterschiedlich sind n
.
Ihr Code sollte eine Zahl pro Wert von ausgeben n
.
Ergebnis
Ihre Punktzahl ist die höchste, die n
Ihr Code in 5 Minuten auf meinem Computer erreicht. Das Timing ist für die Gesamtlaufzeit, nicht nur dafür n
.
Wer gewinnt
Die Person mit der höchsten Punktzahl gewinnt. Wenn zwei oder mehr Personen die gleiche Punktzahl erzielen, gewinnt die erste Antwort.
Beispielantworten
Denn n
von 1
bis zu 8
den optimalen Antworten sind 2, 9, 48, 297, 2040, 15425, 125232, 1070553
.
Sprachen und Bibliotheken
Sie können jede verfügbare Sprache und Bibliothek verwenden, die Sie mögen. Wenn möglich, ist es gut, wenn Sie Ihren Code ausführen können. Geben Sie daher bitte eine vollständige Erklärung an, wie Sie Ihren Code unter Linux ausführen / kompilieren können, wenn dies überhaupt möglich ist.
Mein Computer Die Timings werden auf meinem 64-Bit-Computer ausgeführt. Dies ist eine Standard-Ubuntu-Installation mit 8 GB RAM, AMD FX-8350 Eight-Core-Prozessor und Radeon HD 4250. Dies bedeutet auch, dass ich Ihren Code ausführen kann.
Führende Antworten
- 11 in C ++ von feersum. 25 Sekunden.
- 11 in C ++ von Andrew Epstein. 176 Sekunden.
- 10 in Javascript von Neil. 54 Sekunden.
- 9 in Haskell von Nimi. 4 Minuten und 59 Sekunden.
- 8 in Javascript von fəˈnɛtɪk. 10 Sekunden.
fastest-code
Blätter mehr Raum für Optimierungen durch beide Code - Ebene Optimierungen und einem guten Algorithmus. Also ich denke dasfaster-code
ist besser alsfaster-algorithm
.Antworten:
C ++ 11 (sollte auf 11 oder 12 kommen)
Im Moment ist dies Single-Threaded.
Kompilieren:
quelle
feersum.cpp:111:61: warning: shifting a negative signed value is undefined [-Wshift-negative-value] int middle = int(s >> npre * MAX_N_BITS) & ~(~0 << MAX_N_BITS);
Haskell, Punktzahl 9
Kompilieren mit
-O3
. Auf meiner 6 Jahre alten Laptop-Hardware dauert es 6 Minuten 35 Sekunden, bisn=9
sie ausgeführt wird. Auf der Referenzhardware sind es vielleicht weniger als 5 Minuten .quelle
JavaScript, Punktzahl 10
Erklärung: Die Berechnung
n=10
ist schwierig, da es über zwei Milliarden Paare und über 26 Milliarden mögliche Sequenzen gibt. Um die Sache zu beschleunigen, habe ich die Berechnung in 121 Fächer aufgeteilt. Da die Sequenzen unter bitweisem Komplement invariant sind, kann ich ohne Verlust der Allgemeinheit annehmen, dass das mittlere Bit vonT
Null ist. Dies bedeutet, dass ich das erste und das letzte Element der Sequenz unabhängig von den oberenn-1
und unterenn-1
Bits von bestimmen kannT
. Jeder Behälter entspricht einem anderen Paar von ersten und letzten Elementen; Ich durchlaufe dann alle möglichen Sätze von oberen und unteren Bits, die jedem Bin entsprechen, und berechne die verbleibenden Elemente der Sequenz, wobei ich schließlich die eindeutigen Sequenzen für jeden Bin zähle. Es bleiben dann insgesamt 121 Behälter. Ursprünglich dauerte es 45 Stunden, jetzt war es auf meinem AMD FX-8120 in etwas weniger als dreieinhalb Minuten erledigt. Bearbeiten: Vielen Dank an @ChristianSievers für eine 50% ige Beschleunigung. Volle Ausgabe:quelle
n
als Parameter. (Entschuldigung für die schlechte Wahl des Parameternamens dort.)n=1
umgangen (weiß nicht ohne weiteres, warum es hängt).C ++, Punktzahl
1011Dies ist eine Übersetzung von @ Neils Antwort in C ++ mit einer einfachen Parallelisierung.
n=9
Fertigstellung in 0,4 Sekunden,n=10
in 4,5 Sekunden undn=11
in ungefähr 1 Minute auf meinem 2015 Macbook Pro. Vielen Dank auch an @ChristianSievers. Aufgrund seiner Kommentare zu @ Neils Antwort bemerkte ich einige zusätzliche Symmetrien. Von den ursprünglichen 121 Eimern (fürn=10
) bis zu 66 Eimern, wenn die Umkehrung berücksichtigt wird, habe ich nur noch 21 Eimer.Verwenden Sie das folgende Skript, um den Code auszuführen:
Die Ausgabe war wie folgt: (Das Format ist
M: result, seconds
)n=12
Die Berechnung eines einzelnen Threads dauerte 42 Minuten und ergab ein Ergebnis von 7368225813.quelle
sudo apt-get install libiomp-dev
.__builtin_popcount
.__builtin_popcount
in einem constexpr-Kontext verwendet werden soll. Ich könnte mit der naiven Implementierung gehen und es würde die Laufzeit nicht beeinflussen.JavaScript 2,9,48,297,2040,15425,125232,1070553,9530752
In der Konsole ausführen:
Probieren Sie es online aus!
Oder als Stack-Snippet:
Code-Snippet anzeigen
Der Code initialisiert das Array vor, um das Hinzufügen von Einsen zum Array erheblich zu beschleunigen
Der Code findet alle Hamming-Distanzsequenzen und behandelt sie als Zahlenbasis (Eingabe + 1). Er verwendet sie, um 1s in einem Array zu platzieren. Infolgedessen wird ein Array mit den n 1s erzeugt, wobei n die Anzahl der eindeutigen Hamming-Distanzsequenzen ist. Schließlich wird die Anzahl der Einsen mit array.reduce () gezählt, um alle Werte im Array zu summieren.
Dieser Code kann nicht für die Eingabe von 10 ausgeführt werden, da er die Speichergrenzen erreicht
Dieser Code wird in O (2 ^ 2n) ausgeführt, da so viele Elemente generiert werden.
quelle
n = 9
Die Verwendung von node.js dauert 5 Minuten und 30 Sekunden, ist also einfach zu langsam.n = 8
ursprünglich 24 Sekunden auf meinem PC, aber ich konnte den Code so optimieren, dass esn = 8
6 Sekunden dauerte. Ich habe es dann versuchtn = 9
und das hat 100 Sekunden gedauert.