FP Homework 2 - Revision history

Beh01: /* 9 - Path in Graph */

2023-11-16T11:35:17Z

9 - Path in Graph

Beh01 at 11:34, 16 November 2023

2023-11-16T11:34:07Z

Beh01: /* 9 - Path in Graph */

2023-11-16T11:32:38Z

9 - Path in Graph

Beh01 at 10:19, 16 November 2023

2023-11-16T10:19:14Z

Beh01 at 07:31, 16 November 2023

2023-11-16T07:31:39Z

Beh01 at 07:41, 14 November 2023

2023-11-14T07:41:17Z

Beh01 at 07:38, 14 November 2023

2023-11-14T07:38:28Z

Show changes

Beh01 at 07:30, 11 November 2022

2022-11-11T07:30:49Z

Beh01: /* 5 - Drilling */

2022-11-10T20:10:27Z

5 - Drilling

Beh01: /* 5 - Drilling */

2022-11-10T20:06:35Z

5 - Drilling

@@ Line 308: / Line 308: @@
 </syntaxhighlight>
-A ''path'' is a list of nodes, where if we take any two consecutive nodes <math>n_x</math> and <math>n_y</math> 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 it explained here: https://en.wikipedia.org/wiki/Breadth-first_search
+A ''path'' is a list of nodes, where if we take any two consecutive nodes <math>n_x</math> and <math>n_y</math> 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 <code>path </code> that takes a list of nodes (<code>[Node]</code>) - our <code>Graph</code> and two nodes indexes (<code>Int</code>) and finds a path between these two nodes. The result will be the path as a list of nodes (<code><nowiki>[Int]</nowiki></code>), you can safely assume, that there is '''always''' a path beetwen given nodes.

@@ Line 310: / Line 310: @@
 A ''path'' is a list of nodes, where if we take any two consecutive nodes <math>n_x</math> and <math>n_y</math> 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 it explained here: https://en.wikipedia.org/wiki/Breadth-first_search
-Write a function <code>components</code> that takes a list of nodes (<code>[Node]</code>) - our <code>Graph</code> and two nodes indexes (<code>Int</code>) and finds a path between these two nodes. The result will be the path as a list of nodes (<code><nowiki>[Int]</nowiki></code>), you can safely assume, that there is '''always''' a path beetwen given nodes.
+Write a function <code>path </code> that takes a list of nodes (<code>[Node]</code>) - our <code>Graph</code> and two nodes indexes (<code>Int</code>) and finds a path between these two nodes. The result will be the path as a list of nodes (<code><nowiki>[Int]</nowiki></code>), you can safely assume, that there is '''always''' a path beetwen given nodes.
 <syntaxhighlight lang="Haskell">

@@ Line 308: / Line 308: @@
 </syntaxhighlight>
-A ''path'' is a list of nodes, where if we take two distinct nodes <math>n_x</math> and <math>n_y</math> from the original graph, then they are connected by an edge. In detail, it it explained here: https://en.wikipedia.org/wiki/Breadth-first_search
+A ''path'' is a list of nodes, where if we take any two consecutive nodes <math>n_x</math> and <math>n_y</math> 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 it explained here: https://en.wikipedia.org/wiki/Breadth-first_search
 <syntaxhighlight lang="Haskell">
 graph1 :: Graph
@@ Line 316: / Line 317: @@
          Node 1 [2,3],
          Node 2 [1],
-         Node 3 [1],
+         Node 3 [1,4],
          Node 4 [5,6],
          Node 5 [7,4],
@@ Line 325: / Line 326: @@
+       ]
-components::Graph -> [[Int]]
+path :: Graph -> Int -> Int -> [Int]
 </syntaxhighlight>
 <syntaxhighlight lang="Haskell" class="myDark" >
-ghci> components graph1
+ghci> path graph1 1 8
-[[1,2,3],[4,5,6,7,8],[9]]
+[1,3,4,5,7,8]
 </syntaxhighlight>
 = Deprecated=

@@ Line 299: / Line 299: @@
 [[1,2,3],[4,5,6,7,8],[9]]
 </syntaxhighlight>
 = Deprecated=

@@ Line 11: / Line 11: @@
 </syntaxhighlight>
-= 2022 =
+= Tasks =
 == 1 - Painting I ==

@@ Line 196: / Line 196: @@
 </syntaxhighlight>
-== 4 - Maze ==
+== 6 - Maze ==
 <!--T:9-->
@@ Line 228: / Line 228: @@
 </syntaxhighlight>
-== 5 - Drilling ==
+== 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.
@@ Line 268: / Line 268: @@
 </syntaxhighlight>
-== 6 - Components ==
+== 8 - Components ==
 Lets assume, that we have a [https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) graph]. In our exercise, a graph will be defined as a set of nodes. Each node have a unique '''index''' (<code>Int</code>), 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: <code>Node</code>
@@ Line 300: / Line 300: @@
 </syntaxhighlight>
-= 2021 =
+= Deprecated=
 == 4 - Poker ==

@@ Line 224: / Line 224: @@
 type Graph = [Node]
 </syntaxhighlight>
-A ''component'' is a set of nodes, where if we take two distinct nodes <math>n_x</math> and <math>n_y</math> 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 <math>n_x</math> to <math>n_y</math>. Deaily, it it explained here: https://en.wikipedia.org/wiki/Component_(graph_theory)#Algorithms
+A ''component'' is a set of nodes, where if we take two distinct nodes <math>n_x</math> and <math>n_y</math> 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 <math>n_x</math> to <math>n_y</math>. In detail, it it explained here: https://en.wikipedia.org/wiki/Component_(graph_theory)#Algorithms
 Write a function <code>components</code> that takes a list of nodes (<code>[Node]</code>) - our <code>Graph</code> and divides these graph into components. The result will be <code><nowiki>[[Int]]</nowiki></code>, where each of inner lists are indexes of nodes, that forms a component (as was defined above).

@@ Line 187: / Line 187: @@
 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 <code>scheduleDrilling</code> that takes a list of holes (<code>[Point]</code>) and finds the best order with lowest cost, returned as tupple <code>([Point], Int)</code>.
+Write a function <code>scheduleDrilling</code> that takes a list of hole's positions (<code>[Point]</code>) 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 <code>([Point], Int)</code>.
 <syntaxhighlight lang="Haskell">
 type Schedule = [Point]

@@ Line 183: / Line 183: @@
 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 is important in resulting cost for drilling.
+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 <code>scheduleDrilling</code> that takes a list of holes (<code>[Point]</code>) and finds the best order (with lowest cost) in which we can drill these holes.
+Write a function <code>scheduleDrilling</code> that takes a list of holes (<code>[Point]</code>) and finds the best order with lowest cost, returned as tupple <code>([Point], Int)</code>.
 <syntaxhighlight lang="Haskell">
 type Schedule = [Point]