Puzzle (8-14) (answer)

[bearophile]

Using a simple handmade perfect hash the running time of this program becomes 1.3 s on my 2 GHz PC (this also shows why I say that D AAs are slow).

import std.stdio: putr = writefln;

void main() {
    auto squares = new int[70_001];
    for (int i = 1; i < short.max; i++)
        squares[(i * i) % squares.length] = i * i;

    int[][int] pairs;
    for (int x = 3; ; x++) {
        for (int i = 1; i * i < x; i++) {
            int y = x - (i * i);
            if (squares[(x + y) % squares.length] == x + y) {
                auto arr = y in pairs;
                if (arr !is null) {
                    foreach (z; *arr) {
                        if (squares[(x - z) % squares.length] == (x - z) &&
                            squares[(x + z) % squares.length] == (x + z)) {
                            putr(x, " ", y, " ", z);
                            return;
                        }
                    }
                }

                arr = x in pairs;
                if (arr is null) {
                    pairs[x] = new int[0];
                    arr = x in pairs;
                }
                *arr ~= y;
            }
        }
    }
}

Bye,
bearophile