The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
P be a binary string of length
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
P = 101 and
T = 01100. The sequence of Hamming distances you get from this pair is
n starting at
n=1, consider all possible pairs of binary strings
P of length
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
Your code should output one number per value of
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
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.
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.
- 11 in C++ by feersum. 25 seconds.
- 11 in C++ by Andrew Epstein. 176 seconds.
- 9 in Haskell by nimi. 4 minutes and 59 seconds.