Puzzle (8-14) (answer)

bearophile bearophileHUGS at lycos.com
Fri Aug 15 09:11:42 PDT 2008


Python+Psyco version:

from collections import defaultdict
from sys import maxint
from array import array

def main():
    pairs = defaultdict(list)
    squares_len = 65537
    #squares = [0] * squares_len # for Python
    squares = array("l", [0]) * squares_len # for Psyco
    for i in xrange(1, 1 << 15):
        squares[(i * i) % squares_len] = i * i

    for x in xrange(3, maxint):
        i = 1
        while i * i < x:
            y = x - i * i
            if squares[(x + y) % squares_len] == (x + y):
                if y in pairs:
                    for z in pairs[y]:
                        if (squares[(x - z) % squares_len] == (x - z) and
                            squares[(x + z) % squares_len] == (x + z)):
                            print x, y, z
                            return
                pairs[x].append(y)
            i += 1

import psyco; psyco.full()
main()



C++ (MinGW) version:


#include <vector>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

int main() {
    vector<int> squares(65537, 0);
    for (long long i = 1; i < (1 << 15); i++)
        squares[(i * i) % squares.size()] = i * i;

    typedef hash_map<int, vector<int> > Map;
    Map pairs;

    for (int x = 3; ; x++)
        for (int i = 1; i * i < x; i++) {
            int y = x - i * i;
            if (squares[(x + y) % squares.size()] == (x + y)) {
                Map::iterator arr = pairs.find(y);
                if (arr != pairs.end()) {
                    int nitems = arr->second.size();
                    for (int j = 0; j < nitems; j++) {
                        int z = arr->second[j];
                        if (squares[(x - z) % squares.size()] == (x - z) &&
                            squares[(x + z) % squares.size()] == (x + z)) {
                            printf("%d %d %d\n", x, y, z);
                            return 0;
                        }
                    }
                }
                pairs[x].push_back(y);
            }
        }

    return 0;
}


D version takes 1.29 s (DMD), C++ 1.45 s, Psyco 2.74 s. I don't know why the C++ version is so slow.

Bye,
bearophile


More information about the Digitalmars-d-learn mailing list