Download and view my resume (PDF)

Wednesday, March 22, 2017

FooBar Gearing Up For Destruction

I was pulled into Google FooBar. This is my solution to the third problem I received, Gearing Up For Destruction.

Given
R0 is radius of the zeroth element
Rn is any radius of element n
Rlast is the radius of the last element
Pn is the peg position (the input int) for element n

This is an induction problem, so I solved it using a base case and an induction case:

R0 = 2*Rlast
Rn+1 = Pn+1 - Pn - Rn

To get a feel for the resulting math, I then expanded out a few iterations and saw that it formed a predictable series (written with unreduced complexity to show patterns):

Two pegs:
R0 = (2/3) * (-P0 +P1)

Three pegs:
R0 = (2/1) * (-P0 +2P1 -P2)

Four pegs:
R0 = (2/3) * (-P0 +2P1 -2P2 +P3)

Five pegs:
R0 = (2/1) * (-P0 +2P1 -2P2 +2P3 -P4)

...and so on.

So, the pattern was two times each peg, except only one times the first and last peg, and the signs flipped for each peg. Then also there was a coefficient in front of all that: 2 for odd number of pegs and 2/3 for even number of pegs.

That's the basic solution, a simple math problem, but the description also demanded reduced fractions plus recognition of logically invalid cases, so there was a little more code.

    public static int[] answer(int[] pegs) {
        // do the inductive math
        int a = pegs[0];
        int flip = -1;
        for(int peg: pegs) {
            a += 2 * peg * flip;
            flip *= -1;
        }
        a += pegs[pegs.length-1] * flip;
        a *= 2;
        int b = (pegs.length%2==0) ? 3 : 1;

        // reduce

        if(a%b==0) {
            a /= b;
            b = 1;
        }

        // reject bad values

        float prevR = ((float)a) / ((float)b);
        for(int i = 0; i < pegs.length - 2; i++) {
            int width = pegs[i+1] - pegs[i];
            if(prevR < 0 || prevR > (width-1)) return new int[] {-1, -1};
            prevR = width - prevR;
        }

        return new int[] {a, b};

    }

I really enjoyed this problem, I had to puzzle it out on paper. Coding it was made more difficult by lack of access to the test cases so it wasn't clear where the algorithm was failing. The code to reject invalid values looks straightforward but it is the residue of many failed attempts.

No comments:

Post a Comment