--- 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