Třetí série osmnáctého ročníku KSP

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

Hrošík pouští draka

Milí řešitelé!

Poněkud s předstihem dostáváte do rukou zadání třetí série našeho semináře. S ním dostáváte taktéž opravená řešení série první, takže špinavé a podlé fígly, které se z nich naučíte, můžete použít ještě při řešení série druhé :–)

Zadání úloh

18-3-1 Trávník (4 body)

Hrošík Seček si na své zahrádce pěstuje trávník. Čas od času trávník poseče a z výtěžku uspořádá hostinu pro své přátele. Předtím, než trávník poseká, ho musí samozřejmě nechat pěkně narůst. A tak Seček potřebuje napsat program, který mu navrhne ideální den pro posekání trávníku.

Trávník se dá popsat maticí M×N, kde každý prvek matice je celé číslo udávající velikost stébla v trávníku v centimetrech. Toto číslo také udává rychlost růstu stébla v centimetrech za den. Rychlost růstu se nemění. Aby Seček mohl přátele pohostit, potřebuje alespoň K centimetrů stébel trávy.

Napište tedy program, který na vstupu dostane čísla M, N a K a dále matici M×N nezáporných celých čísel, kde každý prvek odpovídá délce stébla trávníku v daném místě první den od posledního posekání. Tato matice udává zároveň rychlost růstu jednotlivých stébel. Váš program by měl vypsat, kolik dní má Seček ještě počkat s posekáním trávníku.

Příklad: Pro M=2, N=3, K=79 a matici

( 109)
893

Seček počká ještě 2 dny. Matice trávníku pak bude:

( 3027)
24279

Z tohoto trávníku lze získat 90 centimetrů trávy.

Řešení

18-3-2 Duel (5 bodů)

Hrošík a prasátko jsou soutěživá zvířátka. Kde mohou, tam se snaží navzájem trumfovat. Jednou objevili zajímavou hru: Na stůl se na papírcích umístí čísla od 1 do 9. Oba hráči se potom střídají v odebírání jednotlivých čísel na svou hromádku. Vyhraje ten hráč, v jehož hromádce se jako prvnímu nachází trojice čísel dávající součet 15.

Hrošík začíná jako první a chce vyhrát. Jenže vůbec neví jak na to… Poraďte hrošíkovi, jak to zařídit, aby když začíná jako první, vždy nad prasátkem vyhrál.

Řešení

18-3-3 Vrah (10 bodů)

Hugo se právě vrátil ze soustředění KSP, kam byl pozván jako účastník, a protože se nyní ve škole nudil, rozhodl se naučit své spolužáky zábavnou hru „na vraha“.

Do pytlíku se vhodí N papírků se jmény a každý si potom vylosuje jméno své oběti. Cílem hry je nikým jiným neviděn sáhnout zezadu své oběti na krk a sám se nestát obětí. Po úspěšném „zabití“ oběť předává vrahovi svůj papírek se jménem a vrah má nový cíl. Hráč končí, když dostane do ruky svůj vlastní papírek.

Jenže hráči za chvíli zjistili, že pro jistá rozlosování některé dvojice vůbec nedostanou šanci se spolu utkat (například když si hráč již na začátku vylosuje sám sebe, ale i jindy). Naštěstí měli osvícenou paní učitelku, která podporovala kulturní vyžití svých žáků a která se zeptala, kdo s kým chce mít šanci se ve hře potkat. Pak se podívala na jinak tajné rozlosování a některým dvojicím hráčů oznámila, aby si mezi sebou vyměnili své papírky, navíc tak, že počet prohození byl nejmenší možný.

Vymyslete algoritmus a napište program, který to bude dělat za paní učitelku. Na vstupu dostanete počet hráčů N, které si místo jmen očíslujeme čísly 1 až N. Následuje N čísel, kde i-té udává číslo hráče, jehož má zabít hráč číslo i. Poté číslo K a za ním K dvojic čísel určujících, kteří hráči se spolu chtějí potkat. Zdůrazněme, že jeden hráč se může chtít potkat i s více než jedním jiným hráčem. Program by měl odpovědět nejmenším možným počtem pokynů k prohození papírků, aby všech K dvojic zaručeně mělo šanci se ve hře potkat (nemusí se potkat v jedné hře, ale pro každou dvojici musí existovat průběh hry, při kterém se potkají).

Příklad: Pro N=6 hráčů, rozlosování 6,2,4,3,1,5 a K=3 dvojice (1,6),(1,3),(4,5), které se chtějí potkat, stačí jediné prohození papírků, a to mezi lidmi 4 a 6.

Řešení

18-3-4 Pochoutka pro prasátko (10 bodů)

V lese sousedícím s poklidným rybníčkem našich hrošíků se objevilo hladem šilhající prasátko. Zaslechlo totiž zvěsti o Velké Bukvici, která si tou dobou lebedila v podzemí lesíku. Začalo tedy bez rozmyslu rejdit mezi stromy, leč brzy mu došly síly – byl to už přeci jenom nějaký čas od poslední mňamky. Budete umět prasátku poradit ?

Les si představme jako čtvercovou síť, v jednom políčku prasátko, v jiném bukvice. Aby to nebylo tak jednoduché, prasátko se v lese může pohybovat jen podle určitých pravidel a každé z nich stojí nějaké kladné množství námahy.

Konkrétně – na vstupu dostanete rozměry lesa a pozici prasátka a bukvice spolu s pravidly, podle kterých se prasátko může pohybovat. Každé pravidlo obsahuje trojici čísel x y z, kde x a y je povolený posun v mřížce (o kolik se změní pozice prasátka ve čtvercové síti), zatímco z je úsilí, které prasátko musí vynaložit pro daný přesun. Vaším úkolem je najít a vypsat cestu od prasátka k bukvici. Na své cestě nesmí prasátko opustit lesík. A aby milý čuník hlady nepošel, musí být vynaložené úsilí nejmenší možné.

Příklad: Les má rozměry 6×6, poloha prasátka je [3,3] a poloha bukvice [1,5]. Pohyb prasátka se řídí třemi pravidly 2 2 3, 1 1 1 a -4 0 5. Potom je pro prasátko nejvýhodnější použít dvakrát pravidlo 2 (→[5,5]) a pak jednou pravidlo 3 (→[1,5]). Vynaložená námaha je pak 2·1 + 5=7.

Řešení

18-3-5 Hroší lov (13 bodů)

Do hrošího království vtrhlo šílenství – divoké prase začalo zběsile rozrývat rozsáhlé části lesa. Marné bylo domlouvání ostatních obyvatel polesí, kvičící střela zvolna proměňovala hluboké hvozdy v důlní centrum pro těžbu bukvic.

Hrochům nakonec došla trpělivost a rozhodli se, že nezbedné prase polapí, upečou a sní. Teprve nyní prasátko dostalo strach – ale ouha, bylo příliš pozdě. Stádo nasupených hrochů pročesávalo les a dalo se zastavit leda až večerní tmou. Pomůžete prasátku uniknout ještě dříve, než nastane večer?

Podobně jako v předešlém případě je možné les popsat jako čtvercovou síť, po které je pohyb všech zvířat možný pouze podle předepsaných pravidel a nijak jinak.

Na vstupu tedy dostanete rozměry lesa a pozici prasátka a hrochů společně s neohodnocenými pravidly pohybu pro každého z nich (i pro prasátko). Dále dostanete čas t, který zbývá do setmění. Vaším úkolem je najít a vypsat únikovou cestu pro prasátko. Ta se vyznačuje tím, že se prasátko celou dobu pohybuje po bezpečných polích, a buď uteče z lesa ven (dosáhne hranice lesa), nebo uplyne doba t (pak jej totiž hroši přestanou hledat). Bezpečné pole je takové, na které v čase pobytu prasátka nemůže dostat žádný hroch. Ještě dodáváme, že více hrochů smí v jeden moment stoupnout na jedno políčko a čas chápeme jako diskrétní kroky, v nichž každé zvíře musí udělat pohyb podle nějakého svého pravidla (čili nemůže zůstat stát na místě).

Hroch loví prasátko

Příklad: Les má rozměry 3×3 a do setmění zbývá čas t=5. Prasátko je na souřadnicích [2,2] a smí se pohybovat podle jediného pravidla -1 0. Hroši jsou dva – první je na [3,2] a pohybuje se podle jednoho pravidla -1 0, druhý je na [2,3] a pohybuje se podle dvou pravidel 0 -1 a -1 0.

Hledaná cesta pro prasátko je dvakrát použít pravidlo jedna (čili -1 0), čímž se dostane na [0,2], což jest ven z lesa.

Řešení

18-3-6 Komplikovanější komplikátory (10 bodů)

Jedním z problémů, které je často nutné při optimalizacích v kompilátorech řešit, je analýza toku dat (dataflow). Základní optimalizací, která se pomocí dataflow provádí, je globální propagace konstant. Její úlohou je rozhodnout, které proměnné mají vždy konstantní hodnotu, a nahradit jejich použití touto hodnotou. Například následující kód (v mezijazyce popsaném v první sérii):

assign a 0
assign b 1
if (c = 0) 1 2
 
label 1
assign c (a + b)
goto 3
 
label 2
assign c 1
assign a 2
 
label 3
assign x (c + a)

Bude po propagaci konstant vypadat takto:

assign a 0
assign b 1
if (c = 0) 1 2
 
label 1
assign c 1
goto 3
 
label 2
assign c 1
assign a 2
 
label 3
assign x (1 + a)
Povšimněme si, že nestačí jen určit, která proměnná je konstanta, protože to se může v průběhu programu změnit. Například a je v prvních třech basic blocích konstanta 0, ale v posledním může mít hodnotu 0 nebo 2. Budeme si proto chtít určit, zda je proměnná konstantní, zvlášť na začátku a na konci každého basic bloku – lokální propagace uvnitř každého basic bloku je jednoduchá, prostě projdeme postupně všechny příkazy a odsimulujeme si je. Pro každou proměnnou x a každý basic blok b budeme mít proměnné x
+
b
a x
-
b
, které určují stav x na začátku a na konci bloku b. Ohodnocení proměnných bude nabývat jedné z následujících hodnot:
  • Top – tato hodnota znamená, že x může být konstantní, ale ještě nevíme, jakou by ta konstanta měla mít hodnotu.
  • Nějaké číslo c – to znamená, že x je buď vždy rovno c, nebo není konstantní.
  • Bottom – tato hodnota znamená, že x není konstantní.

Tyto hodnoty si uspořádejme tak, že Bottom < c < Top pro libovolnou konstantu c (konstanty jsou navzájem neporovnatelné). Toto uspořádání je důležité pro důkaz konečnosti algoritmu dataflow.

Jestliže nějak určíme hodnoty těchto proměnných na konci všech basic bloků, určit je na začátku libovolného bloku b je snadné, prostě je potřeba slít hodnoty příslušných proměnných na konci předchůdců b. Pravidla pro slévání jsou tato:

Naopak, pokud bychom znali hodnoty proměnných na začátku basic bloku, hodnoty na konci určíme odsimulováním příkazů v basic bloku s tím, že operace s konstantami vyhodnocujeme. Výsledky operací s Top jsou skoro vždy Top a operací s Bottom zase Bottom, až na drobné výjimky – například 0 krát cokoliv je vždy 0, bez ohledu na hodnotu výrazu, který počítáme. Je potřeba si dávat maličko pozor, aby toto vyhodnocování operací bylo monotónní, tj. pokud x op a vyhodnotíme jako a', x op b vyhodnotíme jako b' a a ≤ b, pak i a'≤ b'. Tedy například pokud chceme, aby Bottom*0 = 0, pak Bottom*Top může být Top nebo 0, ale nic jiného. Tato podmínka je nutná pro zajištění konečnosti níže popsaného algoritmu. Také je vhodné, abychom nevraceli Top, pokud alespoň jeden z operandů nebude Top. To už není nutné pro konečnost, jen to většinou nedává moc smysl – taková operace by tvrdila, že její výsledek je nezávisle na vstupech nějaká neznámá konstanta.

Algoritmus dataflow funguje takto: Na začátku algoritmu nastavíme všechny proměnné na Top, kromě těch na začátku prvního bloku, které nastavíme na Bottom. Poté budeme opakovat operace popsané v minulých odstavcích tak dlouho, dokud se něco mění. Operace lze provádět v libovolném pořadí, prakticky se to dělá tak, že si udržujeme seznam bloků, pro které se změnily hodnoty proměnných na konci některého z jejich předchůdců. Z něj si odebereme libovolný blok b, slijeme hodnoty z jeho předchůdců, vyhodnotíme si výrazy uvnitř b a v případě, že se ohodnocení proměnných na konci b změnilo, přidáme do seznamu všechny následníky b.

Stav proměnných poté, co dosáhneme ustáleného stavu, je řešením problému. K tomu je potřeba dokázat, že se algoritmus vždy zastaví a že je korektní, tj. že pokud proměnná není konstantní, pak její hodnota na konci bude Bottom. Pro důkaz konečnosti si povšimneme, že ohodnocení libovolné proměnné se může změnit nejvýše třikrát – na začátku je Top, pak se můžeme nějakou dobu domnívat, že by její hodnota mohla být konstantní, a nakonec se její hodnota může stát Bottom, pokud dokážeme, že konstantní není. Protože proměnných, jejichž ohodnocení určujeme, je nejvýše N2, kde N je délka programu, algoritmus se časem jistě zastaví.

Zajímavější je korektnost. Nejprve si ukážeme, že na konci žádná proměnná nebude mít hodnotu Top. Předpokládejme, že tomu tak není a že například x
+
b
je Top. Vezměme si libovolnou cestu p z počátku do bloku b a vracejme se z p po b. V každém okamžiku musíme mít alespoň jednu proměnnou ve stavu Top – když přecházíme přes hranu CFG, Top na jejím konci mohl vzniknout jedině z Topu na jejím začátku, případně slitím Topů z ostatních předchůdců. Vyhodnocením příkazu také Top mohl vzniknout, jen pokud některý z operandů byl Top. Tedy Top by musel existovat i na začátku úplně prvního bloku, což ale není možné – ohodnocení všech proměnných na začátku jsme nastavili na Bottom.
Předpokládejme nyní, že algoritmus je chybný a nějaké proměnné x
+
b
přiřadí ohodnocení c, i když x na začátku basic bloku b může nabývat i jiné hodnoty d. Buď p cesta z počátku do b, která odpovídá výpočtu, jenž způsobí, že x je na konci rovno d. Někde na této cestě je první místo, kde se námi nalezené ohodnocení rozchází s tímto výpočtem. Nemůže to být úplně na začátku, neboť tam je ohodnocení všech proměnných Bottom, čili o hodnotách proměnných nic netvrdíme. Nemůže to také být na začátku jiného basic bloku, protože pokud o nějaké proměnné tvrdíme, že má hodnotu c, museli jsme to tvrdit i na konci předchozího basic bloku a na hraně CFG se hodnota proměnné nemohla změnit. Čili bychom museli někde mít výraz, jehož operandy mají správné ohodnocení, ale jeho výsledek chybné. To ale nemůže nastat, protože jsme používali pouze korektní pravidla pro vyhodnocování výrazů. Čili všechny proměnné na konci budou ohodnoceny korektně.

S několika drobnými triky se tento algoritmus se dá implementovat s časovou složitostí O(N·E), kde E je počet hran CFG. Naše implementace je pro lepší čitelnost o něco hloupější a nesnažili jsme se ji příliš optimalizovat, takže její časová složitost je o něco horší, O(N2·E). Můžete ji najít zde:

Ukázková implementace algoritmu propagace konstant.

Úloha

Jedním z problémů, které se dají pomocí dataflow analýze řešit, je mazání mrtvého kódu, tedy výrazů, jejichž hodnota není k ničemu použita. Výraz je živý, pokud má nějaké efekty, které nejdou smazat (například volání funkce, skok, přiřazení do globální proměnné), nebo pokud je jeho hodnota použita v živém výrazu. Například v následujícím příkladě jsou živá jen přiřazení do i (protože hodnota i je použitá v podmínce skoku) a druhé přiřazení do k (které je použito v návratové hodnotě funkce):

assign i 0
assign j 0
assign k 10
assign k 15
 
label 1
assign i (i + 1)
assign j (j + 1)
if (i < 100) 1 2
 
label 2
assign result k

Vaším úkolem je navrhnout algoritmus pro nalezení mrtvých výrazů založený na dataflow analýze.

Řešení