2. kodused ülesanded

Üldinfo

Lahenduste esitamise tähtaeg on 09.11. Lahendused saata mailiga kas varmo@cs.ut.ee või nestra@cs.ut.ee (sõltuvalt sellest, millises praktikumi rühmas olete); subjektiks peab olema fpkodu2. Iga ülesande eest on võimalik saada kuni 10 punkti (seega kokku kuni 50 punkti). Hilinenud lahenduste korral väheneb punkti summa 10% iga hilinenud päeva kohta. Näiteks, kui lahendus on väärt 50 punkti, aga jõuab meieni 11.11 (so. kaks päeva hiljem), siis on tegelik punktisumma 50 * 0.9^2 = 41.

Vormistamisest

Kõigi ülesannete lahendused vormistada ühe Haskelli failina. Faili nimi peab olema FPkodu2.hs ning seal defineeritava mooduli nimi FPkodu2. Faili algusse lisada kommentaaridena kõigi rühmaliikmete nimed (rühmas võib olla max. 4 liiget, kusjuures kõigil peab olema sama praktikumi juhendaja) ja maili-aadressid. Kõigi ülesannete korral peavad protseduuride nimed ja argumentide arv/järjekord vastama täpselt ülesandes esitatule. Lahendused peavad olema loetavad ja piisavalt kommenteeritud (sh. kui kasutate abiprotseduure, siis see mida nad teevad peab olema selgelt välja toodud). Näiteks (FPkodu2.hs):

module FPkodu2 where

---------------------------------------------------------------------
-- FPkodu2.hs
-- Funktsionaalprogrammeerimise meetod - 2. koduülesannete lahendused
--
-- Autorid:
--          Jaan    Tatikas   (tatikas@ut.ee)
--          Salomon Vesipruul (salomon@ut.ee)
---------------------------------------------------------------------

-- 1. ülesanne - Funktsioon shift realiseerib nihkeshifri

shift :: Int -> String -> String

Ülesanded

Kirjutada funktsioon shift, mis realiseerib nihkeshifri.
```
> shift :: Int -> String -> String
```
Shiffer nihutab stringis igat tähte ladina tähestiku (so. "ABCDEFGHIJKLMNOPQRSTUVWXYZ", kokku 26 tähte) järjekorras tsükliliselt argumendina etteantud arvu tähtede võrra. Suur- ja väiketähed nihkuvad eraldi ning stringis olevad mittetähed jäävad samaks. Negatiivse arvu korral toimub nihutamine vastassuunas. Näiteks:
```
shift    3  "ABcd"   ==>  "DEfg"
shift    3  "a1 Z2"  ==>  "d1 C2"
shift  (-3) "a1 Z2"  ==>  "x1 W2"
shift    0  "a1 Z2"  ==>  "a1 Z2"
shift   27  "a1 Z2"  ==>  "b1 A2"
shift (-27) "a1 Z2"  ==>  "z1 Y2"
```

Kirjutada funktsioon segments, mis tükeldab argumentlisti mittekahanevate segmentide listiks.

> segments :: Ord a => [a] -> [[a]]

Segmendid peavad olema maksimaalse võimaliku pikkusega (ehk segmentide arv peab olema minimaalne). Näiteks:

segments []               ==>  []
segments [1]              ==>  [[1]]
segments [3,4,5,5,1,2,3]  ==>  [[3,4,5,5],[1,2,3]]
segments [1,2,3,4]        ==>  [[1,2,3,4]]
segments [4,3,2,1]        ==>  [[4],[3],[2],[1]]

Praktikumi materjalides ListSort.lhs toodud merge-sort algoritmi realisatsioon on alati keerukusega n*log n. Algoritmi on võimalik modifitseerida selliselt, et parimal juhul (kui argumentlist on järjestatud) oleks keerukus lineaarne. Selleks tükeldame argumentlisti kõigepealt mittekahanevate segmentide listiks (kasutades eelmises ülesandes realiseeritavat funktsiooni segments) ja seejärel "sulatame" segmendid funktsiooni mergeall abil paarikaupa kokku nii et järjestus säiliks, kuni kogu list on sorteeritud. Seega modifitseeritud merge-sort on defineeritav kui:
```
> msort :: Ord a => [a] -> [a]
> msort = mergeall . segments
```
Kirjuta funktsioon mergeall kasutades "jaga ja valitse" tehnikat.
```
> mergeall :: Ord a => [[a]] -> [a]
```
NB! Funktsiooni mergeall keerukus halvimal juhul peab olema n * log n.

Kaardi värvimisel tuleb riikide värvid valida sellised, et naaberriigid oleksid erinevat värvi. Eesmärk on kirjutada funktsioon color, mis saades ette riikide naabrusseose, rühmitab riigid värvuse järgi (värvimine ei pea olema optimaalne). Riigi esitamiseks kasutame tema nime (mis on string) ning naabrusseose on esitame naaberriikide paaride listina. Näiteks:

color [("Soome", "Rootsi"), ("Soome","Norra"), ("Rootsi","Norra"),
       ("Norra","Venemaa"), ("Soome","Venemaa")]

      ==> [["Rootsi","Venemaa"],["Soome"],["Norra"]]

Funktsiooni color defineerime järgnevalt, kasutades abifunktsioone colorCountry ja neighbours:

> color :: [(String,String)] -> [[String]]
> color = foldr colorCountry [] . neighbours

4.a.

Kirjuta funktsioon neighbours, mis saab ette riikide naabrusseose ning moodustab listi seal esinevates riikidest koos kõigi nende naabritega:

> neighbours :: [(String,String)] -> [(String,[String])]

Näiteks:

neighbours [("Soome", "Rootsi"), ("Soome","Norra"), ("Rootsi","Norra"),
            ("Norra","Venemaa"), ("Soome","Venemaa")]

     ==>   [("Norra",["Rootsi","Soome","Venemaa"]),
            ("Rootsi",["Norra","Soome"]),
            ("Soome",["Norra","Rootsi","Venemaa"]),
            ("Venemaa",["Norra","Soome"])]

4.b.

Kirjuta funktsioon colorCountry, mis saab argumendiks riigi koos naabrite listiga ning laiendab teise argumendina saadavat "värvimist" selle riigiga. Uuele riigile antakse esimene värv, mida pole kasutatud ühegi tema naabri jaoks. Kui vaba värvi ei leidu, antakse riigile uus värv.

> colorCountry :: (String,[String]) -> [[String]] -> [[String]]

Näiteks:

colorCountry ("Rootsi",["Norra","Soome"]) [["Venemaa"],["Soome"]]
     ==>  [["Rootsi","Venemaa"],["Soome"]]

colorCountry ("Norra",["Rootsi","Soome","Venemaa"]) [["Rootsi","Venemaa"],["Soome"]]
     ==>  [["Rootsi","Venemaa"],["Soome"],["Norra"]]

Varmo Vene