Google foobar gearing_up_for_destruction

Question

I made a google foobar call, but I did not have enough time for the next call. I am trying to understand what I did wrong.

Call

As a personal assistant to Commander Lambda, you have been assigned the task of configuring the axial orientation devices of the Lomson device. It should be pretty simple - just add gears to create the appropriate rotation ratio. But the problem is that due to the location of the LAMBCHOP and the complex system of beams and pipes supporting it, the bindings that will support the gears are locked in place.

LAMBCHOP engineers have provided you with lists identifying the placement of peg groups along various support beams. You need to put the gear on each pin (otherwise the gears will collide with the unoccupied pins). Engineers have many gears in different sizes, so you can choose gears of any size, starting with a radius of 1 inch. Your goal is to build a system in which the last gear rotates at twice the speed (in revolutions per minute or revolutions) of the first gear, regardless of direction. Each gear (except the last) touches and rotates the gear on the next peg to the right.

Given a list of different natural numbers called pegs representing the location of each peg along the support beam, write a response function (pegs) that, if there is a solution, returns a list of two positive numbers a and b, representing the numerator and denominator of the radius of the first gear in its simplest view to achieve the goal above, such that the radius = a / b. The a / b ratio should be greater than or equal to 1. Not all support configurations will necessarily be able to create the correct rotation coefficient, therefore, if the task is impossible, the response of the function (pegs) should return a list of [-1, -1].

For example, if the pins are located in [4, 30, 50], then the first gear can have a radius of 12, the second gear can have a radius of 14, and the last gear can have a radius of 6. Thus, the last gear will rotate twice as fast as the first. In this case, the bindings will be [4, 30, 50], and the answer (bindings) should return [12, 1].

The list codes will be sorted in ascending order and will contain at least 2 and no more than 20 different positive integers, all between 1 and 10000 inclusive.

Testing

Inputs: (int list) pegs = [4, 30, 50] Output: (int list) [12, 1] Inputs: (int list) pegs = [4, 17, 50] Output: (int list) [-1, -1] 

My current solution is as follows

 def answer(pegs): n = len(pegs) g = range(n) k = pegs[1] - pegs[0] for i in range(0,k,2): g[0] = i for j in range(1,n): g[j] = (pegs[j] - pegs[j-1]) - g[j-1] if any(b < 1 for b in g): continue if 1.0*g[0]/g[-1] == 2.0: return [g[0],1] return [-1, -1] 

I could only get 6 test cases to get through. I'm running out of time now, but I'm curious what the right decision was

Answer 1

Here's the working code in python 2.7, for which all test cases have been submitted to Google. This is the best solution I came up with after scratching 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. 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] 

Check out this image as I came up with this code:

Answer 2

I think your decision follows the right line, but does not allow a fractional radius.

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

So you will 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) 

therefore, this gives the candidate x value (as a fraction), which can then be double-checked to ensure that the intermediate radius is not negative.

Answer 3

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

He builds a system of equations where it solves the values ​​for each radius of each gear. Here, how he calculates the solution for 4 bindings, for example.

The system of equations will be:

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

My program creates a matrix to represent it:

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

He then calculates the inverse matrix and then applies it to the distances between the pegs to find the radius of each gear. If you are interested in how mathematicians work, you can see: https://www.mathsisfun.com/algebra/systems-linear-equations-matrices.html

Then each transmission is checked for a radius> = 1 and, finally, the value x * 2 is returned. To support fractions (any rational number), all numbers are of the Fraction type.

I made hard code for some ribs, for example, when the number of horses = 2.

Answer 4

 from fractions import Fraction def answer(a):  l = len(a)  if(not a or l == 1): return [-1,-1]  s = (a[l-1] - a[0]) if (l % 2 == 0) else (-a[l-1]-a[0]);  if(l > 2):      for i in range(1, l-1): s+= 2 * (-1)**(i+1) * a[i]  v = Fraction(2*(float(s)/3 if (l%2==0) else float(s))).limit_denominator();  c = v;  for i in range(0, l-2):    d = a[i+1] - a[i]    n = d - c    if(c < 1 or n < 1): return [-1,-1]    else: c = n  return [v.numerator, v.denominator];