Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Problem 75
#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 hypotenuse and longer catet in the vector of squares and checks if the second catet is there too.
*/
auto start = begin(squares) + start_position;
auto stop = begin(squares) + stop_position;
//c (hypotenuse) can't be longer than half of perimeter, so we have to search only up to squares[limit/2]
for (auto c = start; c < stop; ++c) {
//Print every thousandth index to estimate running time.
if ((c - begin(squares))%1000==0){
mtx.lock();
cout << "Debug: " << c - begin(squares) << endl;
mtx.unlock();
}
//b must be less than c.
for (auto b = begin(squares) + 1; b < c; ++b) {
//And a less than b.
if (binary_search(begin(squares)+1, b, *c - *b)) {
auto a = find(begin(squares)+1, b, *c - *b);
//Sum 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,340000);
thread t2(FindTriangles,340000,530000);
thread t3(FindTriangles,530000,690000);
thread t4(FindTriangles,690000,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;
}
//Print perimeters along with quantity of possible triangles for debugging purposes.
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