This is about the Google foo.bar Gearing Up for Destruction challenge - 2nd of 2 challenges on Level 2. It was pretty interesting and I got through most of it without looking for answers. I did get stuck on 2 failing tests so I finally caved. I didn't copy my solution though, just got an insight from the solution that @CBarraford posted here: https://gist.github.com/1lann/be45311db1bd8cbbe6650b0a3e9d1977, which was a more brute-force trial-and-error solution.
Here's the math I worked out for this problem:
Given:
n pegs, numbered from 1 to n
Let:
d(n) - the distance between peg[n] and peg[n+1]
x - the size of the first gear
y - the size of the last gear
Constraint:
x = 2y
Then:
if n is odd, y = d(n-1) - d(n-2) + d(n-3) - ... - d(1) + x
if n is even, y = d(n-1) - d(n-2) + d(n-3) - ... + d(1) - x
A long mind-numbing proof (work it out yourself if you want) can show that given n number of pegs, you can rearrange the terms to start from d(1) to d(n-1) and get the following:
y = (d(1) - d(2) + d(3) - ... + (sign * d(n-1)))/divisor
where sign (of last term) is
+1 if n is even.
-1 if n is odd.
and divisor is
1 if n odd.
3 if n is even.
This is easier to see with an example:
If n = 4 (even),
y = d(3) - d(2) + d(1) - x
rearranging terms,
y = d(1) - d(2) + d(3) - x
substituting x = 2y,
y = d(1) - d(2) + d(3) - 2y
3y = d(1) - d(2) + d(3)
and you get
y = (d(1) - d(2) + d(3))/3 ## [general form: sign = +1, divisor = 3]
If n = 5 (odd),
y = d(4) - d(3) + d(2) - d(1) + x
substituting x = 2y,
y = d(4) - d(3) + d(2) - d(1) + 2y
y - 2y = d(4) - d(3) + d(2) - d(1)
-y = d(4) - d(3) + d(2) - d(1)
y = -1 * (d(4) - d(3) + d(2) - d(1))
y = -d(4) + d(3) - d(2) + d(1)
rearranging terms,
y = d(1) - d(2) + d(3) - d(4)
and you get
y = (d(1) - d(2) + d(3) - d(4))/1 ## [general form: sign = -1, divisor = 1]
Basically, you sum up the distances from d(1) to d(n-1), alternating the sign of each additional term from negative to positive.
Maybe this might help visualize it better:
Peg 1 2 3 4 5
d(n) <---- d1 ----><---- d2 ----><---- d3 ----><---- d4 ---->
y(n) y(2)=r2 y(3)=r3 y(4)=r4 y(5)=r5
r(n) r1=x = d1-r1 = d2-r2 = d3-r3 = d4-r4
= d1-x = d2 - = d3 - = d4 -
(d1-x) (d2 - (d3 -
(d1-x)) (d2 -
(d1-x)))
So,
y(2) = r2
= d1 - r1
= d1 - x
y(3) = d2 - y(2)
= d2 - (d1 - x)
= d2 - d1 + x
y(4) = d3 - y(3)
= d3 - (d2 - (d1 - x))
= d3 - (d2 - d1 + x)
= d3 - d2 + d1 - x
y(5) = d4 - y(4)
= d4 - (d3 - (d2 - (d1 - x)))
= d4 - (d3 - (d2 - d1 + x))
= d4 - (d3 - d2 + d1 - x)
= d4 - d3 + d2 - d1 + x
and so on...
Basically,
For n >= 2,
y(n) = d(n-1) - y(n-1) for n >= 2
Where
y(1) = -x when n is odd
= +x when n is even
I think that should be right. (Shrug) I haven't done this kind of math in a while so if there's something off, it's in my presentation, not the concept.
Anyway, I submitted my fully verified solution based on this idea. Here's the Java code:
public static int[] answer(int[] pegs) {
int firstGearSize = lastGearSize(pegs) * 2;
int divisor = 1;
if ((pegs.length % 2 == 0)) {
if (firstGearSize % 3 == 0) {
firstGearSize /= 3;
} else {
divisor = 3;
}
}
return allGearsFit(pegs, ...)
? new int[] { firstGearSize, divisor }
: new int[] { -1, -1 };
}
private static int lastGearSize(int[] pegs) {
... // elided - no more than 10 lines of code
}
private static boolean allGearsFit(int[] pegs, int ...) {
... // elided - no more than 10 lines of code
}
This solution is simpler than the two others I have seen, one involving matrix inversion or something like that and the other one which was a more brute force, trial-and-error solution, iterating through all the possible radii to see if a solution that met all requirements could be verified.
This solutions translates almost directly from the math that I show above.
NOTE: I had this in another gist but decided I would elide parts of my solution since it looks like Google could be using this foo.bar challenge as a way to identify potential hires. Sorry if that pisses you off but I understand how hard it is to hire good people; it takes me 15 to 20 audition before I can usually find the one person I think deserves the job. I may be giving away too much with this gist already as it is. Anyway, the parts I left out are kind of obvious once you understand the math that I explained above.
Math always trumps brute force!