Binary file cws/cw03.pdf has changed

--- a/cws/cw03.tex	Thu Nov 22 17:35:30 2018 +0000
+++ b/cws/cw03.tex	Thu Nov 22 23:00:57 2018 +0000
@@ -153,15 +153,17 @@
 
 \subsection*{Reference Implementation}
 
-The Scala assignment comes with reference implementations in form of
-a \texttt{jar}-files. This allows you to run any test cases on your own
+This Scala assignment comes with three reference implementations in form of
+\texttt{jar}-files. This allows you to run any test cases on your own
 computer. For example you can call Scala on the command line with the
 option \texttt{-cp knight1.jar} and then query any function from the
-template file. 
+\texttt{knight1.scala} template file. As usual you have to
+prefix the calls with \texttt{CW8a}, \texttt{CW8b} and \texttt{CW8c}.
+Since some of the calls are time sensitive, I included some timing
+information. For example
 
 \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
 $ scala -cp knight1.jar
-  
 scala> CW8a.enum_tours(5, List((0, 0))).length
 Time needed: 1.722 secs.
 res0: Int = 304
@@ -190,14 +192,14 @@
 sure the list is not \texttt{Nil}); a useful option function:
 \texttt{.isDefined} returns true, if an option is \texttt{Some(..)};
 anonymous functions can be constructed using \texttt{(x:Int) => ...},
-this functions takes an \texttt{Int} as an argument.\medskip
+this function takes an \texttt{Int} as an argument.\medskip
 
 
 \noindent
 \textbf{Part 2} a useful list function: \texttt{.sortBy} sorts a list
 according to a component given by the function; a function can be
-tested to be tail recursive by annotation \texttt{@tailrec}, which is
-made available by importing \texttt{scala.annotation.tailrec}.
+tested to be tail-recursive by annotation \texttt{@tailrec}, which is
+made available by importing \texttt{scala.annotation.tailrec}.\medskip
 
 
 
@@ -270,7 +272,11 @@
   arguments. They exhaustively search for tours starting
   from the given path. The first function counts all possible 
   tours (there can be none for certain board sizes) and the second
-  collects all tours in a list of paths.\hfill[2 Marks]
+  collects all tours in a list of paths. These functions will be
+  called with a path containing a single position---the starting field.
+  They are expected to extend this path so as to find all tours starting
+  from the given position.\\
+  \mbox{}\hfill[2 Marks]
 \end{itemize}
 
 \noindent \textbf{Test data:} For the marking, the functions in (3)
@@ -370,7 +376,7 @@
 
 \begin{itemize}
 \item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of
-  onward moves like in (2) but orders them according to the
+  onward moves like in (2) but orders them according to 
   Warnsdorf’s Rule. That means moves with the fewest legal onward moves
   should come first (in order to be tried out first). \hfill[1 Mark]
   
@@ -386,7 +392,7 @@
   for boards up to
   $30\times 30$.  It is the same function as in (7) but searches for
   tours (not just closed tours). It might be called with any field on the
-  board as start.\\
+  board as starting field.\\
   %You have to be careful to write a
   %tail-recursive function of the \texttt{first\_tour\_heuristic} function
   %otherwise you will get problems with stack-overflows.\\
@@ -396,17 +402,19 @@
 \subsubsection*{Task (file knight3.scala)}
 \begin{itemize}
 \item[(9)] Implement a function \texttt{tour\_on\_mega\_board} which is
-  the same function as (7), \textbf{but} can deal with boards up to
-  $70\times 70$ \textbf{within 30 seconds}. This will be tested
+  the same function as in (8), \textbf{but} should be able to
+  deal with boards up to
+  $70\times 70$ \textbf{within 30 seconds} (on my laptop). This will be tested
   by starting from field $(0, 0)$. You have to be careful to
   write a tail-recursive function otherwise you will get problems
   with stack-overflows. Please observe the requirements about
   the submissions: no tricks involving \textbf{.par}.\medskip
 
-  The timelimit of 30 secs is with respect to the laptop on which the
-  marking will happen. You can estimate how well your
+  The timelimit of 30 seconds is with respect to the laptop on which the
+  marking will happen. You can roughly estimate how well your
   implementation performs by running \texttt{knight3.jar} on your
-  computer. For example:
+  computer. For example the reference implementation shows
+  on my laptop:
   
   \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
 $ scala -cp knight3.jar

--- a/testing3-bak/knight3.scala	Thu Nov 22 17:35:30 2018 +0000
+++ b/testing3-bak/knight3.scala	Thu Nov 22 23:00:57 2018 +0000
@@ -1,96 +1,63 @@
 // Part 3 about finding a single tour using the Warnsdorf Rule
 //=============================================================
 
-object CW7c {
+//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))}%3.0f ")
+      print(f"${path.reverse.indexOf((i, j))}%4.0f ")
     }
     println
   } 
 }
 
-def add_pair(x: Pos)(y: Pos): Pos = 
+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 = 
+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))
+       (-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))
-
+  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 {
+def tour_on_mega_board_aux(dim: Int, paths: List[Path]): Option[Path] = paths match {
   case Nil => None
-  case x::xs => {
-    val result = f(x)
-    if (result.isDefined) result else first(xs, f)
-  }
+  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 first_closed_tour_heuristic(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) => first_closed_tour_heuristic(dim, x::path))
-}
-
-/*
-for (dim <- 1 to 6) {
-  val t = first_closed_tour_heuristic(dim, List((dim / 2, dim / 2)))
-  println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}*/
+def ttour_on_mega_board(dim: Int, path: Path): Option[Path] =
+  tour_on_mega_board_aux(dim, List(path))
 
 
-def first_tour_heuristic(dim: Int, path: Path): Option[Path] = {
-
-  @tailrec
-  def aux(dim: Int, path: Path, moves: List[Pos]): Option[Path] =  
-  if (path.length == dim * dim) Some(path)
-  else
-    moves match {
-      case Nil => None
-      case x::xs => {
-        val r = first_tour_heuristic(dim, x::path)
-        if (r.isDefined) r else aux(dim, path, xs)
-    }
-  }    
- 
-  aux(dim, path, ordered_moves(dim, path, path.head)) 
-}
+def tour_on_mega_board(dim: Int, path: Path) =
+  time_needed(ttour_on_mega_board(dim: Int, path: Path))
 
-/*
-def first_tour_heuristic(dim: Int, path: Path): Option[Path] = {
-  if (path.length == dim * dim) Some(path)
-  else
-    first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristic(dim, x::path))
-}
-*/
-
-/*
-for (dim <- 1 to 50) {
-  val t = first_tour_heuristic(dim, List((dim / 2, dim / 2)))
-  println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-*/
-
-}
-
-
-//CW7c.first_tour_heuristic(50, List((0,0))).get
+//}

--- a/testing3/knight1_test.scala	Thu Nov 22 17:35:30 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,5 +0,0 @@
-
-assert(CW7a.is_legal(8, Nil)(3, 4) == true)
-assert(CW7a.is_legal(8, List((4, 1), (1, 0)))(4, 1) == false)
-assert(CW7a.is_legal(2, Nil)(0, 0) == true)
-

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3/knight_test1.scala	Thu Nov 22 23:00:57 2018 +0000
@@ -0,0 +1,5 @@
+
+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)
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3/knight_test2.scala	Thu Nov 22 23:00:57 2018 +0000
@@ -0,0 +1,11 @@
+
+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)))
+