pep-material: comparison cws/main

equal deleted inserted replaced

-:3ffe978a5664
+:085fefce672e
 hlabelformat=\arabic{ranklabel},
 vlabelformat=\arabic{filelabel}}
 \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}\\
 \mbox{}\hfill\textit{what you got was a gorilla holding the banana and the entire jungle.''}\smallskip\\
 \mbox{}\hfill\textit{ --- Joe Armstrong (creator of the Erlang programming language)}\medskip\bigskip
 \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
+\textit{Knight's Tour Problem} on a chessboard.
-due on  \sout{\cwNINE{}} \textcolor{red}{16 December} at 5pm; the core part (6\%) is due on \cwNINEa{} at 5pm.
+% The preliminary part (4\%) is due on  \sout{\cwNINE{}}
-Any 1\% you achieve in the preliminary part counts as your ``weekly engagement''.
+% \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{}
 \noindent
 setpieces={Ng7, Nb2},
 boardfontsize=12pt,labelfontsize=9pt]}
 \subsection*{Reference Implementation}
-\mbox{}\alert{}\textcolor{red}{You need to download \texttt{knight1.jar} from KEATS. The one
+%\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
+%supplied with github does not contain the correct code. See Scala coursework
-section on KEATS.}\medskip
+%section on KEATS.}\medskip
 \noindent
 This Scala part comes with three reference implementations in form of
 \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
 \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
 56  43  52   3  22  13  24   5
 47  50  45  54  25  20  11  14
 \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
+this function takes an \texttt{Int} as an argument;
+a useful list function: \texttt{.sortBy} sorts a list
-\noindent
-\textbf{Main Part} 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
-\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
 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
 \emph{tour} if the length of the path is $n \times n$, each element
 occurs only once in the path, and each move follows the rules of how a
 knight moves (see above for the rules).
-\subsubsection*{Tasks (file knight1.scala)}
+\subsubsection*{Task 1 (file knight1.scala)}
 \begin{itemize}
 \item[(1)] Implement an \texttt{is\_legal} function that takes a
 tours (there can be none for certain board sizes) and the second
 collects all tours in a list of paths. These functions will be
 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)$,
 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.}\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
 this argument). The function $f$ takes a position as argument and
 \item[(5)] Implement a \texttt{first\_tour} function that uses the
 \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
 %%\newpage
+\subsubsection*{Task 2 (file knight2.scala)}
 \noindent
 As you should have seen in the earlier parts, 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 heuristics, called \emph{Warnsdorf's
 \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 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
 Warnsdorf’s Rule. That means moves with the fewest legal onward moves
 %tail-recursive function of the \texttt{first\_tour\_heuristics} function
 %otherwise you will get problems with stack-overflows.\\
 \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
 deal with boards up to
 $70\times 70$ \textbf{within 30 seconds} (on my laptop). This will be tested
 on my laptop:
 \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}%$
 \mbox{}\hfill[1 Mark]

changeset 397	085fefce672e
parent 379	5616b45d656f
child 400	e48ea8300b2d