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