diff -r ca9c1cf929fa -r e5453add7df6 testing3/knight1.scala --- a/testing3/knight1.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/testing3/knight1.scala Tue Dec 03 01:22:16 2019 +0000 @@ -1,13 +1,119 @@ -// Preliminary Part 1 finding and counting Knight's tours -//======================================================== +// Preliminary Part about finding Knight's tours +//=============================================== + + +object CW8a { -object CW8a { +// If you need any auxiliary function, feel free to +// implement it, but do not make any changes to the +// templates below. Also have a look whether the functions +// 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. -// for measuring time in the JAR +def is_legal(dim: Int, path: Path, x: Pos) : Boolean = { + if ((!(path.contains(x))) && (x._1 >= 0) && (x._2 >= 0) && (x._1 < dim) && (x._2 < dim)) + 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] = {//List[Pos] + val changes = List((1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)) + val returnList = (for ((y,z) <- changes) yield( + //println(y,z)-2,-1 + if ((is_legal(dim,path,((x._1 + y) , (x._2 + z)))) == true) + Some(x._1 + y , x._2 + z) + else + None + )) + returnList.flatten +} + + +//some testcases +// +//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((6,6)), (7,7)) == List((6,5), (5,6))) + + +//(3) Complete the two recursive functions below. +// They exhaustively search for knight's tours starting from the +// given path. The first function counts all possible tours, +// and the second collects all tours in a list of paths. + +def count_tours(dim: Int, path: Path) : Int = (dim,path) match {//Int + case (_, Nil) => 0 + case (0, path) => 0 + case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) + if(path.size < dim*dim) + 0 + else + 1 + else (for (j <- legal_moves(dim,path, path.head)) yield count_tours(dim,j::path)).sum + } +} + +def enum_tours(dim: Int, path: Path) : List[Path] = (dim,path) match { + case (_, Nil) => Nil + case (0, path) => Nil + case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) + if(path.size < dim*dim) + Nil + else + List(path) + else (for (j <- legal_moves(dim,path, path.head)) yield enum_tours(dim,j::path)).flatten + } + +} + + +//(4) 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] = ... + + +// testcases +// +//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None +// +//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0))) +//first(List((1, 0),(2, 0),(3, 0)), foo) // None + + +//(5) Implement a function that uses the first-function from (5) for +// trying out onward moves, and searches recursively for a +// knight tour on a dim * dim-board. + + +//def first_tour(dim: Int, path: Path) : Option[Path] = ... + + + + + + +/* Helper functions + + +// for measuring time def time_needed[T](code: => T) : T = { val start = System.nanoTime() val result = code @@ -16,6 +122,14 @@ result } +// can be called for example with +// time_needed(count_tours(dim, List((0, 0)))) +// in order to print out the time that is needed for +// running count_tours + + + + // for printing a board def print_board(dim: Int, path: Path): Unit = { println @@ -27,144 +141,7 @@ } } -def is_legal(dim: Int, path: Path, x: Pos): Boolean = - 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) -// testcases -//assert(is_legal(8, Nil, (3, 4)) == true) -//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false) -//assert(is_legal(2, Nil, (0, 0)) == true) - - -def add_pair(x: Pos, y: Pos): Pos = - (x._1 + y._1, x._2 + y._2) - -def moves(x: Pos): List[Pos] = - List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), - (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _)) - -// 1 mark - -def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = - moves(x).filter(is_legal(dim, path, _)) - -// testcases -//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((6,6)), (7,7)) == List((6,5), (5,6))) -//assert(legal_moves(1, Nil, (0,0)) == List()) -//assert(legal_moves(2, Nil, (0,0)) == List()) -//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))) - -// 2 marks - -def tcount_tours(dim: Int, path: Path): Int = { - if (path.length == dim * dim) 1 - else - (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum -} - -def count_tours(dim: Int, path: Path) = - time_needed(tcount_tours(dim: Int, path: Path)) - - -def tenum_tours(dim: Int, path: Path): List[Path] = { - if (path.length == dim * dim) List(path) - else - (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten -} - -def enum_tours(dim: Int, path: Path) = - time_needed(tenum_tours(dim: Int, path: Path)) - -// test cases - -/* -def count_all_tours(dim: Int) = { - for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) -} - -def enum_all_tours(dim: Int): List[Path] = { - (for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten -} - - -println("Number of tours starting from (0, 0)") - -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0))))) -} - -println("Number of tours starting from all fields") - -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim))) -} - -for (dim <- 1 to 5) { - val ts = enum_tours(dim, List((0, 0))) - println(s"${dim} x ${dim} ") - if (ts != Nil) { - print_board(dim, ts.head) - println(ts.head) - } -} */ -// 1 mark - -def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { - case Nil => None - case x::xs => { - val result = f(x) - if (result.isDefined) result else first(xs, f) - } } - -// test cases -//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None -// -//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) -//first(List((1, 0),(2, 0),(3, 0)), foo) - - -// 1 mark - -def tfirst_tour(dim: Int, path: Path): Option[Path] = { - if (path.length == dim * dim) Some(path) - else - first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path)) -} - -def first_tour(dim: Int, path: Path) = - time_needed(tfirst_tour(dim: Int, path: Path)) - - -/* -for (dim <- 1 to 8) { - val t = first_tour(dim, List((0, 0))) - println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) -} -*/ - -// 15 secs for 8 x 8 -//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get) - -// no result for 4 x 4 -//val ts2 = time_needed(0, first_tour(4, List((0, 0)))) - -// 0.3 secs for 6 x 6 -//val ts3 = time_needed(0, first_tour(6, List((0, 0)))) - -// 15 secs for 8 x 8 -//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get)) - - -} - -