Export translations

Settings

Group

Language

Format

Export for off-line translation

Export in native format

{{DISPLAYTITLE:FP Domácí úkol 1}}== Základní informace ==

Ve všech zadáních se očekává výstup na obrazovku. Pro něj je možné použít stejný postup jako ve  [[FP_Laboratory_7 | Cvičení 7]].

Definujme si typ pro výstup:
<syntaxhighlight lang="Haskell">type Result = [String]</syntaxhighlight>
Nyní, pokud chceme pěkně vypsat takovýto výstup na obrazovku, můžeme použít:
<syntaxhighlight lang="Haskell">
pp :: Result -> IO ()
pp x = putStr (concat (map (++"\n") x))
</syntaxhighlight>

== Příklad - Lodě==

Napište funkci <code>ships</code>, která má dva argumenty. První je seznam řetězců, které reprezentují hrací plochu jednoho hráče po řádcích postupně shora dolů ('o' - políčko obsazené lodí, ' ' - prázdné pole). Druhým argumentem je seznam dvojic souřadnic políček, na které druhý hráč zkoušel střílet. Vykreslete aktuální stav hry tak, že řádky a sloupce budou označeny svým číslem resp. písmenem, 'o' bude dosud nezasažené políčko s lodí, 'x' zasažené políčko s lodí, '.' místo, kam se střílelo, ale nic nezasáhlo, ' ' prázdná a dosud nezasažená políčka. Můžete předpokládat hrací plochu velikosti 10x10.

<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/NC6pb3R7A0g]]</div>
<div style="clear:both"></div>

<syntaxhighlight lang="Haskell">
ships :: Result -> [(Char, Int)] -> Result
sampleInput = ["  o    o  ",
               "      ooo ",
               "   oo     ",
               "          ",
               "     o    ",
               "     o    ",
               "     o    ",
               "          ",
               "          ",
               "  oooo    "]
</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark" >
Prelude>pp(ships sampleInput [('a',1),('d',1),('d',2),('c',1),('b',1),('e',1),('f',1),('g',1),('c',7),('c',10)])
 10  x    o
  9      ooo
  8   oo
  7  .
  6     o
  5     o
  4     o
  3
  2   .
  1..xxxx.
   abcdefghij
</syntaxhighlight>
<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
import Data.Char ( ord ) 
type Result = [String]

pp :: Result -> IO ()
pp x = putStr (concat (map (++"\n") x))

sampleInput :: Result
sampleInput = ["  o    o  ",
               "      ooo ",
               "   oo     ",
               "          ",
               "     o    ",
               "     o    ",
               "     o    ",
               "          ",
               "          ",
               "  oooo    "]

ships :: Result -> [(Char, Int)] -> Result
ships input coordinates = let
    coordinates' = [(ord ch - ord 'a' +1 ,ri) |(ch, ri)<-coordinates]
    get x ch | elem x coordinates' = if ch == 'o' then 'x' else '.'
             | otherwise = ch
    niceShow x = let 
        number' = show x
        in if length number' == 1 then "  "++number' else " "++number'         
    nicePrint result = reverse [niceShow number ++ row|(number,row)<-zip [1..] result] ++ ["   abcdefghij"]
    in nicePrint ([[get (ci,ri) ch |(ci,ch)<- zip [1..] row ]| (ri,row)<-zip [1..] (reverse input)])
</syntaxhighlight>
</div>
<div style="clear:both"></div>

== 1 - Magic 15 Puzzle ==

Implementujte funkci <code>puzzle</code>, ta bude simulovat hru podobnou [https://en.wikipedia.org/wiki/15_puzzle 15 Puzzle]. V našem případě máme 25 čtverců, kde 24 čtverců je obsazeno kostičkami s velkými písmeny od <code>'A'</code> do <code>'X'</code>. Jedna dlaždice je zdarma, je označena <code>' '</code>. Jedním tahem můžete přesunout dlaždici (označenou jejím písmenem) do této volné. Funkce získá původní konfiguraci a posloupnost '' 'platných''' tahů. Jako výsledek vytvoří výslednou konfiguraci.
<syntaxhighlight lang="Haskell">
puzzle2 = ["AC DE",
           "FBHIJ",
           "KGLNO",
           "PQMRS",
           "UVWXT"]

puzzle :: Result -> [Char] -> Result
</syntaxhighlight>

<syntaxhighlight lang="Haskell" class="myDark" >
*Main> pp(puzzle puzzle2 "CBGLMRST")                    
ABCDE
FGHIJ
KLMNO
PQRST
UVWX
</syntaxhighlight>

== 2 - Slova v křížovce ==

Implementujte funkci <code>answers</code>, která bere jako vstup řešení křížovky a najde všechna slova z tohoto řešení. Slova budou rozdělena do dvou seznamů, nejprve pro řádky (zleva doprava) a druhé pro sloupce (shora dolů). Slovo je vypsáno, pouze pokud je delší než jeden znak.

*TIP: ''Použijte funkci'' <code>words :: String -> [String]</code> ''k rozdělení řádku na sekvenci slov.''

<syntaxhighlight lang="Haskell" class="myDark" >
*Main> words "ABC cdef ghijkl"
["ABC","cdef","ghijkl"]
</syntaxhighlight>

<syntaxhighlight lang="Haskell">
solution1 = ["DAD  SEND",
             "O EAST  A",
             "W A  ITSY",
             "NERF N T ",
             " A ARK U ",
             " S T SYNC",
             "MESH  A A",
             "A  EVER R",
             "NEAR  D D"]

answers :: Result -> ([String],[String])
</syntaxhighlight>

<syntaxhighlight lang="Haskell" class="myDark" >
*Main> answers solution1 
(["DAD","SEND","EAST","ITSY","NERF","ARK","SYNC","MESH","EVER","NEAR"],["DOWN","MAN","EASE","DEAR","FATHER","STINKS","YARD","STUN","DAY","CARD"])
</syntaxhighlight>

== 3 - Vytváření křížovky ==

V tomto úkolu implementujete funkci, která pomáhá při vytváření křížovky. Funkce <code>positions</code> bere jako vstup, ''obrys'' pro budoucí křížovku a vytiskne všechny pozice, kam potřebujeme vložit nějaká slova. Obrys se skládá z prázdných polí (<code>'.'</code>), kde můžeme vložit nějaký znak, a z černých polí (<code>'#'</code>), kde nejsou žádné znaky. V našich křížovkách je potřeba slova umístit do všech posloupností prázdných políček, které jsou alespoň dvě pole dlouhé. Výstupem funkcí jsou indexy všech startovních pozic, kam potřebujeme vložit nějaká slova. Pozice jsou páry <code>(řádek, sloupec)</code>. Jsou indexovány z horního levého rohu se souřadnicemi <code>(0,0)</code>. Zvažte pouze slova v '''řádcích''' (u řádků můžeme otočit a překlopit obrys křížovky a používat stejnou funkci).

<syntaxhighlight lang="Haskell">
--An example of a crossword puzzle with the same outline is in the previous task.
crossword = ["...##....",
             ".#....##.",
             ".#.##....",
             "....#.#.#",
             "#.#...#.#",
             "#.#.#....",
             "....##.#.",
             ".##....#.",
             "....##.#."]

positions :: Result -> [(Int,Int)]
</syntaxhighlight>

<syntaxhighlight lang="Haskell" class="myDark" >
*Main> positions crossword
[(0,0),(0,5),(1,2),(2,5),(3,0),(4,3),(5,5),(6,0),(7,3),(8,0)]
</syntaxhighlight>

== 4 - Dekodér ==

Možností, jak kódovat text, je nahradit časté dvojice znaků novými (do té doby nepoužívanými) znaky.
V tomto úkolu byste měli implementovat funkci, která dekóduje takový kódovaný text. Funkce <code>decode</code> přebírá kódovaný text a slovník. Slovník je posloupnost párů, kde první prvek je zakódovaný znak (<code>Char</code>) a druhý prvek je původní pár (jako <code>String</code> délky 2). Výsledkem je originální text. Což je ve skutečnosti text z parametru, kde byly všechny kódované znaky nahrazeny původními dvojicemi znaků.

<syntaxhighlight lang="Haskell">
decode :: String -> [(Char,String)] -> String
</syntaxhighlight>

<syntaxhighlight lang="Haskell" class="myDark" >
*Main> decode "HAHA" [('E',"AB"),('F',"CD"),('G',"EF"),('H',"GG")]
"ABCDABCDAABCDABCDA"
</syntaxhighlight>

== 5 - Prefixový dekodér ==

Jednou z možností, jak kódovat znaky do binárního kódu, je použít prefixové kódování (příkladem může být [https://en.wikipedia.org/wiki/Huffman_coding Huffmanovo kódování]). V tomto kódování není žádný kód ''prefixem'' žádného jiného kódu. Pokud je například jedno písmeno kódováno jako <code>101</code>, pak žádný kód jiného písmene nezačíná stejnou sekvencí <code>101</code>. V tomto úkolu napište funkci <code>toText</code>, která přebírá kódovanou binární sekvenci (v našem případě <code>String</code> složeny z <code>1</code> a <code>0</code>) spolu se slovníkem a vytvoří jako výsledek původní text. Slovník se skládá z dvojic, kde každá dvojice obsahuje šifrovaný znak (<code>Char</code>) a sekvneci (<code>String</code>) z <code>1</code> a <code>0</code> - což je přiřazený prefixový kód. Bezpečně předpokládejte, že všechny vstupy jsou '''platné'''.

<syntaxhighlight lang="Haskell">
dictionary = [('a',"0"),('b',"101"),('c',"100"),('d',"111"),('e',"1101"),('f',"1100")]

toText :: String->[(Char, String)]->String
</syntaxhighlight>

<syntaxhighlight lang="Haskell" class="myDark" >
*Main> toText "01011001111101" dictionary
"abcde"
</syntaxhighlight>

== 6 - Šachové pozice ==

Napište funkci <code>chess</code>, která má 2 argumenty typu <code>[String]</code>. Řetězce v seznamech obsahují 3 znaky:
* první určuje šachovou figuru ('K' - král, 'D' - dáma, 'V' - věž, 'S' - střelec, 'J' - jezdec, 'P' - pěšec)
* druhý znak určuje sloupec ('a'-'h')
* třetí je číslo řádku ('1'-'8')
První seznam reprezentuje aktuální rozmístění bílých figur a druhý černých. Vypište aktuální pozici tak, že volná políčka budou reprezentována znakem '.', bílé figury svým písmenem velkým a černé figury svým písmenem malým. Řádky i sloupce budou označeny čísly resp. písmeny.
<syntaxhighlight lang="Haskell">
chess :: [String] -> [String] -> Result
</syntaxhighlight>

<syntaxhighlight lang="Haskell" class="myDark" >
Prelude> pp( chess["Ke1","Ra1","Rh1","Pa2","Be5"] ["Ke8","Ra8","Rh8","Pa7","Qd8","Bc8","Nb8"])
8rnbqk..r
7p.......
6........
5....B...
4........
3........
2P.......
1R...K..R
 abcdefgh
</syntaxhighlight>
== 7 - Ticktacktoe ==
 
Napište funkci <code>ticktack</code>, která má 2 argumenty. První je dvojice přirozených čísel určující počet sloupců a řádků hrací plochy. Souřadnice jsou počítány z levého dolního rohu. Druhý seznam reprezentuje průběh hry piškvorky, kde jsou souřadnice políček, na které střídavě hrál hráč 'x' a hráč 'o'. Vypište aktuální stav hry tak, že hrací pole bude ohraničeno znaky '-' a '|', volné pozice ' ' a znaky 'x' a 'o' budou na pozicích, kam zahráli příslušní hráči.
<syntaxhighlight lang="Haskell">
ticktack::(Int,Int) -> [(Int,Int)] -> Result
</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark" >
Prelude>pp(ticktack (8,8) [(1,1),(8,8),(2,2),(3,3),(4,2),(3,2)])
----------
|       o|
|        |
|        |
|        |
|        |
|  o     |
| xox    |
|x       |
----------
</syntaxhighlight>

== 8 - Bludiště==

Napište funkci <code>maze</code>, která má 2 argumenty. Prvním argumentem je seznam řetězců, které reprezentují bludiště po řádcích postupně shora dolů ('*' - stěna, ' ' - průchozí pole, 's' - startovní pozice). Na začátku se nacházíme na pozici 's'. Druhým argumentem je seznam směrů pohybu ('d' - down, 'u' - up, 'l' - left, 'r' - right). Každé písmeno znamená, že se posuneme o 1 buňku daným směrem a na novou pozici umístíme znak '.' Vypište aktuální situaci po provedení všech kroků z druhého seznamu.
<syntaxhighlight lang="Haskell">
maze :: Result -> String -> Result

sampleInput = ["*********",
               "*s*   * *",
               "* * * * *",
               "* * * * *",
               "*   *   *",
               "******* *",
               "        *",
               "*********"]
</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark" >
Prelude>pp(maze sampleInput "dddrruuurrdddrrddllllll")
*********
*s*...* *
*.*.*.* *
*.*.*.* *
*...*...*
*******.*
 .......*
*********
</syntaxhighlight>

== 9 - Hledání min==

Napište funkci <code>minesweeper</code>, která má argument typu seznam řetězců. Řetězce reprezentují hrací plochu po řádcích postupně shora dolů ('*' - mina, ' ' - prázdné pole). Vypište hrací pole tak, že miny budou stále reprezentovány '*', ale na každém políčku bez miny bude číslo znamenající celkový počet min, se kterými toto prázdné pole přímo sousedí (sousedit může vodorovně, svisle i šikmo).
<syntaxhighlight lang="Haskell">
minesweeper :: Result -> Result
sampleInput = ["       ",
               " *     ",
               "    *  ",
               "   *   ",
               "      *",
               "***    ",
               "* *    ",
               "***    "]
</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark" >
Prelude>pp(minesweeper sampleInput)
1110000
1*11110
1122*10
001*221
233211*
***2011
*8*3000
***2000
</syntaxhighlight>

== 10 - Želva== 
Implementujte funkci, která nakreslí pohyb želvy po čtvercové mřížce. Bude se jmenovat <code>draw</code> a bude mít jediný parametr - seznam kroků. Naše želva se může pohybovat pouze horizontálně nebo vertikálně. Každý pohyb bude popsán jako dvojice (jejíž typ bude <code>(Char, Int)</code>), kde první element je znak určující směr pohybu a druhý jeho delka. Možné směry jsou: <b>l</b>eft (doleva), <b>r</b>ight (doprava), <b>u</b>p (nahoru), and <b>d</b>own (dolů). Jako výsledek funkce <code>draw</code> vrátí nejmenší možný obdelník se všemi kroky naší želvy. Každý blok mřížky bude reprezentován jedním znakem. Pokud tento blok byl želvou navštíven, pak to bude <code>'X'</code>, pokud nebyl, pak to bude <code>' '</code>.

<syntaxhighlight lang="Haskell">
draw :: [(Char, Int)] -> Result
</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark" >
*Main> pp (draw [('u',5),('r',5),('d',5),('l',10),('d',5),('r',5),('u',5)])      
     XXXXXX
     X    X
     X    X
     X    X
     X    X
XXXXXXXXXXX
X    X
X    X
X    X
X    X
XXXXXX
</syntaxhighlight>

Export translations

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Education

History Entries

Tools