Dzisiejsze zadanie polegało na znalezieniu węzłów fali (antinodes) generowanych przez anteny o różnych częstotliwościach. Brzmi to skomplikowanie ale w praktyce zadanie nie było trudne. Rozwiązałem je w miarę szybko w Pythonie.

Treść

W mieście (dwuwymiarowa plansza), zanjdują się anteny o różnych częstotliwościach, oznacznanych przez różne znaki alfanumeryczne. Węzły fali pojawiają się w punktach które są w lini prostej na której leżą dwie antenty o tej samej częstotliwości ale tak że jedna z nich jest dwa razy dalej od drugiej.

Poniżej przedstawiony jest przykład w którym mamy dwie anteny o częstotliwości a, które tworzą dwa węzły fali (oznaczone jako #).

Rozwiązanie części 1

Parsowanie

Parsowanie wejścia nie było trudne, iterujemy po każdej lini i każdym znaku, jeśli jest on różny od . znaczy że znaleźliśmy antenę, chcę zagregować anteny o tych samych częstotliwościach, żeby móc analizować rózne częstotliwości niezależnie.

import fileinput
from collections import defaultdict

antenas = defaultdict(list)

for y, line in enumerate(fileinput.input()):
    for x, c in enumerate(line.strip()):
        if c != ".":
            antenas[c].append(complex(x, y))

Jak można zauważyć używam wbudowanego typu complex, czyli liczby zespolonej, nie ma co się bać, jedyne właściwości liczb zespolonych z których będziemy korzystać to to że składają się one z pary liczb i że dodając dwie liczby zespolone wynik uzysujemy dodając pierwszy komponent do pierwszego i drugi do drugiego. Wybór by użyć complex, został podjęty czysto ze względu na skrócenie kodu.

Znajdywanie węzłów

W zadaniu musimy policzyć ile unikalnych węzłów znajduje się na planszy, dlatego do trzymania znalezionych dotychczas węzłów użyjemy obiektu set, który nie trzyma duplikatów.

Użyjemy wbudowaniej funkcji itertools.combinations do wygenerowania wszystkich kombinacji, składających się z dwóch anten tych samych częstotliwości.

antinodes = set()

for frequency, positions in antenas.items():
    for a, b in itertools.combinations(positions, 2):
        diff = a - b
        antinodes.add(a + diff)
        antinodes.add(b - diff)

Filtrowanie i sumowanie węzłów

Okazuje się że niektóre węzły wychodzą poza nasze dwuwymiarowe miasto, nie interesują nas one, dlatego musimy przefiltrować je tak żeby zostały tylko te węzły które są w interesującym nas regionie, zrobimy to za pomocą funkcji filter.

def fits(antinode: complex) -> bool:
    a = antinode.real
    b = antinode.imag
    return a >= 0 and b >= 0 and a <= x and b <= y


print(len(list(filter(fits, antinodes))))

Po uruchomieniu kodu dostajemy poprawny wynik.

Część druga

Do zdobycia drugiej gwiazdki nie musimy zmieniać wiele, okazuje się, że jednak węzły leżą na całej długości linii przechodzącej przez wieże z tymi samymi częstotliwościami.

Na powyższym przykładzie można zauważyć o co chodzi. W tej części liczymy także wieże jako punkty będące węzłami, dlatego w powyższym przykładzie mamy 8 węzłów.

Rozwiązanie

Należy zmienić nieco kod w naszej pętli szukającej węzły.

W pętli while będziemy podejmować kolejne kroki o wielkości takiej jak dystans pomiędzy dwoma antenami, najpierw w jedną stronę (aż dojdziemy do końca miasta), a potem w drugą stronę, w ten sposób dodamy także anteny jako nasze węzły.

for frequency, positions in antenas.items():
    for a, b in combinations(positions, 2):
        diff = a - b
        cur = copy(a)
        while fits(cur):
            antinodes.add(cur)
            cur += diff

        cur = copy(b)
        while fits(cur):
            antinodes.add(cur)
            cur -= diff

print(len(antinodes))

Ta prosta zmiana wystarcza żeby rozwiązać zadanie w bardzo krótkim czasie.

Podsumowanie

Cieszę się że kolejne zadanie poszło w miarę szybko, jak przeczytałem treść na początku to byłem prawie że przekonany że naiwne rozwiązanie nie wystarczy, jednak wejście okazało się nie być dużym i niepotrzebne były żadne dodatkowe optymalizacje.