Wpis z mikrobloga

#naukaprogramowania #programowanie #programista15k #adventofcode
Dzien 5. i mamy typowe bait and switch w stylu AoC - piersza czesc wchodzi bardzo latwo, a w drugiej okazuje sie ze musimy czekac pare milionow lat zeby petla sie skonczyla wykonywac :)


Jak ktos podpatrzyl dane wejsciowe to pewnie zaczal myslec jak to zrobic zeby nie liczyc na duzych liczbach.
Mnie bardziej zastanawialo czy nie sprobowac to napisac wylacznie funkcyjnie, bo przeciez te transformacje to typowe funkcje, wiec mozna by je zlozyc i przez to napisac calkiem zwiezly kod, no ale skonczylem na typowym rozpisaniu krok po kroku.
Bardziej szczegolowo ponizej, spoiler!


Czesc 2 w Pythonie policzona w 4ms, feels good man.
  • 10
@n0c0Mpr3h3nD: jak napisałeś o redukcji do mniejszych liczb to wpadłem na pomysł:
1. Zebrać wszystkie przody i końce przedziałów (w zbiorach ziaren i wszystkich mapowaniach)
2. Posortować
3. Ponadawać nowe numery od zera do (długość - 1)
4. Podmienić wszystkie liczby z danych wejściowych na te nowe numery
5. Przeprowadzić brute-force na tym zminiaturyzowanym zadaniu
6. Mamy jakiś wynik i sprawdzamy czemu on odpowiada w mapowaniu z pkt. 3 i to
@n0c0Mpr3h3nD: w tym rozwiązaniu chodzi o to, że redukuję rozmiar zadania do śmiesznej wielkości, pewnie gdzieś ok 100 elementów

Bazuje to na tym, że w oryginalnym zadaniu ogrom liczb jest mapowana w identyczny sposób (jedynie z jakimś offsetem) - więc zamiast tego wystarczy rozważyć jedynie pierwsze elementy każdego możliwego przedziału

W tym zadaniu taka redukcja jest niepotrzebna, ale zdarzają się czasem zadania, w których trik z podmienieniem wartości na mniejsze jest
@n0c0Mpr3h3nD: ja w końcu pieprznąłem brute force bo się poddałem przy optymalizacji inputu (okazało się, że podejście jakie zaaplikowałem właściwie w ogóle go nie zmieniło), ale teraz jak sobie patrzę to w zasadzie można by było łatwo to rozwiązać od tyłu - robisz analogiczne co w part 1, tylko że zaczynasz od location i tworzysz seedy od 0 do 9999(...), przy pierwszym napotkanym seedzie robisz breaka i go zwracasz
Czesc 2 w Pythonie policzona w 4ms, feels good man

@n0c0Mpr3h3nD: Kurła, u mnie nie chce zejść poniżej 10ms :(
Pewnie za wolno parsuję input ( ͡°( ͡° ͜ʖ( ͡° ͜ʖ ͡°)ʖ ͡°) ͡°)

Ale świadomość, że niektórzy puszczali bruteforce'a i czekali kilka godzin na wynik mnie pociesza ( ͡° ͜ʖ ͡°)