The distance between circles Imagine you are given two lists of numbers which are to be interpreted as points on a circle of circumference 1000.  Let us say

circleA = [10, 24, 44, 175, 321, 579, 618, 841, 871, 979]
circleB = [270, 283, 389, 406, 435, 457, 612, 684, 692, 732]


To measure the distance between these two circles we do the following.

For the first point in circleA, starting from the left, we find the next biggest point in circleB.  So 10 finds 270 and is matched up with it.  Now, using 270, we skip to the next biggest point in circle A which is 321.  We then use 321 to find 389 and match up 321 and 389 and repeat until the end of circleA or we can't find a matching pair.

This gives us a list of pairs as follows.

[(10,270), (321, 389), (579,612), (618,684)]


We say the distance between circleA and circleB is just the average difference between pairs. That is (270-10 + 389-321+612-579+684-618)/4 = 106.75

Now comes the tricky part. As the point are on a circle, we can rotate circleB and recompute this distance.  The task is to compute the following value.


  For arbitrary inputs circleA and circleB, the task is to compute the
  average distance between circleA and all rotations of circleB.


In order to make it interesting I am setting this as fastest-code challenge. I will test with increasing size circles created using (in python)

import random
circumference = 1024
numberpoints = circumference/64
circleA = sorted(random.sample(range(circumference),numberpoints))
circleB = sorted(random.sample(range(circumference),numberpoints))


I will just double the size of circumference until the code takes more than 1 minute to run on my computer.  You output should be accurate to machine precision.

Please provide full instructions for how to compile and run your code on a linux machine.



A rotation simply means adding an offset modulo circumference and then resorting.  In python

rotatedcircleB = sorted([(c+offset)%circumference for c in circleB])
My first try at a fatest-code question. Problem is, I didn't try any optimization…

If the rotation part isn't correct, please tell me.

Also, I don't know how to time test the code, so I tried to use timeit module to run 1000 times in order to have a correct timing. I am not sure if I have to do that, or if it is your part :þ

Anyway, here is my code:

import random
circumference = 1024
numberpoints = circumference/64
circleA = sorted(random.sample(range(circumference),numberpoints))
circleB = sorted(random.sample(range(circumference),numberpoints))

####
from  bisect import bisect_left

def find_next(a, x):
    i = bisect_left(a, x)
    if i != len(a):
        return i, a[i]
    raise ValueError


def dist1(cA, cB):
    l = []
    p = cA[0]
    cA = cA[1:]
    while True:
        try:
            (i, n) = find_next(cB, p)
            l.append(n-p)
            cB = cB[(i+1):]
            (i, p) = find_next(cA, n)
            cA = cA[(i+1):]
        except:
            break
    return (sum(l)/len(l))

def rotate(circleB,i):
    return sorted([(c+i)%circumference for c in circleB])

def distAll(circleA, circleB):
    l = [dist1(circleA, rotate(circleB,i)) for i in xrange(circumference)]
    return sum(l)/circumference

if __name__ == '__main__':
    import timeit
    print(timeit.timeit("distAll(circleA,circleB)", setup="from __main__ import *", number=1000))