Posts

Ten post jest kontynuacją mojego poprzedniego posta w którym pisałem jak pisać rozszerzenia do Pythona korzystając z API w C. W tamtym poście skupiłem się jedynie na implementacji funkcji w module, operowały one na obiektach które były dość mocno ograniczone przez Pythona, np. żeby operować na listach musimy wywoływać funkcje z przedrostkiem PyList które zakładają że lista jest typem dynamicznym. Przydałoby się móc stworzyć typy które będą trzymać dane w odpowiednich do tego strukturach w C zoptymalizowanych pod nasz problem. Postaramy się zaimplementować nasz typ Array, który będzie wspierał podobne funckjonalności jak macierze z numpy. ...

Python jest znany z bardzo słabej wydajności, nie ma się czego dziwić gdyż jest on językiem interpretowalnym i jego celem nigdy nie było być najszybszym językiem na świecie. Sam Python napisany jest w języku C, stąd nazwa oficjalnej implementacji języka: cpython. Twórcy języka pozwolili na relatywnie łatwe tworzenie rozszerzeń do języka, przez tworzenie modułów w C. Celem tego posta jest nauczyć się podstaw tworzenia takiego rozszerzenia na podstawie prostego przykładu, implementacji szybkiego algorytmu sortowania. ...

Część 1 W dzisiejszym zadaniu mamy na wejściu zbiór kluczy i zamków, naszym zadaniem jest obliczyć ile w sumie kluczy pasuje do ilu zamków. Input wygląda w ten sposób: ##### ##.## .#.## ...## ...#. ...#. ..... ..... #.... #.... #...# #.#.# #.### ##### ..... ..... #.#.. ###.. ###.# ###.# ##### Zamki to te macierze które w górnym rzędzie mają same #, a klucze mają w dolnym rzędzie same #, klucz mieści się w zamku jeśli ilość # w każdej kolumnie, nie przekracza wysokości kolumny. Właściwie w treści zadania mamy podane całe jego rozwiązanie, widać że autor nie chciał jak najbardziej ułatwić nam dzisiejsze zadanie. ...

W dzień wigilijny miałem nadzieję że zadanie będzie prosteze gdyż chciałem spędzić go z rodziną, dostaliśmy zadanie którego część 2 była lekkim wyzwaniem ale całkiem szybko zrozumiałem co trzeba w niej zrobić. Zadanie Na wejściu otrzymujemy listę bramek logicznych które mają po dwa wejścia i jedno wyjście, dostajemy też wartości na wejściach to pewnej części bramek. Naszym zadaniem jest zasymulować działanie tych bramek i zwrócić wartości na wyjściach zaczynających się na literę z ...

Zadanie Dzisiejsze zadanie jest klasycznym zadaniem z teorii grafów. W naszym zadaniu komputery to wierzchołki, oznaczone są one jako stringi składające się z dwóch znaków, w danych wejściowych dostajemy listę krawędzi grafu w postaci: kh-tc # komputer kh jest połączony z komputerem tc qp-kh de-cg ta-ka ... Mamy znaleźć takie zbiory trzech komputerów że każdy jest połączony z każdym. Jest to problem znalezienia kliki w grafie. Problem ten jest NP-trudny, jednak dla klik o rozmiarach 3 nawet rozwiązanie typu brute force nie powinno sprawić większego problemu. ...

Poprzez problemy z zadaniem 21 ten post wrzucam z opóźnieniem, ale zadanie z dnia 22 na szczęście było dużo prostsze niż poprzednie. Najtrudniejszym aspektem było zrozumienie treści zadania poprzez czytanie ze zrozumieniem. Część 1 W pierwszej części zadania mamy wygenerować ciąg liczb pseudolosowych zgodnie z podanym w treści algorytmem. Każda linijka zawiera sekretną liczbę początkową od jednego sprzedawcy, dla każdej z tych liczb mamy zasymulować transformacje 2000 razy i zwrócić sumę otrzymanych liczb. ...

Zadanie z dnia 21 mocno przycisnęło mnie do muru, wrzucam rozwiązanie z opóźnieniem, gdyż zajęło mi ono więcej czasu niż chciałbym przyznać. Zadanie Treść zadania jest dosyć skomplikowana, mamy keypad zawierający cyrfy od 0 do 9 oraz przycisk A do akceptowania danej cyfry. Wygląda to tak: +---+---+---+ | 7 | 8 | 9 | +---+---+---+ | 4 | 5 | 6 | +---+---+---+ | 1 | 2 | 3 | +---+---+---+ | 0 | A | +---+---+ Nie możemy jednak bezpośrednio wpisywać nic na tym keypadzie, musi to wykonać robot, którym sterujemy za pomocą takiego keypada: ...

Zadanie Dzisiaj przyszedł czas na kolejne zadanie ze znajdywaniem ścieżki w dwuwymiarowej macierzy. Format wejścia jest podobny jak w zadaniu 16. Czyli mamy grida ze ścieżkami oznaczonymi jako . a ścianami oznaczonymi jako #. Start i koniec oznaczone są kolejno jako S i E. Naszym celem jest znalezienie najkrótszej ścieżki od początku do końca, z tym że mamy możliwość oszukiwania, gracz raz podczas wyścigu może aktywować oszustwo trwające dwa ruchy. Podczas oszustwa może przechodzić przez ściany, ale na końcu trwania oszustwa powinien skończyć na pustym polu. (Czyli efektywnie jesteśmy w stanie przeskoczyć jedną ścianę). ...

Zadanie Dzisiaj na wejściu otrzymujemy listę stringów które możemy wykorzystać do tworzenia innych większch stringów za pomocą konkatenacji. Dostajemy też listę długich stringów które będziemy próbować zbudować. r, wr, b, g, bwu, rb, gb, br brwrr bggr gbbr rrbgbr ubwu bwurrg brgr bbrgwb Naszym zadaniem jest policzyć ile długich ciągów znaków jesteśmy w stanie stworzyć za pomocą fragmentów z pierwszej linijki. Przykłady: brwrr - br + wr + r bggr - b + g + g + r ubwu - nie da się! Rozwiązanie W faktycznym inpucie naszego zadania stringi budulcowe są sporo dłuższe i jest ich więcej, jedną z fajnych struktur do przechowywania takiego typu danych jest trie, pozwala ono bowiem na weryfikowanie w wydajny sposób czy dany prefix występuje w jakim kolwiek ze słow z dużego słownika. ...

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