Created
August 10, 2012 15:30
-
-
Save vlad-shatskyi/3315056 to your computer and use it in GitHub Desktop.
Problem 75, rev.2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <map> | |
#include <thread> | |
#include <mutex> | |
#include <algorithm> | |
#include <iomanip> | |
using namespace std; | |
const long limit = 1500000; | |
mutex mtx; | |
vector<long> squares; | |
map<long, long> used_perimeters; | |
void InitializeSquares(){ | |
for (long i = 0; i <= limit; ++i) { | |
squares.push_back(i*i); | |
} | |
} | |
void FindTriangles(long start_position, long stop_position){ | |
/*Seeks right triangles whose sides are integers and add their perimeters to the map. Perimeter must be less or equal to 'limit'. | |
Searches two catets in the vector of squares and checks if the hypotenuse is there too. | |
*/ | |
auto start = begin(squares) + start_position; | |
auto stop = begin(squares) + stop_position; | |
for (auto b = start; b != stop; ++b) { | |
//Print every thousandth index to estimate running time. | |
if ((b - begin(squares))%1000==0){ | |
mtx.lock(); | |
cout << "Debug: " << b - begin(squares) << endl; | |
mtx.unlock(); | |
} | |
//a must be less then b to avoid duplicates. | |
for (auto a = begin(squares) + 1; a != b; ++a) { | |
if (binary_search(b, end(squares), (*a) + (*b))) { | |
auto c = find(b, end(squares), (*a) + (*b)); | |
//Sum of indexes. | |
if ((a-begin(squares)) + (b - begin(squares)) + (c - begin(squares)) <= limit) { | |
mtx.lock(); | |
++used_perimeters[(a-begin(squares)) + (b - begin(squares)) + (c - begin(squares))]; | |
mtx.unlock(); | |
} | |
} | |
} | |
} | |
} | |
int main(){ | |
InitializeSquares(); | |
thread t1(FindTriangles,1,360000); | |
thread t2(FindTriangles,360000,530000); | |
thread t3(FindTriangles,530000,680000); | |
thread t4(FindTriangles,680000,750000); | |
t1.join(); | |
t2.join(); | |
t3.join(); | |
t4.join(); | |
long answer = 0; | |
for (auto i = begin(used_perimeters); i != end(used_perimeters); ++i) { | |
if (i->second==1) { | |
++answer; | |
} | |
cout << i->first << ": " << i->second << endl; | |
} | |
cout << answer << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment