Adventofcode2020 (10 частей серии)
Спойлер предупреждает Это пост с моими решениями и обучением с головоломки. Не продолжайте Чтение, если вы еще не пробовали головоломку самостоятельно.
Если вы хотите сделать головоломку, посетите adadeofcode.com/2020/day/5 Отказ
Мой язык программирования выбора – Python
И все примеры ниже находятся в Python.
Ключ обучения
- Двоичные номера
Эта головоломка делает игру с двоичными файлами. Хотя не явно, но звание двочков поможет с этой головоломкой.
Головоломка
Головоломка сегодня о трансформации сидений к идентификаторам безопасности разбиение бинарного пространства
Отказ Сиденья состоят из 10 букв. Первые 7 могут быть F
или Преступность
и последние 3 могут быть R
или L
. Буквы стоят на передней, обратно, слева, справа.
Первые 7 символов будут либо F или B; Они указывают ровно один из 128 рядов на плоскости (пронумерован 0-127). Каждое письмо говорит вам, в какую половину региона находится данное место. Начните со всего списка строк; Первая буква указывает, находится ли сиденье на передней части (от 0 до 63) или спиной (от 64 до 127). Следующее письмо указывает, какая половина этого региона находится в сиденье, и так далее, пока вы не останетесь с ровно одним рядом.
Последние три персонажа будут либо l или r; Они указывают ровно один из 8 столбцов сидений на плоскости (пронумерован 0-7). Тот же процесс, что и выше, продолжается снова, на этот раз только с тремя шагами. L означает сохранение нижней половины, в то время как R значит держать верхнюю половину.
Каждое место также имеет уникальный идентификатор сиденья: Умножьте строку на 8, затем добавьте столбец.
Пример ввода для некоторых мест:
FBFBBFFRLR BFBBBFBRLL FBFBBFBLLL BBBFFFBRRR FBFFFBFRRL BFFFFFFRLR
Часть 1.
Головоломка – найти самый высокий идентификатор места. Для этого нам нужно преобразовать имена сидений для идентификаторов и находить один с максимальным значением.
Головоломка дифференцирует первые семь и последние три буквы. Значение строки должна быть умножена на 8, а затем добавляется значение столбца. Это просто трюк, чтобы заставить головоломку кажутся сложнее.
Умножение значения строки с 8 такое же, как переключение его с 3 битами из-за 2 ^ 3
Отказ Добавление значения столбца, то просто объединяет две двоичные строки.
Мы можем рассматривать имя сиденья как двоичный, где B
и R
1 и другой 0.
def calc_id(seat): transformation = { 'F': '0', 'B': '1', 'L': '0', 'R': '1'} binary = "".join([transformation[x] for x in seat]) return int(binary,2) def part1(lines): ids = [calc_id(line) for line in lines] return max(ids) print "Part 1 solution: %d " % part1(lines)
Часть 2
Во-вторых, чтобы найти, какая пара идентификаторов 2 шагов друг от друга. Мы можем повторно использовать наш calc_id
функция выше.
def part2(lines): ids = [calc_id(line) for line in lines] for i in range(max(ids)): low = i - 1 high = i + 1 if low in ids and high in ids and i not in ids: return i print "Part 2 solution: %d " % part2(lines)
Альтернативные решения
Приведенное выше преобразование может быть решено с использованием оператора IF в понимании списка
def calc_id(seat): binary = "".join(['1' if x in ['B','R'] else '0' for x in seat]) return int(binary,2)
Или используя строку-замену.
def calc_id(seat): binary = seat.replace('B', '1').replace('R', '1').replace('F', '0').replace('L', '0') return int(binary,2)
Использование таблицы перевода в Python:
def calc_id(seat): translate_table = str.maketrans(dict(B="1", F="0", R="1", L="0")) return int(seat.translate(translate_table), 2)
Другая альтернатива – использовать двоичные расчеты для преобразования имен сидений на IDS. Вот пример:
def part1(lines): ids = [] for line in lines: current = 0 row = 64 for letter in line[:7]: if letter == 'B': current += row row = row >> 1 # Shift right 1 bit (same as dividing by 2) current = current << 3 # Shift left 3 bits (same as multiplying with 8) row = 4 for c in line[7:]: if c == 'R': current += row row = row >> 1 # Shift right 1 bit (same as dividing by 2) ids.append(current) return max(ids)
Мой начальный поезд мыслей о части 1 должен был найти максимальное значение, сортируя строки и вручную вычисляем двоичное число. Как B
до F
В алфавите вы можете сделать сортировку строк, чтобы получить максимальное значение строки, даже не преобразующее в двоичный. Хотя R
это после Л
и значение столбца будет изменено отсортировано. Я забыл обратный сортировку на значениях столбца, поэтому не удалось и изменил тактику. Угадай, что это было целью AOC для дифференциации колонны и значения строки.
Это будет полное решение для части 1:
sorted_data = sorted([ line.replace('R','B').replace('L','F') for line in lines ]) print sorted_data[0] # Step 2: Manually transform string to binary-string and then to # decimal with help of a online-calculator.
Последняя альтернатива: нечитаемый на один лайнер для части 1:
def part1(lines): return max([ int("".join([{ 'F': '0', 'B': '1', 'L': '0', 'R': '1'}[letter] or letter in line]), 2) for line in lines])
Советы Python
Преобразовать словари
Словари – это хороший способ преобразовать значения во время головоломок AOC. Как я сделал в части 1 выше:
transformation = { 'F': '0', 'B': '1', 'L': '0', 'R': '1' } transformation['F'] # Returns '0' transformation['B'] # Returns '1' transformation['L'] # Returns '0' transformation['R'] # Returns '1'
“” .join (список)
Чтобы объединить массив строк проще всего использовать функцию объединения. Функция соединения вызывается на строке, которая будет работать в качестве разделителя. Пустая строка затем присоединится к массивам-струнам без разделителя.
",".join['comma','seperated','string'] # => "comma,seperated,string" "".join['no','seperation','at','all'] # => "noseperationatall"
int (‘10101010’, 2)
Использование int ()
Мы можем конвертировать строки на цифры. Если мы хотим преобразовать двоичную Строка Мы должны установить базу на 2
Отказ
# Converting string using base 2 int('10111', 2) # outputs: 23 # Hexadecimal example: int('FF', 16) # outputs: 255
Макс (ARR)
В нашем решении мы получили массив чисел. Найти максимальное значение может быть заманчивым использовать для петли и maximum_value
Переменная. Макс ()
Функция в Python может принимать в массиве в качестве аргумента и делает это для нас.
max([6,2,3,8,3,9]) # outputs: 9
Спасибо за прочтение!
Я надеюсь, что эти решения были полезны для вас. Полный код можно найти по адресу: github.com/cnille/adventofcode/blob/master/2020/05.py.
Adventofcode2020 (10 частей серии)
Оригинал: “https://dev.to/cnille/advent-of-code-2020-day-05-1kg5”