Solution for Facebook hacker cup 2016 Boomerang question https://www.facebook.com/hackercup/problem/910374079035613/

fb_hackercup2016_boomerang.py

from datetime import datetime

def reading_input(file, teja):
    with open(file) as w:
        content = w.readlines()
    
    ctr = 0

    boomerangs = []
    nights = content[0] #ignoring this value as we can print without nights
    for i in range(1, len(content)) :
        if ctr == 0:
            ctr = int(content[i]) #count of stars given
            points = [] #flush out the points
        else:
            x_coord = int(content[i].split(" ")[0])
            y_coord = int(content[i].split(" ")[1])
            points.append((x_coord, y_coord))
            ctr = ctr - 1
        
        if ctr == 0 :
            boomerangs.append(teja(points)) #hoping that list order persist
            print "Night " + str(len(boomerangs)) + " :  " + str(boomerangs[len(boomerangs) - 1])
    
    for i, count in enumerate( boomerangs ):
        print "Case #%d: %d" % (i, count)


def chaalu( points ):
    if debug == True:
        print "points %s" % (points)
    pairs = makePointsintoPairs(points)
    if debug == True:
        print "pairs %s length %d" % (pairs, len(pairs))
    return getBoomerangCount( points, pairs)
    

def dumb( points ) :
    if debug == True:
        print "points %s" % (points)
    pairs = makePointsintoUnorderedPairs(points)
    if debug == True:
        print "pairs %s length %d" % (pairs, len(pairs))
    return getBoomerangCountBySlope( points, pairs)    



def zuckerberg_ki_maa_ki( points ):
    totalBoom =0
    for i in range(0, len(points)):
        ghanta = {}
        perStarBoom = 0
        for j in range(0, len(points)):
            if(i != j):
                distance = (points[j][X] - points[i][X]) ** 2 + (points[j][Y] - points[i][Y]) ** 2
                ghanta[distance] = ghanta.get(distance, 0) + 1
        if debug == True:
            print ghanta
        for key in ghanta:
            perStarBoom += boomerangPossiblefromPoints(ghanta[key])
        totalBoom += perStarBoom
    
    return totalBoom
            
            


def makePointsintoPairs( points ):
    pairs = []
    for i in range(0, len(points)):
        for j in range(0, len(points)):
            if(i != j):
                pairs.append( (points[i], points[j]) )  #making pairs for line segments
    
    return pairs


def makePointsintoUnorderedPairs( points ):  # x-->y is equal to y-->x and counted only once
    pairs = []
    for i in range(0, len(points)):
        for j in range(i+1, len(points)):
            pairs.append( (points[i], points[j]) )  #making pairs for line segments
    
    return pairs



def getBoomerangCount( points, pairs ):
    boom = 0
    seenLineSegmentfromCenter = []
    for pair in pairs :

        #first element is center of circle, another is point on its periphery
        if debug == True:
            print "======================="
            print pair
        r2 = (pair[0][X] - pair[1][X]) ** 2 + (pair[0][Y] - pair[1][Y]) ** 2

        seenLineSegmentfromCenter.append( pair ) #keep a list of centers so that they are not repeated
        
        for point in points :
            if point == pair[0] or point == pair[1]:
                if debug == True:
                    print "skipping : " + str(point)
                continue #don't compare with center point or the other end of line segment for circle
            if (pair[0], point) in seenLineSegmentfromCenter:
                if debug == True:
                    print "SKIPPING seenLineSegmentfromCenter %s" %(str((pair[0], point)))
                continue #skip if center and radius has already been used once
                        
            if isPartofCircle( pair[0][X], pair[0][Y], r2, point[X], point[Y]  ) : #if it lies on circle it makes a boomrang with first pair line segment
                boom = boom + 1
                if debug == True:
                    print "boom " + str(boom) + " circle x " + str(pair[0][X]) + " y " + str(pair[0][Y]) + " r2 " + str(r2) + " point x " + str(point[X]) + " y " + str(point[Y])
        
    return boom
            
    


def isPartofCircle( a, b, r2, x, y   ) :
    res = (x - a)** 2  + (y-b) ** 2
    # print "x is %d y is %d res is %d r is %d" %(x, y, res, r2)
    if res == r2 :
        return True
    else :
        return False

def getBoomerangCountBySlope(points, pairs ):
    boom = 0
    for pair in pairs:
        y_diff = pair[1][Y] - pair[0][Y]
        x_diff = pair[1][X] - pair[0][X]
        mid_point = ( (pair[0][X] + pair[1][X])/2.0, (pair[0][Y] + pair[1][Y])/2.0   ) 
        if debug == True:
            print "mid point : " + str(mid_point) + "for pair:" + str(pair)
        m_needed = False
        y_needed = False
        if y_diff is 0:
            c = mid_point[X]
        elif x_diff is 0:
            y_needed = True
            c = mid_point[Y]
        else:
            m_needed = True
            m_perpedicular = (-1.0 * x_diff) / y_diff
            c = mid_point[Y] - m_perpedicular * mid_point[X]  #c = y - mx
        
        for point in points:
            if point == pair[0] or point == pair[1]:
                if debug == True:
                    print "skipping : " + str(point)
                continue #don't compare with center point or the other end of line segment for circle
            if m_needed is True:
                temp = point[Y] - m_perpedicular * point[X]
                if temp == c:
                    boom =  boom + 1
                    if debug == True:
                        print "boom " + str(boom) + "pair " + str(pair) + " point " + str(point)
            else:
                if y_needed is True:
                    if point[Y] == c:
                        boom = boom + 1
                        if debug == True:
                            print "boom " + str(boom) + "pair " + str(pair) + " point " + str(point)                        
                else:
                    if point[X] == c:
                        boom = boom + 1
                        if debug == True:
                            print "boom " + str(boom) + "pair " + str(pair) + " point " + str(point)                                                
    return boom
            
        
            
            
def boomerangPossiblefromPoints(po):
    return (po * (po - 1)) / 2

        

def tests():
    #print isPartofCircle( 10, 10, 25, 15,10 )
    # points = [(0,0), (0,1), (0,2), (0,3), (0,4)]
    # points = [(0,0), (0,100), (100,0), (100,100)]
    points = [(5,6), (6,5), (6,7), (7,6), (7,8), (8,7)]
    print chaalu(points)
    print dumb(points)
    print zuckerberg_ki_maa_ki(points)
    
debug = False
X = 0
Y = 1
old_time = datetime.now()
print old_time
# tests()
# reading_input("inputs/fb_hackercup_boomerang.1", chaalu)
# reading_input("inputs/fb_hackercup_boomerang.1", dumb)
# reading_input("inputs/fb_hackercup_boomerang", zuckerberg_ki_maa_ki)
reading_input("../files/boomerang_constellations.in", zuckerberg_ki_maa_ki)
new_time = datetime.now()
print new_time
print new_time - old_time