Google Foo.Bar Challenge 2019. Часть 1

Не такое уж и сложное испытание.

В один из самых обычных дней разгребая почту наткнулся на письмо с любопытным заголовком “Google has a challenge for you”.

Google has a challenge for you

В отличие от многих историй (по крайней мере в тех что опубликованы), о том как участники попадают в челлендж ища решение своей программистской проблемы, мне пришло письмо потому что раннее годом, а может и больше, я откликнулся на странице челленджа о желании участвовать. Вероятно в то время я не представлял особого интереса для гугла. Однако 6 июня 2019 года алгоритмы решили осчастливить меня возможностью поучаствовать в этом челлендже. Итак, начнем. Правила я уже знал и если вкратце вам дается 5 уровней заданий, решив которые вы получите возможность пройти собеседование в Google.

Начало

Вас встречает терминал с предложением залогиниться с помощью своей учетной записи Google. После этого и начинается самое интересное. Успех! Вы сумели проникнуть в злую организацию Командующего Лямбды и, наконец, заработали себе позицию начального уровня как Миньон на ее космической станции. Отсюда, вы просто можете разрушить ее планы используя устройство конца света LAMBCHOP, чтобы уничтожить Планету Банни. Проблема в том, что миньоны — это самый низкий из минимумов в иерархии Лямбды. Лучше встряхнись и приступай к работе, иначе ты никогда не доберешься до вершины …

Небольшое отступление. В челлендже 5 уровней заданий. В первом уровне  —  1 задание, во втором  —  2, в третьем  —  3, в четвертом  —  2, в пятом  —  1. Каждое задание можно решить на любом из двух языков программирования: Java или Python. На каждое задание дается свой лимит времени на решение. Времени дается прям очень много (от двух часов до двух трех недель). Задания уже все решены, но выкладывать буду постепенно порциями, ибо их еще нужно описать.

Доступные команды:
cd dir — смена каталога
cat filename  —  выводит содержимое файл
deleteme —  удаляет все данные связанные с foobar челленджем
edit filename — открывает файл в редакторе
feedback —  можно оставить отзыв
less filename — выводит содержимое файла постранично
ls —  выводит список каталогов
request —  запрос следующего задания
status —  выводит прогресс челленджа
submit filename —  отправка итогового решения
verify filename —  запускает тесты

Level 1-1. Solar Doomsday

Кто бы мог догадаться? Устройство Судного Дня потребляет МНОГО энергии. Командующий Лямбда хочет дополнить ядро ​​реактора квантового антивещества LAMBCHOP солнечными батареями, и она поручила вам установить солнечные панели.

Из-за характера наружных панелей космической станции все ее солнечные панели должны быть квадратными. К счастью, у вас есть одна очень большая и плоская область материала, пара ножниц промышленной прочности и достаточно ленты MegaCorp (TM), чтобы собрать любой лишний материал панели в квадраты. Например, если бы у вас была общая площадь 12 квадратных ярдов материала, вы могли бы сделать одну квадратную панель размером 3х3 (общей площадью 9). Осталось бы 3 квадратных ярда, так что вы можете превратить их в три солнечных панели размером 1x1. Напишите функцию solution(area), которая принимает в качестве входных данных число, представляющую общую площадь солнечных панелей (от 1 до 1 000 000 включительно), и возвращает список областей наибольших квадратов, которые вы могли бы из них сделать, начиная с самых больших квадратов в первую очередь. Итак, следуя приведенному выше примеру, solution(12) вернет [9, 1, 1, 1].

К слову я frontend разработчик и с python не очень знаком, но давно было в планах опробовать. Вот и выдался случай.

Собственно решение очень простое: берем корень от числа, откидываем дробную часть, возводим в квадрат, результат записываем в массив, от числа отнимаем результат и продолжаем сначала пока от числа ничего не останется.

1
2
3
4
5
6
7
8
9

import math

def solution(area):
    result = []
    while area > 0:
        r = int(math.floor(math.sqrt(area)) ** 2)
        area = area - r
        result.append(r)
    return result

Level 2–1. Power Hungry

Космическая станция Командующего Лямбда ОГРОМНА. И огромные космические станции потребляет много энергии. Огромные космические станции с устройствами конца света потребляют еще больше энергии. Чтобы удовлетворить потребности станции в электроэнергии, Командующий Лямбда установил солнечные панели на внешней поверхности станции. Но станция находится в центре поля квантового потока квазара, которое наносит ущерб солнечным батареям. Вам и вашей команде приспешников поручено отремонтировать солнечные панели, но вы не захотите снимать все панели сразу, если сможете помочь, поскольку они помогают питать космическую станцию ​​и все остальное!

Вам необходимо выяснить, какие наборы панелей в любой конкретной группе вы можете отключить для восстановления, сохраняя при этом максимальный объем выходной мощности в каждой группе, и чтобы сделать ЭТО, вам сначала нужно выяснить, какова максимальная выходная мощность каждой из групп на самом деле. Напишите функцию solution(xs), которая берет список целых чисел, представляющих уровни выходной мощности каждой панели в группе, и возвращает максимальное произведение некоторого не пустого подмножества этих чисел. Так, например, если массив содержит панели с уровнями выходной мощности [2, -3, 1, 0, -5], то максимальная мощность будет найдена при подмножестве: xs [0] = 2, xs [1 ] = -3, xs [4] = -5, что дает произведение 2 * (- 3) * (- 5) = 30. Таким образом, решение ([2, -3,1,0, -5]) будет “ 30”.

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

Решение возможно не идеальное, но работает. Сортируем массив, берем отдельно все положительные числа и отдельно отрицательные. Берем четное количество негативных чисел, мы ведь знаем трюк с волновым стабилизатором панелей, чтобы получить максимальное положительное произведение. После этого складываем массивы положительных и отрицательных чисел вместе в один массив и перемножаем друг на друга.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def solution(xs):
    xs.sort()
    positive = filter(lambda x: x > 0, xs)
    negativeLength = len(filter(lambda x: x < 0, xs))/2 * 2
    negative = xs[0:negativeLength]
    result = negative + positive
    result = (0, reduce(lambda x,y: x*y, result, 1))[len(result) > 0]
    if len(xs) == 1:
        return str(xs[0])
    return str(result)

Level 2–2. Gearing Up for Destruction

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

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

Дан список различных натуральных чисел, названный pegs, представляющих местоположение каждого колышка вдоль опорной балки, напишите функцию solution(pegs), которая, если есть решение, возвращает список из двух положительных чисел а и b, представляющий числитель и знаменатель радиуса первой шестерни в его простейшей форме для достижения цели, указанной выше, такой, что радиус = a / b. Отношение a / b должно быть больше или равно 1. Не все конфигурации обязательно будут способны создать правильный коэффициент вращения, поэтому, если задача невозможна, функция solution(pegs) должно вернуть список [-1, -1].

Например, если колышки расположены в [4, 30, 50], то первая шестерня может иметь радиус 12, вторая шестерня может иметь радиус 14, а последняя — радиус 6. Таким образом, последняя передача будет вращаться в два раза быстрее первой. В этом случае колышки [4, 30, 50], а функция solution(pegs) должна вернуть [12, 1].

Список колышков будет отсортирован в порядке возрастания и будет содержать не менее 2 и не более 20 различных положительных целых чисел, все от 1 до 10000 включительно.

Тут уже немного посложнее, но все так же на уровне школьной математики. Главное придумать алгоритм решения. Если попытать разложить решения через дельты расстояний между колышками и отнять радиус предыдущей шестерни то получится следующее:

Немного поразмыслив можно собрать формулу:

Добавив еще немного фантазии можно получить формулу нахождения радиуса последней шестерни, а от него уже перемножением можно получить и радиус первой шестерни:

Собственно само решение:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from fractions import Fraction

def solution(pegs):
    pegsCount = len(pegs)
    if (not pegs) or pegsCount <= 1:
        return [-1, -1]
    sum1 = 0
    for i in xrange(0, pegsCount - 1):
        sum1 += (pegs[i + 1] - pegs[i]) * (-1)**i

    numerator = 2 * sum1
    denominator = (1,3)[pegsCount % 2 == 0]
    firstGear = Fraction(numerator / denominator).limit_denominator()

    # проверка промежуточных шестерней
    currentGear = firstGear
    for index in xrange(0, pegsCount - 2):
        distance = pegs[index+1] - pegs[index]
        nextGear = distance - currentGear
        if (currentGear < 1 or nextGear < 1):
            return [-1,-1]
        else:
            currentGear = nextGear

    return [firstGear.numerator, firstGear.denominator]

Сначала находится “сумма” дельт и вычисляется радиус первой шестерни, а дальше проходит проверка каждой шестерни начиная от первой, т.к. нужно удостовериться, так как возможны случаи что промежуточные шестерни не существуют в природе по своим параметрам.

Остальные задачи будут в последующих двух статьях.