谷歌 foobar gearing_up_for_destruction

Question

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

挑战

作为指挥官 Lambda 的私人助理，您被分配了配置 LAMBCHOP 末日装置的轴向齿轮的任务。它应该非常简单 - 只需添加齿轮即可创建合适的旋转比。但问题是，由于 LAMBCHOP 的布局以及支撑它的梁和管道的复杂系统，支撑齿轮的销钉固定到位。

LAMBCHOP 的工程师为您提供了列表，这些列表确定了钉组沿着各种支撑梁的位置。您需要在每个钉子上放置一个齿轮（否则齿轮会与未占用的钉子发生碰撞）。工程师们备有大量各种不同尺寸的齿轮，因此您可以选择任何尺寸的齿轮，从半径 1 开始。您的目标是构建一个系统，无论方向如何，最后一个齿轮的旋转速度是第一个齿轮的两倍（以每分钟转数或 rpm 为单位）。每个齿轮（最后一个齿轮除外）接触并向右转动下一个挂钩上的齿轮。

给定一个名为 pegs 的不同正整数列表，表示每个 pegs 沿支撑梁的位置，编写一个函数 answer(pegs) 如果有解，则返回两个正整数 a 和 b 的列表，分别表示分子和分母为了实现上述目标，以最简单的形式计算第一个齿轮的半径，使得半径 = a/b。比率 a/b 应大于或等于 1。并非所有支撑配置都一定能够创建适当的旋转比率，因此如果无法完成任务，函数 answer(pegs) 应返回列表 [-1, -1]。

例如，如果钉子放置在 [4, 30, 50]，那么第一个齿轮的半径可以是 12，第二个齿轮的半径可以是 14，最后一个齿轮的半径可以是 6。因此，最后一个齿轮的旋转速度是第一个齿轮的两倍。在这种情况下，pegs 将是 [4, 30, 50] 并且 answer(pegs) 应该返回 [12, 1]。

列表 pegs 将按升序排序，并将包含至少 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 个测试用例通过我现在已经没时间了，但我很好奇正确的解决方案是什么

原文由 Rajdeep Dosanjh 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这是 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.
    # 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]

请参阅此图片了解我是如何想出此代码的：

原文由 Suresh Lamichhane 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 的值。为了支持分数（任何有理数），所有数字都是 Fraction 类型。

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

原文由 1lann 发布，翻译遵循 CC BY-SA 3.0 许可协议