Google foobar gearing_up_for_destruction

If you're interested in a perfect working solution, this is what I wrote: https://gist.github.com/1lann/be45311db1bd8cbbe6650b0a3e9d1977

It constructs a system of equations where it solves the values for every radius of every gear. Here's how it computes the solution for 4 pegs for example.

The system of equations would be:

2x + a = peg[1] - peg[0]
a + b = peg[2] - peg[1]
b + x = peg[3] - peg[2]

My program constructs a matrix to represent this:

[
    [2, 1, 0],
    [0, 1, 1],
    [1, 0, 1]
]

It then computes the inverse of the matrix, and then applies it to the distances between the pegs in order to find the radius of every gear. If you're wondering how the maths work, you can look at: https://www.mathsisfun.com/algebra/systems-linear-equations-matrices.html

Each gear is then verified to have a radius >= 1, and finally the value of x*2 is returned. In order to support fractions (any rational number), all numbers are of a Fraction type.

I did hard code some edge cases, such as when the number of pegs = 2.

I got this problem in Jan of 2020. After completing it, I wanted to see if anyone else did it my way, but it doesn't look like it.

The positions of the pegs, along with the first radius, implies what the last gear radius will be. There is a linear relationship between the first gear radius and the last gear radius, as well as boundaries on the size of the first gear radius:

This is the function I wrote that will take in the peg positions and the starting gear radius and calculate the implied last gear radius:

def implied_last_radius(pegs, start_radius):
    diffs = [start_radius] + [x - y for x, y in zip(pegs[1:], pegs[:-1])]
    for i in range(1, len(diffs)):
        diffs[i] = diffs[i] - diffs[i - 1]

    return diffs[-1]

The problem states that all gears must has a radius >= 1, and the last gear must be half the size of the first gear. This puts a lower-bound on the first gear of a radius of 2 (i.e. any valid result with a first gear having a radius less than 2 will result in a last gear with a radius less than 1, which isn't allowed). This also puts an upper bound on the first gear size, because the gear in the second peg must also have a minimum radius of 1. Therefore:

first_radius_diff = pegs[1] - pegs[0]
first_radius_range = (2, first_radius_diff - 1)

We can calculate the implied radius of each of the first radii using the above function. For the pegs [4, 30, 50] The answer is:

First Radii = (2, 25)
Implied Last Radii = (-4, 19)

That is, if the first radius is 2, the last radius must be -4 (invalid), and if the first radius is 25, the last radius is 19. The linear relationship can be modelled as y = mx + b:

m = (implied_radii[1] - implied_radii[0]) / (first_radius_range[1] - first_radius_range[0])
b = implied_radii[0] - m * first_radius_range[0]

Now we have a relation between the first and last gear radius sizes. We simply compute the first radius when the last radius is half the value:

first_radius = b / (0.5 - m)

Lastly, we check to see if that value is within the ranges of allowed first gear radius range, but also critically that it does not require any gears on any pegs that have a radius less than 1:

def solvable(pegs, start_radius, radius_range):
    diffs = [start_radius] + [x - y for x, y in zip(pegs[1:], pegs[:-1])]
    for i in range(1, len(diffs)):
        diffs[i] = diffs[i] - diffs[i - 1]

    return radius_range[0] <= start_radius <= radius_range[1] and all([diff >= 1 for diff in diffs])

The last tricky part that got me was converting to a simplified fractional form. This was easily solved by mapping all of the numerical values to a fractions.Fraction class. If first gear radius passed the solvable test, return the numerator and denominator, else return [-1, -1].

I think your solution is along the right lines, but doesn't allow for a fractional radius.

Note that we can consider your algorithm symbolically, setting g[0]=x, and then computing all the g[j] values in terms of x. It turns out that each g[j] is a linear function of x (with gradient 1 or -1).

You will therefore find that g[-1] = a+mx where m is +1 or -1, and a is an integer.

For a solution to exist you need to solve the equation:

g[0]/g[-1] = 2
x/(a+mx) = 2
x=2(a+mx)
x(1-2m)=2a
x=2a/(1-2m)

so this gives a candidate value of x (as a fraction) which you can then recheck to make sure that no intermediate radius went negative.

Here's the working code in python 2.7 for which all the test cases were passed by Google. This is the best solution that I came up with after scratching papers for a while:

from fractions import Fraction  
def answer(pegs):
    arrLength = len(pegs)
    if ((not pegs) or arrLength == 1):
        return [-1,-1]

    even = True if (arrLength % 2 == 0) else False
    sum = (- pegs[0] + pegs[arrLength - 1]) if even else (- pegs[0] - pegs[arrLength -1])

    if (arrLength > 2):
        for index in xrange(1, arrLength-1):
            sum += 2 * (-1)**(index+1) * pegs[index]

    FirstGearRadius = Fraction(2 * (float(sum)/3 if even else sum)).limit_denominator()

    # now that we have the radius of the first gear, we should again check the input array of pegs to verify that
    # the pegs radius' is atleast 1.
    # since for valid results, LastGearRadius >= 1 and FirstGearRadius = 2 * LastGearRadius
    # thus for valid results FirstGearRadius >= 2

    if FirstGearRadius < 2:
        return [-1,-1]

    currentRadius = FirstGearRadius
    for index in xrange(0, arrLength-2):
        CenterDistance = pegs[index+1] - pegs[index]
        NextRadius = CenterDistance - currentRadius
        if (currentRadius < 1 or NextRadius < 1):
            return [-1,-1]
        else:
            currentRadius = NextRadius

    return [FirstGearRadius.numerator, FirstGearRadius.denominator]

See this image for how I came up with this code: