diff -r 438459a8e48b -r 8c868feb917b cws/cw03.tex --- 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