--- 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
--- 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
--- 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.
+
*/
--- /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))
+
+
+//}
+
+
--- /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
+
--- /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
+
+
+//}
--- /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))
+
+//}
--- /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)
--- /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)
--- /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)
--- /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
+
+
--- 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
+