Orchard Planting: Greatest Common Divisor

The Orchard Planting contest from infinite search space is over. So it is time for a quick write-up.

The rules are simple, on a grid of integers, place N points on the grid to get as much 4 points on a line and never more then 4 points on a line.

My big break-through was when I figured out a way to improve the calculation speed of a solution, and make it possible to extend existing solutions (going back and forwards). To do this I used a unique vector (greatest common divisor vector) which is the same for all point on the same line:

//Calculate unique vector(hash):

doubleIntVector(int x1, int y1, int x2, int y2) {
    int stepx = x2-x1;
    int stepy = y2-y1;
    int gcd = gcd(abs(x2-x1), abs(y2-y1));
    if(gcd > 0) {
        stepx /= gcd;
        stepy /= gcd;
    }

    if(stepx < 0) {
        return (10000 * -stepx) + -stepy;
    } else if(stepx == 0 && stepy < 0){
        return -stepy; //this looks curious... but fixed a bug

    } else {
        return (10000 * stepx) + stepy;
    }
}

Now we can evaluate the points:

for point A in points 0....N {
    create list vectorsA 
    for point B in points A+1....N {
         vectorA.add( doubleIntVector(A.x, A.y, B.x, B.y) )
    }
    sort(vectorsA)
    //if vectorsA has three similair vectors you have 4 points on a line! 

    //(3> = invalid and 2 = candidate for extending!)

}

If a point has three vectors that are the same, we have a line with four points! This can be checked easily if you sort the vectors and go through them once.

Also adding and removing points becomes very easy. A lot of the GCD calculations can be cached. To remove a point, just remove the vectors it made. And to add a point, calculate all the new vectors. So in the end it basically all boils down to a lot of GCD calculations and sorting.

Was this the fastest way to calculate solutions in this contest? I don’t know, but I was really pleased when I figured it out. With a better algorithm for picking possible numbers (instead of hill-climbing) and some more processor power I bet I could have ended a bit higher up the hill.

Also: Keep an eye out for the next contest, it is going to be an interesting one! January the 13th.