--- 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.
...<<long_list>>...
\end{lstlisting}%$