Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for The Rows of Cakes by Kurush
# migrated from python 2.7
# I create a line equation for every possible pair of points
# Then I create a dictinary with line equations as keys and sets of points as values
# Then I count the required number of lines.
import itertools
def checkio(cakes):
lines_dict = dict()
point_pairs = list(itertools.combinations(cakes, 2))
for (x1,y1),(x2,y2) in point_pairs:
A, B, C, line_exists = get_line_equation(x1, y1, x2, y2)
if line_exists == False: continue
A1, B1, C1 = round(A, 2), round(B, 2), round(C, 2)
if (A1, B1, C1) not in lines_dict:
lines_dict[(A1, B1, C1)] = set()
lines_dict[(A1, B1, C1)].add((x1, y1))
lines_dict[(A1, B1, C1)].add((x2, y2))
else:
lines_dict[(A1, B1, C1)].add((x1, y1))
lines_dict[(A1, B1, C1)].add((x2, y2))
count = 0
for line, points in lines_dict.items():
if len(points) > 2:
count += 1
return count
# Get line equation Ax + By + C = 0 given two points (xa, ya) and (xb, yb).
def get_line_equation(xa, ya, xb, yb):
if (xb - xa != 0) and (yb - ya != 0):
A = 1. / (xb - xa)
B = 1. / (ya - yb)
C = 1. * ya / (yb - ya) - 1. * xa / (xb - xa)
# normalization of koefficients
B = B / A
C = C / A
A = 1.
return A, B, C, True
elif (xb - xa == 0) and (yb - ya != 0):
A = 1.
B = 0.
C = -xa
return A, B, C, True
elif (xb - xa != 0) and (yb - ya == 0):
A = 0.
B = 1.
C = -ya
return A, B, C, True
elif (xb - xa == 0) and (yb - ya == 0):
return 0, 0, 0, False
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([[3, 3], [5, 5], [8, 8], [2, 8], [8, 2]]) == 2
assert checkio(
[[2, 2], [2, 5], [2, 8], [5, 2], [7, 2], [8, 2],
[9, 2], [4, 5], [4, 8], [7, 5], [5, 8], [9, 8]]) == 6
June 19, 2014
