FP Homework 1 - Revision history

Beh01 at 08:53, 7 October 2022

2022-10-07T08:53:39Z

Beh01: Marked this version for translation

2021-10-07T09:31:45Z

Marked this version for translation

Beh01 at 09:30, 7 October 2021

2021-10-07T09:30:49Z

Beh01 at 09:25, 7 October 2021

2021-10-07T09:25:54Z

Beh01: /* 5 - Prefix Decoder */

2021-10-07T09:11:37Z

5 - Prefix Decoder

Beh01 at 09:10, 7 October 2021

2021-10-07T09:10:05Z

Beh01: /* 3 - Creating Crossword Puzzles */

2021-10-06T13:56:42Z

3 - Creating Crossword Puzzles

Beh01: /* 3 - Creating Crossword Puzzles */

2021-10-06T13:53:28Z

3 - Creating Crossword Puzzles

Beh01: /* 3 - Creating crossword puzzles */

2021-10-06T13:52:13Z

3 - Creating crossword puzzles

Beh01 at 13:31, 6 October 2021

2021-10-06T13:31:58Z

@@ Line 90: / Line 90: @@
 <translate>
 == 1 - Magic 15 Puzzle == <!--T:16-->
@@ Line 213: / Line 212: @@
 <translate>
-= 2020/2021 Homeworks = <!--T:27-->
+== 6 - Chess position == <!--T:5-->
 <!--T:6-->
@@ Line 243: / Line 238: @@
 </syntaxhighlight>
 <translate>
-== 2 - Ticktacktoe == <!--T:7-->
+== 7 - Ticktacktoe == <!--T:7-->
 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.
@@ Line 265: / Line 260: @@
 <translate>
-== 3 - Maze == <!--T:8-->
+== 8 - Maze == <!--T:8-->
 <!--T:9-->
@@ Line 295: / Line 290: @@
 <translate>
-== 4 - Minesweeper == <!--T:10-->
+== 9 - Minesweeper == <!--T:10-->
 <!--T:11-->
@@ Line 324: / Line 319: @@
 <translate>
-== 5 - Turtle == <!--T:14-->
+== 10 - Turtle == <!--T:14-->
 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>.
 </translate>

@@ Line 90: / Line 90: @@
 <translate>
-= 2021/2022 Homeworks =
+= 2021/2022 Homeworks = <!--T:15-->
-== 1 - Magic 15 Puzzle ==
+== 1 - Magic 15 Puzzle == <!--T:16-->
 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.
 </translate>
@@ Line 116: / Line 117: @@
 <translate>
-== 2 - Crossword Answers ==
+== 2 - Crossword Answers == <!--T:18-->
 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.''
 </translate>
@@ Line 148: / Line 151: @@
 <translate>
-== 3 - Creating Crossword Puzzles==
+== 3 - Creating Crossword Puzzles== <!--T:21-->
 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).
 </translate>
@@ Line 174: / Line 178: @@
 <translate>
-== 4 - Decoder ==
+== 4 - Decoder == <!--T:23-->
 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.
@@ Line 190: / Line 195: @@
 <translate>
-== 5 - Prefix Decoder ==
+== 5 - Prefix Decoder == <!--T:25-->
 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'''.
 </translate>
@@ Line 207: / Line 213: @@
 <translate>
-= 2020/2021 Homeworks =
+= 2020/2021 Homeworks = <!--T:27-->
 </translate>
@@ Line 318: / Line 324: @@
 <translate>
-== 5 - Turtle ==  <!--T:14-->
+== 5 - Turtle == <!--T:14-->
 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>.
 </translate>

@@ Line 89: / Line 89: @@
 <div style="clear:both"></div>
 = 2021/2022 Homeworks =
@@ Line 94: / Line 95: @@
 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",
@@ Line 113: / Line 115: @@
 </syntaxhighlight>
 == 2 - Crossword Answers ==
@@ Line 118: / Line 121: @@
 *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"
@@ Line 142: / Line 147: @@
 </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">
@@ Line 166: / Line 173: @@
 </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">
@@ Line 180: / Line 189: @@
 </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">
@@ Line 195: / Line 206: @@
 </syntaxhighlight>
 = 2020/2021 Homeworks =
 <translate>
 == 1 - Chess position == <!--T:5-->

@@ Line 182: / Line 182: @@
 == 5 - Prefix Decoder ==
-The function <code>toText</code>
+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">

@@ Line 185: / Line 185: @@
 <syntaxhighlight lang="Haskell">
-vocabulary = [('a',"0"),('b',"101"),('c',"100"),('d',"111"),('e',"1101"),('f',"1100")]
+dictionary = [('a',"0"),('b',"101"),('c',"100"),('d',"111"),('e',"1101"),('f',"1100")]
 toText :: String->[(Char, String)]->String
@@ Line 191: / Line 191: @@
 <syntaxhighlight lang="Haskell" class="myDark" >
-*Main> toText "01011001111101" vocabulary
+*Main> toText "01011001111101" dictionary
 "abcde"
 </syntaxhighlight>

@@ Line 178: / Line 178: @@
 *Main> decode "HAHA" [('E',"AB"),('F',"CD"),('G',"EF"),('H',"GG")]
 "ABCDABCDAABCDABCDA"
 </syntaxhighlight>

@@ Line 140: / Line 140: @@
 *Main> answers solution1
 (["DAD","SEND","EAST","ITSY","NERF","ARK","SYNC","MESH","EVER","NEAR"],["DOWN","MAN","EASE","DEAR","FATHER","STINKS","YARD","STUN","DAY","CARD"])
 </syntaxhighlight>