Google foobar gearing_up_for_destruction [英] Google foobar gearing_up_for_destruction

问题描述

我当时在做Google foobar挑战，但是在接下来的挑战中没有时间了，我想看看我做错了什么。

I was doing the google foobar challenge but ran out of time on the following challenge i am trying to see what i did wrong.

挑战

作为Lambda指挥官的私人助手，您已获得配置LAMBCHOP世界末日设备的轴向定向齿轮的任务。它应该非常简单-只需添加齿轮以创建适当的旋转比即可。但是问题是，由于LAMBCHOP的布局以及支撑它的梁和管道的复杂系统，将支撑齿轮的销钉固定在适当的位置。

As Commander Lambda's personal assistant, you've been assigned the task of configuring the LAMBCHOP doomsday device's axial orientation gears. It should be pretty simple - just add gears to create the appropriate rotation ratio. But the problem is, due to the layout of the LAMBCHOP and the complicated system of beams and pipes supporting it, the pegs that will support the gears are fixed in place.

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

The LAMBCHOP's engineers have given you lists identifying the placement of groups of pegs along various support beams. You need to place a gear on each peg (otherwise the gears will collide with unoccupied pegs). The engineers have plenty of gears in all different sizes stocked up, so you can choose gears of any size, from a radius of 1 on up. Your goal is to build a system where the last gear rotates at twice the rate (in revolutions per minute, or rpm) of the first gear, no matter the direction. Each gear (except the last) touches and turns the gear on the next peg to the right.

给出一个名为pegs的不同正整数列表，代表每个销钉的位置沿着支撑梁，写一个函数answer（pegs），如果有解决方案，则以最简单的形式返回两个正整数a和b的列表，分别表示第一齿轮半径的分子和分母，以实现目标半径等于a / b。 a / b之比应大于或等于1。并非所有支持配置都必须能够创建适当的旋转比，因此，如果无法完成任务，则功能answer（pegs）应返回列表[-1， -1]。

Given a list of distinct positive integers named pegs representing the location of each peg along the support beam, write a function answer(pegs) which, if there is a solution, returns a list of two positive integers a and b representing the numerator and denominator of the first gear's radius in its simplest form in order to achieve the goal above, such that radius = a/b. The ratio a/b should be greater than or equal to 1. Not all support configurations will necessarily be capable of creating the proper rotation ratio, so if the task is impossible, the function answer(pegs) should return the list [-1, -1].

例如，如果将钉子放置在[4，30，50]，则第一档的半径为12，第二档齿轮的半径为14，最后一个齿轮的半径为6。因此，最后一个齿轮的旋转速度是第一个齿轮的两倍。在这种情况下，钉子将为[4，30，50]，答案（pegs）应返回[12，1]。

For example, if the pegs are placed at [4, 30, 50], then the first gear could have a radius of 12, the second gear could have a radius of 14, and the last one a radius of 6. Thus, the last gear would rotate twice as fast as the first one. In this case, pegs would be [4, 30, 50] and answer(pegs) should return [12, 1].

列表钉的排序方式为升序，将包含至少2个且不超过20个不同的正整数，都在1到10000之间（包括1和10000）。

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

测试用例

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个测试用例现在已经没时间了，但是我很好奇什么是正确的解决方案

I could only get 6 test cases to pass I have now ran out of time but i am curious as to what the right solution was

推荐答案

这是python 2.7中的有效代码其中所有测试用例均由Google通过。这是我抓了一段时间纸之后想到的最好的解决方案：

Here's the working code in python 2.7 for which all the test cases were passed by Google. This is the best solution that I came up with after scratching papers 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.
    # 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]

有关此代码的用法，请参见以下图片：

See this image for how I came up with this code:

这篇关于Google foobar gearing_up_for_destruction的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！