gearing_up_for_destruction Google foobar solution. I'm posting this because I'm angry that foobar glitched up and ate my solution, and `submit` didn't actually go through. `verify` however said it passed all tests. Oh well, I'll post it here for science.

gearing.py

from fractions import Fraction

def invert(matrix):
    n = len(matrix)
    inverse = [[Fraction(0) for col in range(n)] for row in range(n)]

    for i in range(n):
        inverse[i][i] = Fraction(1)

    for i in range(n):
        for j in range(n):
            if i != j:
                if matrix[i][i] == 0:
                    return false
                ratio = matrix[j][i] / matrix[i][i]
                for k in range(n):
                    inverse[j][k] = inverse[j][k] - ratio * inverse[i][k]
                    matrix[j][k] = matrix[j][k] - ratio * matrix[i][k]

    for i in range(n):
        a = matrix[i][i]
        if a == 0:
            return false
        for j in range(n):
            inverse[i][j] = inverse[i][j] / a
    return inverse


def answer(pegs):
    if len(pegs) < 2:
        return [-1, -1]

    if len(pegs) == 2:
        x = (Fraction(pegs[1] - pegs[0]) / Fraction(3)) * Fraction(2)
        if (x.numerator < 1) or (x.numerator < x.denominator):
            return [-1, -1]

        return [x.numerator, x.denominator]

    matrix = []
    rowNum = 0
    deltas = []
    for loc in pegs:
        deltas.append(Fraction(pegs[rowNum + 1] - pegs[rowNum]))

        if rowNum == 0:
            row = [Fraction(2), Fraction(1)] + [Fraction(0)] * (len(pegs) - 3)
            matrix.append(row)
        elif rowNum == len(pegs) - 2:
            row = [Fraction(1)] + [Fraction(0)] * (len(pegs) - 3) + [Fraction(1)]
            matrix.append(row)
            break
        else:
            row = [Fraction(0)] * rowNum + [Fraction(1), Fraction(1)] + [Fraction(0)] * (len(pegs) - rowNum - 3)
            matrix.append(row)
        rowNum = rowNum + 1

    inverse = invert(matrix)
    if not(inverse):
        return [-1, -1]

    # Validate all gears
    for i in range(1, len(pegs)-1):
        y = Fraction(0)
        for j in range(len(pegs)-1):
            y = y + inverse[i][j] * deltas[j]
        if (y.numerator < 1) or (y.numerator < y.denominator):
            return [-1, -1]

    x = Fraction(0)
    for i in range(len(pegs)-1):
        x = x + inverse[0][i] * deltas[i]

    x = x * Fraction(2)

    if (x.numerator < 1) or (x.numerator < x.denominator):
        return [-1, -1]

    return [x.numerator, x.denominator]

print(answer([1, 2]))

While this does work, i found the code hard to read/follow as theres no comments. Heres my answer that works and is a lot simpler.

def answer(pegs):
    # no need to check ratios that are too large to fit on the first peg.
    maximum = pegs[1] - pegs[0] - 1
    for x in xrange(1, maximum):
        # calculate our gear sizes given the first size is x
        gear_sizes = [x]
        for peg in xrange(1, len(pegs)):
            gear_sizes.append(pegs[peg] - (pegs[peg-1] + gear_sizes[-1]))

        # if any of the gear_sizes are zero or negative, this can't be a potential because obviously
        # we can't have a non-existent gear. This isn't our answer, so skip this and try the next
        # one.
        if any(d <= 0 for d in gear_sizes):
            continue

        # see if we got an exact 2/1 match
        if x == 2 * gear_sizes[-1]:
            return [x, 1]

        # test if we have a ratio that works with 3 as the denominator
        if x+1 == 2 * gear_sizes[-1]:
            return [(x * 3) + 1, 3]
        if x+2 == 2 * gear_sizes[-1]:
            return [(x * 3) + 2, 3]

    return [-1, -1]

@cbarraford I see you only check if the solution has a denominator of 3 or 1, is there any reason for that?

@SammyIsra The denominators can only be 3 or 1 because if you work out the math...

Given:
   n is the number of pegs, with 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

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

Since x = 2y, you can solve for y:
if n is odd,   y = d(1) - d(2) + d(3) - ... - d(n-1)
if n is even, 3y = d(1) - d(2) + d(3) - ... + d(n-1)

I'll post my solution and the full rundown of the math in another gist.

IMO, @cbarraford's solution is better than the matrix one but it's also a brute force trial-and-error solution. My solution iterates through the pegs array exactly twice, once to calculate for y, then another time to check that the calculated value of x results in all gears in the chain being valid. I have to confess that I could have been stuck with 2 failing tests for a while if I hadn't gotten some insight from @cbarraford's solution regarding validity of the gear sizes.

Update: I created https://gist.github.com/jlacar/e66cd25bac47fab887bffbc5e924c2f5 to give a more detailed rundown of the math I used and also shared part of my Java solution.

I want to thank everyone on this thread for the insight into this problem. Unfortunately, I ran out of time trying to figure how to handle solutions with fractional radii and was only able to get 6/10 test cases to pass. Seeing the math that shows the denominator of the solution in its simplest form can only be 1 or 3 was enlightening, and I believe I was able to finalize my solution with that info. I'm not positive that it's bulletproof because I couldn't verify, but it takes a similar approach to @cbarraford and I wanted to post it for anyone else who comes across this thread:

https://gist.github.com/rosemichaele/30e138c4fa2125074d50a186fc5652d2

I came up with a very efficient solution for this problem. I also have an image there to explain if you are interested to see. Please upvote my answer if you like it. Thanks
https://stackoverflow.com/a/45626410/8447619

I am struggling to understand the final part of the question.

it says:

returns a list of two positive integers a and b representing the numerator and denominator of the first gear's radius in its simplest form

what does it mean?
suppose I have the full list of gears radius like :
p = [4, 30, 50] and r = [12, 16, 6] how do I get a and b?

I am struggling to understand the final part of the question.

it says:

returns a list of two positive integers a and b representing the numerator and denominator of the first gear's radius in its simplest form

what does it mean?
suppose I have the full list of gears radius like :
p = [4, 30, 50] and r = [12, 16, 6] how do I get a and b?

here r = [12,14,6] .