pep-material: comparison cws/cw03.tex

equal deleted inserted replaced

-:4bda49ec24da
+:f968188d4a9b
 \documentclass{article}
 \usepackage{chessboard}
 \usepackage[LSBC4,T1]{fontenc}
 \let\clipbox\relax
 \usepackage{../style}
+\usepackage{../langs}
 \usepackage{disclaimer}
 \begin{document}
 \setchessboard{smallboard,
 hlabelformat=\arabic{ranklabel},
 vlabelformat=\arabic{filelabel}}
 \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
 second, more advanced part, is due on 20 December at 11pm. You are
 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}.
 \DISCLAIMER{}
 If you cannot remember how a knight moves in chess, or never played
 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,
 shortenend=0.5ex,
 markstyle=cross,
 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]}
-\noindent
+\subsection*{Reference Implementation}
-\textbf{Hints:} useful list functions: \texttt{.contains(..)} checks
+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}).
+sure the list is not \texttt{Nil}); a useful option function:
+\texttt{.isDefined} returns true, if an option is \texttt{Some(..)};
-\noindent
+anonymous functions can be constructed using \texttt{(x:Int) => ...},
-\textbf{Hints:} a useful list function: \texttt{.sortBy} sorts a list
+this functions 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}.
-\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
 take the dimension of the board as an argument.  The fun with this
 problem is that even for small chessboard dimensions it has already an
 with exhaustively exploring the complete search space for small
 chessboards.\medskip
 \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
+board dimension is an integer.
-$40 \times 40$).  A \emph{position} (or field) on the chessboard is
+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
 example the path for the $5\times 5$ chessboard above is represented
 by
 there are 304 of tours. If you try out every field of a $5 \times
 5$-board as a starting field and add up all tours, you obtain
 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
 positions and a function $f$ as arguments; $f$ is the name we give to
 this argument). The function $f$ takes a position as argument and
 \noindent That is, we want to find the first position where the
 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
 possible! Do not calculate $f(x)$ for all elements and then see which
 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]
 \end{itemize}
 \noindent
 \textbf{Testing:} The \texttt{first\_tour} function will be called with board
 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
 boards takes too much time. There is a heuristic, called \emph{Warnsdorf's
 Rule} that can speed up finding a tour. This heuristic states that a
 \noindent
 Whenever there are ties, the corresponding onward moves can be in any
 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
 onward moves like in (2) but orders them according to the
 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}
+\item[(7)] Implement a \texttt{first\_closed\_tour\_heuristic}
-function that searches for a
+function that searches for a single
-\textbf{closed} tour on a $6\times 6$ board. It should use the
+\textbf{closed} tour on a $6\times 6$ board. It should try out
-\texttt{first}-function from (4) and tries out onward moves according to
+onward moves according to
-the \texttt{ordered\_moves} function from (3a). It is more likely to find
+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
+$30\times 30$.  It is the same function as in (7) but searches for
-tours (not just closed tours). You have to be careful to write a
+tours (not just closed tours). It might be called with any field on the
-tail-recursive function of the \texttt{first\_tour\_heuristic} function
+board as start.\\
-otherwise you will get problems with stack-overflows.\\
+%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

changeset 213	f968188d4a9b
parent 212	4bda49ec24da
child 216	8c868feb917b