
diff -r 4bda49ec24da -r f968188d4a9b cws/cw03.tex
--- a/cws/cw03.tex	Tue Nov 20 14:31:14 2018 +0000
+++ b/cws/cw03.tex	Thu Nov 22 17:19:23 2018 +0000
@@ -3,6 +3,7 @@
 \usepackage[LSBC4,T1]{fontenc}
 \let\clipbox\relax
 \usepackage{../style}
+\usepackage{../langs}
 \usepackage{disclaimer}
 
 \begin{document}
@@ -16,7 +17,7 @@
 
 \mbox{}\\[-18mm]\mbox{}
 
-\section*{Coursework 7 (Scala)}
+\section*{Coursework 8 (Scala)}
 
 This coursework is worth 10\%. It is about searching and
 backtracking. The first part is due on 29 November at 11pm; the
@@ -24,11 +25,11 @@
 asked to implement Scala programs that solve various versions of the
 \textit{Knight's Tour Problem} on a chessboard. Note the second, more
 advanced, part might include material you have not yet seen in the
-first two lectures. \bigskip
+first three lectures. \bigskip
 
 \IMPORTANT{}
 Also note that the running time of each part will be restricted to a
-maximum of 360 seconds on my laptop: If you calculate a result once,
+maximum of 30 seconds on my laptop: If you calculate a result once,
 try to avoid to calculate the result again. Feel free to copy any code
 you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and
 \texttt{knight3.scala}.
@@ -138,8 +139,7 @@
 chess, below are all potential moves indicated for two knights, one on
 field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):
 
-
-\chessboard[maxfield=g7,
+{\chessboard[maxfield=g7,
             color=blue!50,
             linewidth=0.2em,
             shortenstart=0.5ex,
@@ -148,24 +148,61 @@
             markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
             color=red!50,
             markfields={f5, e6},
-            setpieces={Ng7, Nb2}]
+            setpieces={Ng7, Nb2},
+            boardfontsize=12pt,labelfontsize=9pt]}
+
+\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
+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. 
+
+\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
+
+scala> CW8a.print_board(8, CW8a.first_tour(8, List((0, 0))).get)
+Time needed: 15.411 secs.
+
+ 51  46  55  44  53   4  21  12 
+ 56  43  52   3  22  13  24   5 
+ 47  50  45  54  25  20  11  14 
+ 42  57   2  49  40  23   6  19 
+ 35  48  41  26  61  10  15  28 
+ 58   1  36  39  32  27  18   7 
+ 37  34  31  60   9  62  29  16 
+  0  59  38  33  30  17   8  63 
+\end{lstlisting}%$
+
+
+\subsection*{Hints}
+
+\noindent
+\textbf{Part 1} useful list functions: \texttt{.contains(..)} checks
+whether an element is in a list, \texttt{.flatten} turns a list of
+lists into just a list, \texttt{\_::\_} puts an element on the head of
+the list, \texttt{.head} gives you the first element of a list (make
+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
 
 
 \noindent
-\textbf{Hints:} useful list functions: \texttt{.contains(..)} checks
-whether an element is in a list, \texttt{.flatten} turns a list of
-lists into just a list, \texttt{\_::\_} puts an element on the head of
-the list, \texttt{.head} gives you the first element of a list (make
-sure the list is not \texttt{Nil}).
-
-\noindent
-\textbf{Hints:} a useful list function: \texttt{.sortBy} sorts a list
+\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}.
 
-            
-\subsection*{Part 1 (7 Marks)}
+
+
+
+\subsection*{Part 1 (6 Marks)}
 
 You are asked to implement the knight's tour problem such that the
 dimension of the board can be changed.  Therefore most functions will
@@ -178,8 +215,8 @@
 
 \noindent
 Let us first fix the basic datastructures for the implementation.  The
-board dimension is an integer (we will never go beyond board sizes of
-$40 \times 40$).  A \emph{position} (or field) on the chessboard is
+board dimension is an integer.
+A \emph{position} (or field) on the chessboard is
 a pair of integers, like $(0, 0)$. A \emph{path} is a list of
 positions. The first (or 0th move) in a path is the last element in
 this list; and the last move in the path is the first element. For
@@ -244,11 +281,11 @@
 1728. A $6\times 6$ board is already too large to be searched
 exhaustively.\footnote{For your interest, the number of tours on
   $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,
-  19591828170979904, respectively.}\bigskip
+  19591828170979904, respectively.}\smallskip
 
 
 
-\subsubsection*{Tasks (file knight2.scala)}
+\subsubsection*{Tasks (cont.)}
 
 \begin{itemize}
 \item[(4)] Implement a \texttt{first}-function. This function takes a list of
@@ -271,7 +308,9 @@
   result of $f$ is not \texttt{None}, if there is one. Note that
   `inside' \texttt{first}, you do not (need to) know anything about
   the argument $f$ except its type, namely \texttt{Pos =>
-    Option[Path]}. There is one additional point however you should
+    Option[Path]}. If you want to find out what the result of $f$ is
+  on a particular argument, say $x$, you can just write $f(x)$. 
+  There is one additional point however you should
   take into account when implementing \texttt{first}: you will need to
   calculate what the result of $f(x)$ is; your code should do this
   only \textbf{once} and for as \textbf{few} elements in the list as
@@ -279,7 +318,7 @@
   is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]
   
 \item[(5)] Implement a \texttt{first\_tour} function that uses the
-  \texttt{first}-function from (2a), and searches recursively for a tour.
+  \texttt{first}-function from (4), and searches recursively for single tour.
   As there might not be such a tour at all, the \texttt{first\_tour} function
   needs to return a value of type
   \texttt{Option[Path]}.\\\mbox{}\hfill[1 Mark]
@@ -290,16 +329,10 @@
 sizes of up to $8 \times 8$.
 \bigskip
 
-\noindent
-\textbf{Hints:} a useful list function: \texttt{.filter(..)} filters a
-list according to a boolean function; 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.
 
 
 %%\newpage
-\subsection*{Part 2 (3 Marks)}
+\subsection*{Advanced Part 2 (4 Marks)}
 
 As you should have seen in Part 1, a naive search for tours beyond
 $8 \times 8$ boards and also searching for closed tours even on small
@@ -333,7 +366,7 @@
 order.  When calculating the number of onward moves for each field, we
 do not count moves that revisit any field already visited.
 
-\subsubsection*{Tasks (file knight3.scala)}
+\subsubsection*{Tasks (file knight2.scala)}
 
 \begin{itemize}
 \item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of
@@ -341,20 +374,48 @@
   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]
   
-\item[(7)] Implement a \texttt{first\_closed-tour\_heuristic}
-  function that searches for a
-  \textbf{closed} tour on a $6\times 6$ board. It should use the
-  \texttt{first}-function from (4) and tries out onward moves according to
-  the \texttt{ordered\_moves} function from (3a). It is more likely to find
+\item[(7)] Implement a \texttt{first\_closed\_tour\_heuristic}
+  function that searches for a single
+  \textbf{closed} tour on a $6\times 6$ board. It should try out
+  onward moves according to
+  the \texttt{ordered\_moves} function from (6). It is more likely to find
   a solution when started in the middle of the board (that is
   position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]
 
 \item[(8)] Implement a \texttt{first\_tour\_heuristic} function
   for boards up to
-  $40\times 40$.  It is the same function as in (7) but searches for
-  tours (not just closed tours). 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.\\
+  $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.\\
+  %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.\\
+  \mbox{}\hfill[1 Mark]
+\end{itemize}    
+
+\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
+  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
+  implementation performs by running \texttt{knight3.jar} on your
+  computer. For example:
+  
+  \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+$ scala -cp knight3.jar
+  
+scala> CW8c.tour_on_mega_board(70, List((0, 0)))
+Time needed: 9.484 secs.
+...<<long_list>>...
+\end{lstlisting}%$
+
   \mbox{}\hfill[1 Mark]
 \end{itemize}  
 \bigskip




