require 'set'
class TriangleFinder
def initialize rays
@rays = rays
end
def find
find_line_segments
find_point_connections
find_triangles
@triangles
end
# Find all (O, D) such that O and D are joined by a line segment.
def find_line_segments
@segments = Set.new
@rays.each do |ray|
ray.each do |origin|
(ray - [origin]).each do |destination|
@segments << [origin, destination].sort
end
end
end
end
# For every point A, find all points that connect to A with a
# line segment.
def find_point_connections
@connections = Hash.new
@segments.each do |a, b|
(@connections[a] ||= []) << b
(@connections[b] ||= []) << a
end
@points = @connections.keys
end
# For every point A, find all points B and C that are both
# connected to A with a line segment, but such that (A, B, C)
# are not connected by a straight line.
def find_triangles
@triangles = Set.new
@points.each do |a|
@connections[a].each do |b|
@connections[b].each do |c|
if @connections[a].include? c
unless connected_by_straight_line? a, b, c
@triangles << [a, b, c].sort
end
end
end
end
end
end
# Find whether a ray exists that intersects A, B, and C.
def connected_by_straight_line? a, b, c
@rays.any? do |ray|
ray.include? a and ray.include? b and ray.include? c
end
end
end
rays = [
[0, 1],
[0, 2, 4, 6],
[0, 3, 7, 9],
[0, 5, 8, 10],
[1, 2, 3, 5],
[1, 4, 7, 8],
[1, 6, 9, 10]
]
p TriangleFinder.new(rays).find