Część 1

W dzisiejszym zadaniu mamy na wejściu zbiór kluczy i zamków, naszym zadaniem jest obliczyć ile w sumie kluczy pasuje do ilu zamków. Input wygląda w ten sposób:

#####
##.##
.#.##
...##
...#.
...#.
.....

.....
#....
#....
#...#
#.#.#
#.###
#####

.....
.....
#.#..
###..
###.#
###.#
#####

Zamki to te macierze które w górnym rzędzie mają same #, a klucze mają w dolnym rzędzie same #, klucz mieści się w zamku jeśli ilość # w każdej kolumnie, nie przekracza wysokości kolumny. Właściwie w treści zadania mamy podane całe jego rozwiązanie, widać że autor nie chciał jak najbardziej ułatwić nam dzisiejsze zadanie.

Rozwiązanie

Parsowanie wejścia

import sys

data = sys.stdin.read().strip().split("\n\n")

WIDTH = 5
HEIGHT = 7

# zbieramy klucze i zamki do oddzielnych list
keys, locks = [], []
for d in data:
    arr = d.strip().split("\n")
    # counts to krotka z ilością # w każdej kolumnie, np. (1, 0, 3, 4, 1)
    counts = tuple(
        len(list(filter(lambda a: a == "#", col))) for col in list(zip(*arr))
    )
    if arr[0][0] == "#": # jeśli w pierwszym rzędzie jest # to to zamek
        locks.append(counts)
    else:
        keys.append(counts)

W powyższym kodzie użyłem ciekawego tricka: list(zip(*arr)), który w prosty sposób pozwala na transpozycję dwuwymiarowej listy w pythonie.

Obliczenie rozwiązaina

Iterujemy po produkcie kartezjańskim kluczy i zamków, sumujemy ilość pól # w każdej kolumnie i jeśli liczba przekroczy wyosość kolumny (7) to pomijamy tę parę klucz-zamek.

result = 0
for key, lock in itertools.product(keys, locks):
    if all(key[i] + lock[i] <= HEIGHT for i in range(len(lock))):
        result += 1

print(result)

Podsumowanie

W tym roku udało mi się pierwszy razy zrobić wszystkie zadania z Advent of Code, było to ciekawe doświadczenie, tym bardziej że dokumentowałem wszystko na blogu. Zadania były bardzo ciekawe, poziom trudności osiągnął szczyt w dniu 17 i 21.

Na następny rok na pewno warto ogarnąć sobie parę bibliotek do często powtarzających się problemów:

• networkx pozwala na znajdywanie rozwiązań problemów z grafami (np. shortest-path, clique…)
• z3 - pozwala na rozwiązywanie różnych równań
• stworzenie prostej biblioteki do parsowania wejścia
• prosta biblioteka do pracy na 2d gridach

A może warto spóbować swoich sił w innym języku programowania? Zobaczę na co będę miał ochotę, pisanie pierwszych kilku części w awku było odświeżającym doświaczeniem ale na dłuższą metę męczącym, być może jakbym wybrał jakiś bardziej rozwinięty język jak Rust, Go albo C++ to byłoby łatwiej.

Dzięki za przeczytanie moich notatek z tegorocznej edycji Advent of Code, mam nadzieję że były pomocne i ciekawe. Do zobaczenia za rok!