Export translations

Settings

Group

Language

Format

Export for off-line translation

Export in native format

{{DISPLAYTITLE:FP Homework 1}}== Basic notes ==

In all exercises you are required to write something to standard output. You can use the same strategy as in  [[FP_Laboratory_7 | Laboratory 7]].

Lets define a type for the result:
<syntaxhighlight lang="Haskell">type Result = [String]</syntaxhighlight>
Now, if you want to print this result nicely on the screen, you can use:
<syntaxhighlight lang="Haskell">
pp :: Result -> IO ()
pp x = putStr (concat (map (++"\n") x))
</syntaxhighlight>

== Example - Ships ==

Implement the function <code>ships</code> which has 2 arguments. First argument is a list of strings representing play field of one player row by row from top to bottom ('o' - square containing a ship, ' ' - empty square). Second list contains coordinates of squares attacked by second player. Print actual state of a play in the way where every row and column will be labelled by its number or letter, 'o' will be square with ship not attacked yet, 'x' square with ship already attacked, '.' already attacked empty square, ' ' empty square not attacked yet. You can consider that the size of play-field is 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 ==

Implement the function <code>puzzle</code>, it will simulate the game similar to [https://en.wikipedia.org/wiki/15_puzzle 15 Puzzle]. In our case, we have 25 squares, where 24 squares are ocupied by tiles with big case letters from <code>'A'</code> to <code>'X'</code>. One tile is free, it is denotated by <code>' '</code>. In one move, you can move a tile (denotated by its letter) into the free one. The function gets the original configuration and a sequence of '''valid''' moves. It will output the resulting configuration.
<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 - Crossword Answers ==

Implement the function <code>answers</code> 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'' <code>words :: String -> [String]</code> ''to split lines into sequence of words.''

<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 - Creating Crossword Puzzles==

In this task, you will implement a function, that helps when creating the crossword puzzle. The function <code>positions</code> 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 (<code>'.'</code>), where we can put some character, and from black boxes (<code>'#'</code>), 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 <code>(row, column)</code>. They are indexed from topmost leftmost corner with coordinates <code>(0,0)</code>. Consider only words in '''lines''' (for rows, we can rotate and flip the puzzle outline and use the same function).

<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 - 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 <code>decode</code> takes an encoded text and a vocabulary. Vocabulary is a sequence of pairs, where the first element is an encoded character (<code>Char</code>) and the second element is the original pair (as <code>String</code> 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.

<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 - Prefix Decoder ==

One possibility, how to code characters into the binary code is to use prefix coding (an example can be  [https://en.wikipedia.org/wiki/Huffman_coding Huffman coding] ). In this coding, a given code is not ''a prefix'' of any other code. If for example, one letter is coded as <code>101</code>, then no other letter's code starts with the same sequence <code>101</code>. In this task, write a function <code>toText</code>, that takes an encoded binary sequence (in our case <code>String</code> composed from <code>1</code> and <code>0</code>) along with a dictionary, and produces the original text like a result. Dictionary compose of pairs, where each pair contains the encrypted character (<code>Char</code>) and a sequence (<code>String</code>) of <code>1</code> and <code>0</code> - assigned prefix code. Safely assume, that all inputs are '''valid'''.

<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 - Chess position ==

Implement the function <code>chess</code> which has 2 arguments of the type <code>[String]</code>. Each of these strings in both lists contain 3 characters:
* first stands for chess piece ('K' - king, 'Q' - queen, 'R' - rook, 'B' - bishop, 'N' - knight, 'P' - pawn)
* second stands for column ('a'-'h')
* third is row ('1'-'8')
First list contains actual positions of white pieces and second list positions of black pieces. Print actual state of a chessboard in the way where '.' stands for empty square, capital letters mean white pieces and small letters mean black pieces. Each row and column should be labeled by its number or letter.
<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 ==
 
Implement the function <code>ticktack</code> which has 2 arguments. First argument is a tuple of natural numbers and defines the number of columns and rows  of a play field. Coordinates are counted from bottom left corner. Second list contains a record of a match of ticktacktoe game given by coordinates on which played in turns player 'x' and player 'o'. Print actual state of the game in the way where play-field will be bordered by characters '-' and '|', empty squares ' ' and characters 'x' and 'o' will be on squares where the players have played.
<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 - Maze ==

Implement the function <code>maze</code> which has 2 arguments. First argument is a list of strings representing a maze row by row from top to bottom ('*' - wall, ' ' - empty square, 's' - starting position). At the beginning we are at position 's'. Second argument is list of directions ('d' - down, 'u' - up, 'l' - left, 'r' - right). Each letter means move by one square in the given direction and on this new square character '.' is placed. Print actual state of a maze.
<syntaxhighlight lang="Haskell">
maze :: Result -> String -> Result

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

== 9 - Minesweeper ==

Implement the function <code>minesweeper</code> which has 1 argument of the type list of strings. The strings represent play field row by row from top to bottom ('*' - mine, ' ' - empty square). Print play field in a way where mines will be represented by '*' and on each square not containing a mine will be a number - count of all mines directly adjacent to this square (it can be adjacent vertically, horizontally or diagonally).
<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 - Turtle ==
Implement a function that will draw the movement of a turtle in a rectangular grid. It will be named <code>draw</code> and it will have one parameter - a list movements. Our turtle can move only horizontally or vertically. Each movement will be described by a pair (its type will be <code>(Char, Int)</code>), where the first character denotates a direction of this movement and the second its length. Possible directions are: <b>l</b>eft, <b>r</b>ight, <b>u</b>p, and <b>d</b>own. As the result, function <code>draw</code> returns a smallest possible rectangle with all turtle's movements. Each block from the grid will be represented with one character. If it was visited by our turtle, then it will be <code>'X'</code>, if it was not, then it will be <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