diff -r d061f3a94fa7 -r ec9cbf969edf testing3/knight1.scala --- a/testing3/knight1.scala Thu Nov 29 17:15:11 2018 +0000 +++ b/testing3/knight1.scala Fri Nov 30 03:44:27 2018 +0000 @@ -7,39 +7,44 @@ // at the end are of any help. + type Pos = (Int, Int) // a position on a chessboard type Path = List[Pos] // a path...a list of positions //(1) Complete the function that tests whether the position x // is inside the board and not yet element in the path. -def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ((!(path.contains(x))) && (x._1 < dim) && (x._2 < dim)) +def is_legal(dim: Int, path: Path, x: Pos) : Boolean = { + if ((x._1 < dim && x._2 < dim) && !(path.contains(x))) + true + else + false +} //(2) Complete the function that calculates for a position x // all legal onward moves that are not already in the path. // The moves should be ordered in a "clockwise" manner. + +def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = { + 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)) -def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] ={ - val y = 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) - ) - y.filter(next => is_legal(dim, path, next)) + for (i <- legalMovesList + if (is_legal(dim, path, i))) + yield i + } + //some test cases // -//assert(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, Nil, (2,2)) == +// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) //assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) -//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == +// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) @@ -49,35 +54,43 @@ // and the second collects all tours in a list of paths. def count_tours(dim: Int, path: Path) : Int = { - if(path.length == dim*dim) 1 else - (for(i <- legal_moves(dim, path, path.head)) yield - count_tours(dim, i :: path) - ).sum + if (path.size == (dim ^ 2)){ + List(path).size + } else { + val totalTours = legal_moves(dim, path, path.head) + totalTours.map(element => count_tours(dim, element :: path)).sum + } } -def enum_tours(dim: Int, path: Path) : List[Path] ={ - if(path.length == dim*dim) List(path) else - (for(i <- legal_moves(dim, path, path.head)) yield - enum_tours(dim, i :: path) - ).flatten +def enum_tours(dim: Int, path: Path) : List[Path] = { + if (path.size == (dim ^ 2)){ + List(path) + } else { + val totalEnums = legal_moves(dim, path, path.head) + totalEnums.map(element => enum_tours(dim, element :: path)).flatten + } } + //(5) Implement a first-function that finds the first // element, say x, in the list xs where f is not None. // In that case Return f(x), otherwise None. If possible, // calculate f(x) only once. def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = { - if(xs == Nil) None - else( - for(x <- xs) yield{ - val a = f(x) - if(a != None) a - else first(xs.drop(1), f) + if (xs eq Nil) { + None + } else { + if (f(xs.head) != None) { + f(xs.head) + } else { + first(xs.tail, f) } - ).head + } + } + // test cases //def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None // @@ -92,10 +105,13 @@ // knight tour on a dim * dim-board. -// def first_tour(dim: Int, path: Path) : Option[Path] = { -// first(legal_moves(dim, path, path.head), (x : Pos => )) -// } +//def first_tour(dim: Int, path: Path) : Option[Path] = ... + + + + + /* Helper functions