17 hlabelformat=\arabic{ranklabel}, |
17 hlabelformat=\arabic{ranklabel}, |
18 vlabelformat=\arabic{filelabel}} |
18 vlabelformat=\arabic{filelabel}} |
19 |
19 |
20 \mbox{}\\[-18mm]\mbox{} |
20 \mbox{}\\[-18mm]\mbox{} |
21 |
21 |
22 \section*{Main Part 4 (Scala, 9 Marks)} |
22 \section*{Main Part 4 (Scala, 11 Marks)} |
23 |
23 |
24 \mbox{}\hfill\textit{``The problem with object-oriented languages is they’ve got all this implicit,}\\ |
24 \mbox{}\hfill\textit{``The problem with object-oriented languages is they’ve got all this implicit,}\\ |
25 \mbox{}\hfill\textit{environment that they carry around with them. You wanted a banana but}\\ |
25 \mbox{}\hfill\textit{environment that they carry around with them. You wanted a banana but}\\ |
26 \mbox{}\hfill\textit{what you got was a gorilla holding the banana and the entire jungle.''}\smallskip\\ |
26 \mbox{}\hfill\textit{what you got was a gorilla holding the banana and the entire jungle.''}\smallskip\\ |
27 \mbox{}\hfill\textit{ --- Joe Armstrong (creator of the Erlang programming language)}\medskip\bigskip |
27 \mbox{}\hfill\textit{ --- Joe Armstrong (creator of the Erlang programming language)}\medskip\bigskip |
212 according to a component given by the function; a function can be |
212 according to a component given by the function; a function can be |
213 tested to be tail-recursive by annotation \texttt{@tailrec}, which is |
213 tested to be tail-recursive by annotation \texttt{@tailrec}, which is |
214 made available by importing \texttt{scala.annotation.tailrec}.\medskip |
214 made available by importing \texttt{scala.annotation.tailrec}.\medskip |
215 |
215 |
216 |
216 |
217 \newpage |
217 %%\newpage |
218 |
218 |
219 \subsection*{Tasks} |
219 \subsection*{Tasks} |
220 |
220 |
221 You are asked to implement the knight's tour problem such that the |
221 You are asked to implement the knight's tour problem such that the |
222 dimension of the board can be changed. Therefore most functions will |
222 dimension of the board can be changed. Therefore most functions will |
430 Time needed: 9.484 secs. |
430 Time needed: 9.484 secs. |
431 ...<<long_list>>... |
431 ...<<long_list>>... |
432 \end{lstlisting}%$ |
432 \end{lstlisting}%$ |
433 |
433 |
434 \mbox{}\hfill[1 Mark] |
434 \mbox{}\hfill[1 Mark] |
435 \end{itemize} |
435 \end{itemize} |
436 \bigskip |
436 |
437 |
437 \subsubsection*{Task 4 (file knight4.scala)} |
|
438 \begin{itemize} |
|
439 \item[(10)] In this task we want to solve the problem of finding a single |
|
440 tour (if there exists one) on what is sometimes called ``mutilated'' |
|
441 chessboards, for example rectangular chessbords or chessboards where |
|
442 fields are missing. For this implement a search function |
|
443 |
|
444 \begin{center} |
|
445 \begin{tabular}{@{}l@{}} |
|
446 \texttt{def one\_tour\_pred(dim: Int, path: Path,}\\ |
|
447 \texttt{\phantom{def one\_tour\_pred(}n: Int, f: Pos => Boolean): Option[Path]} |
|
448 \end{tabular} |
|
449 \end{center} |
|
450 |
|
451 which has, like before, the dimension and current path as arguments, |
|
452 and in addtion it takes an integer, which specifies the length of |
|
453 the longest path (or length of the path after which the search |
|
454 should backtrack), and a function from positions to Booleans. This |
|
455 function acts as a predicate in order to restrict which onward legal |
|
456 moves should be considered in the search. The function |
|
457 \texttt{one\_tour\_pred} should return a single tour |
|
458 (\texttt{Some}-case), if one or more tours exist, and \texttt{None}, if no |
|
459 tour exists. For example when called with |
|
460 |
|
461 \begin{center} |
|
462 \texttt{one\_tour\_pred(7, List((0, 0)), 35, x => x.\_1 < 5)} |
|
463 \end{center} |
|
464 |
|
465 we are looking for a tour starting from position \texttt{(0,0)} on a |
|
466 7 $\times$ 5 board, where the maximum length of the path is 35. The |
|
467 predicate \texttt{x => x.\_1 < 5} ensures that no position with an |
|
468 x-coordinate bigger than 4 is considered. One possible solution is |
|
469 |
|
470 \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] |
|
471 0 13 22 33 28 11 20 |
|
472 23 32 1 12 21 34 27 |
|
473 14 7 16 29 2 19 10 |
|
474 31 24 5 8 17 26 3 |
|
475 6 15 30 25 4 9 18 |
|
476 -1 -1 -1 -1 -1 -1 -1 |
|
477 -1 -1 -1 -1 -1 -1 -1 |
|
478 \end{lstlisting}%$ |
|
479 |
|
480 where \texttt{print\_board} prints a \texttt{-1} for all fields that |
|
481 have not been visited. |
|
482 |
|
483 \mbox{}\hfill[2 Marks] |
|
484 \end{itemize} |
438 |
485 |
439 |
486 |
440 |
487 |
441 \end{document} |
488 \end{document} |
442 |
489 |