/*
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