Рубрики
Без рубрики

Advent of Code 2020 – Обзор решений

С 2018 года, каждый декабрь, я стараюсь пройти через Advent of Code, раскрыт набор из 25 головоломок … Tagged with AdventofCode, Python.

Появление кода (серия 2 частей)

С 2018 года, каждый декабрь, я Попробуйте Пробирайся через Появление кода Набор из 25 головоломок раскрывается каждый день в этом месяце, до Рождества. Это существует с 2015 года (я также пытался поработать над более ранними годами, проверить все мои решения в моем появлении Code Repo ).

Краткое описание со своей страницы:

Advent of Code – это календарь Адвента небольших головоломок программирования для различных наборов навыков и уровней навыков, которые можно решить на любом языке программирования, который вам нравится. Люди используют их в качестве конкурса скорости, подготовки к собеседованию, подготовку компании, университетской курсовой работы, практики или бросают вызов друг другу.

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

В основном я буду использовать Python для решений. Это язык, в котором я наиболее опытный, и в этом году он доказал, что у него есть много отличных инструментов, чтобы получить более чистые результаты.

Мы на 6 -й день на момент написания статьи, поэтому я прохожу каждый день в этом посте, а затем обновляюсь на неделю. Следуй со мной!

День 1: Ремонт отчета (ссылка)

Для начала: я очень люблю истории каждый год. Каждый год главный герой – это эльф, которому поручено Сохранение Рождества Анкет В этом году мы собираемся в отпуск. Рождество безопасно! Несколько хороших новостей в этом году, наконец:)

В первую часть 1-го дня нам поручено обработать отчет о расходах-список чисел, и мы должны найти две записи, которые составляют до 2020 года, и умножить эти цифры вместе. Вход был очень коротким, чтобы я мог пойти с подходом «грубой силы». Для каждого номера снова переходите через список и найдите тот, который добавляет до 2020 года. Я знал простой трюк, чтобы пройти один раз в список: использование набора в качестве структуры данных для хранения чисел, я могу найти элемент в постоянное время. Для каждого номера мне нужно проверить, есть ли 2020 - номер в списке!

def part_one(report: List[int]):
    report_set = set(report)
    for number in report:
        if 2020 - number in report_set:
            return number * (2020 - number)

Вторая часть представляет аналогичную головоломку, но теперь нам нужно найти 3 числа, которые составляют до 2020 года. В этот момент я вспомнил о Python’s itertools.combinations Анкет Это возвращает последствия списка с данным размером. Я могу использовать его также для части 1, поэтому я только что написал общее решение:

from functools import reduce
from itertools import combinations

def solve_with_combinations(report, n):
    for test in combinations(report, n):
        if sum(test) == 2020:
            return reduce(mul, test)

def part_one_combinations():
    solve_with_combinations(report, 2)

def part_one_combinations():
    solve_with_combinations(report, 3)

Python будет генерировать комбинации в сложности лучше, чем O (n^2) или O (n^3), но я обнаружил, что могу получить O (n^2) для части второй. Решение включает в себя сортировку списка заранее, а затем использование двухточковой техники: для каждого номера в списке я держу указатель на следующий номер и последний из списка. Если сумма превышает 2020 года, я уменьшаю конечный указатель, чтобы уменьшить сумму. Если это менее 2020 года, я увеличиваю первый указатель, чтобы получить большую сумму. Я повторяю его для каждого элемента, пока не найду все 3 номера, которые соответствуют требованиям. Я должен был сделать немного исследований, так что вот Источник Анкет

def best_performance_part_two(report):
    n = len(report)
    for i in range(n):
        left = i + 1
        right = n - 1
        while left < right:
            result = report[i] + report[left] + report[right]
            if result == 2020:
                return report[i] * report[left] * report[right]
            if result < 2020:
                left += 1
            else:
                right -= 1

best_performance_part_two(sorted(report))

День 2: Философия пароля (ссылка)

На 2 -й день нам поручено обработать список паролей и проверить, следуют ли они установленной политике. Каждая строка ввода дает политику и пароль для проверки. Политика паролей указывает на самое низкое и самое большое количество раз, когда данный буквы должны появиться, чтобы пароль был действительным. Допустимый ввод выглядит так:

1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc

Для этого я пошел с Регулярное выражение проанализировать каждую строку и Коллекции. Счетчик Чтобы увидеть, имеет ли букву правильный счет. Не много, чтобы улучшить там.

import re
from collections import Counter

def part_one(passwords: List[str]):
    valid = 0

    expression = re.compile(r"(\d+)-(\d+) (.): (.*)")
    for password in passwords:
        if match := expression.match(password):
            min_, max_, letter, password = match.groups()
            count = Counter(password)[letter]
            if count >= int(min_) and count <= int(max_):
                valid += 1
    return valid

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

def part_two(passwords: List[str]):
    valid = 0

    expression = re.compile(r"(\d+)-(\d+) (.): (.*)")
    for password in passwords:
        if match := expression.match(password):
            pos_1, pos_2, letter, password = match.groups()
            letters = {password[int(pos_1) - 1], password[int(pos_2) - 1]}
            if len(letters) == 2 and letter in letters:
                valid += 1
    return valid

День 3: Toboggan Truectory (ссылка)

В этом вход головоломки – это раздел «карты», где Анкет представляют пустые пространства и # Представляет дерево, представляющее географию области, которую вы собираетесь скользить с Toboggan Анкет Вы хотите найти наклон на карте, где вы находите меньшее количество деревьев (рулевое управление тяжело в этой области!).

Карта – это только раздел всей географии: шаблон повторяется вправо «много раз. ” Это был намек на то, что может быть способ выяснить, где на карте вы находитесь без «склеивания» этих разделов вместе.

Часть 1 спрашивает, сколько там деревьев, если вы пойдете по склону Справа 3, вниз 1 , что означает, что вы будете идти 3 квадратами вправо, затем один вниз. Карта имеет гораздо больше рядов, чем столбцы, так что это означает, что вы окажетесь в этой «расширенной области». «Как мы можем прочитать эту карту и подсчитать деревья без дублирования линий, чтобы выяснить, как выглядят эти скрытые области? Решение заключается в отслеживании вашей позиции, и каждый раз, когда ваши координаты приземляются за пределы размера линии, вы выясняете новый индекс, получив модулю вашего положения и размер линии.

Я сделал часть 1 общей для любого склона, думая о том, что мне нужно было сделать это для большего количества случаев; Вот решение, которое я приземлился:

from itertools import count

def count_trees(right, down):
    # [`itertools.count`][count] yields numbers separated by `step`.
    # Think range() but unbound. Really nice for this case!
    counter = count(step=right)
    total_trees = 0
    for i, line in enumerate(read_file()):
        # line is something like ".....#.##......#..##..........#"
        if i % down != 0:
            # If going down more than once at a time, go straight to
            # the lines that are multiple of `down`.
            continue
        line = line.strip()
        # next counter will return the steps I'm walking right.
        # If I land after the end of the line, the modulo
        # will return an index that will represent what's in the
        # square out of bounds.
        position = next(counter) % len(line)
        # this is a nice trick with python booleans. They are actually an
        # extension of integers, and False == 1 :)
        total_trees += line[position] == "#"
    return total_trees

Для части 2 было просто попросило проверить количество деревьев на наличие других склонов (в том числе один, где вы пойдете по большему количеству двух рядов). Я только что передал их функции выше и умножил значения.

from functools import reduce
from operator import mul

vals = [
    count_trees(1, 1),
    count_trees(3, 1),
    count_trees(5, 1),
    count_trees(7, 1),
    count_trees(1, 2),
]
print(reduce(mul, vals))

День 4: Обработка паспорта (ссылка)

Этот чувствовал себя как работа. Нам поручено проверить паспорта и проверить, есть ли у них необходимые поля. Поля – это общий паспорт (дата рождения, дата выпуска, страна и т. Д.). Страна не требуется, потому что «Страна Северного полюса не выдается страной».

Я использовал [DataClasses] [DataClasses] и прочитал входной файл, передавая карту клавиш-значения результатов в автоматическое конструктор. Если какой -либо из необходимых аргументов отсутствовал, конструктор поднял бы исключение, которое я поймаю, и пропустил паспорт как недействительный.

@dataclass
class Passport:
    byr: str  # Birth Year
    iyr: str  # Issue Year
    eyr: str  # Expiration Year
    hgt: str  # Height
    hcl: str  # Hair Color
    ecl: str  # Eye Color
    pid: str  # Passport ID
    cid: str = ""  # country. The assignment at the class definition will make this field not required

def part_1():
    passports = []
    p = {}
    for line in read_file():
        if not line.strip():
            try:
                passports.append(Passport(**p))
            except TypeError:
                continue
            finally:
                p = {}
            continue
        values = line.strip().split(" ")
        for value in values:
            k, v = value.split(":")
            p[k] = v
    # last line
    passports.append(Passport(**p))
    return passports

first_pass_valid = part_1()
print(len(first_pass_valid))

Часть 2 расширяет проверку. Итак, я добавил подтвердить Метод для класса данных паспорта и призвал к действительным паспортам в части 1.

@dataclass
class Passport:
    # fields...

    def validate(self):
        assert 1920 <= int(self.byr) <= 2002
        assert 2010 <= int(self.iyr) <= 2020
        assert 2020 <= int(self.eyr) <= 2030
        h, unit = size_re.match(self.hgt).groups()
        if unit == "cm":
            assert 150 <= int(h) <= 193
        else:
            assert 59 <= int(h) <= 76
        assert hair_re.match(self.hcl)
        assert self.ecl in ["amb", "blu", "brn", "gry", "grn", "hzl", "oth"]
        assert pid_re.match(self.pid)

# ... part 1

valid = 0
for passport in first_pass_valid:
    try:
        passport.validate()
        valid += 1
    except Exception:
        print(passport)
        continue

print(valid)

Я чуть не пропустил это. Это слишком похоже на мою повседневную работу (проверка форм для бизнес-логики и сохранения-это хлеб и масло веб-приложений в настоящее время).

День 5: Бинарный посадка

Это было весело. Я должен был заметить по имени сегодняшней головоломки, было более простое решение, чем почти написание дословно правила головоломки. Сегодня мы просматриваем список посадочных талонов и «декодируя» идентификаторы сидений из кодов проходов. Со времен дневных инструкций «сиденье может быть указано, например, fbfbbffrlr, где f означает« фронт », B означает« назад », L означает« левый », а R означает« справа ». Это определяет бинарное пространство распределения. Затем я продолжил писать алгоритм точно так же, как описанная головоломка. Часть 1 просит отправить самый высокий идентификатор места. Итак, вот реализация:

def partition(code: str, count: int, lower_ch: str, upper_ch: str) -> int:
    left = 0
    right = 2 ** count

    for i in range(count):  # for each char in the code
        ch = code[i]
        mid = (right + left) // 2  # split the current length in two groups
        if ch == lower_ch:
            # if the char represent the "lower half" of the current region, move
            # the right pointer to the middle
            right = mid
        elif ch == upper_ch:
            # else, move the left pointer to the middle
            left = mid
    # you'll either end with the same number or there will be a difference
    # of 1. Return the minimum.
    return min(left, right)

def part_1():
    max_id = 0
    for code in read_file():
        # First 7 letters represent the row
        row = partition(code[:7], 7, "F", "B")
        # last 3 represent the colums
        col = partition(code[-3:], 3, "L", "R")
        seat_id = row * 8 + col
        if seat_id > max_id:
            max_id = seat_id
    return max_id

При обсуждении с коллегами о решениях 5-го дня один из них отметил, что правила были лишь шагами по преобразованию двоичного числа в свое представление базы 10, где являются «f»/«B» и «L»/«R» 0 “и” 1 “. int Конструктор в Python может отливать строки чисел в любой базе, которую вы можете установить в качестве второго параметра. Так int ("1001", 2) вернется 9 Анкет

def to_int(code, zero, one):
    code = code.replace(zero, "0").replace(one, "1")
    return int(code, base=2)

# ...
    for code in read_file():
        row = to_int(code[:7], "F", "B")
        col = to_int(code[-3:], "L", "R")
        seat_id = row * 8 + col

Аккуратный.

Для части 2 мы хотим найти единственный идентификатор пропущенного места в списке (персонаж истории потерял свой посадочный талон!). Я не мог на всю жизнь, выяснить, как это сделать. Головоломка утверждает, что задняя часть и передняя часть самолета пусты, поэтому вам нужно найти пустое место в «Середине». «Я пошел с первой идеей в моей голове: давайте визуализируем самолет после заполнения всех мест, распечатайте колонку и строку и найдем идентификатор сиденья.

def part_2_visualization():
    """
    Will print something like this with my input
    ...
    086 -> ['#', '#', '#', '#', '#', '#', '#', '#']
    087 -> ['#', '#', '#', '#', '#', '#', '#', '#']
    088 -> ['#', '.', '#', '#', '#', '#', '#', '#']
    089 -> ['#', '#', '#', '#', '#', '#', '#', '#']
    090 -> ['#', '#', '#', '#', '#', '#', '#', '#']
    ...
    Meaning the free seat is in row 88, col 1.
    """
    aircraft = [["." for _ in range(8)] for _ in range(128)]
    for code in read_file():
        row = partition(code[:7], 7, "F", "B")
        col = partition(code[-3:], 3, "L", "R")
        aircraft[row][col] = "#"
    for i, x in enumerate(aircraft):
        print("{:0>3} -> {}".format(i, x))

Опять же, разговоры с коллегами заставили меня понять программное решение. Дается, что самолет заполнен. Формула ID – ряд * 8 + col Анкет Самолет имеет 8 столбцов, поэтому места в одном и том же ряду будут делиться первой «частью» этого уравнения, причем «COL» делает эти идентификаторы карты для всех целых чисел от 0 до 1024 (127 * 8 + 8). Со всеми рассчитанными идентификаторами мне нужно найти разницу между идентификаторами, которые у меня есть, и набором всех возможных идентификаторов.

def part_2_for_real_now():
    ids = set()
    for code in read_file():
        row = partition(code[:7], 7, "F", "B")
        col = partition(code[-3:], 3, "L", "R")

        ids.add(row * 8 + col)
    # all possible IDs are between the first and last
    # non-empty seat
    seat = set(range(min(ids), max(ids))) - ids
    return seat.pop()

День 6: Пользовательские таможни

Этот день был упражнением на Python’s Счетчик структура данных. Ввод представляет вопросы (отмеченные от A до z), люди ответили «да» в таможенную форму объявления. Для части 1 мы заинтересованы в том, чтобы найти, сколько вопросов в группе людей ответил «да». Каждая строка является человеком, а пустая линия отделяет группы.

Ах! Кроме того, с этого дня я перестал отделять головоломки по частям. Я напишу решения и разделю их на функции повторных битов для лучшей организации.

Поэтому я просто передаю каждую строку Счетчик экземпляр и добавьте их для каждой группы. Счетчик реализует дополнение SO Счетчик ('abc') + counter ('cde') будет эквивалентен словарем {'c': 2, 'a': 1, 'b': 1, 'd': 1, 'e': 1} (не ключ c имеет значение 2 , потому что они появляются в обеих сторонах дополнения).

groups = []
current_group = Counter()
group_size = 0
for line in read_file():
    if line:
        current_group += Counter(line)
        group_size += 1
    else:
        groups.append([current_group, group_size])
        current_group = Counter()
        group_size = 0

print("--- part 1 ---")
# the "length" of each group counter is the number of unique answers for that group.
# I could use a `set` here: the actual count is not important for part 1
print(sum(map(lambda c: len(c[0]), groups)))

Используя Счетчик S сделал часть 2 супер легкой. Мы узнаем, что не хотим считать, сколько вопросов кто -нибудь ответил «да», но те, где все В группе ответили да.

Для каждой группы, захваченной в части 1, я называю mest_common () в стойке, которая вернет каждую букву, отсортированную по своему подсчету в порядке уменьшения. Если счет такой же, как размер группы, это письмо представляет вопрос, на который все люди ответили «да».

total_count = 0
for group, count in groups:
    for _, ans_count in group.most_common():
        if ans_count == count:
            total_count += 1
        else:
            break

print(total_count)

Появление кода (серия 2 частей)

Оригинал: “https://dev.to/rbusquet/advent-of-code-2020-solutions-review-11o0”