Posts

Problem Dzisiejsze zadanie polega na znalezieniu ścieżki w labiryncie która będzie miała najniższy score, gdzie score liczony jest w taki sposób że każdy ruch zwiększa go o jeden a każdy skręt o 90 stopni zwiększa go o 1000. Zaczynamy w punkcie S a kończymy w punkcie E. Oto przykładowy labirynt: ############### #.......#....E# #.#.###.#.###.# #.....#.#...#.# #.###.#####.#.# #.#.#.......#.# #.#.#####.###.# #...........#.# ###.#.#####.#.# #...#.....#.#.# #.#.#.###.#.#.# #.....#...#.#.# #.###.#.#.#.#.# #S..#.....#...# ############### Rozwiązanie Jak tylko widzę zadanie ze znajdywaniem najkrótszej ścieżki to od razu myślę o algorytmie Dijkstry. Nasz labirynt możemy rozważać jako graf. Ważne jest to że każdym wierzchołkiem nie mogą być same koordynaty a także kierunek w którym jesteśmy zwróceni, lub bardziej powinienem powiedzieć orientacja, gdyż z punktu widzenia liczenia score nie ma znaczenia w którą stronę skręcamy a jedynie że zmieniamy orientację z pionowej na poziomą lub na odwrót. ...

Zadanie W tym zadaniu znowu mamy do czynienia z robotem, teraz jednak przesuwa on się po planszy i jeśli natrafi na pudełko to przesuwa je o jedno pole w kierunku swojego ruchu razem ze wszystkimi pudełkami które są za nim (jeśli pudełek nie blokuje ściana). Wejście zawiera planszę i listę kroków, gdzie # to ściana, O to pudełko, @ to robot: ######## #..O.O.# ##@.O..# #...O..# #.#.O..# #...O..# #......# ######## <^^>>>vv<v>>v<< Rozwiązanie Parsowanie Jako że w naszym wejściu jest więcej pustych pól niż zajętych, uznałem że lepiej będzie przechowywać koordynaty pudełek i ścian w słowniku, zamiast zapisywać całego 2d grida. Uznałem też że znowu użyję tricka z trzymaniem koordynatów i wektorów przemieszenia w obiekcie complex, żeby kod był nieco zwięźlejszy. ...

Zadanie W zadaniu posiadamy listę robotów z podanymi koordyatami startowymi i wektorami prędkości na sekundę. p=0,4 v=3,-3 Przykładowo powyżej mamy robota na pozycji x=0 y=4, który będzie się poruszał z każdą sekundą o 3 pola w prawo i 3 w dół. Nasza mapa jest ograniczona z lewej i górnej strony przez 0 a z prawej i dolnej przez największe wartości x i y ze wszystkich robotów, jeśli robot miałby wyjść poza planszę teleportuje on się na drugą stronę. ...

Zadanie W dzisiejszym zadaniu musimy zagrać w grę “szpon”, mamy do dyspozycji dwa przyciski A i B wciśnięcie przycisku A kosztuje nas 3 kredyty a B jeden. Każdy przycisk ma zdefiniowany wektor przesunięcia szpona. Naszym zadaniem jest przesunąć szpona na pole z nagrodą, w jak najmniejszym koście w kredytach. Wynikiem jest minimalna suma kredytów potrzebna do zdobycia nagród w każdej grze gdzie jest to możliwe. Przykładowe dane: Button A: X+94, Y+34 Button B: X+22, Y+67 Prize: X=8400, Y=5400 Button A: X+26, Y+66 Button B: X+67, Y+21 Prize: X=12748, Y=12176 W powyższym przykładzie mamy dwie gry, pierwsza jest niemożliwa do rozwiązania, z kolei w drugiej rozwiązaniem jest wcisnąć przycisk A 80 razy i przycisk B 40 razy, co daje razem 280 kredytów ...

Zadanie W dzisiejszym zadaniu musimy policzyć pola i obwody regionów na gridzie 2d, przykładowo: AAAA BBCD BBCC EEEC Na powyższym gridzie mamy region A który ma pole 4 i obwód 10 (obwód liczymy jako ilość sąsiadujących pól które nie są z tego regionu), region B ma pole 4 a obwód 8. Jednym z problemów może być to że regiony mogą być też w środku innych regionów np: AAA AOA AAA Region A ma pole 8 ale obwód 16, a region O ma pole 1 i obwód 4 ...

Zadanie Na wejściu distajemy listę liczb, która zmienia się przy każdym naszym mrugnięciu, wedle ściśle określonych zasad. 0 zamienia się w 1 liczby o parzystej liczbie cyfr dzielą się na dwa (1234 -> [12, 34]) pozostałe liczby są mnożone razy 2024 Nasza lista rośnie z każdym mrugnięciem oto przykładowa progresja: 125 17 253000 1 7 253 0 2024 14168 512072 1 20 24 28676032 512 72 2024 2 0 2 4 2867 6032 ... Musimy policzyć jak długa będzie nasza lista po 25 mrugnięciach. ...

Dzisiaj ponownie rozwiązanie nie było szczególnie skomplikowane, właściwie to pierwszy pomysł od razu zadziałał, a rozwinięcie go do wspierania także części drugiej było tak proste jak dodanie jednej dodatkowej zmiennej. Zadanie Na wejściu dostajemy mapę wysokościową przedstawioną jako macierz 2d, każdy punkt ma cyfrę, która oznacza wysokośc w danym miejscu. Naszym celem jest znalezienie ścieżek na szczyt. Nasze trasy powinny się zaczynać w punkcie o wysokości 0 i każdy krok który wyoknujemy (tylko prostopadle do osi x i y, nie ma przekątnych) powinien zwiększać naszą wysokośc o jeden aż dojdziemy do szczytu o cyfrze 9. ...

Dzisiejsze zadanie podniosło nieco poziom trudności i sprawiło że musiałem dłużej nad nim pomyśleć. Treść Naszym zadaniem jest dokonać defragmentacji dysku. Na wejściu dostajemy listę cyfr, które oznaczają ile bloków dysku zajętych jest przez pliki i puste przestrzenie. Cyfry na parzystych pozycjach oznaczają ilość bloków zajętych przez pliki, zaś na nieparzystych oznaczają puste bloki. 1234501 # tak to wygląda na wejściu 0..111....22222.3 # tak to wygląda na dysku (. to puste miejsca a cyfry to idki plików) Każdy plik ma swoje id i są one przydzielane inkrementując id o jeden przy każdym kolejnym zajętym klastrze bloków z wejścia. ...

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. ...

Dzisiaj nie chciało mi się kombinować więc zadanie rozwiązałem po prostu w Pythonie. Zadanie Treść nie jest była dzisiaj skomplikowana, w każdej lini otrzymujemy liczbę i listę liczb, pomiędzy liczby z listy musimy umieścić operatory (+ albo *), w taki sposób żeby uzyskać pierwszą liczbę w linii. (operacje wykonywane są od lewej do prawej). 190: 10 19 # 190 = 10 * 19 100: 3 60 10 # nie da się 83: 17 5 # nie da się 4: 1 1 2 # 4 = (1 + 1) * 2 Rozwiązanie Do sprawdzenia czy dana linia jest poprawna (możemy w niej dobrać odpowiednie operatory), napisałem prostą rekurencyjną funkcję. Sprawdza ona wszystkie kombinacje operatorów, aż znajdzie ten poprawny. ...