Druhá série třicátého šestého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Řešení úloh

• 36-2-1: Fronty na poště
• 36-2-2: Záchrana mravenců
• 36-2-3: Ztracená bunda
• 36-2-4: Nejlepší programovací jazyk, část II.
• 36-2-S: Chození po gradientu

36-2-1 Fronty na poště (Zadání)

Pro začátek si všimněme, že chceme přijít na poštu těsně před tím, než přijde jiný zákazník. Kdyby tomu tak nebylo, tak jednoduše můžeme přijít o jednotku času později a zkrátit si tím čas čekání.

Co se stane, když přijdeme na poštu před zákazníkem i, oproti tomu, kdybychom na poštu nepřišli? Úředník ve frontě 0 místo původního zákazníka pošle do fronty nás. Zákazník za námi potom skončí ve stejné frontě jako původně zákazník za ním a tak dál. To, co se původně dělo zákazníkovi j (pro j ≥ i), se nyní děje zákazníkovi j+1, a my nahrazujeme zákazníka i.

A tedy všichni před zákazníkem i zůstávají nezměněni. Pozor, toto funguje jenom díky tomu, že zákazníci nebudou nikdy posláni zpět do fronty 0. Např. pro:

1 7
3 N
4 N
5 N
6 P
0 0
7 V
0
8 V
0
9 V
0

To znamená, že když přijdeme před zákazníkem i, tak potom odejdeme v čase, kdy by býval odešel zákazník i, pokud bychom vůbec nepřišli.

Stačí si tedy odsimulovat celý proces na poště bez nás. Po jednotlivých frontách požadujeme, aby se dalo rychle přidat na konec a odebrat ze začátku, takže na to můžeme (překvapivě) použít frontu. Jednotlivé druhy událostí budeme obsluhovat následovně:

• Když přijde nový zákazník, tak ho dáme na konec fronty 0 a poznačíme si, v jakém čase přišel.
• Když je zákazník přesunut, tak ho z fronty j přemístíme do fronty k.
• A když zákazník odejde, tak ho z fronty odebereme a poznačíme si, v jakém čase odešel.

Na konci si spočítáme pro každého zákazníka s vyřízenou žádostí, kolik času na poště strávil, a přijdeme hned před ním. Na poště potom strávíme o tuto jednotku více času.

Simulaci i projití všech zákazníků stihneme v O(N) (kde N je počet událostí). Paměťová složitost bude také O(N).

Program (Python)

36-2-2 Záchrana mravenců (Zadání)

Vyplatí se zachraňovat jen ty mravence, na které něco může dopadnout. Dále když na mravence dopadne jedna šiška, tak je jednodušší ho zachránit, než když na něj dopadnou dvě. Tedy budeme nejprve chtít zachraňovat ty mravence, na které dopadne nejméně šišek.

Jak to spočítat? Naivně můžeme pro každého mravence projít všechny šišky a podívat se, jestli na něj dopadnou. To je ale hodně pomalé, až O(N²S).

Můžeme to vylepšit tak, že použijeme (inverzní) dvourozměrné prefixové součty, ty sestavíme tak, aby nám říkaly, kolik šišek dopadne na každé políčko. V levém horním rohu šišky přičteme 1, v pravém horním rohu šišky 1 zase odečteme (protože tam šiška končí). Taktéž v levém dolním rohu odečteme 1. Jenže takto bychom jedničku pro políčka pod a za šiškou odečetli dvakrát, takže v pravém dolním rohu zase 1 přičteme.

Takto nejprve do prefixových součtů započítáme všechny šišky a posléze z nich vypočítáme, kolik šišek dopadne na každé políčko. Celkem to stihneme v čase O(N² + S).

Nyní, když známe, kolik šišek dopadne na každé políčko, umíme si najít všechna políčka, na která dopadne určitý počet šišek (přihrádkovým řazením). Nejprve budeme krabičky přiřazovat všem mravencům, na které dopadne jedna šiška, pak všem, na které dopadnou dvě a tak dále. Těchto přiřazovacích kroků může být nejvýše K. Také si můžeme všimnout, že přiřazovacích kroků nemůže být víc než N², protože to bychom už zcela jistě zachránili všechny mravence.

Takže celkově nám algoritmus běží v čase O(N² + S).

36-2-3 Ztracená bunda (Zadání)

Značka kuchařkové úlohy napovídá, že můžeme úlohu vyřešit pomocí Dijkstrova algoritmu. Ale jak?

Dijkstrův algoritmus se často představuje v kontextu plánovačů cest. Vrcholy pak představují křižovatky a body zájmu a hrany cesty mezi nimi. Dijkstrův algoritmus však můžeme využít i k řešení obecnějších problémů, které s hledáním nejkratší cesty na první pohled nijak nesouvisí. Stačí, abychom měli nějakou konečnou množinu stavů a různě drahých způsobů, jak mezi nimi přecházet. Poté můžeme pomocí Dijkstrova algoritmu najít způsob, jak se co nejlevněji dostat z jednoho stavu do druhého.

Prvním krokem tedy bude reprezentovat jízdní řády pomocí grafu.

Stav cestujícího se skládá ze dvou hodnot, a to zastávky a času (0:00 – 23:59). Vrcholy tedy budou reprezentovat právě dvojice zastávek a časů. Nemusíme však vytvářet vrcholy pro všechny možné dvojice, stačí ty, kde a kdy se děje něco zajímavého, neboli příjezd nebo odjezd vlaku. Také přidáme vrchol pro čas a místo začátku cesty.

Dále přidáme hranu pro každou akci, kterou může cestující provést. Akce jsou dvou druhů:

• jízda vlakem na další zastávku,
• čekání do dalšího zajímavého času.

Pro každý úsek každého vlaku tedy přidáme hranu vedoucí ze zastávky a času odjezdu do zastávky a času příjezdu. Při cestě vlakem není třeba mrznout na nástupišti, proto bude mít tato hrana nulovou cenu. Dále vrcholy v rámci jedné zastávky pospojujeme do kruhu podle jejich časů. Každé z těchto hran přiřadíme cenu odpovídající rozdílu časů, které spojuje.

Uvažujme například tento jízdní řád:

Jeho graf bude vypadat takto:

Pokud se o vlaky zajímáte, tak vám možná tento graf připomíná grafikon.

Ke každé „vlakové“ hraně si také poznamenáme, jaký je její vlak a cílová stanice, abychom později mohli snadno nalezenou cestu vypsat.

Poté stačí použít Dijkstrův algoritmus, abychom našli nejkratší cestu z počátečního vrcholu do všech ostatních vrcholů. Jirka může dorazit domů v libovolný čas, takže poté projdeme všechny vrcholy v cílové stanici a vybereme z nich ten s nejnižší vzdáleností. Dijkstrův algoritmus nám také ke každému vrcholu určí seznam hran, po kterých se do něj dostaneme co nejkratší cestou. Projdeme tedy nejkratší cestu do zvoleného cílového vrcholu a vypíšeme informace o všech vlakových hranách, které potkáme.

Program (Python 3)

36-2-4 Nejlepší programovací jazyk, část II. (Zadání)

Úkol 1 – Nula [3b]

Jak jste si mohli při pročtení seznamu instrukcí všimnout, většina z nich konzumuje číslo, které je na vrcholu zásobníku. Takové instrukce samozřejmě na začátku použít nemůžeme, jinak bychom neuměli zrekonstruovat původní zásobník. Nedestruktivních instrukcí máme pomálu: control flow instrukce, u kterých zde nejde garantovat, že budou skákat na rozumné místo v programu, a pak ciferný součet CS a medián m. Medián vyžaduje pěkné číslo navrchu, takže nám vlastně zbývá jenom CS.

Jaký může být výsledek CS pro 64-bitová znaménková čísla? Číslo s největším ciferným součtem, které se do jejich rozsahu ještě vejde, je 8 999 999 999 999 999 999 (a jeho záporná verze) s ciferným součtem 170.

Pomocí CS tedy můžeme vyrobit jedno číslo, o kterém alespoň víme, že je z rozsahu 0–170. Podívejme se, co se stane, když CS budeme ještě opakovat. Jednoduchým programem či chytrým přemýšlením lze ověřit, že ciferný součet pro 170 a nižší čísla nikdy nepřesáhne 18, což je ciferný součet čísla 99.

Pojďme si rovnou ukázat dva způsoby, jak odsud postupovat. První postup pokračuje s dalšími CS. Třetím opakováním CS totiž umíme získat číslo z rozsahu 0–9. Dalšími opakováními už akorát vyrobíme kopii toho samého čísla. Když máme za sebou dvě kopie stejného čísla, tak z nich už lze vyrobit nulu.

Jeden nástroj, který se pro to nabízí, je instrukce %, popřípadě ekvivalentní REM. Ty ale nebudou fungovat pro případ, kdy naše číslo je nulou (což nastane, když na vrcholu zásobníku byla nula), protože dělit nulou bohužel nelze. Naštěstí to je řešitelný problém, stačí ve správný moment přičíst jedničku pomocí ++ a tím získat číslo z rozsahu 1–10. Pak stačí přidat další CS a jsme na pěkném rozsahu 1–9. Výsledné jednociferné číslo si můžeme zduplikovat pomocí CS, a nyní už % či REM budou fungovat. Alternativně lze použít instrukci funkcia, která taktéž pro dvě stejná čísla za sebou vždy vyrobí nulu, a dokonce jí nula na vstupu nevadí. Nakonec už jen zbývá odstranit mezivýsledky pomocí pop2.

Máme tedy následující dva programy na výrobu nuly:

CS CS CS ++ CS CS % pop2 pop2 pop2

CS CS CS CS funkcia pop2 pop2

Druhý, ještě kratší postup je využít instrukci lensum. Jakmile provedeme CS CS, tak máme na vrchu zásobníku dvě čísla, která mají maximálně délku 3 a 2 (zase lze ověřit experimentem či přemýšlením, „nejhorší“ případ je 169 a 16). Provedením lensum tedy dostaneme číslo z rozsahu 0–5. Opět můžeme incrementovat a použít modulo, nebo rovnou použít instrukci funkcia:

CS CS lensum ++ CS %

CS CS lensum CS funkcia

Mimochodem, toto jsou nám nejkratší známá řešení (první na počet znaků, druhé na počet instrukcí). Pokud vymyslíte kratší, dejte nám prosím vědět.

Pro fajnšmekry ještě nabízíme následující program na výrobu nuly:

CS CS ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++
++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++
++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++
++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++
++ ++ bitshift

Poznámka o konstantách

Pokud by to nebylo zřejmé, nyní také umíme vyrábět rozumně malé kladné konstanty, a to vyrobením nuly a poté použitím správného počtu instrukce ++. Jak si v rozumném čase vyrobit větší konstanty prozatím ponecháváme otevřené.

Pro lepší čitelnost budeme v tomto řešení tomuto stavebnímu bloku říkat push(n), kde n je konstanta, kterou přidáváme.

Úkol 2 – Negace [2b]

Jeden přímočarý způsob na řešení tohoto úkolu je pořídit si číslo -1 a poté jej vynásobit s číslem na vrcholu zásobníku pomocí instrukce u. Druhý, kratší způsob si ukážeme poté.

Číslo -1 si můžeme pořídit hned celou řadou způsobů, tak si pojďme dva ukázat:

1. Za pomoci instrukce bitshift a u. Výsledkem operace 1 << 63 je záporné číslo -2⁶³, nejmenší reprezentovatelná hodnota. Z libovolného záporného čísla už umíme vyrobit -1 pomocí univerzální aritmetické instrukce u s parametrem 5, která vrátí její znaménko.

   push(1) push(63) bitshift push(5) u
   

2. Za pomocí instrukce qeq. Kvadratická rovnice (x+1)(x+1) = 0, neboli x²+2x+1 = 0, má jedno řešení, a to právě -1.

   push(1) push(2) push(1) qeq
   

Teď, když umíme implementovat push(-1), tak pro dokončení negace stačí využít násobení pomocí instrukce u:

push(-1) push(2) u

Kratší negace

Ještě jsme slíbili alternativní, kratší způsob. Instrukce qeq umí totiž řešit i lineární rovnice, stačí nastavit koeficient a u x² na nulu. Pro libovolné číslo k na vrcholu zásobníku vyrobíme rovnici x + k = 0 a tu vyřešíme pomocí qeq, výsledkem je totiž -k:

push(1) push(0) qeq

Nejkratší (na počet instrukcí) nám známé řešení, které oproti předchozímu akorát optimalizuje výrobu nuly:

CS CS lensum CS funkcia ++ CS CS % qeq

Podobně jako u předchozího úkolu nám prosím dejte vědět, pokud vymyslíte ještě kratší řešení na počet instrukcí.

Poznámka o psaní ksplangu

Jak jste si jistě všimli, postupně získáváme nové stavební bloky, které se hodí pro psaní složitějších programů. Mohli bychom je vkládat do ksplangových programů v textovém souboru ručně, ale mnohem rozumnější a pohodlnější přístup je vytvořit si nějaký nástroj, který ksplang generuje.

Takovým nástrojem může být například preprocessor, který umí na vstupu přečíst ksplang s novými instrukcemi a vygeneruje reálný ksplangový program. Další a výrazně snazší alternativou je program, který ksplang generuje přímo, a místo psaní ksplangu voláme funkce v jiném jazyku, který nám ten ksplangový program vygeneruje.

Zejména budeme od takového nástroje chtít, aby uměl na zásobník přidat všechny konstanty, co potřebujeme (doporučujeme umět vyrobit každou konstantu). Také může být pohodlné umět snadno používat instrukce s konstantními parametry.

Úkol 3 – Duplikace [5b]

V tomto úkolu bylo cílem zduplikovat na zásobníku číslo k, abychom získali velice užitečný stavební prvek, kterému budeme říkat dup. Rovnou prozradíme, že lze napsat duplikaci, která umí zpracovat libovolné číslo, a na konci řešení ji naleznete, byť bez detailního vysvětlení. Detailněji si popíšeme pouze varianty, které umí omezenější rozsah hodnot.

Nastal čas vyzkoušet si druhou z nedestruktivních instrukcí, a to medián m. Nabízí se hned několik možností, jak ho použít, a víceméně každá z nich vyžaduje nějaké obcházení speciálních případů. Hlavní rozhodnutí, co nás čeká, je počet prvků, přes které budeme medián počítat. Instrukce m nám přišla s popisem „vrať medián z horních x čísel, kde x je číslo na vrchu zásobníku“, což samozřejmě znamená, že se číslo x neodstraňuje, a medián se počítá i z něj.

Medián dvou čísel

První možností je použít medián dvou čísel, což znamená, že po použití m máme na zásobníku hodnotu, která vychází (k+2)/2, zaokrouhlená směrem k nule. Bohužel právě tento způsob zaokrouhlování přináší potíže: podívejte se v následující tabulce na čísla -1, -2, nebo -3, kde se to chová zvláštně:

Pokud si ale před použitím instrukce m číslo k vynásobíme dvěma, tak se najednou vše začne chovat mnohem rozumněji. Můžeme to provést třeba sekvencí push(1) bitshift. Ještě je potřeba si uvědomit, že jsme si tím snížili rozsah duplikovatelných čísel na -2⁶² až 2⁶²-1.

S tímto trikem už není těžké domyslet, jak duplikaci dodělat. V následujícím programu v komentářích ukazujeme hodnoty, které jsou zrovna na konci zásobníku mezi sekvencemi instrukcí:

# k
push(1) bitshift
# 2k
push(2)
# 2k 2
m
# 2k 2 k+1
push(-1) push(0) u
# 2k 2 k
push(1) push(3) lroll
# k 2k 2
push(1) push(2) lroll
# k 2 2k
push(3) u
# k k

Alternativně bychom mohli místo dvou použití lroll použít pouze jeden lroll na prohození horních dvou čísel, znovu opakovat operaci m, a na konec odečíst jedničku.

Medián tří čísel

Jinou možností je použít medián 3 hodnot, kde žádné problémy se zaokrouhlováním nejsou. Najednou ale máme problém, že nelze vybrat žádnou třetí hodnotu a, která by zaručila, že mediánem trojice 3, k, a je číslo k. Pro k < 3 a k > 3 bychom potřebovali různá a.

Naštěstí existuje jednoduchý trik, pokud nám stačí podporovat duplikaci čísel z omezeného rozsahu, jako například 32-bitová čísla, což pro vyřešení úkolu stačilo. Můžeme totiž k číslu k nejdříve přičíst offset – v našem případě číslo větší než 2³²+3, aby nejmenší možná hodnota k byla také 3 nebo větší. Poté můžeme použít medián 3 čísel s třetí hodnotou a > 2³²+offset. Nakonec offset odečteme od výsledku m i od duplikovaného čísla. Samozřejmě nesmíme zapomenout odstranit trojku a a, které po mediánu zůstaly.

V následujícím kódu volíme pro jednoduchost offset 2³³ a třetí hodnotu a = 2⁶². Implementovat push(2^c) můžeme pomocí push(1) push(c) bitshift. Znegovat takové číslo pak umíme z předchozího úkolu.

push(2^33) push(0) u      # přičteme offset
push(2^62) push(3) m      # přidáme a, 3, provedeme medián
pop2 pop2                 # odstraníme 3, a
push(-2^33) push(0) u     # odečteme offset od výsledku mediánu
push(1) push(2) lroll     # prohodíme horní 2 prvky
push(-2^33) push(0) u     # odečteme offset od původního čísla

Univerzální duplikace

Následující duplikace umí zduplikovat všechna čísla.

CS CS lensum ++ CS lensum m CS CS lensum CS funkcia CS ++ CS qeq u CS CS
lensum CS funkcia ++ bitshift CS CS lensum ++ CS lensum m CS CS lensum CS
funkcia CS ++ CS qeq u CS CS lensum CS funkcia ++ bitshift pop2 CS CS
lensum ++ CS lensum CS ++ ++ lroll m CS CS lensum CS funkcia ++ CS CS
funkcia qeq CS CS lensum CS funkcia ++ bitshift pop2 CS CS lensum CS
funkcia u ++ ++ ++ CS CS CS CS lensum CS funkcia CS ++ CS qeq u CS ++ CS
lensum CS ++ ++ lroll CS funkcia u CS CS lensum CS funkcia ++ CS ++ ++
lroll CS CS lensum CS funkcia CS ++ CS qeq u CS CS funkcia u

Program pro úkol 1 (ksplang)

Program pro úkol 2 (ksplang)

Program pro úkol 3 (ksplang)

36-2-S Chození po gradientu (Zadání)

Vzorová řešení všech dílů seriálu vydáme během prázdnin.