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]))

Hi, it would be useful if you provided some comments on what the code is doing.

Did you ever manage to submit it? I'm having the exact problem on this exact challenge (My solution was different)

I haven't done extensive testing, but it does fail when there are only two pegs two units apart (e.g [0, 2], [5754, 5756], etc.).

can you explain, what is the actual requirement. i have read the question, but i was not able to understand it completely.

Can anyone explain the requirements please, i have this assignment but not able to finish it since i am not able to understand the requirements. I have 1 day left.

His code works..!! Thank you @1lann.
You'll need to implement inverse because google does not allow numpy library

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] .