6
1
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])
You should add an example of what rotation does. Increment all points modulo 1000 and then resort? – John Dvorak – 2014-08-10T06:49:02.520
4Is rotation continuous or discrete? – Peter Taylor – 2014-08-10T06:49:35.957
@PeterTaylor I meant it to be continuous. If this causes a problem then I will rethink of course. – None – 2014-08-10T08:00:04.330
@JanDvorak Yes you are right. I updated the question. – None – 2014-08-10T08:04:05.677
@QuadrExAtt The difference can't be negative. Note that in my example 979 just isn't paired up with anything. – None – 2014-08-13T19:58:03.503