Difference between revisions of "FP Test3 2024"

From Marek Běhálek Wiki
Jump to navigation Jump to search
(Created page with "= Home Preparation For Test 3 - 2024 =")
 
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
<translate>
 
= Home Preparation For Test 3 - 2024 =
 
= Home Preparation For Test 3 - 2024 =
 +
</translate>
 +
 +
<translate>
 +
== Data definition ==
 +
</translate>
 +
 +
<translate>
 +
Consider following type representing a maze:
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">type Maze = [String]</syntaxhighlight>
 +
 +
<translate>
 +
If you want to print this maze on a screen you can use:
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">
 +
printMaze :: Maze -> IO ()
 +
printMaze x = putStr (concat (map (++"\n") x))
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:14-->
 +
Maze example:
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">
 +
sample1 :: Maze
 +
sample1 = ["*********",
 +
          "* *  * *",
 +
          "* * * * *",
 +
          "* * * * *",
 +
          "*  *  *",
 +
          "******* *",
 +
          "        *",
 +
          "*********"]
 +
sample2 :: Maze
 +
sample2 = ["      ",
 +
          "      ",
 +
          "  ***  ",
 +
          "  ***  ",
 +
          "  ***  ",
 +
          "      ",
 +
          "      "]
 +
sample3 :: Maze
 +
sample3 = ["  * *  ",
 +
          " ##### ",
 +
          "  ***  ",
 +
          "  * *  ",
 +
          "  ***  ",
 +
          "    * ",
 +
          "      "]
 +
sample4 :: Maze
 +
sample4 = ["*********",
 +
          "*s*  *e*",
 +
          "* *  * *",
 +
          "* *  * *",
 +
          "*      *",
 +
          "******* *",
 +
          "        *",
 +
          "*********"]
 +
arrow :: Maze
 +
arrow = [ "....#....",
 +
          "...###...",
 +
          "..#.#.#..",
 +
          ".#..#..#.",
 +
          "....#....",
 +
          "....#....",
 +
          "....#####"]
 +
</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
ghci> printMaze sample1                                         
 +
*********
 +
* *  * *
 +
* * * * *
 +
* * * * *
 +
*  *  *
 +
******* *
 +
        *
 +
*********
 +
</syntaxhighlight>
 +
 +
<translate>
 +
== Tasks ==
 +
</translate>
 +
 +
<translate>
 +
Create functions that:
 +
</translate>
 +
 +
<translate>
 +
*Place one maze above another.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">above :: Maze -> Maze -> Maze</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> printMaze(above arrow arrow)
 +
....#....
 +
...###...
 +
..#.#.#..
 +
.#..#..#.
 +
....#....
 +
....#....
 +
....#####
 +
....#....
 +
...###...
 +
..#.#.#..
 +
.#..#..#.
 +
....#....
 +
....#....
 +
....#####
 +
</syntaxhighlight>
 +
 +
<translate>
 +
*Place two mazes side by side (consider, that they have the same height).
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">sideBySide :: Maze -> Maze -> Maze</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> printMaze(sideBySide arrow arrow)
 +
....#........#....
 +
...###......###...
 +
..#.#.#....#.#.#..
 +
.#..#..#..#..#..#.
 +
....#........#....
 +
....#........#....
 +
....#####....#####
 +
</syntaxhighlight>
 +
 +
<translate>
 +
*Rotate maze to the left and to the right.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">
 +
rotateR :: Maze -> Maze
 +
rotateL :: Maze -> Maze
 +
</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> printMaze (rotateR arrow)     
 +
.......
 +
...#...
 +
....#..
 +
.....#.
 +
#######
 +
#....#.
 +
#...#..
 +
#..#...
 +
#......
 +
*Main> printMaze(rotateL arrow)
 +
......#
 +
...#..#
 +
..#...#
 +
.#....#
 +
#######
 +
.#.....
 +
..#....
 +
...#...
 +
.......
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* Define a function <code>getFromMaze</code> that takes a character from a maze. The coordinates are given as: <code>(row index, column index)</code> where the indexes start from <code>(0,0)</code>. The coordinate <code>(0,0)</code> is a top left corner.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">getFromMaze :: Maze -> (Int, Int) -> Char</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
ghci> getFromMaze  sample1  (1,1)
 +
' '
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* Using the same coordinates as for the function above, define a function <code>putIntoMaze</code> that takes a maze and a list of triplets <code>(row index, column index, character)</code> and puts on given coordinate given character.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">putIntoMaze :: Maze -> [(Int, Int, Char)] -> Maze</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
ghci> printMaze(putIntoMaze sample2 [(0,0,'1'),(6,6,'2'),(0,6,'3')])
 +
1    3
 +
 +
  ***
 +
  ***
 +
  ***
 +
 +
      2
 +
</syntaxhighlight>
 +
 +
<translate>
 +
*  Using the same coordinates as for the functions above, define a function <code>getPart</code> that takes a maze and extracts a rectangular part of this maze. The maze is given as first parameter. The extracted part is defined by the position of the top left corner (second parameter) and its size (third parameter, given as (height, width)).
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">
 +
getPart :: Maze -> (Int,Int) -> (Int,Int) -> Maze
 +
</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
ghci> printMaze(getPart sample1 (1,1) (7,7))
 +
*  *
 +
* * *
 +
* * *
 +
  *
 +
******
 +
 +
*******
 +
</syntaxhighlight>
 +
 +
<translate>
 +
* Implement the function <code>solveMaze</code>. It has 1 argument. It is a list of strings representing a maze row by row from top to bottom ('*' - wall, ' ' - empty square, 's' - starting position, 'e' - ending possition). At the beginning we are at position 's' and we want to get the length of the shortest path to the position denotated by 'e'. Such path compose from steps. in each step we can move one square left, right, up or down. The function returns a number of these steps in the shortest path from 's' to 'e'.</translate>
 +
 +
<syntaxhighlight lang="Haskell">solveMaze :: Result -> Int</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
solveMaze sample4
 +
12
 +
</syntaxhighlight>

Latest revision as of 11:29, 15 November 2024

Home Preparation For Test 3 - 2024

Data definition

Consider following type representing a maze: 

type Maze = [String]

If you want to print this maze on a screen you can use: 

printMaze :: Maze -> IO ()
printMaze x = putStr (concat (map (++"\n") x))

Maze example: 

sample1 :: Maze
sample1 = ["*********",
           "* *   * *",
           "* * * * *",
           "* * * * *",
           "*   *   *",
           "******* *",
           "        *",
           "*********"]
sample2 :: Maze
sample2 = ["       ",
           "       ",
           "  ***  ",
           "  ***  ",
           "  ***  ",
           "       ",
           "       "]
sample3 :: Maze
sample3 = ["  * *  ",
           " ##### ",
           "  ***  ",
           "  * *  ",
           "  ***  ",
           "     * ",
           "       "]
sample4 :: Maze
sample4 = ["*********",
           "*s*   *e*",
           "* *   * *",
           "* *   * *",
           "*       *",
           "******* *",
           "        *",
           "*********"]
arrow :: Maze
arrow = [ "....#....",
          "...###...",
          "..#.#.#..",
          ".#..#..#.",
          "....#....",
          "....#....",
          "....#####"]

ghci> printMaze sample1                                           
*********
* *   * *
* * * * *
* * * * *
*   *   *
******* *
        *
*********

Tasks

Create functions that:

  • Place one maze above another.
above :: Maze -> Maze -> Maze

*Main> printMaze(above arrow arrow)
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
....#####
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
....#####
  • Place two mazes side by side (consider, that they have the same height).
sideBySide :: Maze -> Maze -> Maze

*Main> printMaze(sideBySide arrow arrow)
....#........#....
...###......###...
..#.#.#....#.#.#..
.#..#..#..#..#..#.
....#........#....
....#........#....
....#####....#####
  • Rotate maze to the left and to the right.
rotateR :: Maze -> Maze
rotateL :: Maze -> Maze

*Main> printMaze (rotateR arrow)       
.......
...#...
....#..
.....#.
#######
#....#.
#...#..
#..#...
#......
*Main> printMaze(rotateL arrow)
......#
...#..#
..#...#
.#....#
#######
.#.....
..#....
...#...
.......
  • Define a function getFromMaze that takes a character from a maze. The coordinates are given as: (row index, column index) where the indexes start from (0,0). The coordinate (0,0) is a top left corner.
getFromMaze :: Maze -> (Int, Int) -> Char

ghci> getFromMaze  sample1  (1,1)
' '
  • Using the same coordinates as for the function above, define a function putIntoMaze that takes a maze and a list of triplets (row index, column index, character) and puts on given coordinate given character.
putIntoMaze :: Maze -> [(Int, Int, Char)] -> Maze

ghci> printMaze(putIntoMaze sample2 [(0,0,'1'),(6,6,'2'),(0,6,'3')]) 
1     3

  ***
  ***
  ***

      2
  • Using the same coordinates as for the functions above, define a function getPart that takes a maze and extracts a rectangular part of this maze. The maze is given as first parameter. The extracted part is defined by the position of the top left corner (second parameter) and its size (third parameter, given as (height, width)).
getPart :: Maze -> (Int,Int) -> (Int,Int) -> Maze

ghci> printMaze(getPart sample1 (1,1) (7,7))
 *   *
 * * *
 * * *
   *
******

*******
  • Implement the function solveMaze. It has 1 argument. It is a list of strings representing a maze row by row from top to bottom ('*' - wall, ' ' - empty square, 's' - starting position, 'e' - ending possition). At the beginning we are at position 's' and we want to get the length of the shortest path to the position denotated by 'e'. Such path compose from steps. in each step we can move one square left, right, up or down. The function returns a number of these steps in the shortest path from 's' to 'e'.
solveMaze :: Result -> Int

solveMaze sample4 
12
Retrieved from "http://behalek.cs.vsb.cz/wiki/index.php?title=FP_Test3_2024&oldid=3872"