diff -r ea39bbc8d98d -r 9755af1d74df cws/main_cw04.tex --- a/cws/main_cw04.tex Fri Nov 05 16:47:55 2021 +0000 +++ b/cws/main_cw04.tex Fri Nov 05 17:20:01 2021 +0000 @@ -19,7 +19,7 @@ \mbox{}\\[-18mm]\mbox{} -\section*{Preliminary and Main Part 4 (Scala, 4 + 6 Marks)} +\section*{Main Part 4 (Scala, 9 Marks)} \mbox{}\hfill\textit{``The problem with object-oriented languages is they’ve got all this implicit,}\\ \mbox{}\hfill\textit{environment that they carry around with them. You wanted a banana but}\\ @@ -29,11 +29,14 @@ \noindent This part is about searching and backtracking. You are asked to implement Scala programs that solve various versions of the -\textit{Knight's Tour Problem} on a chessboard. The preliminary part (4\%) is -due on \sout{\cwNINE{}} \textcolor{red}{16 December} at 5pm; the core part (6\%) is due on \cwNINEa{} at 5pm. -Any 1\% you achieve in the preliminary part counts as your ``weekly engagement''. +\textit{Knight's Tour Problem} on a chessboard. +% The preliminary part (4\%) is due on \sout{\cwNINE{}} +% \textcolor{red}{16 December} at 5pm; the core part (6\%) +% is due on \cwNINEa{} at 5pm. Any 1\% you achieve in the +% preliminary part counts as your ``weekly engagement''. \bigskip -%Note the core, more advanced, part might include material you have not + +% Note the core, more advanced, part might include material you have not %yet seen in the first three lectures. \bigskip \IMPORTANTNONE{} @@ -164,9 +167,9 @@ \subsection*{Reference Implementation} -\mbox{}\alert{}\textcolor{red}{You need to download \texttt{knight1.jar} from KEATS. The one -supplied with github does not contain the correct code. See Scala coursework -section on KEATS.}\medskip +%\mbox{}\alert{}\textcolor{red}{You need to download \texttt{knight1.jar} from K%EATS. The one +%supplied with github does not contain the correct code. See Scala coursework +%section on KEATS.}\medskip \noindent This Scala part comes with three reference implementations in form of @@ -174,17 +177,17 @@ 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 \texttt{knight1.scala} template file. As usual you have to -prefix the calls with \texttt{CW9a}, \texttt{CW9b} and \texttt{CW9c}. +prefix the calls with \texttt{M4a}, \texttt{M4b} and \texttt{M4c}. 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> CW9a.enum_tours(5, List((0, 0))).length +scala> M4a.enum_tours(5, List((0, 0))).length Time needed: 1.722 secs. res0: Int = 304 -scala> CW9a.print_board(8, CW9a.first_tour(8, List((0, 0))).get) +scala> M4a.print_board(8, M4a.first_tour(8, List((0, 0))).get) Time needed: 15.411 secs. 51 46 55 44 53 4 21 12 @@ -201,18 +204,15 @@ \subsection*{Hints} \noindent -\textbf{Preliminary Part} useful list functions: \texttt{.contains(..)} checks +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 function takes an \texttt{Int} as an argument.\medskip - - -\noindent -\textbf{Main Part} a useful list function: \texttt{.sortBy} sorts a list +this function takes an \texttt{Int} as an argument; +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}.\medskip @@ -220,7 +220,7 @@ -\subsection*{Preliminary Part (4 Marks)} +\subsection*{Tasks} You are asked to implement the knight's tour problem such that the dimension of the board can be changed. Therefore most functions will @@ -254,7 +254,7 @@ knight moves (see above for the rules). -\subsubsection*{Tasks (file knight1.scala)} +\subsubsection*{Task 1 (file knight1.scala)} @@ -294,9 +294,9 @@ 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] + \mbox{}\hfill[1 Mark] \end{itemize} - + \noindent \textbf{Test data:} For the marking, the functions in (3) will be called with board sizes up to $5 \times 5$. If you search for tours on a $5 \times 5$ board starting only from field $(0, 0)$, @@ -307,18 +307,6 @@ $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320, 19591828170979904, respectively.}\smallskip - -\subsection*{Core Part (6 Marks)} - - -\subsubsection*{Tasks (file knight1.scala cont.)} - -\mbox{}\alert{}\textcolor{red}{You need to copy your \texttt{knight1.scala} - from the preliminary part to the main part and then solve Tasks 4 and 5 - inside the copied file. Do not forget to ``git add'' the file for - pushing the results to the directory \texttt{main4}.}\medskip - - \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 @@ -353,7 +341,7 @@ \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] + \texttt{Option[Path]}.\\\mbox{}\hfill[1 Mark] \end{itemize} \noindent @@ -362,6 +350,7 @@ \bigskip %%\newpage +\subsubsection*{Task 2 (file knight2.scala)} \noindent As you should have seen in the earlier parts, a naive search for tours beyond @@ -396,8 +385,6 @@ 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 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 @@ -423,7 +410,7 @@ \mbox{}\hfill[1 Mark] \end{itemize} -\subsubsection*{Task (file knight3.scala)} +\subsubsection*{Task 3 (file knight3.scala)} \begin{itemize} \item[(9)] Implement a function \texttt{tour\_on\_mega\_board} which is the same function as in (8), \textbf{but} should be able to @@ -443,7 +430,7 @@ \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] $ scala -cp knight3.jar -scala> CW9c.tour_on_mega_board(70, List((0, 0))) +scala> M4c.tour_on_mega_board(70, List((0, 0))) Time needed: 9.484 secs. ...<>... \end{lstlisting}%$