--- 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.
Binary file cws/main_cw04.pdf has changed
--- 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}
Binary file main_solution4/knight1.jar has changed
Binary file main_solution4/knight2.jar has changed
Binary file main_solution4/knight3.jar has changed
--- /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] = ???
+
+
+}
--- 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
--- 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/)
+++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[
--- /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)
+
+
+}
--- 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/)
+++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[