The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
Let P
be a binary string of length n
and T
be a binary string of length 2n-1
. We can compute the n
Hamming distances between P
and every n
-length substring of T
in order from left to right and put them into an array (or list).
Example Hamming distance sequence
Let P = 101
and T = 01100
. The sequence of Hamming distances you get from this pair is 2,2,1
.
Task
For increasing n
starting at n=1
, consider all possible pairs of binary strings P
of length n
and T
of length 2n-1
. There are 2**(n+2n-1)
such pairs and hence that many sequences of Hamming distances. However many of those sequences will be identical . The task is to find how many are distinct for each n
.
Your code should output one number per value of n
.
Score
Your score is the highest n
your code reaches on my machine in 5 minutes. The timing is for the total running time, not the time just for that n
.
Who wins
The person with the highest score wins. If two or more people end up with the same score then it is the first answer that wins.
Example answers
For n
from 1
to 8
the optimal answers are 2, 9, 48, 297, 2040, 15425, 125232, 1070553
.
Languages and libraries
You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.
My Machine The timings will be run on my 64-bit machine. This is a standard ubuntu install with 8GB RAM, AMD FX-8350 Eight-Core Processor and Radeon HD 4250. This also means I need to be able to run your code.
Leading answers
- 11 in C++ by feersum. 25 seconds.
- 11 in C++ by Andrew Epstein. 176 seconds.
- 10 in Javascript by Neil. 54 seconds.
- 9 in Haskell by nimi. 4 minutes and 59 seconds.
- 8 in Javascript by fəˈnɛtɪk. 10 seconds.
fastest-code
leaves more space for optimizations through both code level optimizations and a good algorithm. So I do think thatfaster-code
is better thanfaster-algorithm
. \$\endgroup\$