WDP* MIM UW
- api: [zad. 1.] bar apis (C++) ✅🔬
- bul: [zad. 2.] bułki (C++) ✅🔬
- naj: [zad. 3.] najdłuższe wspólne podsłowo (C++) ✅🔬
Ćwiczenia I: Wstęp
- rectangles_intersection: [zad. 1.] prostokąty; rzutowanie na osie (C++) ✅🔬
- line_segments_intersection: [zad. 2.] odcinki; sprawdzanie, z której strony jest punkt (C++) ✅🔬
- parallelograms_intersection: [zad. 3.] równoległoboki; sprawdzanie punktów wewnątrz i przecinania się przekątnych (C++)
- point_inside_polygon: [zad. 4.] czy punkt leży wewnątrz dowolnego wielokąta
Ćwiczenia II: Funkcje operujące na liczbach
- [zad. 1.] stopień parzystości
- parity_degree (C) ✅
- zad1_ms: autor: @MrD4rkne (C) ✅
- [zad. 2.] odwracanie kolejności cyfr w liczbie
- [zad. 3.] podłoga z pierwiastka; suma kolejnych liczb nieparzystych
- sqrt_floor (C) ✅
- zad3_ms: autor: @MrD4rkne (C) ✅
- [zad. 4.] szukanie następnej liczby, która w zapisie binarnym nie ma dwóch jedynek koło siebie
- next_sparse_number (C)
- sparse: autor: @lbozyk (C) ✅
- zad4_ms: autor: @MrD4rkne (C) ✅
- [zad. 5.] zliczanie wszystkich liczb rzadkich mniejszych od danej liczby
- count_sparse_numbers_brute (C) ✅🔬
- count_sparse_numbers (C) ✅
- consecutive_ones programowanie dynamiczne, GFG (C)
- is_prime: [zad. 6.] sprawdzanie czy liczba jest pierwsza (C) ✅🔬
- encode_in_one_integer: [zad. 7.] kodowanie pary liczb naturalnych jako liczbę naturalną (C)
- modulo: [zad. 8.] czy pierścień reszt modulo n zawiera nietrywialne pierwiastki z 1 (C) ✅
- count_zeros: [zad. 10.] ile jest zer na końcu n! (C)
- count_ones: [zad. 12.] ile jest jedynek w zapisie binarnym liczby n (C)
Ćwiczenia III: Zadania na tablice
- [zad. 1.] obrót tablicy
- rotate_table (C)
- rotate: autor: @lbozyk (C) ✅
- zad1_ms: autor: @MrD4rkne (C) ✅
- [zad. 2.] tasowanie dwóch tablic
- [zad. 3.] ile różnych liczb występuje w dwóch niemalejących tablicach
- nondecreasing_tables (C)
- count_distinct: autor: @lbozyk (C) ✅
- zad3_ms: autor: @MrD4rkne (C) ✅
- [zad. 4.] ciąg Bonifacego (podobny do Fibonacciego)
- [zad. 5.] znajdź lidera
- find_leader (C)
- leader: autor: @lbozyk (C) ✅
- zad5_ms: autor: @MrD4rkne (C) ✅
- [zad. 6.] podziel std::vector na mniejsze części
- split_to_vectors (C++) ✅
- [zad. 7.] fragment tablicy zawierający wszystkie indeksy jego elementów
- find_fragments_containing_all_indexes (C)
- divide: autor: @lbozyk (C) ✅
- zad7_ms: autor: @MrD4rkne (C) ✅
- [zad. 8.] dekompresuj tablicę ciągów skompresowanych 2^(i−1)⋅(2⋅k−1)
- decompress.cpp (C++) ✅🔬
- compress.cpp (C++) ✅🔬
- decompress.c (C)
- zad8_ms: autor: @MrD4rkne (C) ✅
- [zad. 9.] ile jest trójek spełniających nierówność trójkąta w tablicy
- triangle_inequality (C)
- zad9_ms: autor: @MrD4rkne (C) ✅
- [zad. 10.] zabawka Jasia
- cylinder_toy (C)
- toy: autor: @lbozyk (C) ✅
- zad10_ms: autor: @MrD4rkne (C) ✅
- [zad. 11.] kodowanie w systemie minus-dwójkowym
- minus_2_binary (C)
- minus2: autor: @lbozyk (C) ✅
- [zad. 12.] następna permutacja
- lexicographical_order (C)
- next_perm: autor: @lbozyk (C) ✅
- zad12_ms: autor: @MrD4rkne (C) ✅
- [zad. 14.] sprawdź, czy jeden ciąg zawiera się w drugim
- subsequence (C) ✅🔬
- [zad. 16.] ciąg różnicowy
- differential_sequence (C)
- diff_seq (C): autor: @lbozyk (C) ✅
- diff_seq_fam (C) ✅🔬
- [zad. 17.] ciąg ciągu różnicowego
- diff_diff_seq_fam (C) ✅🔬
- zad17_ms: autor: @MrD4rkne (C) ✅
Ćwiczenia IV: Złożoność czasowa i pamięciowa
- [zad. 1.]
$n^{3}$ - [zad. 2.]
$n^{4}$ - [zad. 3.]
$\frac{1}{n^{4}}$ $\frac{1}{n^{2}}$
- [zad. 6.] znajdź minimalną liczbę ruchów potrzebnych do uzyskania danej konfiguracji wież Hanoi
- hanoi (C) ✅
- print_hanoi (C)
- [zad. 8.] cykl deterministycznej funkcji
- cyclic_sequence: dwóch biegaczy (C) 📝
Ćwiczenia V: Zliczanie, sumy_prefiksowe, gąsienica, bisekcja
- [zad. 1.]
- sum_table_brute (C) ✅
- zad1_ms: autor: @MrD4rkne (C) ✅🔬
- [zad. 2.]
- absolute_minimum_of_sequence (C++)
- zad2_ms: autor: @MrD4rkne (C) ✅🔬
- zad2_pxl: autor: @pixelkubek (C) ✅🔬
- [zad. 3.]
- minimal_sum_of_two_elements (C) ✅
- minimal_sum_of_two_elements_brute (C) ✅
- zad3_ms: autor: @MrD4rkne (C) ✅🔬
- [zad. 4.]
- [zad. 5.2.]
- convex_func_min (C)
- zad5_2_ms: autor: @MrD4rkne (C) ✅🔬
- [zad. 6.]
- diagonal (C)
- [zad. 7.]
- [zad. 8.]
- find_duplicate (C)
- zad8_ms: autor: @MrD4rkne (C) ✅🔬
- [zad. 10.]
- find_number_in_monotonic_matrix (C)
- zad10_ms: autor: @MrD4rkne (C) ✅🔬
- [zad. 11.]
- find_rotated_min (C)
- zad11_ms: autor: @MrD4rkne (C) ✅🔬
- [zad. 12.]
- zad12_ms: autor: @MrD4rkne (C) ✅🔬
- [zad. 14.]
- farthest_pair (C)
- daleko: autor: @MrD4rkne (C) ✅🔬
- [zad. 15.]
- [zad. 17.]
- orzechy (C) ✅🔬
- [zad. 18.]
- zad18_pxl: autor: @pixelkubek (C) ✅
Ćwiczenia VI: Stosy, kolejki i koszt zamortyzowany
- [zad. 2.]
- lifo_stack (C++)
- [zad. 3.]
- [zad. 4.]
- [zad. 5.]
- katastrofy stos indeksów, które wskazują na rosnące elementy (C++) ✅🔬
- wtc_ms: autor: @MrD4rkne (C++) ✅
- [zad. 6.]
- zad_6: autor: @pixelkubek (C++) ✅
- [zad. 7.] stos indeksów
- scyscrapers_rectangle_field (C++)
- zad_7: autor: @pixelkubek (C++) ✅
- zad7_ms: autor: @MrD4rkne (C++) ✅
- [zad. 8.]
- zad_8: autor: @pixelkubek (C++) ❌
- [zad. 9.]
- [zad. 10.]
- parentheses (C++) ✅
- zad_10: autor: @pixelkubek (C++) ✅
- zad_10_ms: autor: @MrD4rkne (C++) ✅
- [zad. 11.]
- zad_11: autor: @pixelkubek (C++) ❌ (gorsza zlozonosc dla powtarzajacych sie elementow)
- [zad. 12.]
- fibonacci_word (C++)
- slowa: autor: @MrD4rkne (C++)
- zad_12: autor: @pixelkubek (C++) ✅
Ćwiczenia VII: Zastosowanie sortowania
- [zad. 1.]
- bars O(n logn) znaleźć medianę, potem abs(t[i] - median) dla każdego elementu (C++)
- bars_linear O(n) liniowe znajdowanie mediany (C++)
- median_of_medians (C++)
- zad1_ms: autor: @MrD4rkne (C++) ✅
- zad1_jc: autor: @pixelkubek (C++)
- [zad. 2.]
- contains_triangle O(n), wystarczy sprawdzić trójki elementów dla indeksów k = j + 1 = i + 2 (C++)
- zad2_ms: autor: @MrD4rkne (C++) ✅
- zad2_jc: autor: @pixelkubek (C++)
- [zad. 3.]
- [zad. 4.]
- max_combined_diff (C++)
- zad4_ms: autor: @MrD4rkne (C++) ✅
- zad4_jc: autor: @pixelkubek (C++)
- [zad. 5.]
- [zad. 6.] ilu maksymalnie kolegów Tomka może popłynąć na k-dniowy rejs (koledzy mogą się "teleportować")
- [zad. 7.] ilu maksymalnie dni może trwać rejs, w którym bierze udział k kolegów Tomka (koledzy nie mogą się zamieniać)
- zad_7: pomysł: @lbozyk, autor: @pixelkubek ✅
Ćwiczenia VIII: Listy i drzewa
- [zad. 1.]
- [zad. 2.]
- [zad. 3.]
- concatenate_lists (C)
- zad3_ms: autor: @MrD4rkne (C++) ✅
- zad3_jc: autor: @pixelkubek (C++) ✅
- [zad. 5.]
- common_suffix_hourglass (C)
- common_suffix_len (C)
- zad5_ms: autor: @MrD4rkne (C++) ✅
- zad5_jc: autor: @pixelkubek (C++) ✅
- [zad. 6.]
- find_cycle_reverse_copy (C++)
- find_cycle_runners (C++)
- zad6_jc: autor: @pixelkubek (C++) ✅
- zad6_ms: autor: @MrD4rkne (C++) ✅
- [zad. 7.]
- general_tree (C)
- zad7_ms: autor: @MrD4rkne (C++) ✅
- zad7_jc: autor: @pixelkubek (C++) ✅
- [zad. 8.]
- jump_traversal (C)
- zad8_ms: autor: @MrD4rkne (C++) ✅
- zad8_jc: autor: @pixelkubek (C++) ✅
- [zad. 9.]
- zad9_ms: autor: @MrD4rkne (C)
- [zad. 10.]
- is_ultraleftist (C)
- zad10_ms: autor: @MrD4rkne (C) ✅
- [zad. 11.]
- [zad. 12.]
- cut_tree_into_two (C)
- zad12_ms: autor: @MrD4rkne (C) ✅
- [zad. 13.]
- [zad. 14.]
- [zad. 15.]
- [zad. 16.]
- [zad. 17.]
Ćwiczenia IX: Find-union i grafy
- [zad. 1.] skarbonki z kluczykami - graf cykliczny
- piggybanks_dfs zliczanie zamkniętych cykli poprzez skakanie po indeksach
- piggybanks_find_union zliczanie zamkniętych cykli z pomocą grafu find-union
- zad1_ms autor: @MrD4rkne (C++) ✅
- [zad. 2.]
- [zad. 3.]
- [zad. 4.]
- zad4_ms autor: @MrD4rkne (C++) ✅
- [zad. 5.]
- path 📝
- [zad. 6.]
- zad6_ms autor: @MrD4rkne (C++) ✅
- [zad. 7.]
- zad7_ms autor: @MrD4rkne (C++) ✅
- [zad. 8.]
- zad8_ms autor: @MrD4rkne (C++) ✅
- [zad. 9.] wyspy - graf macierz
- [zad. 10.] polaczenie
- polaczenie: BFS
- zad10_ms autor: @MrD4rkne (C++) ✅
- [zad. 11.]
- zad11_ms autor: @MrD4rkne (C++) ✅
- [zad. 12.]
- zad12_ms autor: @MrD4rkne (C++) ✅
- [zad. 13.]
- zad13_ms autor: @MrD4rkne (C++) ✅
Ćwiczenia X: Backtracking
- [zad. 1.] Schweck's Theorem
- zad1_ms autor: @MrD4rkne (C++) ✅
- [zad. 2.]
- get_number_of_prime_summands (C++) ✅
- goldbachs_conjecture (C++) ✅
- zad2_ms autor: @MrD4rkne (C++) ✅
- [zad. 3.]
- zad3_ms autor: @MrD4rkne (C++) ✅
Ćwiczenia XI: Spamiętywanie i programowanie dynamiczne
- [zad. 1.]
- GetMinimalNumberOfCoinsInChange wydanie reszty minimalną liczbą monet dla danych nominałów (C++) ✅
- zad1_ms autor: @MrD4rkne (C++) ✅
- zad1_mb autor: @stopnoanime (C++) ✅
- [zad. 2.]
- CountPossibleWaysToBreakAmount (C++) ✅
- zad2_ms autor: @MrD4rkne (C++) ✅
- zad2_mb autor: @stopnoanime (C++) ✅
- [zad. 3.]
- GetSmallestDifferentBanknotesCount (C++) ✅
- zad3_ms autor: @MrD4rkne (C++) ✅
- zad3_mb autor: @stopnoanime (C++)
- [zad. 4.]
- GetSmallestDifferentBanknotesCount (C++) ✅
- zad4_ms autor: @MrD4rkne (C++) ✅
- zad4_mb autor: @stopnoanime (C++) ✅
- [zad. 5.]
- BreakAmountUniquely unikalna rozmiana dla danych nominałów (C++) ✅
- unique (C++)
- zad5_ms autor: @MrD4rkne (C++) ✅
- zad5_mb autor: @stopnoanime (C++) ✅
- [zad. 6.]
- zad6_ms autor: @MrD4rkne (C++)
- [zad. 7.]
- zad7_ms autor: @MrD4rkne (C++) ✅
- [zad. 8.]
- zad8_ms autor: @MrD4rkne (C++) ✅
- [zad. 9.]
- GetMaxBusPassengersCount (C++) ✅
- zad9_ms autor: @MrD4rkne (C++) ✅🔬
- [zad. 16.]
- GetMaxBusPassengersCount (C++) ✅
- [zad. 17.]
- Parentheses (C++) ✅
Ćwiczenia XII: Programowanie zachłanne
Ćwiczenia XIV: Wyszukiwanie wzorców w tekście
Laboratorium I: Podzielny fragment ciągu
- divisible_sequence: najdłuższy dzielny fragment ciągu (C) ✅🔬
- divisible_sequence: najdłuższy dzielny fragment ciągu (C++) ✅🔬
Laboratorium II: Gra w skakanie (NWD)
- game.c: strategia wygrywająca (C) ✅🔬
- game.h: prototyp funkcji ✅🔬
- evaluate_game.c: program grający w grę (C) ✅🔬
- [zad. 2.]
- zad2_ms: autor @MrD4rkne (C++)
- [zad. 2.]
- mice_in_the_corridor (C++)
- [zad. 1.]
- schodki: autor: @stopnoanime (C) ✅🔬
- count_stepped_sequences (C) ✅🔬
- [zad. 2.]
- cieniowanie: autor: @stopnoanime (C) ✅
- shading_matrix (C) ✅
- [zad. 1.]
- [zad. 2.]
- [zad. 1.]
- sparse_mask O(1) (INT_MAX / 3) << 1 + 1 (C) ✅
- sparse_mask_unsigned O(1) ~0u/3 (C) ✅
- sparse_shuffle_bits O(N) liniowe tasowanie bitów (C) ✅
- [zad. 2.]
- fragments_two_pointers: O(n) gąsienica (C) ✅
- fragments_binsearch: O(n logn) binsearch po wyniku (C) ✅
- caterpillar_bozyk: O(n) gąsienica, autor: @lbozyk (C) ✅
- [zad. 1.]
- [zad. 2.]
- rotate_double_cycled_list O(n) przepinanie wskaźników (C) ✅
- Find Union
- Fibonacci
- Thue-Morse
- Potok bez gwiazdki
- Inne
- count_symmetrical_nodes: policz symetryczne węzły w drzewie (C)
- get_diameter średnica drzewa (C)
✅ skończony program (da się go uruchomić i wydaje się, że działa poprawnie)
❌ program z wykrytym bugiem
🔬 program przechodzący testy
📝 koncepcja bez implementacji
Jeśli rozwiązałeś zadanie innym sposobem, zaimplementowałeś nierozwiązane wcześniej zadanie lub po prostu chcesz się podzielić swoim kodem - nie krępuj się, wrzuć kod na repo. Razem stwórzmy bazę różnych rozwiązań i źródło do nauki dla każdego! Moje rozwiązania często nie są najoptymalniejsze, więc jeśli masz lepszy pomysł na zadanie, twój wkład będzie tym bardziej cenny.
Jeżeli już zdecydujesz się podzeilić swoim kodem, umieść go w folderze src, w odpowiednim podfolderze - np. src/cw1/zad1. Idealnie, gdybyś do kodu dołączył testy - ostatecznie pliki .IN i .OUT powinny się znaleźć w folderze tests, zachowując dalszą ścieżkę analogiczną z plikiem z kodem (w tym przykładzie tests/cw1/zad1).
Jeśli twój program to power_of_two.c, to testy powinny nazywać się power_of_two0.in, power_of_two0.out, power_of_two1.in, power_of_two1.out... i powinieneś je umieścić w folderze c. Oczywiście pliki .IN zawierają input, a pliki .OUT oczekiwany output. Po każdym pushu na branch main testy automatycznie się uruchomią i ich wyniki będziesz mógł zobaczyć w szczegółach odpowiedniej githubowej akcji. Wszystkie testy odpalają się po skompilowaniu pliku z restykcyjnymi opcjami - dla kodów w C: configs/options, a dla C++: configs/optionsCpp.
Jeżeli jesteś leniwy i nie chce ci się dla każdego programu tworzyć ręcznie serii plików, możesz wpisać pary input-output do CSVki. Dla programu power_of_two.c będzie to przykładowo:
3,8
11,2048
12,4096
Następnie możesz skorzystać ze skryptu test_generator.py w folderze scripts, aby wygenerować pliki do testowania:
foo@WDP:~$ py scipts/test_generator.py other/power_of_two.csv power_of_two.c
Jeżeli masz bardziej skomplikowany program, który przykładowo wymaga wskazania headera podczas kompilacji, możesz samodzielnie skonfigurować cały proces w .github/workflows/ci_pipeline.yml. Najlepiej, jeśli testy wrzucisz wtedy do folderu tests/manual.
Szczególnie jeśli chcesz ręcznie skonfigurować testy, możesz potrzebować skorzystać ze skryptów. Wszystkie znajdują się w folderze scripts.
Skrypt compiler.py kompiluje kod napisany w C (z restrykcyjnymi opcjami configs/options) lub w C++ (z configs/optionsCpp).
foo@WDP:~$ py scipts/compiler.py src/power_of_two.c
foo@WDP:~$ py scipts/compiler.py src/power_of_two.cpp
Skrypt tester.py uruchamia podaną liczbę testów dla danego pliku. Uwaga! Należy podać numer ostatniego testu (czyli o jeden mniej niż jest testów, bo numerację zaczynamy od zera). Jeżeli chcesz przetestować program power_of_two i mamy testy (pliki .IN i .OUT w folderach odpowiednich dla rozszerzenia) o numerach 0, 1, 2, to napisz:
foo@WDP:~$ py scipts/tester.py src/power_of_two.c 2
foo@WDP:~$ py scipts/tester.py src/power_of_two.cpp 2
Jeżeli nasz kod wymaga niestandardowej kompilacji i testy do niego znajdują się w folderze tests/manual, wtedy napisz:
foo@WDP:~$ py scipts/tester.py src/power_of_two.c 2 manual
Skrypt test_detector.py służy do automatycznego wykrywania testów i najlepiej zrozumieć jego działanie, zaglądając do .github/workflows/ci_pipeline.yml.
Skrypt space_to_underscore.sh zamienia spacje na znaki podkreślenia w folderze problems.