FP Homework 2

Basic notes

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

Lets define a type for the result:

type Result = [String]

Now, if you want to print this result nicely on the screen, you can use:

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

Tasks

1 - Painting I

Lets define a new data types representing a ellipse and a square.

data Point = Point Int Int
data Shape = Ellipse Point Point Int 
           | Square {topLeft:: Point, size::Int}

Using these types write a function view that creates a view of defined shapes. The first parameter is a tuple (columns, rows) defining the size of the resulting view. Left top corner has a coordinate (0,0). Second argument is a list of shapes (either ellipses or squares). Ellipse is given by two focal points and a distance a. Then all points on this ellipse have the distance from both focal points 2a. Square si given by the coordinates of the top most corner (given as Point) and a size of its sides.

view :: (Int,Int) -> [Shape] -> Result

The result may differ based on rounding. In following example '.' was used for the free spot, '#' for the filled spot.

Prelude>pp(view (40,15) [Ellipse (Point 8 4) (Point 16 4) 6, Square {topLeft = Point 15 5, size = 6 }, Ellipse (Point 25 7) (Point 35 12) 7] )
........#########........................
.......##.......##.......................
.......#.........#.......................
......#...........#......................
......#...........#........##............
......#........#######...########........
.......#.......#.#...#..#......###.......
.......##......###...#..#........##......
........#########....#.##.........##.....
...........###.#.....#..#..........##....
...............#.....#..##..........#....
...............#######...##.........##...
..........................##........#....
...........................###......#....
............................########.....
................................##.......

2 - Painting II

Lets define a new data types representing a circle and a rectangle.

data Point = Point Int Int
data Shape = Circle Point Int
           | Rectangle {topLeft:: Point, bottomRight::Point}

Using these types write a function view that creates a view of defined shapes. The first parameter is a tuple (columns, rows) defining the size of the resulting view. Left top corner has a coordinate (0,0). Second argument is a list of shapes (either circles or rectangles).

view :: (Int,Int) -> [Shape] -> Result

The result may differ based on rounding. In following example '.' was used for the free spot, '#' for the filled spot.

Prelude>pp(view (40,15) [Circle (Point 8 4) 5, Rectangle {topLeft = (Point 15 5), bottomRight = (Point 35 12) }, Circle (Point 30 12) 8] )
....###...###...........................
....#.......#...........................
...##.......##..........................
...#.........#..........................
...#.........#.............#######......
...#.........#.#####################....
...##.......##.#........##.........##...
....#.......#..#.......##..........###..
....###...###..#.......#...........#.#..
......#####....#......##...........#.##.
...............#......#............#..#.
...............#......#............#..#.
...............#####################..#.
......................#...............#.
......................#...............#.

3 - Drawing I

Lets define a new data types representing a point and a line.

data Point = Point Int Int
data Line = Line Point Point

Using these types write a function drawLines that creates a view of defined lines. The first parameter is a tuple (columns, rows) defining the size of the resulting view. Left top corner has a coordinate (0,0). Second argument is a list of lines.

drawLines :: (Int,Int) -> [Line] -> Result

The result may differ based on rounding. In following example '.' was used for the free spot, '#' for the filled spot.

Prelude>pp(drawLines (31,15) [Line (Point x y) (Point 15 7)|(x,y)<-concat [[(x,y)|y<-[0,7,14]]|x<-[0,15,30]]])
##.............#.............##
..##...........#...........##..
....##.........#.........##....
.....###.......#.......###.....
........##.....#.....##........
..........###..#..###..........
.............#####.............
###############################
.............#####.............
..........###..#..###..........
........##.....#.....##........
.....###.......#.......###.....
....##.........#.........##....
..##...........#...........##..
##.............#.............##

4 - Drawing II

Lets define a new data types representing a point and a triangle.

data Point = Point Int Int
data Triangle = Triangle Point Point Point

Using these types write a function drawTriangles that creates a view of defined triangles. The first parameter is a tuple (columns, rows) defining the size of the resulting view. Left top corner has a coordinate (0,0). Second argument is a list of triangles.

drawTriangles :: (Int,Int) -> [Triangle] -> Result

The result may differ based on rounding. In following example '.' was used for the free spot, '#' for the filled spot.

Prelude>pp(drawTriangles  (40,15) [(Triangle (Point 7 4) (Point 33 4) (Point 20 14)),(Triangle (Point 7 11) (Point 33 11) (Point 20 1))])
.........................................
....................#....................
..................##.##..................
.................##....#.................
.......###########################.......
........##....##.........#.....##........
..........#..##...........##..##.........
..........###..............###...........
..........###..............###...........
..........#..##...........##..##.........
........##....##.........#.....##........
.......###########################.......
.................##....#.................
..................##.##..................
....................#....................
.........................................

5 - Filling

Lets define a picture that is composed from '.' which is used for a free spot and '#' is used for the filled spot.

sampleInput = 
   ["....................",
    "....................",
    "....#####...........",
    "...##...##..........",
    "..##.....##.........",
    "..#.......#.........",
    "..#...############..",
    "..#...#...#......#..",
    "..##..#..##......#..",
    "...##.#.##.......#..",
    "....#####........#..",
    "......#..........#..",
    "......############..",
    "....................",
    "...................."]

Write a function fill that takes a defined picture and a starting position (tuple (column, row)) and it fills the continuous area of free cells starting from the defined starting position with character '*'. You can use the algorithm flood fill.

fill :: Result -> (Int,Int) -> Result

Prelude> pp(fill sampleInput (0,0))
********************
********************
****#####***********
***##...##**********
**##.....##*********
**#.......#*********
**#...############**
**#...#...#......#**
**##..#..##......#**
***##.#.##.......#**
****#####........#**
******#..........#**
******############**
********************
********************

6 - Maze

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

sampleInput1 = ["*********",
                "*s*   *e*",
                "* *   * *",
                "* *   * *",
                "*       *",
                "******* *",
                "        *",
                "*********"]
sampleInput2 = ["*********",
                "*s*   * *",
                "* *   * *",
                "* *   * *",
                "*       *",
                "******* *",
                "e       *",
                "*********"

ghci> solveMaze sampleInput1 
12
ghci> solveMaze sampleInput2 
18

7 - Drilling

Lets assume, that we have an automatic drilling machine. It get a schedule - possitions of holes that needs to be drilled and drills them. Our drilling machine moves only horizontally or vertically. The coast of drilling is the length of the path, that the driller needs to follow. The machine always starts at position (0,0) and at the end it returns to this starting position.

For example, if we need to drill just one hole at position (10,10), the driller moves from (0,0) to (10,10), the cost of this movement is 20, then it returns to position (0,0), it cost again 20. So, the overall cost is 40.

In our task, we need to drill all holes, but the order in which they are drilled is not strict. It is important to note, that ordering in which we drill the holes affects resulting cost.

For example, if we drill holes in the order: (0,10) (10, 0) (10, 10) then the cost will be 60. If we change the order to: (0,10) (10, 10) (10, 0), then the cost will be 40.

Write a function scheduleDrilling that takes a list of hole's positions ([Point]) and it finds the order in which they can be drilled with the lowes cost. If there are more solutions, with the same cost, return any of them. It will be returned as a tupple ([Point], Int).

type Schedule = [Point]
data Point = Point {getX :: Int, getY :: Int } deriving (Eq, Show)

task1 = [Point 1 1,
         Point 10 10,
         Point 8 1,
         Point 1 8,
         Point 8 2,
         Point 7 2]

task2 = [Point 10 10]

task3 = [Point 0 10,
         Point 10 0,
         Point 10 10]

scheduleDrilling :: [Point] -> ([Point], Int)

ghci> scheduleDrilling task1 
([Point {getX = 1, getY = 1},Point {getX = 1, getY = 8},Point {getX = 10, getY = 10},Point {getX = 8, getY = 1},Point {getX = 8, getY = 2},Point {getX = 7, getY = 2}],42)
ghci> scheduleDrilling task2 
([Point {getX = 10, getY = 10}],40)
ghci> scheduleDrilling task3 
([Point {getX = 0, getY = 10},Point {getX = 10, getY = 10},Point {getX = 10, getY = 0}],40)

8 - Components

Lets assume, that we have a graph. In our exercise, a graph will be defined as a set of nodes. Each node have a unique index (Int), that distinguish this node form all other nodes. Nodes are connected by edges. Every node has a set of indexes of its neighbors, in other words, this list contains indexes of all nodes that shares some edge with the original node. It is represented by type: Node

data Node = Node {index::Int, neighbors::[Int] } deriving (Show, Eq)
type Graph = [Node]

A component is a set of nodes, where if we take two distinct nodes $n_{x}$ and $n_{y}$ from the component, then they are connected. Two nodes are connected, if there is a path (composed from edges) that we can take to get from $n_{x}$ to $n_{y}$. In detail, it it explained here: https://en.wikipedia.org/wiki/Component_(graph_theory)#Algorithms

Write a function components that takes a list of nodes ([Node]) - our Graph and divides these graph into components. The result will be [[Int]], where each of inner lists are indexes of nodes, that forms a component (as was defined above).

graph1 :: Graph
graph1=[
        Node 1 [2,3],
        Node 2 [1],
        Node 3 [1],
        Node 4 [5,6],
        Node 5 [7,4],
        Node 6 [4,7],
        Node 7 [5,6,8],
        Node 8 [7],
        Node 9 []
      ]  

components::Graph -> [[Int]]

ghci> components graph1 
[[1,2,3],[4,5,6,7,8],[9]]

9 - Path in Graph

Lets assume, that we have a graph. In our exercise, a graph will be defined as a set of nodes. Each node have a unique index (Int), that distinguish this node form all other nodes. Nodes are connected by edges. Every node has a set of indexes of its neighbors, in other words, this list contains indexes of all nodes that shares some edge with the original node. It is represented by type: Node

data Node = Node {index::Int, neighbors::[Int] } deriving (Show, Eq)
type Graph = [Node]

A path is a list of nodes, where if we take any two consecutive nodes $n_{x}$ and $n_{y}$ from this path, then they are connected by an edge. Your task will be to find a path between two given nodes. One possibility how to find a path between two nodes is Breadth-first search algorithm, it is explained here: https://en.wikipedia.org/wiki/Breadth-first_search

Write a function path that takes a list of nodes ([Node]) - our Graph and two nodes indexes (Int) and finds a path between these two nodes. The result will be the path as a list of nodes ([Int]), you can safely assume, that there is always a path beetwen given nodes.

graph1 :: Graph
graph1=[
        Node 1 [2,3],
        Node 2 [1],
        Node 3 [1,4],
        Node 4 [5,6],
        Node 5 [7,4],
        Node 6 [4,7],
        Node 7 [5,6,8],
        Node 8 [7],
        Node 9 []
      ]  

path :: Graph -> Int -> Int -> [Int]

ghci> path graph1 1 8 
[1,3,4,5,7,8]

Deprecated

4 - Poker

Lets define a data types representing a deck of Poker cards. In Poker, a player gets 5 cards into the hand. Dealt hands are classified into several categories. These categories are important to define who is the winner. Rules for each category cen be found Here

data Suit = Hearts | Clubs | Diamonds | Spades deriving (Eq, Show)
data Rank = Numeric Int | Jack | Queen | King | Ace deriving (Eq, Show)
data Card = Card Rank Suit deriving (Eq, Show)
type Hand = [Card]
data Category = RoyalFlush
              | StraightFlush
              | Four
              | FullHouse
              | Flush
              | Straight
              | Three
              | TwoPair
              | Pair
              | HighCard deriving (Eq, Show)

Write a function decide that takes 5 dealt cards - Hand and returns a poker category in which it fits.

decide:: Hand -> Category

Prelude> decide [Card (Numeric 2) Hearts,Card (Numeric 2) Clubs,Card Ace Hearts,Card Ace Clubs,Card King Spades]
TwoPair
Prelude> decide [Card (Numeric 2) Hearts,Card (Numeric 2) Clubs,Card Ace Hearts,Card Ace Clubs,Card Ace Spades]
FullHouse
Prelude> decide [Card Ace Hearts,Card (Numeric 2) Hearts,Card (Numeric 5) Hearts,Card (Numeric 3) Hearts,Card (Numeric 4) Clubs]
Straight
Prelude> decide [Card (Numeric 2) Hearts,Card (Numeric 5) Clubs,Card Ace Hearts,Card King Clubs,Card Jack Spades]
HighCard

5 - Cubes

Lets assume, that we have a 3D model composed from cubes in standard Euclidean space. In our model, we are using only positive integers. Each of these cubes is defined by its corner with the smallest x, y and z coordinates and by its size. Also each of these boxes have a color. In our case, while we are using only a text mode, it will be a character. You can assume, that the cubes in our model do not overlap, but there can be cubes placed above other cubes. In the code, it will be represented by following type Cube

-- Point x y z
data Point = Point Int Int Int
data Cube = Cube {start::Point, size::Int, color::Char }

Write a function view that takes a list of cubes ([Cube]) and returns a floor plan (a view from the top). The size of this floor plan will be computed based on the size of the boxes in the input. The result will be a list of strings. Use following function pp to print it on the screen. For the output format, see the sample output bellow. The bottom left corner has the coordinates (0,0), y-axis corresponds to rows and x-axis to columns. Visible parts of the cubes are visualized by its colors. Empty space is represented by character ' '.

sampleInput :: [Cube]
sampleInput = [Cube { start = Point 1 1 10, size = 4, color = 'X'}, 
               Cube { start = Point 1 5 10, size = 3, color = 'O'},
               Cube { start = Point 10 8 0, size = 2, color = '#'},
               Cube { start = Point 0 0 0, size = 10, color = '*'}]

view :: [Cube] -> Result

*Main> pp (view sampleInput )
**********##
**********##
*OOO******
*OOO******
*OOO******
*XXXX*****
*XXXX*****
*XXXX*****
*XXXX*****
**********

6 - Components

Lets assume, that we have a 3D model composed from cubes in standard Euclidean space. In our model, we are using only positive integers. Each of these cubes is defined by its corner with the smallest x, y and z coordinates and by its size. It will be represented by following type Cube

-- Point x y z
data Point = Point Int Int Int deriving (Eq, Show)
data Cube = Cube {start::Point, size::Int }  deriving (Eq, Show)

Cubes in our model do overlap. To overlap, they need to have some shared volume, just touching is not enough. A component is a set of cubes that are overlapping. In other words, if we want to add a cube x to a component, we need to find a cube from the component, that overlaps with the cube x

Write a function components that takes a list of cubes ([Cube]) and as a result divides these cubes into components. The result will be [[Cube]], where each of inner lists represents a component (as was defined above). You can use function printIt to print each of these components on a separated line.

sampleInput :: [Cube]
sampleInput = [Cube { start = Point 0 0 0, size = 5},
               Cube { start = Point 4 4 4, size = 5},
               Cube { start = Point 8 8 8, size = 4}, 
               Cube { start = Point 12 12 12, size = 2},
               Cube { start = Point 13 13 13, size = 2},
               Cube { start = Point 10 10 0, size = 2},
               Cube { start = Point 9  9 0, size = 4}]

printIt :: [[Cube]] -> IO ()
printIt components = putStr (concat [show component ++ "\n" |component<-components])

components::[Cube] -> [[Cube]]

*Main> printIt (components sampleInput) 
[Cube {start = Point 0 0 0, size = 5},Cube {start = Point 4 4 4, size = 5},Cube {start = Point 8 8 8, size = 4}]
[Cube {start = Point 12 12 12, size = 2},Cube {start = Point 13 13 13, size = 2}]
[Cube {start = Point 10 10 0, size = 2},Cube {start = Point 9 9 0, size = 4}]