• bearophile <bearophileHUGS lycos.com> Jun 10 2010

bearophile <bearophileHUGS lycos.com> writes:

This D2 code adapted from the Java version finds the correct solutions, but I
don't think of it as the a good solution because it stores all items and uses
lot of memory. The Python version I was trying to translate uses only few MB of
RAM, while this version uses almost 100 MB of it.


import std.stdio: writeln;
import std.bigint: BigInt;
import std.algorithm: min, map;
import std.range: iota;
import std.array: array;

BigInt hamming(int limit) {
    BigInt two   = 2;
    BigInt three = 3;
    BigInt five  = 5;

    auto h = new BigInt[limit];
    h[0] = 1;
    BigInt x2 = 2;
    BigInt x3 = 3;
    BigInt x5 = 5;
    int i, j, k;

    foreach (ref el; h[1 .. $]) {
        el = min(x2, x3, x5);
        if (x2 == el)
            x2 = two * h[++i];
        if (x3 == el)
            x3 = three * h[++j];
        if (x5 == el)
            x5 = five * h[++k];
    }
    return h[$ - 1];
}

const(char)[] bigIntRepr(BigInt i) {
    const(char)[] result;
    i.toString((const(char)[] s){ result = s; }, "d");
    return result;
}

void main() {
    writeln(array(map!bigIntRepr(map!hamming(iota(1, 21)))));
    writeln(bigIntRepr(hamming(1691)));
    writeln(bigIntRepr(hamming(1_000_000)));
}


I think it's the first time I am able to write a working program that uses
BigInt :-)
In the first line of the main I have had to use two maps because I was not able
to make it run with just one map.
While writing this program I have found only two problems (beside the known map
one), filed as 4300 and 4301.
This code runs in D 2.62 seconds, its Java version in 1.95 seconds, and its
Python+Psyco version in 1.03 seconds. (The Haskell version that uses a better
algorithm can be a bit faster than the Python version).

The Python translation:

import psyco

def hamming(limit):
    h = [1] * limit
    x2, x3, x5 = 2, 3, 5
    i = j = k = 0

    for n in xrange(1, limit):
        h[n] = min(x2, x3, x5)
        if x2 == h[n]:
            i += 1
            x2 = 2 * h[i]
        if x3 == h[n]:
            j += 1
            x3 = 3 * h[j]
        if x5 == h[n]:
            k += 1
            x5 = 5 * h[k]

    return h[-1]

psyco.bind(hamming)
print [hamming(i) for i in xrange(1, 21)]
print hamming(1691)
print hamming(1000000)

Bye,
bearophile