How Many Triangles Do You See?
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…