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 Cvičení 7.
Definujme si typ pro výstup:
type Result = [String]
Nyní, pokud chceme pěkně vypsat takovýto výstup na obrazovku, můžeme použít:
pp :: Result -> IO ()
pp x = putStr (concat (map (++"\n") x))
Příklad - Lodě
Napište funkci ships, 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.
ships :: Result -> [(Char, Int)] -> Result
sampleInput = [" o o ",
" ooo ",
" oo ",
" ",
" o ",
" o ",
" o ",
" ",
" ",
" oooo "]
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
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)])
2021/2022 Domácí úkol
1 - Magic 15 Puzzle
Implementujte funkci puzzle, ta bude simulovat hru podobnou 15 Puzzle. V našem případě máme 25 čtverců, kde 24 čtverců je obsazeno kostičkami s velkými písmeny od 'A' do 'X'. Jedna dlaždice je zdarma, je označena ' '. 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.
puzzle2 = ["AC DE",
"FBHIJ",
"KGLNO",
"PQMRS",
"UVWXT"]
puzzle :: Result -> [Char] -> Result
*Main> pp(puzzle puzzle2 "CBGLMRST")
ABCDE
FGHIJ
KLMNO
PQRST
UVWX
2 - Crossword Answers
Implement the function answers that takes as an input a crosword puzzle's solution and outputs all words from this solution. Words will be divided into two lists, first for lines (from left to right) and second for columns (from top to bottom). A word is written only if it is longer than just one character.
- TIP: Use the function
words :: String -> [String]to split lines into sequence of words.
*Main> words "ABC cdef ghijkl"
["ABC","cdef","ghijkl"]
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])
*Main> answers solution1
(["DAD","SEND","EAST","ITSY","NERF","ARK","SYNC","MESH","EVER","NEAR"],["DOWN","MAN","EASE","DEAR","FATHER","STINKS","YARD","STUN","DAY","CARD"])
3 - Creating Crossword Puzzles
In this task, you will implement a function, that helps when creating the crossword puzzle. The function positions takes an input, an outline for the future puzzle, and prints all positions, where we need to put some words. The outline compose from empty spaces ('.'), where we can put some character, and from black boxes ('#'), where there are no characters. In our crossword puzzles, words need to be placed in all sequences of empty spaces, that are at least two spaces long. The functions output is all starting positions where we need to put some words. Positions are pairs (row, column). They are indexed from topmost leftmost corner with coordinates (0,0). Consider only words in lines (for rows, we can rotate and flip the puzzle outline and use the same function).
--An example of a crossword puzzle with the same outline is in the previous task.
crossword = ["...##....",
".#....##.",
".#.##....",
"....#.#.#",
"#.#...#.#",
"#.#.#....",
"....##.#.",
".##....#.",
"....##.#."]
positions :: Result -> [(Int,Int)]
*Main> positions crossword
[(0,0),(0,5),(1,2),(2,5),(3,0),(4,3),(5,5),(6,0),(7,3),(8,0)]
4 - Decoder
On possibility how to encode text is to replace frequent pairs of characters by a new (until that time, not used) character.
In this task, you should implement a function that decodes such encoded text. The function decode takes an encoded text and a vocabulary. Vocabulary is a sequence of pairs, where the first element is an encoded character (Char) and the second element is the original pair (as String of the length 2). The result is an original text. In fact, it is the text from the parameter, where all encoded characters were replaced by its original pairs of characters.
decode :: String -> [(Char,String)] -> String
*Main> decode "HAHA" [('E',"AB"),('F',"CD"),('G',"EF"),('H',"GG")]
"ABCDABCDAABCDABCDA"
5 - Prefix Decoder
One possibility, how to code characters into the binary code is to use prefix coding (an example can be Huffman coding ). In this coding, a given code is not a prefix of any other code. If for example, one letter is coded as 101, then no other letter's code starts with the same sequence 101. In this task, write a function toText, that takes an encoded binary sequence (in our case String composed from 1 and 0) along with a dictionary, and produces the original text like a result. Dictionary compose of pairs, where each pair contains the encrypted character (Char) and a sequence (String) of 1 and 0 - assigned prefix code. Safely assume, that all inputs are valid.
dictionary = [('a',"0"),('b',"101"),('c',"100"),('d',"111"),('e',"1101"),('f',"1100")]
toText :: String->[(Char, String)]->String
*Main> toText "01011001111101" dictionary
"abcde"
2020/2021 Homeworks
1 - Šachové pozice
Napište funkci chess, která má 2 argumenty typu [String]. Ř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.
chess :: [String] -> [String] -> Result
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
2 - Ticktacktoe
Napište funkci ticktack, 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.
ticktack::(Int,Int) -> [(Int,Int)] -> Result
Prelude>pp(ticktack (8,8) [(1,1),(8,8),(2,2),(3,3),(4,2),(3,2)])
----------
| o|
| |
| |
| |
| |
| o |
| xox |
|x |
----------
3 - Bludiště
Napište funkci maze, 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.
maze :: Result -> String -> Result
sampleInput = ["*********",
"*s* * *",
"* * * * *",
"* * * * *",
"* * *",
"******* *",
" *",
"*********"]
Prelude>pp(maze sampleInput "dddrruuurrdddrrddllllll")
*********
*s*...* *
*.*.*.* *
*.*.*.* *
*...*...*
*******.*
.......*
*********
4 - Hledání min
Napište funkci minesweeper, 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).
minesweeper :: Result -> Result
sampleInput = [" ",
" * ",
" * ",
" * ",
" *",
"*** ",
"* * ",
"*** "]
Prelude>pp(minesweeper sampleInput)
1110000
1*11110
1122*10
001*221
233211*
***2011
*8*3000
***2000
5 - Želva
Implementujte funkci, která nakreslí pohyb želvy po čtvercové mřížce. Bude se jmenovat draw 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 (Char, Int)), kde první element je znak určující směr pohybu a druhý jeho delka. Možné směry jsou: left (doleva), right (doprava), up (nahoru), and down (dolů). Jako výsledek funkce draw 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 'X', pokud nebyl, pak to bude ' '.
draw :: [(Char, Int)] -> Result
*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
