-
Notifications
You must be signed in to change notification settings - Fork 1
Aoc 2024 Day 1
Jeszcze nie wyszliście, a grupa starszych historyków elfów już napotkała problem: ich lista miejsc do sprawdzenia jest obecnie pusta. W końcu ktoś decyduje, że najlepszym miejscem do sprawdzenia będzie biuro Głównego Historyka.
Po wejściu do biura wszyscy potwierdzają, że Głównego Historyka rzeczywiście nigdzie nie ma. Zamiast tego elfy odkrywają zbiór notatek i list historycznie znaczących miejsc! Wydaje się, że to planowanie Głównego Historyka przed wyjściem. Być może te notatki mogą posłużyć do określenia, w których miejscach szukać?
W całym biurze Głównego Historyka historycznie znaczące miejsca są wymienione nie według nazwy, ale według unikalnego numeru zwanego identyfikatorem lokalizacji. Aby mieć pewność, że niczego nie pominą, Historycy podzielili się na dwie grupy, z których każda przeszukuje biuro i próbuje stworzyć własną kompletną listę identyfikatorów lokalizacji.
Jest tylko jeden problem: trzymając dwie listy obok siebie (Twoja zagadka), szybko staje się jasne, że listy nie są zbyt podobne. Może możesz pomóc Historykom pogodzić ich listy?
Na przykład:
3 4
4 3
2 5
1 3
3 9
3 3
Być może listy różnią się tylko nieznacznie! Aby się o tym przekonać, połącz liczby w pary i zmierz, jak daleko się od siebie znajdują. Połącz najmniejszą liczbę na lewej liście z najmniejszą liczbą na prawej liście, a następnie drugą najmniejszą liczbę po lewej stronie z drugą najmniejszą liczbą po prawej stronie itd.
W obrębie każdej pary oblicz, jak daleko od siebie znajdują się dwie liczby; musisz zsumować wszystkie te odległości. Na przykład, jeśli połączysz 3 z lewej listy z 7 z prawej listy, odległość między nimi wynosi 4; jeśli sparujesz 9 z 3, odległość między nimi wynosi 6.
Na powyższej przykładowej liście pary i odległości byłyby następujące:
Najmniejsza liczba na lewej liście to 1, a najmniejsza liczba na prawej liście to 3. Odległość między nimi wynosi 2. Druga najmniejsza liczba na lewej liście to 2, a druga najmniejsza liczba na prawej liście to kolejne 3. Odległość między nimi wynosi 1. Trzecia najmniejsza liczba na obu listach to 3, więc odległość między nimi wynosi 0. Następne liczby do sparowania to 3 i 4, odległość 1. Piąte najmniejsze liczby na każdej liście to 3 i 5, odległość 2. Na koniec, największa liczba na lewej liście to 4, a największa liczba na prawej liście to 9; są one oddalone od siebie o 5. Aby znaleźć całkowitą odległość między listą lewą a listą prawą, dodaj odległości między wszystkimi znalezionymi parami. W powyższym przykładzie jest to 2 + 1 + 0 + 1 + 2 + 5, czyli całkowita odległość 11!
Twoje rzeczywiste listy lewa i prawa zawierają wiele identyfikatorów lokalizacji. Jaka jest całkowita odległość między listami?
Twoja analiza potwierdziła tylko to, czego wszyscy się obawiali: dwie listy identyfikatorów lokalizacji są rzeczywiście bardzo różne.
Czy na pewno?
Historycy nie mogą się zgodzić, która grupa popełniła błędy lub jak odczytać większość pisma ręcznego Szefa, ale w zamieszaniu zauważasz interesujący szczegół: wiele identyfikatorów lokalizacji pojawia się na obu listach! Być może pozostałe liczby wcale nie są identyfikatorami lokalizacji, a raczej błędnie zinterpretowanym pismem.
Tym razem musisz dokładnie ustalić, jak często każda liczba z lewej listy pojawia się na prawej liście. Oblicz całkowity wynik podobieństwa, dodając każdą liczbę z lewej listy po pomnożeniu jej przez liczbę wystąpień tej liczby na prawej liście.
Oto te same przykładowe listy:
3 4
4 3
2 5
1 3
3 9
3 3
Dla tych przykładowych list, oto proces znajdowania wyniku podobieństwa:
Pierwsza liczba na lewej liście to 3. Pojawia się na prawej liście trzy razy, więc wynik podobieństwa wzrasta o 3 * 3 = 9. Druga liczba na lewej liście to 4. Pojawia się na prawej liście raz, więc wynik podobieństwa wzrasta o 4 * 1 = 4. Trzecia liczba na lewej liście to 2. Nie pojawia się na prawej liście, więc wynik podobieństwa nie wzrasta (2 * 0 = 0). Czwarta liczba, 1, również nie pojawia się na prawej liście. Piąta liczba, 3, pojawia się na prawej liście trzy razy; wynik podobieństwa wzrasta o 9. Ostatnia liczba, 3, pojawia się na prawej liście trzy razy; wynik podobieństwa ponownie wzrasta o 9. Tak więc dla tych przykładowych list wynik podobieństwa na końcu tego procesu wynosi 31 (9 + 4 + 0 + 0 + 9 + 9).
Rozważ ponownie swoje listy po lewej i prawej stronie. Jaki jest ich wynik podobieństwa?