In the last month I came across a few posts in facebook asking to count different triangles in a bigger triangle like this one.

After a few attempts counting on screen while pointing with my finger on the display or drawing the triangles on paper and trying to highlight the ones I’ve already counted I realised that it takes me way too long and is kind of boring. Thinking about it a bit I decided try and solve it with a small ruby programm.

Idea

My basic idea was to model the triangle puzzle as a set of lines and intersection points. By detecting common intersection points for each set of three lines I then can see if they form a triangle or not.

Architecture

There are points and lines and puzzles. Lines can have many points. A puzzle has multiple lines. The Puzzle class also handles all the calculations.

Steps

  • Divide the puzzle into line triples
  • Check if line triple makes a trianlge
  • Count total triangles

Implementation

	class Point
    attr_accessor :name

  	def initialize(name)
    	@name = name
  	end
  end
  class Line
    attr_accessor :name, :points

    def initialize(name, points=[])
      @name = name
      @points = points
    end

    def add_points(points)
      @points << points
      @points.flatten!
    end
  end

Point and Line classes describe the basic structures. The whole magic then happens in the Puzzle class.

  class Puzzle
    attr_accessor :name, :lines

    def initialize(name, lines)
      @name = name
      @lines = lines
    end

    def count_triangles
      triangles(@lines.combination(3).to_a)
    end

    private

    def triangles(line_triples)
      triangles = []

      line_triples.each do |triple|
        triangles << triangle_points(triple) if  triangle_points(triple).size == 3
      end

      puts "#{triangles.compact.size} triangles found:\n#{print_triangles(triangles.compact)}"
    end

    def triangle_points(line_triple)
      matching_points = []

      line_triple.combination(2).to_a.each do |line_tuple|
        matching_points << common_point(line_tuple)
      end

      matching_points.uniq.compact.size == 3 ? matching_points : [nil]
    end

    def common_point(line_tuple)
      line_tuple[0].points.each do |point_line_1|
        line_tuple[1].points.each do |point_line_2|
          return point_line_1.name if point_line_1 == point_line_2
        end
      end
      nil
    end

    def print_triangles(triangles_points)
      triangles_points.each do |triangle|
        puts triangle.to_s
      end
    end

  end

What’s next

For now I will concentrate on writing tests and making small refactorings to the code base.

I’m wondering how would you approach such problem…