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. +...<>... +\end{lstlisting}%$ + \mbox{}\hfill[1 Mark] \end{itemize} \bigskip