谷歌foobar gearing_up_fortruction_

我正在做谷歌foobar的挑战，但跑出了以下挑战的时间我试图看看我做错了什么。谷歌foobar gearing_up_fortruction_

挑战

司令员拉姆达的私人助理，你被分配配置LAMBCHOP世界末日装置的轴向取向齿轮的任务。它应该非常简单 - 只需添加齿轮即可创建适当的旋转比率。但问题是，由于LAMBCHOP的布局以及支撑它的横梁和管道的复杂系统，支撑齿轮的挂钩固定在位。

LAMBCHOP的工程师给你列出了各种支撑梁上钉组的位置。您需要在每个挂钩上放置一个齿轮（否则齿轮会与未占用的挂钩碰撞）。工程师有大量不同尺寸的齿轮，因此您可以选择任何尺寸的齿轮，范围从1到1。您的目标是建立一个系统，其中最后一个齿轮以一倍速度（以每分钟转数或rpm）旋转，无论方向如何。每个齿轮（除最后一个齿轮）都接触并转动右侧下一个齿轮上的齿轮。

给定一个名为pegs的不同正整数列表，它表示每个peg沿支撑梁的位置，编写一个函数答案（pegs），如果有解，则返回一个包含两个正整数a和b的列表为了实现上述目标，第一个齿轮半径的分子和分母最简单的形式，即半径= a/b。比率a/b应大于或等于1.并非所有支持配置都必须能够创建正确的旋转比率，因此如果任务不可行，函数answer（pegs）应返回列表[-1， -1]。

例如，如果挂钉放置在[4,30,50]处，则第一个齿轮可以具有12的半径，第二个齿轮可以具有14的半径，并且最后一个半径为6 。因此，最后一个齿轮将旋转两倍于第一个齿轮的速度。在这种情况下，pegs会是[4,30,50]，回答（pegs）应该返回[12,1]。

列表挂钩将按升序排列，并且包含至少2个且不超过20个不同的正整数，全部在1到10000之间。

测试用例

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

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

我目前的解决方案如下

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]

我只能得到6测试用例来传递我现在已经没有时间了，但我很好奇至于什么是正确的解决方案

来源

2016-11-07 Rajdeep Dosanjh

这里是在Python 2.7，工作代码，所有的测试用例是由谷歌通过。这是我想出了刮擦论文一段时间后最好的解决办法：

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]

看到该图片的我怎么想出了这个代码：

来源

2017-08-11 03:17:23

哇，好像你做了很多工作..很详细的答案。 – sulavvr

感谢您的详细解答。按照相同的逻辑，如果将该公式看作线性方程组，并用矩阵求逆来求解r0，r1，r2 ... rn，则可以简化公式。系数矩阵的逆矩阵有一个模式，非常容易计算。奇数和偶数的唯一不同之处在于最终答案必须用偶数除以3。 –

我认为你的解决方案是沿着正确的路线s，但不允许小数半径。

请注意，我们可以象征性地考虑您的算法，设置g[0]=x，然后根据x计算所有的g[j]值。事实证明，每个g[j]是x（具有梯度1或-1）的线性函数。

因此，您会发现g[-1] = a+mx其中m是+1或-1，并且a是整数。

对于解决存在您需要解决的方程式：

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

所以这给了x的候选值（分数），然后您可以重新检查，以确保没有中间半径是负数。

来源

2016-11-07 13:25:56

嗨，我认为这但被认为是挂钩必须是整数值的齿轮半径将是这个假设是否正确？我想不出一个分数齿轮工作的例子 –

如果只有2个销钉距离为10，那么该怎么办？第一档的半径应为10/3，第二档的半径为20/3。 –

这实际上很有意义 –

如果你有兴趣在一个完美可行的解决方案，这是我写的：https://gist.github.com/1lann/be45311db1bd8cbbe6650b0a3e9d1977

它构造方程的一个系统，它解决了每一个轮的每一个半径值。例如，它是如何计算4个钉的解决方案的。

方程的系统将是：

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

我的程序构建了一个矩阵来表示的：

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

然后计算该矩阵的逆，然后将其应用到的距离在钉之间以便找到每个齿轮的半径。如果你想知道数学如何工作，你可以看看：https://www.mathsisfun.com/algebra/systems-linear-equations-matrices.html

然后验证每个齿轮的半径> = 1，最后返回x * 2的值。为了支持分数（任何有理数），所有数字都是分数类型。

我没有硬编码了一些边缘的情况下，例如当桩的数量= 2

来源

2016-11-12 04:22:19 1lann

很酷的解决方案，但矩阵求逆可能有点矫枉过正？ – Luke

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

来源

2018-02-16 06:00:55

谷歌foobar gearing_up_fortruction_

回答

相关问题