Google gearing_up_for_destruction

Question

我在做谷歌足球的挑战，但在接下来的挑战中没有时间了，我想看看我做错了什么。

挑战 作为指挥官Lambda的个人助理，您已经被分配了配置LAMBCHOP世界末日设备的轴向定位齿轮的任务。这应该是相当简单的-只是增加齿轮，以创造适当的旋转比率。但问题是，由于路灯的布局和复杂的梁和管道系统支持它，将支持齿轮固定的位置。 兰博的工程师已经给出了你的清单，确定在不同的支撑梁上的一组钉的位置。你需要在每个钉上放置一个齿轮(否则齿轮会与空置的木桩相撞)。工程师有很多不同大小的齿轮储备，所以你可以选择任何大小的齿轮，从半径1向上。您的目标是建立一个系统，其中最后一个齿轮旋转两倍的速度(转速每分钟，或转速)的第一个齿轮，无论方向。每个齿轮(最后一个除外)接触和转动齿轮在下一个钉向右。 给定一个不同的正整数列表，名为pegs，代表支撑梁上每个钉的位置，写一个函数答案(Pegs)，如果有解，它返回一个由两个正整数a和b组成的列表，它们代表第一齿轮半径的分子和分母，以最简单的形式表示，例如radius = a/b。a/b的比率应该大于或等于1。并不是所有的支持配置都有能力创造适当的旋转比，所以如果任务不可能，函数答案(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个测试用例，我现在已经没有时间了，但我想知道正确的解决方案是什么。

Answer 1

以下是python2.7中的工作代码，所有测试用例都由Google通过。这是我在抓取文件一段时间后想出的最好的解决方案：

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]

查看这张图像，以了解我是如何编写这段代码的：

​

​

Answer 2

如果您对完美的工作解决方案感兴趣，这就是我所写的：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的值。为了支持分数(任何有理数)，所有数字都是分数类型的。

我对一些边缘情况进行了硬编码，例如当pegs数= 2时。

Answer 3

我认为你的解是沿着正确的线，但不允许分数半径。

请注意，我们可以象征性地考虑您的算法，设置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(作为一个分数)，然后您可以重新检查，以确保没有中间半径为负值。