Skip to content

Instantly share code, notes, and snippets.

@dudo
Created January 19, 2018 22:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dudo/964f256b4b0b4516ba240bc5b5dc08e0 to your computer and use it in GitHub Desktop.
Save dudo/964f256b4b0b4516ba240bc5b5dc08e0 to your computer and use it in GitHub Desktop.
# Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
# y = mx + b (Equation of a straight line)
class Plot
attr_accessor :coordinates
def initialize(points=[])
@coordinates = points
end
def line_with_most_points
@line_with_most_points ||= slopes_of_all_points.group_by { |n| n }.values.max_by(&:size).first
end
def max_points_on_line
coordinates.count{ |c| point_on_max_line?(tuple_from_coords(c)) }
end
def print_max
puts "Given the #{coordinates.count} points on the plot, #{max_points_on_line} share the same line"
end
def slopes_of_all_points
# n(n-1)/2 possible combinations
# [['4 3', '2 6'], ['4 3', '1 1'], ['2 6', '1 1']]
# [ s1 s2 s3 ]
# 0.5 0.5 1 ]
# http://ruby-doc.org/core-2.2.0/Array.html#method-i-combination
coordinates.combination(2).to_a.map do |c|
line_from_two_points(tuple_from_coords(c[0]), tuple_from_coords(c[1]))
end
end
def tuple_from_coords(coords)
coords.split(' ').map(&:to_f)
end
def line_from_two_points(point1, point2)
# y - y1 = (y2-y1)/(x2-x1) * (x-x1)
# y - y1 = m(x − x1)
# y = (mx - m*x1) + y1
x1 = point1[0]
y1 = point1[1]
x2 = point2[0]
y2 = point2[1]
m = ((y2-y1) / (x2-x1)).round(2)
b = (y1-m*x1).round(2)
{ slope: m, intercept: b }
end
def point_on_max_line?(point)
x = point[0]
y = point[1]
y == line_with_most_points[:slope] * x + line_with_most_points[:intercept]
end
end
test = Plot.new(['4 6', '5 6', '1 1'])
raise 'TESTS FAILING' unless test.max_points_on_line == 2
Plot.new(['5 6', '4 6', '1 1', '2 2', '7 7', '9 12', '7 6', '10 6']).print_max
# working example
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment