Pátá série patnáctého ročníku KSP

Zadání úloh

15-5-1 Komprimovaný obrázek (10 bodů)

Firma Quartz Graphics řešila v jednom ze svých programů následující problém: Měla obrázek o rozměrech r×s bodů. Každý bod obrázku měl určen svou barvu – nějaké celé číslo z intervalu 0,… ,255. Problém spočíval v nalezení co největší souvislé jednobarevné oblasti (dva body pokládáme za sousední, pokud se jejich poloha liší o jedna buď v x-ové nebo y-ové souřadnici). Programátoři firmy ale zjistili, že obrázky jsou příliš velké, a proto se je rozhodli komprimovat pomocí metody RLE. Tato metoda spočívá v tom, že si jednotlivé řádky obrázku naskládáme za sebe a vzniklou posloupnost pak zakomprimujeme tak, že celý souvislý úsek tvořený jediným číslem zakódujeme jako dvojici (délka úseku, číslo v úseku). Tedy například posloupnost 1112233313333222 zakomprimujeme na (3,1), (2,2), (3,3), (1, 1), (4, 3), (3,2). Řešit ovšem problém největší souvislé jednobarevné oblasti v takto zakomprimovaném obrázku již není jednoduché, a proto se firma obrátila na vás.

Vaším úkolem je navrhnout algoritmus a napsat program, který na vstupu dostane rozměry obrázku a zakomprimovaný obrázek (tedy nějakou posloupnost dvojic) a na výstup vypíše velikost největší souvislé jednobarevné oblasti. Protože po dekompresi může být obrázek značně velký, zkuste se ve svých řešeních vyhnout jeho dekompresi, nebo ho alespoň nedekomprimovat celý najednou.

Příklad: Pro obrázek o rozměrech 4×4 a výše uvedenou posloupnost dvojic by měl váš program vypsat 6 – oblast této velikosti je tvořená trojkami na druhém a třetím řádku.

Řešení

15-5-2 Odečtolam (12 bodů)

Pepíček k vánocům dostal novou počítačovou logickou hru Odečtolam. Hra se hraje na pravidelném n-úhelníku, v jehož vrcholech jsou umístěna celá čísla. Navíc pro hru vždy platí, že součet všech čísel je nezáporný. Povoleným tahem ve hře je zvolení nějakého záporného čísla, jeho přičtení k oběma jeho sousedům na n-úhelníku a otočení jeho znaménka. Pokud tedy ve třech následujících vrcholech byla čísla a,b,c, kde b<0, tak po tahu do vrcholu s číslem b tam budou čísla a+b,-b,c+b. Cílem hry je dosáhnout situace, kdy jsou všechna čísla v n-úhelníku nezáporná. Protože Pepíček hru pořád nemohl vyhrát, rozhodl se, že si na ni napíše program. Pomůžete mu s ním?

Vaším úkolem je napsat program, který dostane na vstupu počet vrcholů mnohoúhelníka n a dále n čísel, která jsou na počátku v jeho vrcholech. Na výstup má váš program vypsat posloupnost tahů, která vede do cílové pozice, popřípadě zprávu, že taková posloupnost neexistuje. Nezapomeňte, že součástí řešení by měl být nejen váš algoritmus, ale i důkaz, že váš algoritmus pracuje správně. Tedy že najde posloupnost tahů právě tehdy když existuje.

Příklad: Pro n=4 a čísla -1,-2,3,1 je možná posloupnost tahů například 1 (tím získáme čísla (1,-3,3,0)), 2 (-2,3,0,0), 1 (2,1,0,-2), 4 (0,1,-2,2), 3 (0,-1,2,0), 2 (-1,1,1,0), 1 (1,0,1,-1), 4 (0,0,0,1).

Řešení

15-5-3 Manhattan (10 bodů)

Ulice na Manhattanu mají jak známo tvar čtvercové sítě. Řekněme, že na Manhattanu vede m ulic severojižním směrem a n ulic východozápadním. Bill vyjíždí každé ráno z křižovatky o souřadnicích 1,1 (severozápadní roh) a jede do práce na křižovatku o souřadnicích m,n (jihovýchodní roh). Některé křižovatky se ovšem opravují, a tak přes ně Bill nemůže jet. Billa by zajímalo, kolika způsoby se může do práce dostat, pokud chce vždy jet pouze ze severu na jih nebo ze západu na východ. A to je úkol pro vás.

Napište program, který dostane na vstupu rozměry města m a n, počet opravovaných křižovatek k a souřadnice oněch opravovaných křižovatek (předpokládejte, že křižovatka (1,1) ani křižovatka (m,n) nejsou opravované). Na výstup má pak váš program vypsat počet cest, kterými Bill může jet.

Příklad: Pro město o rozměrech 3×4 a 2 rozkopané křižovatky na souřadnicích (2,2) a (3,3) má Bill 2 možnosti, jak do práce dojet.

Řešení

15-5-4 Továrna (12 bodů)

Továrna na tvarůžky (TNT) získala velkou zakázku na výrobu svých jedinečných tvarůžků výbušné chuti. Problémem ale je, že továrna vlastní pouze N1 strojů na lisování tvarůžků a N2 strojů na jejich balení. Protože stroje jsou různě staré je i jejich rychlost lisování a balení různá. Je proto poměrně obtížné vymyslet, jak strojům práci rozdělit, aby zakázka byla co nejrychleji splněna. Vedení podniku se tedy obrátilo na vás, abyste pomohli svými znalostmi.

Vaším úkolem je napsat program, který dostane na vstupu počet tvarůžků T, které je třeba vyrobit. Dále dostane počet lisovacích strojů N1 a časy, za které stroje vylisují jeden tvarůžek – nějaká posloupnost N1 čísel t
1
1
,… ,t
1
N1
. Nakonec dostane ještě počet balících strojů N2 a časy, za které stroje zabalí jeden tvarůžek – posloupnost N2 čísel t
2
1
,… ,t
2
N2
. Na výstup má váš program vypsat nejkratší čas, za který je možno zakázku splnit.

Příklad: Pro 10 tvarůžků, 3 lisovací stroje s časy 2,2,5 a 2 balící stroje s časy 6,3 je nejkratší možný čas výroby 21.

Řešení

15-5-5 Haskell (10 bodů)

Vzhledem k tomu, že praktické úložky v Haskellu byly pro vás zřejmě příliš triviální a bylo pod vaši úroveň je řešit, podíváme se nyní na funkcionální jazyky z teoretické stránky.

Nejspíš už jste slyšeli, že teoretickým základem pro funkcionální programovací jazyky je lambda-kalkulus. Co to vlastně je?

Všechny objekty, se kterými v lambda-kalkulu pracujeme, jsou funkce. Pokud bychom opravdu toužili po tom, mít i nějaké hodnoty, mohli bychom je chápat jako funkce z jednobodové množiny (nicméně se bez toho obejdeme). Tyto funkce budou mít vždy právě jeden parametr – nicméně vzhledem k tomu, že to, co vrací, je zase funkce, můžeme je chápat jako funkce s libovolným množstvím parametrů (viz podobný trik použitý pro funkce s více parametry v Haskellu). Termy (tedy výrazy) lambda-kalkulu jsou definovány takto:

Výskyt proměnné x v termu T je vázaný, pokud je uvnitř podtermu tvaru lambda x (S), jinak je volný. Výrazem Tx := S budeme rozumět term T, kam za všechny volné výskyty x dosadíme S, tj. formálně (pro x≠ y):

Pro aplikaci a abstrakci platí následující pravidlo, které formalizuje výše popsanou sémantiku: (lambda x (T))(S) = Tx:=S.

Aby se nám zbytečně nekupily závorky, zavedeme si následující konvence (podobné řešení užíval i Haskell): Pokud neuvedeme závorky, aplikace se závorkují doleva, abstrakce doprava. Závorky kolem proměnných neuvádíme. Tj. například

lambda x lambda y lambda z x y z = (lambda x (lambda y (lambda z (x)))(y))(z)

Výraz lambda x . T znamená „zazávorkuj T tak, aby pravá závorka byla co nejvíc vpravo“, tj.

lambda x . lambda y . lambda z . x y z = lambda x (lambda y (lambda z (x y z)))

Povšimněte si, že nemáme žádný způsob, jak si funkce pojmenovat – zdá se, že o něčem takovém jako rekurze nemůže být řeč. Naštestí máme následující term (budeme ho označovat Y):

lambda f . (lambda x . f (x x)) (lambda x . f (x x))

Y splňuje následující identitu:

Y g = (lambda x . g (x x)) (lambda x . g (x x)) =
= g ((lambda x . g (x x)) (lambda x . g (x x))) = g (Y g),

tj. pro libovolnou funkci g vrátí její pevný bod (tj. y takové, že y = g y. Y se proto nazývá operátor pevného bodu. K čemu je to dobré? Mějme například rekurzivní funkci, která vrací délku seznamu:

length = lambda s . if empty s then 0
                     else 1+length(tail s)

S použitím operátoru pevného bodu ji můžeme napsat bez použití rekurze takto:

length = Y (lambda g . lambda s . if empty s then 0
                        else 1+g(tail s))

Skutečně, označíme-li si term vpravo od Y jako T, dostáváme

length (h:t) = Y T (h:t) = T (Y T) (h:t) =
= 1 + Y T t = 1 + length t,

což je přesně to, co chceme.

Nyní si můžeme již snadno zavést aritmetiku. Označme si například Nula = lambda x . lambda y . x a Succ = lambda s . lambda x . lambda y . y s. Pak za nulu považujeme term Nula, za jedničku term Succ Nula, za dvojku Succ (Succ Nula), atd. Každé takové číslo je pak funkce se dvěma parametry; Nula vrátí první z nich, zatímco jakékoliv jiné číslo zavolá druhý z nich s parametrem o jedna menším. Například funkce Pred, která od kladného čísla odečte jedničku a nulu nezmění vypadá takto:

Pred = lambda n . n Nula (x . x).

Nyní asi již není těžké uvěřit, že v lambda-kalkulu dokážeme napsat libovolný program, který lze napsat v Haskellu (nebo jakémkoliv jiném rozumném programovacím jazyce).

Úlohy:

  1. Napište term Sum, který dostane dvě čísla ve výše popsané reprezentaci a sečte je.
  2. Napište termy Y1 a Y2 – operátory dvojného pevného bodu, splňující následující identity: Y1 g h = g (Y1 g h) (Y2 g h), Y2 g h = h (Y1 g h) (Y2 g h).

Řešení