Posts

Problem Dzisiaj znajdujemy się na planszy 2d o wielkości 71 na 71, zaczynamy w narożniku o koordynatach (0,0) musimy dojść do pola (70, 70). Na wejściu dostajemy listę koordynatów w takiej formie: 5 4 4 3 2 6 , , , , , , 4 2 5 0 1 3 Koordynaty te wskazują na których polach znajduje się przeszkoda. Naszym zadaniem jest znaleźć najkrótszą ścieżkę (omijając przeszkody) z punktu startowego do końcowego, ale mamy brać pod uwagę tylko 1024 pierwszych linijek z koordynatami przeszkód. Zakładam że pozostałe przeszkody będą potrzebne do części 2. ...

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: # # # # # # # # # # # # # # # # . . . . . . . # . . . . S # # . # . # # # . # . # . # . # # . . . # . . . . . . . # . # # . # . # # # . # # # . # # # # . # . . . # . . . . . . . # # . # # # . # . # . # # # . # # . . . # . # . # . # . . . # # # # # # . # . # . # . # . # # . . . # . . . # . . . . . # # . # . # . # . # # # # # # # # . # . . . # . . . . . . . # # . # # # # # # # # # # # . # # E . . . . . . . . . . . . # # # # # # # # # # # # # # # # 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 . . . . . # # . . . . . . # # # # # # # # # 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: B B P B B P u u r u u r t t i t t i t t z t t z o o e o o e n n : n n : A B X A B X : : = : : = 8 1 X X 4 X X 2 + + 0 + + 7 9 2 0 2 6 4 4 2 , 6 7 8 , , , , , Y Y Y = Y Y Y + + 5 + + = 3 6 4 6 2 1 4 7 0 6 1 2 0 1 7 6 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: A B B E A B B E A C C E A D C C 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: ...

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: 1 2 2 5 5 2 5 5 1 1 5 3 3 2 2 0 0 1 0 0 7 7 7 0 2 2 2 1 0 1 2 2 0 7 4 2 2 0 4 1 4 2 2 1 4 6 0 8 2 8 2 6 7 4 6 0 2 3 8 2 6 7 6 0 3 2 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. ...