/* buss.cpp - solve the problem on http://www.frank-buss.de/challenge/index.html Uses a non clever algorithm. My idea was to try to solve the problem with as little fore thought as possible. This was the simplest solution I could come up with, without trying to think of a solution! Generate every possible triangle from the points Remove duplicates Remove those which are invalid per the diagram Time taken: about 45 mins - far too much of that was farting round with the STL */ #include #include #include #include /* points are numbered 0-10 on the diagram so we will use that mapping for point indexes too */ #define NUM_POINTS 11 typedef int Point; /* each buss line segment contains 4 points, either end and two contained points - except for the base of the figure which contains two points and no contained points. We shall use -1 for this lines additional points. */ typedef Point BussLine[4]; /* initialize the lines and per the diagram */ #define NUM_LINES 7 BussLine lines[NUM_LINES] = { {0, 5, 8, 10}, {0, 3, 7, 9}, {0, 2, 4, 6}, {1, 2, 3, 5}, {1, 4, 7, 8}, {1, 9, 6, 10}, {0, -1, -1, 1} }; /* a triangle consist of the three points connected by lines */ class Triangle { public: Point points[3]; /* we need to keep the points of the triangle sorted so we can maintain a proper ordering in the set */ Triangle(const Point& a, const Point& b, const Point& c) { points[0] = a; points[1] = b; points[2] = c; std::sort(&points[0], &points[3]); } Triangle(const Triangle& other) { for(int i=0; i<3; i++) points[i] = other.points[i]; } bool operator<(const Triangle& other) const { if(points[0] != other.points[0]) return points[0] < other.points[0]; else if(points[1] != other.points[1]) return points[1] < other.points[1]; else return points[2] < other.points[2]; } }; /* output a triangle - utility function */ template T& operator<<(T& os, const Triangle& t) { os << "Triangle(" << t.points[0] << ", " << t.points[1] << ", " << t.points[2] << ")"; return os; } /* is a point on the line? */ bool point_on_line(const BussLine& line, const Point& p) { for(int i=0; i<4; i++) { if(line[i] == p) return true; } return false; } /* is a line segment defined by two points a valid line on the diagram? return the line the points lie on or -1 for failure */ int valid_line(const Point& start, const Point& end) { for(int i=0; i& triangles) { for(int a=0; a& result, const std::set& candidates) { for(std::set::const_iterator i = candidates.begin(); i != candidates.end(); ++i) { if(valid_triangle(*i)) { result.push_back(*i); } } } int main(int argc, char **argv) { std::set candidates; std::vector result; permute_triangles(candidates); buss_validate(result, candidates); for(int i=0; i