Posts

Zadanie Zadanie z dnia 17 polega na tym żeby uruchomić program na fikcyjnym procesorze opisanym dokładnie w treści zadania. Omówię jedynie najważniejsze aspekty. Nasz procesor operuje na liczbach 3 bitowych, każda operacja składa się z kodu operacji zaraz za nią operandu (para zajmuje razem 6 bitów). Procesor posiada też 3 rejestry: A, B i C, rejestry te mogą trzymać dowolne wartości nie ograniczone przez 3 bity. Program składa się z ciągu 3 bitowych wartości, operator operand, IP jest rejestrem który na początku ma wartość 0, wskazuje on na instrukcję która powinna zostać wykonana następna. Moment w którym próbujemy wykonać instrukcją znajdującą się poza pamięcią jest momentem kiedy nasz program się kończy. ...

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