# HG changeset patch # User Christian Urban # Date 1543447607 0 # Node ID 3020f8c76baaafd300df8ba8ac0462c7091656c3 # Parent 44161f2c322627e4949c49d1703fbfcb3d3ceda3 updated diff -r 44161f2c3226 -r 3020f8c76baa templates4/postfix.scala --- a/templates4/postfix.scala Wed Nov 28 17:13:40 2018 +0000 +++ b/templates4/postfix.scala Wed Nov 28 23:26:47 2018 +0000 @@ -3,10 +3,10 @@ // ======================== - +// type of tokens type Toks = List[String] -// the operations in the simple version +// the operations in the basic version of the algorithm val ops = List("+", "-", "*", "/") // the precedences of the operators @@ -21,39 +21,25 @@ // (6) Implement below the shunting yard algorithm. The most // convenient way to this in Scala is to implement a recursive -// function using pattern matching. The function takes some input -// tokens as first argument. The second and third arguments represent -// the stack and the output or the shunting yard algorithm. +// function and to heavily use pattern matching. The function syard +// takes some input tokens as first argument. The second and third +// arguments represent the stack and the output of the shunting yard +// algorithm. // // In the marking, you can assume the function is called only with -// an empty stack and empty output list. You can also assume the -// input are only properly formated (infix) arithmetic expressions -// (for example all parentheses are well-nested, the input only contains +// an empty stack and an empty output list. You can also assume the +// input os only properly formatted (infix) arithmetic expressions +// (all parentheses will be well-nested, the input only contains // operators and numbers). -// You can implement any helper function you need. I found it helpful -// to implement auxiliary functions: - -def is_op(op: String) : Boolean = ops.contains(op) - -def prec(op1: String, op2: String) : Boolean = precs(op1) <= precs(op2) +// You can implement any additional helper function you need. I found +// it helpful to implement two auxiliary functions for the pattern matching: +// +// def is_op(op: String) : Boolean = ... +// def prec(op1: String, op2: String) : Boolean = ... -def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { - case (Nil, _, _) => out.reverse ::: st - case (num::in, st, out) if (num.forall(_.isDigit)) => - syard(in, st, num :: out) - case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => - syard(op1::in, st, op2 :: out) - case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) - case ("("::in, st, out) => syard(in, "("::st, out) - case (")"::in, op2::st, out) => - if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) - case (in, st, out) => { - println(s"in: ${in} st: ${st} out: ${out.reverse}") - Nil - } -} +// def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ... // test cases @@ -71,23 +57,14 @@ // (7) Implement a compute function that evaluates an input list -// in postfix notation. This function takes an input list of tokens -// and a stack as argument. The function should produce the -// result in form of an integer using the stack. You can assume -// this function will be only called with proper postfix expressions. +// in postfix notation. This function takes a list of tokens +// and a stack as argumenta. The function should produce the +// result as an integer using the stack. You can assume +// this function will be only called with proper postfix +// expressions. -def op_comp(s: String, n1: Int, n2: Int) = s match { - case "+" => n2 + n1 - case "-" => n2 - n1 - case "*" => n2 * n1 - case "/" => n2 / n1 -} +// def compute(toks: Toks, st: List[Int] = Nil) : Int = ... -def compute(toks: Toks, st: List[Int] = Nil) : Int = (toks, st) match { - case (Nil, st) => st.head - case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) - case (num::in, st) => compute(in, num.toInt::st) -} // test cases // compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 diff -r 44161f2c3226 -r 3020f8c76baa templates4/postfix2.scala --- a/templates4/postfix2.scala Wed Nov 28 17:13:40 2018 +0000 +++ b/templates4/postfix2.scala Wed Nov 28 23:26:47 2018 +0000 @@ -1,86 +1,65 @@ -// Shunting Yard Algorithm -// Edsger Dijkstra +// Shunting Yard Algorithm +// including Associativity for Operators +// ===================================== - +// type of tokens type Toks = List[String] -def split(s: String) = s.split(" ").toList +// helper function for splitting strings into tokens +def split(s: String) : Toks = s.split(" ").toList + +// left- and right-associativity +abstract class Assoc +case object LA extends Assoc +case object RA extends Assoc -abstract class Assoc -case object RA extends Assoc -case object LA extends Assoc - +// power is right-associative, +// everything else is left-associative def assoc(s: String) : Assoc = s match { case "^" => RA case _ => LA } +// the precedences of the operators val precs = Map("+" -> 1, - "-" -> 1, - "*" -> 2, - "/" -> 2, - "^" -> 4) + "-" -> 1, + "*" -> 2, + "/" -> 2, + "^" -> 4) +// the operations in the basic version of the algorithm val ops = List("+", "-", "*", "/", "^") -def is_op(op: String) : Boolean = ops.contains(op) - -def prec(op1: String, op2: String) : Boolean = assoc(op1) match { - case LA => precs(op1) <= precs(op2) - case RA => precs(op1) < precs(op2) -} +// (8) Implement the extended version of the shunting yard algorithm. +// This version should properly account for the fact that the power +// operation is right-associative. Apart from the extension to include +// the power operation, you can make the same assumptions as in +// basic version. -def syard(toks: Toks, st: Toks = Nil, rout: Toks = Nil) : Toks = (toks, st, rout) match { - case (Nil, _, _) => rout.reverse ::: st - case (num::in, st, rout) if (num.forall(_.isDigit)) => - syard(in, st, num :: rout) - case (op1::in, op2::st, rout) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => - syard(op1::in, st, op2 :: rout) - case (op1::in, st, rout) if (is_op(op1)) => syard(in, op1::st, rout) - case ("("::in, st, rout) => syard(in, "("::st, rout) - case (")"::in, op2::st, rout) => - if (op2 == "(") syard(in, st, rout) else syard(")"::in, st, op2 :: rout) - case (in, st, rout) => { - println(s"in: ${in} st: ${st} rout: ${rout.reverse}") - Nil - } -} +// def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ... + -def op_comp(s: String, n1: Long, n2: Long) = s match { - case "+" => n2 + n1 - case "-" => n2 - n1 - case "*" => n2 * n1 - case "/" => n2 / n1 - case "^" => Math.pow(n2, n1).toLong -} - -def compute(toks: Toks, st: List[Long] = Nil) : Long = (toks, st) match { - case (Nil, st) => st.head - case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) - case (num::in, st) => compute(in, num.toInt::st) -} +// test cases +// syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + +// (9) Implement a compute function that produces a Long(!) for an +// input list of tokens in postfix notation. + +//def compute(toks: Toks, st: List[Long] = Nil) : Long = ... -compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 -compute(syard(split("10 + 12 * 33"))) // 406 -compute(syard(split("( 5 + 7 ) * 2"))) // 24 -compute(syard(split("5 + 7 / 2"))) // 8 -compute(syard(split("5 * 7 / 2"))) // 17 -compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 +// test cases +// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 +// compute(syard(split("10 + 12 * 33"))) // 406 +// compute(syard(split("( 5 + 7 ) * 2"))) // 24 +// compute(syard(split("5 + 7 / 2"))) // 8 +// compute(syard(split("5 * 7 / 2"))) // 17 +// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 +// compute(syard(split("4 ^ 3 ^ 2"))) // 262144 +// compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 +// compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 +// compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 -compute(syard(split("4 ^ 3 ^ 2"))) // 262144 -compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 -compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 - - -syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + -compute(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3"))) - -compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 - - -def pow(n1: Long, n2: Long) = Math.pow(n1, n2).toLong diff -r 44161f2c3226 -r 3020f8c76baa templates4/re.scala --- a/templates4/re.scala Wed Nov 28 17:13:40 2018 +0000 +++ b/templates4/re.scala Wed Nov 28 23:26:47 2018 +0000 @@ -1,7 +1,7 @@ // Part 1 about Regular Expression Matching //========================================== - +// Regular Expressions abstract class Rexp case object ZERO extends Rexp case object ONE extends Rexp @@ -11,7 +11,7 @@ case class STAR(r: Rexp) extends Rexp // star -// some convenience for typing in regular expressions +// some convenience for typing regular expressions import scala.language.implicitConversions import scala.language.reflectiveCalls @@ -102,11 +102,13 @@ size(simp(der('a', der('a', EVIL)))) // => 8 size(simp(der('a', der('a', der('a', EVIL))))) // => 8 -// Java needs around 30 seconds for matching 28 a's with EVIL. +// Python needs around 30 seconds for matching 28 a's with EVIL. +// Java 9 and later increase this to an "astonishing" 40000 a's in +// 30 seconds. // // Lets see how long it really takes to match strings with -// 0.5 Million a's...it should be in the range of some -// seconds. +// 5 Million a's...it should be in the range of a couple +// of seconds. def time_needed[T](i: Int, code: => T) = { val start = System.nanoTime() @@ -119,5 +121,14 @@ println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i)))) } +// another "power" test case +simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE + +// the Iterator produces the rexp +// +// SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE) +// +// where SEQ is nested 50 times. + */ diff -r 44161f2c3226 -r 3020f8c76baa testing3/knight1.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/knight1.scala Wed Nov 28 23:26:47 2018 +0000 @@ -0,0 +1,170 @@ +// Part 1 about finding and counting Knight's tours +//================================================== + +//object CW8a { // for preparing the jar + +type Pos = (Int, Int) // a position on a chessboard +type Path = List[Pos] // a path...a list of positions + + +// for measuring time in the JAR +def time_needed[T](code: => T) : T = { + val start = System.nanoTime() + val result = code + val end = System.nanoTime() + println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") + result +} + +// for printing a board +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") + } + println + } +} + +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)) + + +//} + + diff -r 44161f2c3226 -r 3020f8c76baa testing3/knight1_test.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/knight1_test.sh Wed Nov 28 23:26:47 2018 +0000 @@ -0,0 +1,166 @@ +#!/bin/bash +set -euo pipefail + +out=${1:-output} + +echo -e "" > $out + +echo -e "Below is the feedback for your submission of CW 8, Part 1 and 2." >> $out +echo -e "" >> $out + + +# compilation tests + +function scala_compile { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) +} + +# functional tests + +function scala_assert_slow { + (ulimit -t 120; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + +function scala_assert_thirty { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + +function scala_assert_quick { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + +# purity test + +function scala_vars { + (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null) +} + + +# knights1: purity test + +echo -e "knight1.scala does not contain vars, returns etc?" >> $out + +if (scala_vars knight1.scala) +then + echo -e " --> fail (make triple-sure your program conforms to the required format)" >> $out + tsts0=$(( 0 )) +else + echo -e " --> success" >> $out + tsts0=$(( 0 )) +fi + + +# compilation test + +if [ $tsts0 -eq 0 ] +then + echo -e "knight1.scala runs?" >> $out + + if (scala_compile knight1.scala) + then + echo -e " --> success " >> $out + tsts1=$(( 0 )) + else + echo -e " --> SCALA DID NOT RUN KNIGHT1.SCALA\n" >> $out + tsts1=$(( 1 )) + fi +else + tsts1=$(( 1 )) +fi + +### knight1 test + +if [ $tsts1 -eq 0 ] +then + echo -e "Takes 10 seconds or less to execute: " >> $out + echo -e " is_legal(8, Nil, (3, 4)) == true " >> $out + echo -e " is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false " >> $out + echo -e " is_legal(2, Nil, (0, 0)) == true" >> $out + + if (scala_assert_quick "knight1.scala" "knight_test1.scala") + then + echo -e " --> success" >> $out + else + echo -e " --> \n ONE TEST FAILED\n" >> $out + fi +fi + +### knight2 test + +if [ $tsts1 -eq 0 ] +then + echo -e "Takes 10 seconds or less to execute: " >> $out + echo -e " legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))" >> $out + echo -e " legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))" >> $out + echo -e " legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))" >> $out + echo -e " legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))" >> $out + echo -e " legal_moves(1, Nil, (0,0)) == Nil" >> $out + echo -e " legal_moves(2, Nil, (0,0)) == Nil" >> $out + echo -e " legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))" >> $out + + if (scala_assert_quick "knight1.scala" "knight_test2.scala") + then + echo -e " --> success" >> $out + else + echo -e " --> \n ONE TEST FAILED\n" >> $out + fi +fi + + +### knight3 test + +if [ $tsts1 -eq 0 ] +then + echo -e "Takes 10 seconds or less to execute: " >> $out + echo -e " count_tours from every position on the board" >> $out + echo -e " dim = 1: 1" >> $out + echo -e " 2: 0,0,0,0" >> $out + echo -e " 3: 0,0,0,0,0,0,0,0,0" >> $out + echo -e " 4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" >> $out + #echo -e " 5: 304,0,56,0,304,0,56,0,56,0,56,0,64,0,56,0,56,0,56,0,304,0,56,0,304" >> $out + echo -e " enum_tours(5, List((0,0)) ) == 304 and all correct?" >> $out + echo -e " enum_tours(5, List((0,1)) ) == 0" >> $out + echo -e " enum_tours(5, List((0,2)) ) == 56 and all correct?" >> $out + + if (scala_assert_quick "knight1.scala" "knight_test3.scala") + then + echo -e " --> success" >> $out + else + echo -e " --> \n ONE TEST FAILED\n" >> $out + fi +fi + +### knight4 test + +if [ $tsts1 -eq 0 ] +then + echo -e "Takes 10 seconds or less to execute: " >> $out + echo -e " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " >> $out + echo -e " first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0)))" >> $out + echo -e " first(List((1,0),(2,0),(3,0)), f) == None" >> $out + + if (scala_assert_quick "knight1.scala" "knight_test4.scala") + then + echo -e " --> success" >> $out + else + echo -e " --> \n ONE TEST FAILED\n" >> $out + fi +fi + + +### knight5 test + +if [ $tsts1 -eq 0 ] +then + echo -e "Takes 10 seconds or less to execute: " >> $out + echo -e " is first_tour(6, List((0, 0))) ok? " >> $out + echo -e " is first_tour(4, List((0, 0))) == None " >> $out + + if (scala_assert_quick "knight1.scala" "knight_test5.scala") + then + echo -e " --> success" >> $out + else + echo -e " --> \n ONE TEST FAILED\n" >> $out + fi +fi + diff -r 44161f2c3226 -r 3020f8c76baa testing3/knight2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/knight2.scala Wed Nov 28 23:26:47 2018 +0000 @@ -0,0 +1,89 @@ +// Part 3 about finding a single tour using the Warnsdorf Rule +//============================================================= + +//object CW8b { // for preparing the jar + +type Pos = (Int, Int) +type Path = List[Pos] + + +// for measuring time in the JAR +def time_needed[T](code: => T) : T = { + val start = System.nanoTime() + val result = code + val end = System.nanoTime() + println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") + result +} + + +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((i, j))}%4.0f ") + } + println + } +} + +def add_pair(x: Pos, y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +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) + +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, _)) + +def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = + moves(x).filter(is_legal(dim, path, _)) + +def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = + legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) + +import scala.annotation.tailrec + +@tailrec +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) + } +} + + +def tfirst_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path) + else + first(ordered_moves(dim, path, path.head), (x: Pos) => tfirst_closed_tour_heuristics(dim, x::path)) +} + +def first_closed_tour_heuristics(dim: Int, path: Path) = + time_needed(tfirst_closed_tour_heuristics(dim: Int, path: Path)) + + +// heuristic cannot be used to search for closed tours on 7 x 7 an beyond +//for (dim <- 1 to 6) { +// val t = time_needed(0, first_closed_tour_heuristics(dim, List((dim / 2, dim / 2)))) +// println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) +//} + + +def tfirst_tour_heuristics(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim) Some(path) + else + first(ordered_moves(dim, path, path.head), (x: Pos) => tfirst_tour_heuristics(dim, x::path)) +} + + +def first_tour_heuristics(dim: Int, path: Path) = + time_needed(tfirst_tour_heuristics(dim: Int, path: Path)) + + +// will be called with boards up to 30 x 30 + + +//} diff -r 44161f2c3226 -r 3020f8c76baa testing3/knight3.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/knight3.scala Wed Nov 28 23:26:47 2018 +0000 @@ -0,0 +1,63 @@ +// Part 3 about finding a single tour using the Warnsdorf Rule +//============================================================= + +//object CW8c { // for preparing the jar + +type Pos = (Int, Int) +type Path = List[Pos] + + +// for measuring time in the JAR +def time_needed[T](code: => T) : T = { + val start = System.nanoTime() + val result = code + val end = System.nanoTime() + println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") + result +} + + +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((i, j))}%4.0f ") + } + println + } +} + +def add_pair(x: Pos, y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +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) + +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, _)) + +def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = + moves(x).filter(is_legal(dim, path, _)) + +def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = + legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) + +import scala.annotation.tailrec + +@tailrec +def tour_on_mega_board_aux(dim: Int, paths: List[Path]): Option[Path] = paths match { + case Nil => None + case (path::rest) => + if (path.length == dim * dim) Some(path) + else tour_on_mega_board_aux(dim, ordered_moves(dim, path, path.head).map(_::path) ::: rest) +} + +def ttour_on_mega_board(dim: Int, path: Path): Option[Path] = + tour_on_mega_board_aux(dim, List(path)) + + +def tour_on_mega_board(dim: Int, path: Path) = + time_needed(ttour_on_mega_board(dim: Int, path: Path)) + +//} diff -r 44161f2c3226 -r 3020f8c76baa testing3/knight_test3.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/knight_test3.scala Wed Nov 28 23:26:47 2018 +0000 @@ -0,0 +1,47 @@ + + +//type Pos = (Int, Int) // a position on a chessboard +//type Path = List[Pos] // a path...a list of positions + +def count_all_tours_urban(dim: Int) = { + for (i <- (0 until dim).toList; + j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) +} + +def add_pair_urban(x: Pos)(y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean = + 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) + +def moves_urban(x: Pos): List[Pos] = + List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), + (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x)) + +def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] = + moves_urban(x).filter(is_legal_urban(dim, path)) + +def correct_urban(dim: Int)(p: Path): Boolean = p match { + case Nil => true + case x::Nil => true + case x::y::p => if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false +} + + +assert(count_all_tours_urban(1) == List(1)) +assert(count_all_tours_urban(2) == List(0, 0, 0, 0)) +assert(count_all_tours_urban(3) == List(0, 0, 0, 0, 0, 0, 0, 0, 0)) +assert(count_all_tours_urban(4) == List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)) +//assert(count_all_tours_urban(5) == List(304, 0, 56, 0, 304, 0, 56, 0, 56, 0, 56, 0, 64, 0, 56, 0, 56, 0, 56, 0, 304, 0, 56, 0, 304)) + +val ts00_urban = enum_tours(5, List((0, 0))) +assert(ts00_urban.map(correct_urban(5)).forall(_ == true) == true) +assert(ts00_urban.length == 304) + +val ts01_urban = enum_tours(5, List((0, 1))) +assert(ts01_urban.map(correct_urban(5)).forall(_ == true) == true) +assert(ts01_urban.length == 0) + +val ts02_urban = enum_tours(5, List((0, 2))) +assert(ts02_urban.map(correct_urban(5)).forall(_ == true) == true) +assert(ts02_urban.length == 56) diff -r 44161f2c3226 -r 3020f8c76baa testing3/knight_test4.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/knight_test4.scala Wed Nov 28 23:26:47 2018 +0000 @@ -0,0 +1,5 @@ + +val f_urban = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None + +assert(first(List((1,0),(2,0),(3,0),(4,0)), f_urban) == Some(List((4,0)))) +assert(first(List((1,0),(2,0),(3,0)), f_urban) == None) diff -r 44161f2c3226 -r 3020f8c76baa testing3/knight_test5.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/knight_test5.scala Wed Nov 28 23:26:47 2018 +0000 @@ -0,0 +1,30 @@ + +//type Pos = (Int, Int) // a position on a chessboard +//type Path = List[Pos] // a path...a list of positions + +def add_pair_urban(x: Pos)(y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean = + 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) + +def moves_urban(x: Pos): List[Pos] = + List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), + (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x)) + +def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] = + moves_urban(x).filter(is_legal_urban(dim, path)) + +def correct_urban(dim: Int)(p: Path): Boolean = p match { + case Nil => true + case x::Nil => true + case x::y::p => + if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false +} + + +val ts1_urban = first_tour(6, List((0, 0))).get +assert(correct_urban(6)(ts1_urban) == true) + +val ts2_urban = first_tour(4, List((0, 0))) +assert(ts2_urban == None) diff -r 44161f2c3226 -r 3020f8c76baa testing3/mark --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/mark Wed Nov 28 23:26:47 2018 +0000 @@ -0,0 +1,18 @@ +#!/bin/bash +###set -e + +trap "exit" INT + +DIR="$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd )" + +cp $DIR/* . + +./knight1_test.sh output1 +#./knight2_test.sh output2 + +echo "Here is an automated test report for your work so far on assignment 8. Please note that this is not the mark for your work; it is provided only in the hope that it is useful in developing your solution. Passing these tests does not guarantee your code is free from bugs: after the deadline, your code will be marked against a different, more thorough set of test cases.\n\n" > $1 + + +cat output1 >> $1 + + diff -r 44161f2c3226 -r 3020f8c76baa testing4/mark --- a/testing4/mark Wed Nov 28 17:13:40 2018 +0000 +++ b/testing4/mark Wed Nov 28 23:26:47 2018 +0000 @@ -3,6 +3,15 @@ trap "exit" INT +DIR="$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd )" + +cp $DIR/* . + ./re_test.sh output1 -./bf_test.sh output2 +#./bf_test.sh output2 + +echo -e "Here is an automated test report for your work so far on assignment 9. Please note that this is not the mark for your work; it is provided only in the hope that it is useful in developing your solution. Passing these tests does not guarantee your code is free from bugs: after the deadline, your code will be marked against a different, more thorough set of test cases.\n\n" > $1 + +cat output1 >> $1 +