5 // implement it, but do not make any changes to the |
5 // implement it, but do not make any changes to the |
6 // templates below. Also have a look whether the functions |
6 // templates below. Also have a look whether the functions |
7 // at the end are of any help. |
7 // at the end are of any help. |
8 |
8 |
9 |
9 |
|
10 |
10 type Pos = (Int, Int) // a position on a chessboard |
11 type Pos = (Int, Int) // a position on a chessboard |
11 type Path = List[Pos] // a path...a list of positions |
12 type Path = List[Pos] // a path...a list of positions |
12 |
13 |
13 //(1) Complete the function that tests whether the position x |
14 //(1) Complete the function that tests whether the position x |
14 // is inside the board and not yet element in the path. |
15 // is inside the board and not yet element in the path. |
15 |
16 |
16 def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ((!(path.contains(x))) && (x._1 < dim) && (x._2 < dim)) |
17 def is_legal(dim: Int, path: Path, x: Pos) : Boolean = { |
|
18 if ((x._1 < dim && x._2 < dim) && !(path.contains(x))) |
|
19 true |
|
20 else |
|
21 false |
|
22 } |
17 |
23 |
18 |
24 |
19 |
25 |
20 //(2) Complete the function that calculates for a position x |
26 //(2) Complete the function that calculates for a position x |
21 // all legal onward moves that are not already in the path. |
27 // all legal onward moves that are not already in the path. |
22 // The moves should be ordered in a "clockwise" manner. |
28 // The moves should be ordered in a "clockwise" manner. |
|
29 |
23 |
30 |
|
31 def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = { |
|
32 val legalMovesList = List((x._1 + 1, x._2 + 2), (x._1 + 2, x._2 + 1), (x._1 + 2, x._2 - 1), (x._1 + 1, x._2 - 2), (x._1 - 1, x._2 - 2), (x._1 - 2, x._2 - 1), (x._1 - 2, x._2 + 1), (x._1 - 1, x._2 + 2)) |
24 |
33 |
25 def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] ={ |
34 for (i <- legalMovesList |
26 val y = List((x._1 + 1, x._2 + 2), |
35 if (is_legal(dim, path, i))) |
27 (x._1 + 2, x._2 + 1), |
36 yield i |
28 (x._1 + 2, x._2 - 1), |
37 |
29 (x._1 + 1, x._2 - 2), |
|
30 (x._1 - 1, x._2 - 2), |
|
31 (x._1 - 2, x._2 - 1), |
|
32 (x._1 - 2, x._2 + 1), |
|
33 (x._1 - 1, x._2 + 2) |
|
34 ) |
|
35 y.filter(next => is_legal(dim, path, next)) |
|
36 } |
38 } |
|
39 |
37 |
40 |
38 //some test cases |
41 //some test cases |
39 // |
42 // |
40 //assert(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) |
43 //assert(legal_moves(8, Nil, (2,2)) == |
|
44 // List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) |
41 //assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) |
45 //assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) |
42 //assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) |
46 //assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == |
|
47 // List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) |
43 //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) |
48 //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) |
44 |
49 |
45 |
50 |
46 //(3) Complete the two recursive functions below. |
51 //(3) Complete the two recursive functions below. |
47 // They exhaustively search for knight's tours starting from the |
52 // They exhaustively search for knight's tours starting from the |
48 // given path. The first function counts all possible tours, |
53 // given path. The first function counts all possible tours, |
49 // and the second collects all tours in a list of paths. |
54 // and the second collects all tours in a list of paths. |
50 |
55 |
51 def count_tours(dim: Int, path: Path) : Int = { |
56 def count_tours(dim: Int, path: Path) : Int = { |
52 if(path.length == dim*dim) 1 else |
57 if (path.size == (dim ^ 2)){ |
53 (for(i <- legal_moves(dim, path, path.head)) yield |
58 List(path).size |
54 count_tours(dim, i :: path) |
59 } else { |
55 ).sum |
60 val totalTours = legal_moves(dim, path, path.head) |
|
61 totalTours.map(element => count_tours(dim, element :: path)).sum |
|
62 } |
56 } |
63 } |
57 |
64 |
58 def enum_tours(dim: Int, path: Path) : List[Path] ={ |
65 def enum_tours(dim: Int, path: Path) : List[Path] = { |
59 if(path.length == dim*dim) List(path) else |
66 if (path.size == (dim ^ 2)){ |
60 (for(i <- legal_moves(dim, path, path.head)) yield |
67 List(path) |
61 enum_tours(dim, i :: path) |
68 } else { |
62 ).flatten |
69 val totalEnums = legal_moves(dim, path, path.head) |
|
70 totalEnums.map(element => enum_tours(dim, element :: path)).flatten |
|
71 } |
63 } |
72 } |
|
73 |
64 |
74 |
65 //(5) Implement a first-function that finds the first |
75 //(5) Implement a first-function that finds the first |
66 // element, say x, in the list xs where f is not None. |
76 // element, say x, in the list xs where f is not None. |
67 // In that case Return f(x), otherwise None. If possible, |
77 // In that case Return f(x), otherwise None. If possible, |
68 // calculate f(x) only once. |
78 // calculate f(x) only once. |
69 |
79 |
70 def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = { |
80 def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = { |
71 if(xs == Nil) None |
81 if (xs eq Nil) { |
72 else( |
82 None |
73 for(x <- xs) yield{ |
83 } else { |
74 val a = f(x) |
84 if (f(xs.head) != None) { |
75 if(a != None) a |
85 f(xs.head) |
76 else first(xs.drop(1), f) |
86 } else { |
|
87 first(xs.tail, f) |
77 } |
88 } |
78 ).head |
89 } |
|
90 |
79 } |
91 } |
|
92 |
80 |
93 |
81 // test cases |
94 // test cases |
82 //def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None |
95 //def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None |
83 // |
96 // |
84 //first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0))) |
97 //first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0))) |