Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Problem 75, rev.2
#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