Google foobar gearing_up_for_destruction

Question

我正在做谷歌foobar挑战,但在以下挑战时没时间我试图看到我做错了什么.

挑战

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

LAMBCHOP的工程师为您提供了一系列清单,用于识别沿各种支撑梁的桩柱放置位置.您需要在每个挂钉上放置一个齿轮(否则齿轮会与未占用的挂钉碰撞).工程师拥有大量不同尺寸的齿轮,因此您可以选择任意尺寸的齿轮,从半径为1.您的目标是建立一个系统,其中最后一个齿轮以第一档的速率(每分钟转数或转速)的两倍旋转,无论方向如何.每个齿轮(除了最后一个齿轮)接触并转动下一个挂钩的齿轮到右边.

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

例如,如果钉子放置在[4,30,50],那么第一个齿轮的半径可以是12,第二个齿轮的半径可以是14,最后一个齿轮的半径可以是6.因此,最后一个齿轮的旋转速度是第一个齿轮的两倍.在这种情况下,钉子将是[4,30,50]并且答案(钉子)应该返回[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

这是python 2.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.

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

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