Témata zápočtových programů

Verze 3.0 (2023-11-11)

Martin Mareš & Jirka Kalvoda

Toto je seznam nápadů na různá drobná programátorská dílka, vhodná například jako zápočtové programy z Programování 1/2 na Matfyzu. Není nijak závazný (aspoň na našich cvičeních určitě ne), spíš by měl posloužit jako inspirace pro vaše vlastní nápady. Budeme jedině rádi, když přijdete s něčím novým.

U každého tématu je uveden odhad obtížnosti od nuly do devíti. Pozor, stupnice je logaritmická a silně subjektivní. Často jsou zmíněna i různá rozšíření tématu, která pochopitelně obtížnost zvyšují.

Knihovny funkcí

Matice (5): Implementace běžných operací s maticemi (sčítání, násobení, inverze, determinant, LUP-dekompozice) použitím efektivních algoritmů. Doporučuji nahlédnout do knihy L. Kučery a J. Nešetřila Algebraické metody diskrétní matematiky.
Dlouhá čísla (5): Implementace běžných operací s dlouhými čísly (sčítání, odčítání, násobení, dělení, umocňování, vstup a výstup v libovolné číselné soustavě) efektivními algoritmy. Viz též Donald Knuth: Seminumerical algorithms (The Art of Computer Programming, Volume 2).
Reziduová aritmetika (6): Podobně jako předchozí téma, ale čísla reprezentujte pomocí reziduí: zvolí se n navzájem různých prvočísel a každé číslo se zapíše jako vektor zbytků po dělení těmito prvočísly. Výhody: extrémně efektivní sčítání, odčítání a násobení – vše po složkách; nevýhody: obtížný převod do tohoto tvaru a zpět, jakož i dělení. Opět viz Knuth.
Stromy (5): Implementace operací s vyváženými vyhledávacími stromy (např. AVL, červeno-černými nebo 2-3): Insert, Delete, Find, FindMin, FindMax, Next.
Ozdobené stromy (6): Stromy jako v předchozím tématu, ale rozšiřitelné o uložení pomocných hodnot ve vrcholech. Uživatel knihovny dodá, co se má do vrcholů ukládat a jak to počítat z hodnot v synech. Možné aplikace: k-tý nejmenší prvek, součet hodnot přes interval klíčů, případně i líné aktualizace.
Grafy (5): Knihovna pro práci s grafy orientovanými a neorientovanými (a třeba také s multigrafy nebo hypergrafy) – definuje si nějaké rozumné uložení grafu v paměti (třeba pole vrcholů a seznamy hran z vrcholů vycházejících) a nabízí funkce pro běžné grafové operace (např. hledání nejkratší cesty, minimální kostry, komponent souvislosti, topologického uspořádání, největšího párování apod.).
Databáze (5): Jednoduchá databázová knihovna organizující záznamy, které se skládají z klíče a hodnoty (vesměs libovolných délek). Záznamy jsou uložené v souboru na disku a knihovna nabízí efektivní (tj. v logaritmickém čase) přidávání a odebírání záznamů, a hlavně vyhledávání podle klíče. Na to se hodí například hešování nebo (a,b)-stromy. Dalším rozšířením může být třeba jednoduchý dotazovací jazyk.

Hledání hrubou silou (vhodně usměrněnou)

Optimal sorting (5): Generátor třídícího algoritmu pro N prvků, který používá minimální možný počet porovnání. Viz Donald Knuth: Sorting and Searching (The Art of Computer Programming, Volume 3).
Křížovky (6): Generátor křížovek – zadáte slovník a velikost křížovky, případně obrazec a nějaké požadavky na pevné rozmíštění rozdělovacích znamének a program vygeneruje nějakou křížovku z daných slov v daném obrazci. Další nápady: požadavky na symetrii obrazce a „rozdělítek“ (u klasických křížovek to je zvykem, stejně tak se v nich nesmí vyskytovat jedno slovo vícekrát, byť s různou legendou), ornamentální, slabikové, střídavé a jiné křížovky, výstup hotového obrazce v PDF.
Sudoku (5): Vytvoří Sudoku zadané obtížnosti (míra obtížnosti je nutně heuristická, její stanovení je součástí úkolu). Možná rozšíření: hexadecimální sudoku, KenKen, součtové sudoku.
Skoky po šachovnici (3): Programu dáte definici zobecněné šachové figurky (to jest nějak popíšete, jak se daná figurka může pohybovat; inspirace zde), velikost šachovnice a souřadnice počátečního políčka. Program zjistí, zda a jak je možno touto figurkou „obskákat“ celou šachovnici (to jest navštívit každé políčko právě jednou) a skončit přesně tam, kde jsme začali.
Polyomino (4): Pentomino je tvořeno obrazci složenými z pěti jednotkových čtverečků, které sice nemusí být konvexní, ale musí být souvislé a bez děr. Napište program, který nalezne všechny obrazce skládající se z n čtverečků. Obrazce lišící se pouze otočením nebo zrcadlením se za různé nepovažují. (Pro n=15 existuje 3 001 127 obrazců, zkuste je najít.)
Skládačka (4): Jsou zadány dílky složené z jednotkových čtverečků (třeba ty z předchozí úlohy) a máte zjistit, zda z nich je možno složit obdélník dané velikosti. Dílky je možno otáčet a překlápět.
IQ! (5): Řešítko na klasické IQ-testové úložky typu „doplňte následující posloupnost“. Mělo by znát běžné finty (sčítání a násobení předchozích členů, prvočísla apod.) a možná si též vést katalog již známých posloupností a odvozovat nové z nich.

Geometrie

Mnohostěny (5): Polopravidelný mnohostěn je konvexní těleso, jehož všechny stěny jsou tvořeny dvěma typy shodných pravidelných mnohoúhelníků a ve všech vrcholech se stýká stejný počet hran. (Každé pravidelné těleso je tedy současně polopravidelným.) Napište program, který dostane na vstupu parametry tělesa (typy a počty stěn a stupně vrcholů) a poté těleso zobrazí buďto v nějakém rozumném průmětu nebo jako rovinnou síť (dle vašeho výběru).
Mongeovský invertor (7): Určitě všichni znáte Mongeovo promítání – to je takové to promítání trojrozměrných objektů na 3 kolmé průmětny (nárys, půdorys, bokorys), které použivají strojaři a architekti. Opačná úloha je ale zajímavější: dostanete zadané všechny tři průměty nějakého tělesa a program má toto těleso zkonstruovat (často bude existovat více variant, tehdy stačí objevit jednu).

Fyzika

Problém mnoha těles (4): Program simulující pohyb N těles navzájem na sebe působící gravitační silou. Grafický vstup, editor na polohy těles, proměnlivá rychlost simulace a velikost kroku.
Sky Globe (4): Hvězdná mapa. V souboru jsou uloženy polohy hvězd na nebeské sféře (v rovníkových souřadnicích), program dostane zadané místo na Zemi, datum a čas a zobrazí oblohu tak, jak je v daný okamžik vidět. Další nápady: korekce na atmosférickou refrakci, paralaxu, precesi a nutaci, počítání východů a západů hvězd, kreslení hranic a tvarů souhvězdí atd.
Heliocentrický simulátor (4): Simulace pohybu planet ve sluneční soustavě a zobrazení v ekliptikálních souřadnicích (to jest něco jako pohled shora). Výpočet poloh planet buďto podle Keplerových zákonů nebo přímo z Newtonových zákonů simulací problému N těles. Další nápady: proměnlivost dráhových elementů v čase (vzorce dodám), dráhy komet.
Geocentrický simulátor (5): Simulace pohybu planet, ale s pohledem z daného místa na Zemi v daný okamžik. Též může počítat východy, průchody poledníkem a západy. Viz předchozí dvě úlohy.
Kmitání (3): Simulace harmonických oscilátorů (tlumené kmity, resonance apod.).
Chemické rovnice (5): Vyčíslování chemických rovnic – uživatel zadá reakci (ve standardní notaci) a program dopočítá, kolikrát se který reaktant a produkt v rovnici má objevit, aniž by se ztrácela či naopak materializovala hmota.
Čočky (5): Simulace optických soustav – uživatel zadá systém čoček a zrcadel a program spočítá průchod paprsků tímto systémem (nebo třeba pohled tímto systémem na obrázek umístěný v nějkém bodě). Možná rozšíření: částečné odrazy, polopropustná zrcadla, disperze světla ...
Malý dráteník (5): Stavebnice elektrických obvodů – uživatel si ze základních součástek a vodičů vytvoří elektrický obvod a program simuluje jeho činnost. V jednoduché variantě třeba pouze digitální obvody (hradla, klopné obvody, zdroje signálů a indikátory), složitěji třeba obvody analogové s odpory, kondenzátory, cívkami a transistory.
Orloj (5): Simulátor orloje, třeba toho staroměstského.

Interprety, kompilátory a programovací nástroje

Basic (6): Interpret rozumné podmnožiny jazyka Basic (nebo nějakého jiného jednoduchého programovacího jazyka dle vlastního výběru).
LISP (6): Interpret nějakého dialektu LISPu: čtení a vypisování LISPovských objektů, interpretace (tedy vlastně funkce eval), garbage collector.
Simulátor CPU (5): Program pro simulaci nějakého jednoduchého procesoru (vhodnými příklady jsou např. ARM, AVR nebo RISC-V, ale můžete si vymyslet i procesor vlastní). Tedy program, který načte program ve strojovém kódu příslušného procesoru a poté jej provádí a umožňuje si nechat vypisovat, co se zrovna děje (obsah registrů a paměti plus právě prováděné instrukce). K této úloze existuje spousta různých zajímavých vylepšení: implementace vstupu v assembleru, „vyspělejší“ debugger (podporující podmíněné breakpointy apod.), simulování okolního hardwaru (kupříkladu řadič přerušení, časovače a nějaké porty) či memory manageru.
Simulátor paralelního počítače (6): Simulace paralelního počítače na bázi předchozí úlohy, tentokráte již ovšem značně zjednodušující reálný svět. Dodefinujeme instrukce pro práci se zámky (init, lock, unlock; zámek je dán svou adresou v paměti), ve speciálním registru je pevně uloženo číslo procesoru, všechny procesory mají sdílenou paměť (nesmí jich ovšem zapisovat v daném okamžiku více na touž adresu či na ni jeden zapisovat a jiný z ní číst). Simulátor načte program v assembleru resp. strojovém kódu a simuluje jeho běh na všech procesorech současně včetně detekce kolizí přístupů k paměti a detekce vzniku deadlocku (procesy vzájemně čekající na uvolnění zámků).
Compiler 1 (5): Kompilátor výrazů (syntaxí podobných Pythonu) do instrukcí nějakého procesoru (viz předchozí témata).
Compiler 2 (7): Kompilace nějakého jednoduchého vyššího jazyka do instrukcí nějakého procesoru (viz předchozí témata). Možno implementovat některé základní optimalizační techniky (což může dát úlohu obtížnosti až 9).
Compiler 3 (8): Kompilace nějakého jednoduchého vyššího jazyka (viz předchozí úloha) s rozumným využitím paralelismu. Opět možnost optimalizací.
The Last Optimizer (6): Odvěkým snem všech programátorů je překladač, který k danému programu najde nejkratší možnou posloupnost instrukcí procesoru, která dělá totéž. To bohužel není algoritmicky řešitelné. Ale zkusme si to zjednodušit: omezíme se na programy bez cyklů (skoků dozadu), maximálně 20 instrukcí zdrojového programu a maximálně 10 cílového. Budeme generovat všechny kombinace instrukcí od nejkratších a heuristicky porovnávat, jestli programy dělají totéž (na náhodných vstupech).
Indent (6): Program pro formátování zdrojových textů ve vašem oblíbném jazyce. Automatické odsazování podle blokové struktury programu, formátování a správné umísťování komentářů. Viz například UNIXový program téhož jména.
Hledač funkcí (6): Ve zdrojáku ve vašem oblíbeném jazyce najde definici všech funkcí, proměnných, tříd apod. zadaného jména. Dá se doplnit o interaktivní rozhraní umožňující rovnou z editoru vyhledávat odkazy na jméno právě se nacházející pod kurzorem, nebo třeba přejmenovat funkci včetně všech jejích volání.

Interaktivní programy

Textový viewer (3): Jednoduché „prohlížítko“ na textové soubory. Zadá se mu jméno souboru a ono nechá uživatele listovat si obsahem souboru. Nechť podporuje posun doleva, doprava, nahoru i dolů, jakož i po stránkách a hledání řetězce v souboru a nezalekne se netištitelných znaků ani milionu řádků.
HTML viewer (5): Program na prohlížení dokumentů v jazyce HTML, včetně „inteligentního“ formátování odstavců, seznamů apod. Možno přidávat spoustu funkcí a dotáhnout to až na webový prohlížeč ...
Markdown viewer (5): Program na prohlížení dokumentů v jazyce Markdown, včetně „inteligentního“ formátování odstavců, seznamů apod.
Textový editor (5): Jednoduchý textový editor na soubory, které se celé vejdou do paměti (ovšem bez omezení na počet řádků či délku řádku!). Běžné editační funkce: pohyb v textu, pohyb po slovech, delete slova či řádku, skok na řádek daného čísla, hledání a nahrazování textu, save, load, operace s bloky. (Dále třeba formátování odstavců, automatické odsazování, makra, ...)
Editor binárních souborů (5): Jednoduchý editor binárních souborů. Zobrazení i editace jak v šestnáctkové soustavě, tak po znacích. Vkládání a mazání bajtů, kopírování a přesun bloků. Možná rozšíření: interpretace vícebajtových hodnot (integery, floaty, UTF-8), práce se soubory, které se nevejdou do paměti.
Twilight Commander (5): Něco jako Midnight Commander – to jest něco, čemu se z příčin, které jsou dosud předmětem vyšetřování, v českých zemích říká souborový manažer. Konkrétněji: program poskytující komfortní rozhraní k operacím se soubory a adresáři. Další nápady: jak najít, které části stromu zabírají hodně místa, nebo třeba jsou přístupné danému uživateli?
Blbenka čili inteligentní diář (3): Připomínátko (jinak též reminder alias blbenka) je program, kterému píšete seznam událostí spolu s časy, kdy mají nastat (tedy takový plánovací kalendář) a ono vám je s volitelným předstihem připomíná (můžete si jej třeba spouštět každý den při zapnutí počítače). Spousta možností k rozšíření: periodické události (to jsou třeba narozeniny vašich bližních), zadávání pomocí parametrů (např. „každý pátek třináctého“ nebo „každé úterý v 10:30“), triggery (přednastavíte si událost typu „vyndat oběd z trouby“, která se objeví 5 minut po spuštění, přičemž ji pak v libovolném okamžiku můžete třeba stiskem nějaké předem přiřazené klávesy spustit; to je taková zobecněná minutka), deník (můžete připomínátku psát, kdy jste na čem pracovali, a ono vám pak spočítá, kolik času jste čím strávili).
Kdy my tři sejdeme se (5): ... v dešti a hromobití? Tak se ptaly čarodějnice v Macbethovi a my jim zkusíme pomoci programem na domlouvání schůzek. Program si pro každého uživatele eviduje jeho časové možnosti (například to může být založeno na diáři z předchozí úlohy) a kdokoliv má možnost pozvat ostatní na dostaveníčko a prostřednictvím programu se s nimi dohodnout na termínu schůzky. Také by z toho mohla být pěkná webová aplikace.
Notičky (6): Editor notových zápisů (noty, pomlky, ligatury, takty, slova písně etc.), třeba i se zvukovým výstupem. Nápady: Automatická harmonizace v zadané stupnici.

Grafika

Kreslítko (5): Program pro kreslení bitmapových obrázků. Základními operacemi jsou kreslení bodů, čar a kružnic, nastavování barev a tlouštěk čar a načítání a ukládání obrázků v nějakém standardním formátu (třeba PNG). Další funkce: vyplňování oblastí, práce s bloky, filtry, volitelné zvětšení, editování obrázků větších než obrazovka, psaní textu, transparentní a polotransparentní barvy, zvětšování, zmenšování a otáčení obrázků.
Vektorové kreslítko (6): Opět kreslící program, tentokráte na obrázky vektorové, tj. skládající se z úseček, křivek (například Bézierových) a šrafovaných ploch a nezávislé na rozlišení výstupního zařízení (tak se vytváří například většina obrázků v knížkách, pokud to zrovna nejsou reprodukce fotek). Definice vlastních grafických prvků pomocí prvků elementárních a dříve nadefinovaných; práce se symetriemi, snapping (když uživatel ukáže „někam do neznáma“, vybrat si nejbližší významný bod (vrchol, průsečík, řídící bod křivky, bod mřížky apod., tak, jak uživatel nastaví), export do SVG nebo PDF.
Editor na grafy (5): Program pro interaktivní editaci orientovaných i neorientovaných grafů. Ukládání do souboru v rozumném formátu (seznam vrcholů a hran či něco podobného) a načítání zpět. Ovladatelné klávesnicí i myší.
Chytrý editor na grafy (8): Grafový editor, který navíc umí najít hezké nakreslení grafu. Podporuje víc různých druhů nakreslení: minimalizaci počtu křížení, kreslení stromů atd. Export výstupu do SVG nebo PDF.
Grafy funkcí (5): Uživatel zadá funkci, program nakreslí její graf, přičemž inteligentně zvolí měřítko a popíše osy. Manuální ovládání – zoom vybrané části grafu apod. Rozšíření: trojrozměrné grafy (funkcí dvou proměnných nebo třeba komplexních funkcí).
Interaktivní geometrie (5): Program, který na základě popisu v nějakém jednoduchém jazyce (vzpomínáte si na zápisy konstrukce ze základní školy?) provádí rovinné geometrické konstrukce ze zadaných bodů a zobrazuje je. Mohl by také dovolit uživateli, aby myší pohyboval zadanými body a sledoval při tom, jak se výsledek mění.
Interaktivní stereometrie (7): Trojrozměrná verze předchozí úlohy.
Interaktivní hypergeometrie (8): N-rozměrná verze předchozích dvou úloh. Zkuste vymyslet vhodné promítání, ve kterém by se daly rozumně pozorovat alespoň čtyřrozměrné, lépe i vícerozměrné objekty.
Alternativní geometrie (7): Ne každá geometrie je euklidovská – existují i jiné, třeba sférická (ta se odehrává na sféře, tj. povrchu koule) a hyperbolická (tu potkáte např. v horských sedlech). Jsou v mnohém podobné, ale třeba úhly v trojúhelníku mohou v takové geometrii dát dohromady klidně více (ve sférické) nebo méně (v hyperbolické) než 180 stupňů. To je na první pohled velice neintuitivní, ale kupodivu mnoho matematických i fyzikálních teorií (za všechny jmenujme alespoň obecnou teorii relativity) se snadno popisuje právě v takovýchhle „divných“ geometriích, a tak stojí za to si (třeba právě na interaktivním počítačovém simulátoru) chování sférického nebo hyperbolického světa osahat.
Interpolace křivkami (3): Mějme N bodů v rovině. Program je zobrazí a proloží jimi nějakou pěknou křivku. To může být třeba polynom zadaného stupně (nalezený metodou nejmenších čtverců), spline křivky nebo křivky z Bézierových segmentů (B-splines). Ruční pohybování body za současného překreslování proložené křivky není rozhodně na škodu.
Formuláře (6): Program pro vyplňování formulářů a podobných lejster: dostane oskenovaný formulář, najde si v něm čáry a podle nich kolonky, nechá uživatele kolonky upravit a popsat a výsledek si uloží jako šablonu, do které pak půjde doplňovat data a tisknout tak, aby vyšla přesně do kolonek na papíře.

Matematika

Faktorizátor (5): Rozklad velkých čísel na součin prvočísel chytrými algoritmy. Viz Donald Knuth: Seminumerical Algorithms (The Art of Computer Programming, Volume 2).
Kalkulačka (4): Vyhodnocování výrazů s běžnými operacemi včetně základních funkcí (sin, cos, ln, exp, sqrt atd.), závorek a předností operátorů. Pozor na správné ošetření chyb (dělení nulou apod.).
Programovatelná kalkulačka (5): Kalkulačka, v níž si uživatel může definovat vlastní funkce a operátory, případně i typy (to znamená například komplexní čísla či kvaterniony, nebo dokonce zlomky a intervaly).
Úpravy výrazů (7): Program na operace s výrazy (zjednodušování, roznásobování a derivování). Nejlépe interaktivně; záhodno spojit s kalkulačkou.
Lineární rovnice (3): Řešení soustav lineárních rovnic (zadaných textově, ne pouze jako matice).
Nelineární rovnice (6): Řešení nelineárních rovnic a jejich soustav, například nějakou šikovnou numerickou metodou.
Kostkové vzorce (5): V mnoha hrách na hrdiny se objevují vzorce typu XdY. To znamená „Vezmi kostku o Y stěnách, X-krát s ní hoď a výsledek sečti.“ Jednoduchý vzorec stylu 2d4, 3d6+1, 2d10+1d20-5 se ještě dá pochopit a odhadnout, ale jak se chová vzorec (2d3-2)d(3d2), to už se určuje opravdu těžko. Napište program, který na vstupu přečte takovýto vzorec (s operátory +-,*,d v tomto pořadí priorit vzestupně, pro machry i dělení) a vypíše pro každý možný výsledek pravděpodobnost, s jakou nastane.

Jazyky a texty

Rozpoznání jazyka (4): Rozhodnutí, v jakém jazyku (řekněme z pěti známých) je zadaný text. Statistické metody (pravděpodobnosti výskytu dvojic znaků nebo něco podobného).
Markovovské texty (4): Generování náhodného textu napodobujícího text zadaný (řekněme se stejnými pravděpodobnostmi výskytu znaku v závislosti na předchozích k znacích). Případně totéž pro slova. [Lze též řešit způsobem připomínajícím Huffmanovu kompresní metodu, na požádání předvedu.]
Spelling Checker (5): Kontrola textu za pomoci slovníku známých slov. Interaktivní mód umožňující online doplňování do slovníku včetně uvedení skloňování slova (jako vzor je možno uvést libovolné již známé slovo). Důraz se klade na rychlost. Pokud objeví překlep, zkusí najít nejbližší známá slova.
Špión (5): Luštění tajných abeced. Je zadán text (poměrně dlouhý a ve znamém jazyce) zašifrovaný neznámým šifrovacím algoritmem (z nějaké dostatečně jednoduché skupiny šifer, řekněme těch, které nahrazují každý znak pevně zvoleným znakem nezávisle na tom, kde se v textu vyskytl – tj. změna abecedy) a náš program na základě známých statistických vlastností jazyka (např. pravděpodobnosti výskytu jednotlivých písmen a dvojpísmenných kombinací) nalezne nejpravděpodobnější znění původního textu.
Zlutoucky kun (5): Program se natrénuje na velkém množství textů a pak bude do textů bez diakritiky doplňovat háčky a čárky.
Slabiky (4): Rozklad českého textu na slabiky (to se hodí třeba při sázení zpěvníku).
Regulární vyhledávač (5): Najde v textu všechny podřetězce, které vyhovují zadanému regulárnímu výrazu. Program by měl mít i v nejhorším případě polynomiální časovou složitost s velikostí textu i délkou regulárního výrazu.

Hry (proti počítači)

Pišqorky (4): Klasická hra piškvorky. Statické ohodnocování možných tahů včetně možné reakce soupeře.
Pišqorky 2 (5): Chytřejší implementace hry piškvorky – prohledávání stavového prostoru hry na zadaný počet tahů dopředu, minimaxový algoritmus založený na statickém hodnocení pozic překračujících hloubku prohledávání. Rozšíření: kešování už ohodnocených pozic, vícerozměrné piškvorky, piškvorky tvůrce-ničitel (jeden hráč se snaží vytvořit k-tici svých kamenů, druhý mu v tom svými kameny brání).
Reversi (5): Hra Reversi má následující pravidla: Hraje se na klasické šachovnici, na počátku jsou uprostřed hracího plánu položeny dva černé (na D4 a E5) a dva bílé (na E4 a D5) kameny. Hráči se střídají v pokládání kamenů své barvy, při položení kamene na dané políčko se všechny nově vzniknuvší kombinace (v řádku, sloupci či úhlopříčce) dvou kamenů právě táhnoucího hráče, mezi nimiž jsou (bez prázdných políček) kameny druhého hráče, přebarví na barvu táhnoucího hráče. Položení kamene, po kterém by nenásledovalo žádné přebarvení, není dovoleno. Hra končí, nemůže-li hráč, který je zrovna na tahu, nikam položit další kámen. Vyhrává ten, komu patřilo na konci hry více kamenů.
Reversi 2 (7): Chytrý algoritmus na Reversi – prohledávání na více tahů do hloubky, keš zabraňující zbytečnému přepočítávání stejné situace vícekrát, normalizace situací zabraňující opakovaným výpočtům ekvivalentních situací (všimněte si, že situace lišící se jen otočením, zrcadlením a několika dalšími transformacemi šachovnice jsou ekvivalentní).
Exploding Atoms (5): Hra se hraje na normální šachovnici. Na každém políčku je jedno atomové jádro, které může patřit jednomu z hráčů a mohou kolem něj obíhat elektrony. Na počátku hry nepatří žádné jádro nikomu a nikde nejsou žádné elektrony. Hráči se střídají, v každém tahu jeden z nich přidá elektron k některému ze svých atomů, případně k atomu dosud neobsazenému (který si tím přivlastní). Pokud tak počet elektronů dosáhne kritického množství (to je rovno počtu sousedů daného atomu, tedy 2 pro rohové atomy až 4 pro vnitřní), atom exploduje a jeho elektrony se rozletí do všech směrů k sousedním atomům, které tak rovněž připadnou táhnuvšímu hráči a případně také explodují atd. Hra končí, přijde-li jeden z hráčů o všechny své atomy (tím prohraje), případně dojde-li k zacyklení explozí (remíza, může vůbec nastat?). [Podobnost s fyzikálními zákony, pokud nějaká existuje, je čistě náhodná.]
Exploding Atoms 2 (7): Lepší strategie na předchozí hru prohledávající na více tahů do hloubky a používající keš a transformace.
Logik (5): Známá hra logik. Hra je parametrizována dvěma čísly: počet pozic N (typicky 5) a počet barev M (typicky 8). První hráč na počátku zvolí nějakou N-prvkovou kombinaci daných barev (mohou se i opakovat), druhý se ji snaží uhodnout. V každém tahu druhý hráč navrhne nějakou kombinaci barev a první mu na ni odpoví dvěma čísly: počet správně uhodnutých pozic a počet barev, které sice v utajované kombinaci jsou, ale na jiném místě (tedy například je-li tajná kombinace 12321 a druhý hráč hádá 14212, je odpověď 1/3). Od programu se očekává, že pro typické zadání bude schopen do deseti tahů a jedné minuty problém vyřešit.
Mefisto (5): Táž hra, jako v předchozí úloze, tentokráte ovšem z pozice druhého hráče, který podle využívá toho, že jej nikdo nenutil, aby na začátku hry přiznal, co přesně zadal za kombinaci, a tak si nějak udržuje přípustné kombinace (to jest takové, které nejsou vyloučeny tím, jak v průběhu hry odpovídal) a vždy odpovídá nejškodoliběji, jak jen může (to jest snaží se co nejvíce hru protahovat a soupeře vhánět do úzkých).
Hangman (3): Pravidla: program hádá slovo (za pomoci slovníku), jehož délka je předem známa. V každém tahu navrhne jedno písmeno a protihráč mu odpoví, kde všude se v hádaném slově vyskytuje. Čím méněkrát se splete, tím lépe.
Life (3): Simulace života buněk. Je dán čtvercový životní prostor a v něm jsou buňky, které se vyvíjí v závislosti na svém okolí (např. buňka přežije do další generace, pokud má alespoň dva sousedy a naopak na prázdném políčku může vzniknout buňka, má-li více jak dva živé sousedy). Na vstupu je počáteční rozložení buněk a nějaká pravidla vývoje (buďto mezní počty pro přežití a množení nebo dokonce něco složitějšího v závislosti na rozsáhlejším okolí) a program pak simuluje generaci po generaci vývoj v celém prostoru. Další náměty: definování maximálního stáří buňky či třeba zkusit množící se buňky použít na řešení nějaké praktické úlohy (sčítání dvou čísel je krásný příklad); je zde spousta prostoru k optimalizacím pomocí bitových operací.
Lloydova Patnáctka (4): Další ze série poněkud antikvitních her. V krabičce velikosti 4 krát 4 se vyskytuje 15 jednotkových čtverečků (očíslovaných 1 až 15) a jedna unikátní jednotková díra. Cílem je posouváním (v daném kroku lze vždy na místo díry posunout libovolný sousední čtvereček, čímž vznikne další díra [nebo se ta stávající posune?]) čtverečky srovnat tak, aby čteno po řádcích byly očíslovány vzestupně.
Lloydova 255ka? (6): Různé další variace na předchozí téma – vícerozměrná patnáctka, třeba i hyperkvádrová, patnáctka na anuloidu (to jest konce krabičky jsou slepeny k sobě), patnáctka na Möbiově proužku atd.
Šachové úlohy (5): Řešení šachových úloh typu „je dána tato pozice, bílý táhne a dá třetím tahem mat“.
Vláčky (6): Simulátor železnice. Hráč si vytvoří kolejiště (tratě, výhybky, návěstidla, zastávky) a pak si po něm může pouštět vláčky (některé mohou třeba jezdit automaticky podle přednastavených jízdních řádů). Další nápady: simulace zabezpečovacího zařízení s automatickými návěstidly.
Code Wars (7): Souboj robotů. Každý z hráčů si naprogramuje v nějakém jednoduchém jazyce svého robota a poté jsou roboti vypuštěni do předem připraveného prostředí Každý z nich se začne chovat podle svého programu a jeho cílem je zničit všechny soupeřovy roboty – kdo přežije, vyhrává.
Člověče, nezlob se (4): Počítačová verze známé deskové hry.
Pexeso (4): Opět klasická desková hra: v rovině jsou rozmístěny kartičky obrázkem dolů, každý obrázek se vyskytuje právě dvakrát. Hráč, který je právě na tahu, otočí dvě kartičky. Pokud je na nich tentýž obrázek, obě získává, odebírá ze hry a otáčí další dvojici; pokud obrázky různé, otáčí je zpět a pokračuje další z hráčů. Hra končí, když jsou uhodnuty všechny páry obrázků; vyhrává ten hráč, který jich nasbíral nejvíce. Hra proti počítači by měla mít nastavitelnou obtížnost, která bude určovat pravděpodobnost, že počítač zapomene už jednou zpozorovaný obrázek.
Matfyzácké Pexeso (4): Pexeso, v němž když hráč otočí dvě různé kartičky, vrací je zpět v opačném pořadí.
Deflektor (5): Hra se hraje v bludišti, ve kterém je rozmístěn laser, terč a několik zrcadel. Cílem hráče je před uplynutím časového limitu otočit zrcadly tak, aby se paprsek z laseru trefil do terče; stěny místnosti mohou světlo buďto pohlcovat nebo naopak odrážet. Varianta pro dva hráče: Každý hráč má svůj terč, který má zasáhnout, hráči si otáčením zrcadel paprsek navzájem „kradou“.
Červi (5): Hra pro n hráčů, z nichž každý ovládá jednoho červa. Všichni červi lezou bludištěm, ve kterém jsou rozmístěny kousky jídla a jedu. Na počátku má každý červ délku jedno políčko, když objeví jídlo (tj. dolezou na políčko, na kterém nějaké je), prodlouží se o další políčko. Když červ sežere jed, narazí do zdi nebo do libovolného červa (včetně sebe sama), vypadává ze hry. Ovládání: Pro každého hráče nezávislé klávesy pro zatočení doleva a doprava. Rozšíření: Síťová verze.
Férové miny (5): Implementace klasického minesweeperu se dvěma vlastnostmi navíc: Pokud uživatel, soudě dle stavu hrací plochy, nemohl mít ani u jednoho políčka jistotu, že na něm mina není (např. vždy na začátku hry), mina po odkrytí libovolného políčka na tomto políčku není. Naopak pokud uživatel mohl mít jistotu, že na některém políčku mina není, a přesto odkryl políčko, u nějž tuto jistotu mít nemohl, mina na něm je.
Puzzle (5): Rozřeže obrázek na různě tvarované dílky a nechá si ho složit.
Tantrix (6): Strategie na hru Tantrix.

Soubory

Duplikáty (4): Program prohledávající disk a zkoumající, jestli nějaké dva soubory nemají tentýž obsah (a to nějakou lepší metodou než je porovnávání každého souboru s každým).
Domácí úkoly (6): Program prohledávající disk a zobrazující podobné soubory (rozumné kriterium podobnosti souborů stanovte sami – dva textové soubory lišící se přidáním či změnou několika málo řádků zaručeně podobné jsou). Můžete předpokládat, že soubory jsou poměrně velké (aspoň desítky kilobytů) a změny poměrně řídké.
Diff (4): Nalezení rozdílů mezi dvěma textovými soubory. Výstup by měl obsahovat informace typu „zde vloženo těchto pět řádků, tamhle vymazáno těchto šest, onde změněn jeden“.
Komprese (5): Implementace nějakého pěkného (ať již klasického či vlastní provenience) kompresního (a k tomu též dekompresního) algoritmu.
Hledej, Šmudlo! (6): Program, který vyřeší odvěký problém zmatku na disku. Bude umět hledat soubory podle zadaných kriterií – součástí jména, data poslední změny, textu uloženém v souboru atd. A aby to zvládl rychle, sám si soubory čas od času projde a z objevených dat si vytvoří nějaký jednoduchý index. Bylo by pěkné, kdyby uměl volat externí programy pro převádění různých formátů souborů (třeba PDF) na text.
Poštovní skřítek (6): Hledání mailů podle různých kriterií: stáří zprávy, předmět, odesílatel a příjemci, příslušnost do vlákna, existence odpovědi, velikost a typy příloh apod. Rozšíření: Udržování indexů na zrychlení běžných typů dotazů, aktualizace indexů, když přijde nový mail.

Různé aneb co se jinam nevešlo

NetMapper (7): Program na mapování sítí – prostřednictvím různých protokolů si „očuchá“ topologii sítě a v přehledné formě ji vypíše, respektive nakreslí. (Může zahrnovat spoustu zajímavých věcí včetně odhadování propustnosti linek na základě závislosti zpoždění na velikosti paketů.)
JunkBuster (6): Heuristický analyzátor e-mailů snažící se uhodnout (s co největší úspěšností, pochopitelně), které maily jsou nesmyslné reklamy a které nikoliv. Nejlépe adaptivní algoritmus schopný zkonstruovat si rozpoznávací pravidla sám, je-li mu poskytnut velký archiv s příklady reklamních a smysluplných mailů. Nabízí se celá řada triků z nejrůznějších oblastí, počínaje jednoduchým vyhledáváním podezřelých slov a frází v hlavičkách i těle mailu, konče třeba učením neuronových sítí.
Akordy (4): Generátor kytarových akordů – pro akord zadaný jménem vymyslí, ze kterých tónů se skládá a nalezne všechny rozumné možnosti, jak jej na kytaru zahrát.
Jede vláček motoráček... (6): Hledání optimálního spojení v železniční síti nebo třeba v městské hromadné dopravě [nezapomeňte, že ve všech našich městech jezdí i pěškobus]. Existuje spousta možností, jak si hledátko vylepšit: například optimalizace na dobu jízdy, dobu čekání [na cesty v zimě], počet přestupů [pokud jste proflámovali noc] nebo nějakou míru pohodlí.