asmoth.me
Google Foo.Bar Challenge 2019. Часть 2
2019-09-04
Google Foo.Bar Challenge 2019. Часть 2

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

Разбор задач третьего уровня
📅 ⏱ Читать около 8 минут
GoogleЧелленджPython

Продолжаем разбирать задачи челленджа

Это уже вторая часть и она немного запоздала, т.к. я отвлекся на статью о конкурсе от Пикабу. В этой части будет разбор трех задач третьего уровня, а в следующей части все оставшиеся задачи. Для тех кто пропустил: Google Foo.Bar Challenge 2019. Часть 1

Приступим в разбору!

Level 3–1. Find the Access Codes

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

К счастью, теперь, когда вы являетесь личным помощником Командующей Лямбды, она призналась вам, что она сделала все коды доступа “счастливыми тройняшками”, чтобы помочь ей лучше найти их в списках. “Счастливые тройняшки” — это сочетание (x, y, z), где x делит y и y делит z, например (1, 2, 4). С помощью этой информации вы сможете определить, какой список содержит количество кодов доступа, соответствующее количеству замков на двери, когда будете готовы войти (например, если есть 5 паролей, вам понадобится список с 5 “счастливыми тройными” кодами доступа).

Напишите функцию solution(l), которое принимает список положительных целых чисел l и подсчитывает число “счастливых тройняшек” (li, lj, lk), где индексы списка соответствуют требованию i < j < k. Длина l от 2 до 2000 включительно. Элементы l находятся в диапазоне от 1 до 99999999 включительно. Ответ помещается в знаковое32-битное целое число. Некоторые из списков специально сгенерированы без кодов доступа, чтобы запутать шпионов, поэтому если тройняшек не найдено, верните 0.

Например, [1, 2, 3, 4, 5, 6] содержит тройняшки: [1, 2, 4], [1, 2, 6], [1, 3, 6], в результате чего ответ получается 3.

Первый вариант который я написал это был рекурсивный поиск по остатку массива на предмет кратных чисел и составление “тройняшек”, алгоритм работал, но на больших данных это было медленно.

Второй вариант уже намного лучше. При прохождении по массиву мы берем число как y и проходимся в обе стороны сравнивая потенциальные x и z по условию, попутно считая их. Получившееся количество x умножаем на количество z и мы получим количество комбинаций при данном y. Таким образом пройдясь по массиву мы посчитаем количество всех комбинаций без надобности создания массивов и без рекурсии.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def solution(list):
    result = 0
    length = len(list)
    for i in range(1, length - 1):
        countX = 0
        countZ = 0
        for j in range(0, i):
            if float(list[i])/list[j] == float(list[i])//list[j]:
            countX += 1
        for k in range(i + 1, length):
            if float(list[k])/list[i] == float(list[k])//list[i]:
            countZ += 1
        result += countX * countZ
    return result

print solution([1, 2, 3, 4, 5, 6])

Level 3–2. Fuel Injection Perfection

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

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

Механизмы контроля топлива функционируют в трех направлениях:

  1. Добавить одну упаковку топлива
  2. Удалить одну упаковку
  3. Разделить кучу упаковок топлива на 2 (из-за разрушительной энергии, высвобождающейся при разрезании гранул квантовой антиматерии пополам, органы безопасности позволят это сделать только при четном количестве упаковок).

Напишите функцию под названием solution(n), которая принимает строкой целое положительное число и возвращает минимальное количество операций, необходимое для преобразования количества упаковок до одной. Прибор может отображать только число до 309 знаков в длину, поэтому количество упаковок не будет превышать, чем вы можете выразить в таком количестве цифр.

Пример:
solution(4) возвращает 2: 4 -> 2 -> 1
solution(15) возвращает 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1

Будем считать количество операций в бесконечном цикле пока не останется одна упаковка. Если количество упаковок n делится на 2, то мы делим пополам. В противном случае, если n равно 3 или остаток от деления на 4 равно 1, то мы отнимаем одну упаковку, если нет то добавляем одну. В конце итерации цикла добавляем к количеству операций count единицу.

Почему второе условие проверяет именно на 3 и остаток от деления на 4 равном 1? Все просто. Разберем пример:

Даны числа от 1 до 14: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Если из них выделить числа кратные 4 и посмотреть на числа между них то можно увидеть, что например числу 5 выгоднее преобразоваться в 4 чем в 6, как раз остаток от деления на 4 равен 1. Число 6 делится на 2 и так далее. Семерке без разницы, оба пути до конечного результата одинаковые по длине. Всем числам перед числом кратному 4 выгодно прибавлять единицу, кроме 3 на этом примере все наоборот. Можете сами все расписать на бумаге и будет понятно.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def solution(n):
    n = int(n)
    count = 0
    while n != 1:
        if n % 2 == 0:
            n /= 2
        else:
            if n == 3 or n % 4 == 1:
                n -= 1
            else:
                n += 1
        count += 1
    return count

Level 3–3. Prepare the Bunnies’ Escape

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

У вас есть карты частей космической станции, каждая из которых начинается с выхода из тюрьмы и заканчивается у двери спасательной капсулы. Карта представлена в виде матрицы нулей и единиц, где нули — это проходное пространство, а единицы — непроходимые стены. Дверь из тюрьмы сверху слева (0,0), а дверь в спасательную капсулу внизу справа (w-1, h-1).

Напишите функциюю solution(map), которое генерирует кратчайший путь от тюремной двери до спасательной капсулы, где вам разрешено убрать одну стену в рамках ваших планов реконструкции. Длина пути — это общее количество узлов, через которые вы проходите, с учетом как входных, так и выходных узлов. Начальное и конечное положения всегда являются допустимыми (нулями). Карта всегда будет разрешима, хотя вам может понадобиться удалить стену, а может и не понадобиться. Высота и ширина карты может быть от 2 до 20. Перемещения могут осуществляться только в кардинальных направлениях; диагональные перемещения не допускаются.

Здесь берем матрицу и клонируем, удаляем одну стенку и пробуем решить и так пока не переберем все варианты, при этом запоминая длину самого короткого пути.

Заполняем в цикле матрицу пока не достигнем конца или не сможем пройти дальше. Если достигли конца то запоминаем число в ячейке выхода из лабиринта, в ней находится цифра отображающая количество шагов.

Вариант не самый идеальный, BFS (Breadth-first search, поиск в ширину) будет работать намного быстрее.

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Maze:
    def __init__(self, matrix):
        self.matrix = matrix
        self.width = len(matrix[0])
        self.height = len(matrix)

    def getMinDistance(self):
        result = []
        walls = []
        for y, line in enumerate(self.matrix):
            for x, cell in enumerate(line):
                if cell == 1:
                    walls.append({'x': x, 'y': y})
                    self.matrix[y][x] = '.'
        for index, wall in enumerate(walls):
            clonedMatrix = map(lambda x: [] + x, self.matrix)
            clonedMatrix[wall['y']][wall['x']] = 0
            result.append(self.solveWithoutWall(clonedMatrix))
        result.sort()
        return result[0]

    def getCellValue(self, matrix, x, y):
        cell = Ellipsis
        try:
            cell = matrix[y][x]
        except:
            cell = Ellipsis
        if x < 0:
            cell = Ellipsis
        if y < 0:
            cell = Ellipsis
        if cell == '.':
            cell = Ellipsis
        return (cell, Ellipsis)[cell == 0]
  
    def solveWithoutWall(self, matrix):
        matrix[0][0] = 1
        while (matrix[self.height - 1][self.width - 1] == 0):
            placed = 0
            for y, line in enumerate(matrix):
                for x, cell in enumerate(line):
                    if cell == 0:
                        up = self.getCellValue(matrix, x, y - 1)
                        down = self.getCellValue(matrix, x, y + 1)
                        left = self.getCellValue(matrix, x - 1, y)
                        right = self.getCellValue(matrix, x + 1, y)
                        minimum = min(min(up, down), min(left, right))
                        if minimum != Ellipsis:
                            matrix[y][x] = minimum + 1
                            placed = 1
            if placed == 0:
                break
        end = matrix[self.height - 1][self.width - 1]

    return (end, Ellipsis)[end == 0]

def solution(matrix):
    station = Maze(matrix)
    return station.getMinDistance()

Ну чтож осталось написать разбор последних трех задач этого челленджа. Есть пара инвайт кодов, есть желающие попробовать?