User Tools

Site Tools



Project Euler: Integer Right Triangles

Solve Project Euler Problem 39 as efficient and as elegant as possible. Document your source code and describe why your solution better than naive solutions.

Simple Meshing Operations

The following piece of source code shows a very simple C++ framework for triangular and quadraliteral meshing in 2D. The task for this puzzle is to complete the source-code. At first the cell class should be specialized for triangles and quadraliterals. Simple tag classes are used for identification. A simple pre-implementation for a triangular cell is given but may be expanded by needed funcionality. Then two simple algorithms have to be implemented:

  • get_area: a simple algorithm which calculates the area of a given cell (triangle or quadrilateral)
  • get_area for multiple cells
  • refine: this algorithm takes a cell apart into smaller cells which cover the original cell (see here and here for examples). Any refinement can be chosen.

At the end of the source code there is a small example which uses the implemented source code. The solution should be coded in C++ STL and Boost. High level C++ features like template and coding paradigms like generic programming or functional programming are beneficial! Adaptions of the presented source codes are welcome and legal (if you wish to provide another interface or something like that). Keep in mind that there is no one true solution to this puzzle. We are seeking for clever and elegant programming skill so feel free to rewrite the code below. The code framework is only for guiding purpose.

An introduction into generic programming is given here and here.

Direct contact for questions and puzzle solutions:

// a simple point type for arbitray dimensions
template<typename coord_type_, unsigned int dim>
struct point
  typedef coord_type_ coord_type;
  point( double x ) { data[0] = x; }
  point( double x, double y ) { data[0] = x; data[1] = y; }
  point( double x, double y, double z ) { data[0] = x; data[1] = y; data[2] = z; }
  boost::array<double, dim> data;
// cell tags for triangles and quadrilaterals
struct triangle_tag {};
struct quadrilateral_tag {};
// this trait generates the number of points for a cell
namespace resulf_of
   template<typename tag>
   struct number_of_points
      static const int value = -1;
   struct number_of_points<triangle_tag>
      static const in value = 3;
// a cell defines a geometric entity, like a line, a triangle, a quadrilateral, a tetrahedron, ...
template<typename cell_tag, typename point_type>
struct cell; // TODO: implement specialization for quadrilateral_tag
struct cell<triangle_tag, point_type>
   // TODO: finish specialization
   boost::array<point_type, resulf_of::number_of_points<triangle_tag>::value > points;
// a simple algorithm which calculates the area of a given cell
template<typename point_type>
typename point_type::coord_type get_area( cell<triangle_tag, point_type> & c )
    // TODO: implement
// TODO: implement get_area for quadraliteral cells
// TODO: implement version for containers (std::vector, std::deque, std::list, std::set, boost::array ...) using iterators. The function should work with the following code
//       implement the corresponding backend
//   std::vector<cell_type> cells;
//   numeric_type area = get_area(cells.begin(), cells.end());
template<typename cell_type, typename cell_container_type>
void refine( cell_type const & c, cell_container_type & refined_cells )
   // TODO: implement refinement for triangles and quadraliterals
int main()
      // defining the base types
      typedef point<double, 2> point_type;
      typedef cell<point_type, triangle_tag> triangle_type;
      // a container of cells
      std::vector<triangle_type> triangles;
      // adding one cell to the container
         triangle_type tmp;
         tmp.points[0] = point_type(0,0);
         tmp.points[1] = point_type(2,0);
         tmp.points[2] = point_type(0,2);
      // adding one cell to the container
         triangle_type tmp;
         tmp.points[0] = point_type(2,0);
         tmp.points[1] = point_type(0,2);
         tmp.points[2] = point_type(2,2);
      // calculating the area of each cell
      double area0 = get_area( triangles[0] );  // should be 2
      double area1 = get_area( triangles[1] );  // should be 2
      // calculating the area of all cells
      double area = get_area( triangles.begin(), triangles.end() );  // should be 4
      // refine the cell
      std::vector<triangle_type> refined_triangles;
      refine( triangles[0], refined_triangles );
      // check the area of the refined cells
      double refined_area = get_area( refined_triangles.begin(), refined_triangles.end() );  // should also be 2
      typedef point<double, 3> point_type;
      typedef cell<point_type, triangle_tag> quadrilateral_type;
      std::vector<quadrilateral_type> quadrilaterals;
         quadrilateral_type tmp;
         tmp.points[0] = point_type(0,0,5);
         tmp.points[1] = point_type(10,0,5);
         tmp.points[2] = point_type(0,10,5);
         tmp.points[3] = point_type(10,10,5);
         quadrilateral_type tmp;
         tmp.points[0] = point_type(10,0,5);
         tmp.points[1] = point_type(20,0,5);
         tmp.points[2] = point_type(10,10,5);
         tmp.points[3] = point_type(20,10,5);
      double area0 = get_area( quadrilaterals[0] );  // should be 100
      double area1 = get_area( quadrilaterals[1] );  // should be 100
      double area = get_area( quadrilaterals.begin(), quadrilaterals.end() );  // should be 200
      std::vector<quadrilateral_type> refined_quadrilaterals;
      refine( quadrilaterals[0], refined_quadrilaterals );
      double refined_area = get_area( refined_quadrilaterals.begin(), refined_quadrilaterals.end() );  // should also be 100
   return 0;
viennamesh/viennamesh_puzzles.txt · Last modified: 2015/03/17 15:01 by viennastar