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