#include <iostream>
#include <list>
#include <unordered_set>
using namespace std;
#include <functional>
#include <chrono>
unsigned int N = 19;
class Point{
private:
int x, y;
public:
Point(int a_x, int a_y)
: x(a_x), y(a_y)
{}
~Point(){}
int getX()const { return x; }
int getY()const { return y; }
void setX(int ax) { x = ax; }
void setY(int ay) { y = ay; }
bool operator == (const Point& rhs) const{
return x == rhs.x && y == rhs.y;
}
bool operator != (const Point& rhs) const{
return !(*this == rhs);
}
Point transpose() { return Point(y,x); }
};
namespace std
{
// specializing hash function for Point
template <>
struct hash<Point>
{
size_t operator()(Point const & x) const /*noexcept*/ // since VS 2012 compiler doesnt support this yet
{
return (
(101 + std::hash<int>()(x.getX())) *
101 + std::hash<int>()(x.getY())
);
}
};
}
class Data{
public:
Data()
: m_count(0), rightBottom(0,0)
{}
~Data(){ m_Points.clear(); }
// returns true if point was successfully inserted into this
bool insert(Point p);
size_t count();
static bool isLegitPoint(const Point& p);
void print();
private:
unordered_set<Point> m_Points;
size_t m_count;
Point rightBottom;
};
bool Data::insert(Point p){
if(this->m_Points.count(p))
return false;
this->m_Points.insert(p);
int mul = 1;
if(p.getX() == 0 && p.getY() == 0)
mul = 1;
else if(p.getX() == 0 || p.getY() == 0)
mul = 2;
else
mul = 4;
m_count += mul;
if(p.getX() >= rightBottom.getX())
rightBottom.setX(p.getX());
if(p.getY() >= rightBottom.getY())
rightBottom.setY(p.getY());
return true;
}
size_t Data::count(){
return this->m_count;
}
bool Data::isLegitPoint(const Point& p){
int x = abs(p.getX());
int y = abs(p.getY());
unsigned int xsum, ysum;
xsum = ysum = 0;
while(x != 0){
xsum += (x % 10);
x = x / 10;
}
while(y != 0){
ysum += (y % 10);
y = y / 10;
}
return xsum + ysum <= N;
}
#include <fstream>
void Data::print(){
ofstream f;
f.open("data.txt");
for(auto i = m_Points.begin(); i != m_Points.end(); ++i){
f << i->getX() << "," << i->getY() << "\n";
}
f.close();
}
int main(){
Point origin(0,0);
list<Point> points;
Data legitPoints;
unordered_set<Point> seenPoints;
auto startTime = chrono::steady_clock::now();
points.push_back(origin);
while(!points.empty()){
Point p = points.front(); // this is a seek operation
points.pop_front(); // this actually deletes an element
// continue if p has already been checked
if(seenPoints.count(p))
continue;
else
{
seenPoints.insert(p);
if(p.getX() != p.getY())
seenPoints.insert(p.transpose());
}
if(Data::isLegitPoint(p)){
points.push_back( Point(p.getX()+1, p.getY()) );
points.push_back( Point(p.getX(), p.getY()+1) );
legitPoints.insert(p);
if(p.getX() != p.getY())
legitPoints.insert(p.transpose());
}
}
auto endTime = chrono::steady_clock::now();
auto diff = endTime - startTime;
cout << chrono::duration <double, milli> (diff).count() << " ms" << endl;
cout << "Total number of points: " << legitPoints.count();
//legitPoints.print();
seenPoints.clear();
return 0;
}