Google foobar gearing_up_for_destruction

Я делал вызов google foobar, но у меня не хватило времени на следующий вызов. Я пытаюсь понять, что я сделал не так.

Вызов

В качестве личного помощника командира Лямбды вам была назначена задача настройки устройств осевой ориентации устройства Loms. Это должно быть довольно просто – просто добавьте шестерни, чтобы создать соответствующий коэффициент вращения. Но проблема в том, что из-за расположения LAMBCHOP и сложной системы балок и труб, поддерживающих его, привязки, которые будут поддерживать шестерни, фиксируются на месте.

Инженеры LAMBCHOP дали вам списки, идентифицирующие размещение групп колышек вдоль различных опорных балок. Вам нужно поместить шестерню на каждый штифт (иначе шестерни будут сталкиваться с незанятыми штифтами). Инженеры имеют множество передач в разных размерах, поэтому вы можете выбрать шестерни любого размера, начиная с радиуса 1 дюйма. Ваша цель – построить систему, в которой последняя шестерня вращается с удвоенной скоростью (в оборотах в минуту или оборотах) первой передачи независимо от направления. Каждая передача (кроме последней) касается и поворачивает шестерню на следующей привязке вправо.

Учитывая список различных натуральных чисел, названных колышки, представляющих местоположение каждого колышка вдоль опорной балки, написать функцию ответ (колышки), которые, если есть решение, возвращает список из двух положительных чисел а и Ь, представляющий числитель и знаменатель радиуса первой шестерни в его простейшей форме для достижения цели выше, такой, что радиус = a / b. Отношение a / b должно быть больше или равно 1. Не все конфигурации поддержки обязательно будут способны создавать правильный коэффициент вращения, поэтому, если задача невозможна, ответ функции (колышки) должен возвращать список [-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 тестовых случаев. У меня теперь закончилось время, но мне интересно, какое правильное решение было

3 Solutions collect form web for “Google foobar gearing_up_for_destruction”

Вот рабочий код в 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] 

Посмотрите это изображение, как я придумал этот код:

Образ

Я думаю, что ваше решение идет по правильной линии, но не допускает дробного радиуса.

Обратите внимание, что мы можем рассматривать ваш алгоритм символически, устанавливая g[0]=x , а затем вычисляя все значения g[j] в терминах x . Оказывается, что каждый 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 (как долю), которое затем можно перепроверить, чтобы убедиться, что промежуточный радиус не отрицательный.

Если вас интересует идеальное рабочее решение, вот что я написал: 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.

  • Каков наиболее эффективный способ найти факторы в списке?
  • алгоритм сокращения минимума karger в python 2.7
  • Определение того, как сложно вводить слово на клавиатуре QWERTY
  • Быстрый способ разместить бит для головоломки
  • Перемешать и повторно перетасовать список в python?
  • Эффективный расчет рядов Фибоначчи
  • Как ускорить выполнение кода для решения проблемы удаления битов
  • Самый короткий Sudoku Solver в Python - Как это работает?
  •  
    Interesting Posts for Van-Lav

    python, используя __init__ vs, просто определяя переменные в классе – любая разница?

    Программа, которая открывает текстовый файл, подсчитывает количество слов и сообщает верхние N слов, упорядоченных по количеству раз, когда они появляются в файле?

    декоратор для установки атрибутов функции

    Многопроцессный демона, не заканчивающийся на родительском выходе

    Начальный вопрос: возврат логического значения из функции в Python

    Импорт __module__ python: почему символы подчеркивания?

    Если файл Dill слишком велик для ОЗУ, есть другой способ его загрузки

    Как кодировать ('ascii', 'ignore') бросать UnicodeDecodeError?

    неверный литерал для int () с базой 10 в представлении listAPI django rest framework

    Хранение словарей Python

    Декораторы и методы python

    Как нарисовать линию ширины двух направлений в matplotlib

    Как проверить последнюю цифру номера

    Панды: разница между точкой поворота и поворотным столом. Почему работает только pivot_table?

    Получить последнюю запись в django в нескольких измерениях

    Python - лучший язык программирования в мире.