# HG changeset patch # User Christian Urban # Date 1667425782 0 # Node ID 274c865b3878458d104c6e079ac181a3f5cee427 # Parent 126d0e47ac85c7f3690d171078dbbde93eb8f42a updated diff -r 126d0e47ac85 -r 274c865b3878 core_templates1/collatz.scala --- a/core_templates1/collatz.scala Wed Nov 02 13:22:59 2022 +0000 +++ b/core_templates1/collatz.scala Wed Nov 02 21:49:42 2022 +0000 @@ -23,10 +23,3 @@ } - - -// This template code is subject to copyright -// owned by King's College London. Do not -// make this template code public in any shape or -// form, and do not exchange it with other students -// under any circumstance. diff -r 126d0e47ac85 -r 274c865b3878 cws/main_cw04.pdf Binary file cws/main_cw04.pdf has changed diff -r 126d0e47ac85 -r 274c865b3878 cws/main_cw04.tex --- a/cws/main_cw04.tex Wed Nov 02 13:22:59 2022 +0000 +++ b/cws/main_cw04.tex Wed Nov 02 21:49:42 2022 +0000 @@ -19,7 +19,7 @@ \mbox{}\\[-18mm]\mbox{} -\section*{Main Part 4 (Scala, 9 Marks)} +\section*{Main Part 4 (Scala, 11 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}\\ @@ -214,7 +214,7 @@ made available by importing \texttt{scala.annotation.tailrec}.\medskip -\newpage +%%\newpage \subsection*{Tasks} @@ -432,9 +432,56 @@ \end{lstlisting}%$ \mbox{}\hfill[1 Mark] -\end{itemize} -\bigskip +\end{itemize} + +\subsubsection*{Task 4 (file knight4.scala)} +\begin{itemize} +\item[(10)] In this task we want to solve the problem of finding a single + tour (if there exists one) on what is sometimes called ``mutilated'' + chessboards, for example rectangular chessbords or chessboards where + fields are missing. For this implement a search function + + \begin{center} + \begin{tabular}{@{}l@{}} + \texttt{def one\_tour\_pred(dim: Int, path: Path,}\\ + \texttt{\phantom{def one\_tour\_pred(}n: Int, f: Pos => Boolean): Option[Path]} + \end{tabular} + \end{center} + which has, like before, the dimension and current path as arguments, + and in addtion it takes an integer, which specifies the length of + the longest path (or length of the path after which the search + should backtrack), and a function from positions to Booleans. This + function acts as a predicate in order to restrict which onward legal + moves should be considered in the search. The function + \texttt{one\_tour\_pred} should return a single tour + (\texttt{Some}-case), if one or more tours exist, and \texttt{None}, if no + tour exists. For example when called with + + \begin{center} + \texttt{one\_tour\_pred(7, List((0, 0)), 35, x => x.\_1 < 5)} + \end{center} + + we are looking for a tour starting from position \texttt{(0,0)} on a + 7 $\times$ 5 board, where the maximum length of the path is 35. The + predicate \texttt{x => x.\_1 < 5} ensures that no position with an + x-coordinate bigger than 4 is considered. One possible solution is + + \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] + 0 13 22 33 28 11 20 + 23 32 1 12 21 34 27 + 14 7 16 29 2 19 10 + 31 24 5 8 17 26 3 + 6 15 30 25 4 9 18 + -1 -1 -1 -1 -1 -1 -1 + -1 -1 -1 -1 -1 -1 -1 +\end{lstlisting}%$ + +where \texttt{print\_board} prints a \texttt{-1} for all fields that +have not been visited. + + \mbox{}\hfill[2 Marks] +\end{itemize} diff -r 126d0e47ac85 -r 274c865b3878 main_solution4/knight1.jar Binary file main_solution4/knight1.jar has changed diff -r 126d0e47ac85 -r 274c865b3878 main_solution4/knight2.jar Binary file main_solution4/knight2.jar has changed diff -r 126d0e47ac85 -r 274c865b3878 main_solution4/knight3.jar Binary file main_solution4/knight3.jar has changed diff -r 126d0e47ac85 -r 274c865b3878 main_solution4/knight4.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_solution4/knight4.scala Wed Nov 02 21:49:42 2022 +0000 @@ -0,0 +1,33 @@ +// Part 4 about finding a single tour on "mutilated" chessboards +//============================================================== + +object M4d { + +// !!! Copy any function you need from file knight1.scala !!! +// !!! or knight2.scala or knight3.scala !!! +// +// If you need any auxiliary function, feel free to +// implement it, but do not make any changes to the +// templates below. + +type Pos = (Int, Int) +type Path = List[Pos] + +def print_board(dim: Int, path: Path): Unit = { + println() + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((i, j))}%4.0f ") + } + println() + } +} + +// ADD YOUR CODE BELOW +//====================== + +// (10) +def one_tour_pred(dim: Int, path: Path, n: Int, pred: Pos => Boolean): Option[Path] = ??? + + +} diff -r 126d0e47ac85 -r 274c865b3878 main_solution5/bf.scala --- a/main_solution5/bf.scala Wed Nov 02 13:22:59 2022 +0000 +++ b/main_solution5/bf.scala Wed Nov 02 21:49:42 2022 +0000 @@ -219,5 +219,5 @@ //M5a.run(M5a.load_bff("mandelbrot.bf")) //M5a.run(M5a.load_bff("collatz.bf")) -println(M5a.generate("ABC".toList)) -M5a.run(M5a.generate("Hello World\n".toList)) \ No newline at end of file +//println(M5a.generate("ABC".toList)) +//M5a.run(M5a.generate("Hello World\n".toList)) \ No newline at end of file diff -r 126d0e47ac85 -r 274c865b3878 main_solution5/mandelbrot.bf --- a/main_solution5/mandelbrot.bf Wed Nov 02 13:22:59 2022 +0000 +++ b/main_solution5/mandelbrot.bf Wed Nov 02 21:49:42 2022 +0000 @@ -1,5 +1,5 @@ // a Mandelbrot set generator in brainf___ written by Erik Bosman -// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) +// (http://esoteric^dot^sange^dot^fi/brainfuck/utils/mandelbrot/) +++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[ diff -r 126d0e47ac85 -r 274c865b3878 main_templates4/knight4.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_templates4/knight4.scala Wed Nov 02 21:49:42 2022 +0000 @@ -0,0 +1,53 @@ +// Part 4 about finding a single tour on "mutilated" chessboards +//============================================================== + +object M4d { // for preparing the jar + +type Pos = (Int, Int) +type Path = List[Pos] + +def print_board(dim: Int, path: Path): Unit = { + println() + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((i, j))}%4.0f ") + } + println() + } +} + +def add_pair(x: Pos, y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +def is_legal(dim: Int, path: Path, x: Pos): Boolean = + 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) + +def moves(x: Pos): List[Pos] = + List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), + (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _)) + +def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = + moves(x).filter(is_legal(dim, path, _)) + +import scala.annotation.tailrec + +@tailrec +def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { + case Nil => None + case x::xs => { + val result = f(x) + if (result.isDefined) result else first(xs, f) + } +} + + +def one_tour_pred(dim: Int, path: Path, n: Int, pred: Pos => Boolean): Option[Path] = { + if (path.length == n) Some(path) + else + first(legal_moves(dim, path, path.head).filter(pred), (x: Pos) => one_tour_pred(dim, x::path, n, pred)) +} + +//print_board(8, one_tour_pred(8, List((0, 0)), 40, x => x._1 < 5).get) + + +} diff -r 126d0e47ac85 -r 274c865b3878 main_templates5/mandelbrot.bf --- a/main_templates5/mandelbrot.bf Wed Nov 02 13:22:59 2022 +0000 +++ b/main_templates5/mandelbrot.bf Wed Nov 02 21:49:42 2022 +0000 @@ -1,5 +1,5 @@ // a Mandelbrot set generator in brainf___ written by Erik Bosman -// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) +// (http://esoteric^dot^sange^dot^fi/brainfuck/utils/mandelbrot/) +++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[