Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Speedy category for The Rows of Cakes by zcjsword
# migrated from python 2.7
def checkio(cakes):
#use a dict with (slope, intercept) as key to record how may points on a line
#double loop n**2 to try all point pairs and add to the line dict
#at the end, check how many lines have more than 2 points on them
#assuming: no duplicate points
import itertools as it
def getLine(a, b):
if a[0] == b[0]: return ('INF', float(a[0]))
slope = 0.0 if a[1] == b[1] else (float(a[1])-b[1])/(a[0]-b[0])
return (slope, float(a[1])-a[0]*slope)
lines = dict([])
for a, b in it.combinations(cakes,2): #n**2 double loop
ln = getLine(a, b)
if ln in lines:
if a not in lines[ln]: lines[ln].append(a)
if b not in lines[ln]: lines[ln].append(b)
else:
lines[ln] = [a, b]
return sum(1 for pts in lines.values() if len(pts) > 2)
#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
March 24, 2016
Comments:
