--- a/core_templates1/README.md Thu Nov 02 23:34:53 2023 +0000
+++ b/core_templates1/README.md Sat Nov 04 18:53:37 2023 +0000
@@ -1,6 +1,6 @@
-# assignment2022scala - Core 1
+# assignment2023scala - Core 1
-* deadline: 19 January, 5pm
+* deadline: 4 January, 4pm
* [coursework description](https://nms.kcl.ac.uk/christian.urban/core_cw01.pdf)
* reference jar:
[collatz.jar](https://nms.kcl.ac.uk/christian.urban/collatz.jar)
\ No newline at end of file
--- a/core_templates2/README.md Thu Nov 02 23:34:53 2023 +0000
+++ b/core_templates2/README.md Sat Nov 04 18:53:37 2023 +0000
@@ -1,6 +1,6 @@
-# assignment2022scala - Core 2
+# assignment2023scala - Core 2
-* deadline: 19 January, 5pm
+* deadline: 4 January, 4pm
* [coursework description](https://nms.kcl.ac.uk/christian.urban/core_cw02.pdf)
* reference jar:
[docdiff.jar](https://nms.kcl.ac.uk/christian.urban/docdiff.jar)
\ No newline at end of file
--- a/core_templates3/README.md Thu Nov 02 23:34:53 2023 +0000
+++ b/core_templates3/README.md Sat Nov 04 18:53:37 2023 +0000
@@ -1,6 +1,6 @@
-# assignment2022scala - Core 3
+# assignment2023scala - Core 3
-* deadline: 19 January, 5pm
+* deadline: 4 January, 4pm
* [coursework description](https://nms.kcl.ac.uk/christian.urban/core_cw03.pdf)
* reference jar:
[postfix.jar](https://nms.kcl.ac.uk/christian.urban/postfix.jar),
Binary file cws/main_cw04-old.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/main_cw04-old.tex Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,493 @@
+% !TEX program = xelatex
+\documentclass{article}
+\usepackage{chessboard}
+\usepackage[LSBC4,T1]{fontenc}
+\let\clipbox\relax
+\usepackage{../styles/style}
+\usepackage{../styles/langs}
+\usepackage{disclaimer}
+\usepackage{ulem}
+
+\begin{document}
+
+\setchessboard{smallboard,
+ zero,
+ showmover=false,
+ boardfontencoding=LSBC4,
+ hlabelformat=\arabic{ranklabel},
+ vlabelformat=\arabic{filelabel}}
+
+\mbox{}\\[-18mm]\mbox{}
+
+\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}\\
+\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.
+\medskip
+
+% Note the core, more advanced, part might include material you have not
+%yet seen in the first three lectures. \bigskip
+
+\IMPORTANTNONE{}
+
+\noindent
+Also note that the running time of each part will be restricted to a
+maximum of 30 seconds on my laptop: If you calculate a result once,
+try to avoid to calculate the result again. Feel free to copy any code
+you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and
+\texttt{knight3.scala}.
+
+\DISCLAIMER{}
+
+\subsection*{Background}
+
+The \textit{Knight's Tour Problem} is about finding a tour such that
+the knight visits every field on an $n\times n$ chessboard once. For
+example on a $5\times 5$ chessboard, a knight's tour is:
+
+\chessboard[maxfield=d4,
+ pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
+ text = \small 24, markfield=Z4,
+ text = \small 11, markfield=a4,
+ text = \small 6, markfield=b4,
+ text = \small 17, markfield=c4,
+ text = \small 0, markfield=d4,
+ text = \small 19, markfield=Z3,
+ text = \small 16, markfield=a3,
+ text = \small 23, markfield=b3,
+ text = \small 12, markfield=c3,
+ text = \small 7, markfield=d3,
+ text = \small 10, markfield=Z2,
+ text = \small 5, markfield=a2,
+ text = \small 18, markfield=b2,
+ text = \small 1, markfield=c2,
+ text = \small 22, markfield=d2,
+ text = \small 15, markfield=Z1,
+ text = \small 20, markfield=a1,
+ text = \small 3, markfield=b1,
+ text = \small 8, markfield=c1,
+ text = \small 13, markfield=d1,
+ text = \small 4, markfield=Z0,
+ text = \small 9, markfield=a0,
+ text = \small 14, markfield=b0,
+ text = \small 21, markfield=c0,
+ text = \small 2, markfield=d0
+ ]
+
+\noindent
+This tour starts in the right-upper corner, then moves to field
+$(3,2)$, then $(4,0)$ and so on. There are no knight's tours on
+$2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every
+bigger board there is.
+
+A knight's tour is called \emph{closed}, if the last step in the tour
+is within a knight's move to the beginning of the tour. So the above
+knight's tour is \underline{not} closed because the last
+step on field $(0, 4)$ is not within the reach of the first step on
+$(4, 4)$. It turns out there is no closed knight's tour on a $5\times
+5$ board. But there are on a $6\times 6$ board and on bigger ones, for
+example
+
+\chessboard[maxfield=e5,
+ pgfstyle={[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
+ text = \small 10, markfield=Z5,
+ text = \small 5, markfield=a5,
+ text = \small 18, markfield=b5,
+ text = \small 25, markfield=c5,
+ text = \small 16, markfield=d5,
+ text = \small 7, markfield=e5,
+ text = \small 31, markfield=Z4,
+ text = \small 26, markfield=a4,
+ text = \small 9, markfield=b4,
+ text = \small 6, markfield=c4,
+ text = \small 19, markfield=d4,
+ text = \small 24, markfield=e4,
+ % 4 11 30 17 8 15
+ text = \small 4, markfield=Z3,
+ text = \small 11, markfield=a3,
+ text = \small 30, markfield=b3,
+ text = \small 17, markfield=c3,
+ text = \small 8, markfield=d3,
+ text = \small 15, markfield=e3,
+ %29 32 27 0 23 20
+ text = \small 29, markfield=Z2,
+ text = \small 32, markfield=a2,
+ text = \small 27, markfield=b2,
+ text = \small 0, markfield=c2,
+ text = \small 23, markfield=d2,
+ text = \small 20, markfield=e2,
+ %12 3 34 21 14 1
+ text = \small 12, markfield=Z1,
+ text = \small 3, markfield=a1,
+ text = \small 34, markfield=b1,
+ text = \small 21, markfield=c1,
+ text = \small 14, markfield=d1,
+ text = \small 1, markfield=e1,
+ %33 28 13 2 35 22
+ text = \small 33, markfield=Z0,
+ text = \small 28, markfield=a0,
+ text = \small 13, markfield=b0,
+ text = \small 2, markfield=c0,
+ text = \small 35, markfield=d0,
+ text = \small 22, markfield=e0,
+ vlabel=false,
+ hlabel=false
+ ]
+
+
+\noindent
+where the 35th move can join up again with the 0th move.
+
+If you cannot remember how a knight moves in chess, or never played
+chess, below are all potential moves indicated for two knights, one on
+field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):
+
+{\chessboard[maxfield=g7,
+ color=blue!50,
+ linewidth=0.2em,
+ shortenstart=0.5ex,
+ shortenend=0.5ex,
+ markstyle=cross,
+ markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
+ color=red!50,
+ markfields={f5, e6},
+ setpieces={Ng7, Nb2},
+ boardfontsize=12pt,labelfontsize=9pt]}
+
+\subsection*{Reference Implementation}
+
+%\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
+\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{M4a}, \texttt{M4b}, \texttt{M4c} and \texttt{M4d}.
+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> M4a.enum_tours(5, List((0, 0))).length
+Time needed: 1.722 secs.
+res0: Int = 304
+
+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
+ 42 57 2 49 40 23 6 19
+ 35 48 41 26 61 10 15 28
+ 58 1 36 39 32 27 18 7
+ 37 34 31 60 9 62 29 16
+ 0 59 38 33 30 17 8 63
+\end{lstlisting}%$
+
+
+\subsection*{Hints}
+
+\noindent
+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;
+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
+
+
+%%\newpage
+
+\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
+incredibly large search space---finding a tour is like finding a
+needle in a haystack. In the first task we want to see how far we get
+with exhaustively exploring the complete search space for small
+chessboards.\medskip
+
+\noindent
+Let us first fix the basic datastructures for the implementation. The
+board dimension is an integer.
+A \emph{position} (or field) on the chessboard is
+a pair of integers, like $(0, 0)$. A \emph{path} is a list of
+positions. The first (or 0th move) in a path is the last element in
+this list; and the last move in the path is the first element. For
+example the path for the $5\times 5$ chessboard above is represented
+by
+
+\[
+\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,
+ $\underbrace{\texttt{(2, 3)}}_{23}$, ...,
+ $\underbrace{\texttt{(3, 2)}}_1$, $\underbrace{\texttt{(4, 4)}}_0$)}
+\]
+
+\noindent
+Suppose the dimension of a chessboard is $n$, then a path is a
+\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*{Task 1 (file knight1.scala)}
+
+
+
+\begin{itemize}
+\item[(1)] Implement an \texttt{is\_legal} function that takes a
+ dimension, a path and a position as arguments and tests whether the
+ position is inside the board and not yet element in the
+ path. \hfill[1 Mark]
+
+\item[(2)] Implement a \texttt{legal\_moves} function that calculates for a
+ position all legal onward moves. If the onward moves are
+ placed on a circle, you should produce them starting from
+ ``12-o'clock'' following in clockwise order. For example on an
+ $8\times 8$ board for a knight at position $(2, 2)$ and otherwise
+ empty board, the legal-moves function should produce the onward
+ positions in this order:
+
+ \begin{center}
+ \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}
+ \end{center}
+
+ If the board is not empty, then maybe some of the moves need to be
+ filtered out from this list. For a knight on field $(7, 7)$ and an
+ empty board, the legal moves are
+
+ \begin{center}
+ \texttt{List((6,5), (5,6))}
+ \end{center}
+ \mbox{}\hfill[1 Mark]
+
+\item[(3)] Implement two recursive functions (\texttt{count\_tours} and
+ \texttt{enum\_tours}). They each take a dimension and a path as
+ arguments. They exhaustively search for tours starting
+ from the given path. The first function counts all possible
+ 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[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
+
+\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
+ produces an optional path. So $f$'s type is \texttt{Pos =>
+ Option[Path]}. The idea behind the \texttt{first}-function is as follows:
+
+ \[
+ \begin{array}{lcl}
+ \textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\
+ \textit{first}(x\!::\!xs, f) & \dn & \begin{cases}
+ f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
+ \textit{first}(xs, f) & \textit{otherwise}\\
+ \end{cases}
+ \end{array}
+ \]
+
+ \noindent That is, we want to find the first position where the
+ result of $f$ is not \texttt{None}, if there is one. Note that
+ `inside' \texttt{first}, you do not (need to) know anything about
+ the argument $f$ except its type, namely \texttt{Pos =>
+ Option[Path]}. If you want to find out what the result of $f$ is
+ on a particular argument, say $x$, you can just write $f(x)$.
+ There is one additional point however you should
+ take into account when implementing \texttt{first}: you will need to
+ calculate what the result of $f(x)$ is; your code should do this
+ only \textbf{once} and for as \textbf{few} elements in the list as
+ possible! Do not calculate $f(x)$ for all elements and then see which
+ is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]
+
+\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
+Rule} that can speed up finding a tour. This heuristics states that a
+knight is moved so that it always proceeds to the field from which the
+knight will have the \underline{fewest} onward moves. For example for
+a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible
+onward moves, namely 2.
+
+\chessboard[maxfield=g7,
+ pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
+ text = \small 3, markfield=Z5,
+ text = \small 7, markfield=b5,
+ text = \small 7, markfield=c4,
+ text = \small 7, markfield=c2,
+ text = \small 5, markfield=b1,
+ text = \small 2, markfield=Z1,
+ setpieces={Na3}]
+
+\noindent
+Warnsdorf's Rule states that the moves on the board above should be
+tried in the order
+
+\[
+(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)
+\]
+
+\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.
+
+\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
+ should come first (in order to be tried out first). \hfill[1 Mark]
+
+\item[(7)] Implement a \texttt{first\_closed\_tour\_heuristics}
+ function that searches for a single
+ \textbf{closed} tour on a $6\times 6$ board. It should try out
+ onward moves according to
+ the \texttt{ordered\_moves} function from (6). It is more likely to find
+ a solution when started in the middle of the board (that is
+ position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]
+
+\item[(8)] Implement a \texttt{first\_tour\_heuristics} function
+ for boards up to
+ $30\times 30$. It is the same function as in (7) but searches for
+ tours (not just closed tours). It might be called with any field on the
+ board as starting field.\\
+ %You have to be careful to write a
+ %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 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
+ by starting from field $(0, 0)$. You have to be careful to
+ write a tail-recursive function otherwise you will get problems
+ with stack-overflows. Please observe the requirements about
+ the submissions: no tricks involving \textbf{.par}.\medskip
+
+ The timelimit of 30 seconds is with respect to the laptop on which the
+ marking will happen. You can roughly estimate how well your
+ implementation performs by running \texttt{knight3.jar} on your
+ computer. For example the reference implementation shows
+ on my laptop:
+
+ \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
+$ scala -cp knight3.jar
+
+scala> M4c.tour_on_mega_board(70, List((0, 0)))
+Time needed: 9.484 secs.
+...<<long_list>>...
+\end{lstlisting}%$
+
+ \mbox{}\hfill[1 Mark]
+\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}
+
+
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
Binary file cws/main_cw04.pdf has changed
--- a/cws/main_cw04.tex Thu Nov 02 23:34:53 2023 +0000
+++ b/cws/main_cw04.tex Sat Nov 04 18:53:37 2023 +0000
@@ -7,6 +7,35 @@
\usepackage{../styles/langs}
\usepackage{disclaimer}
\usepackage{ulem}
+%\usepackage{tipauni}
+
+
+
+\tikzset
+{%
+ pics/piece/.style n args={1}{
+ code={%
+ \fill[rounded corners] (-0.1,-0.1) rectangle (-0.9, -0.9);
+ \fill[left color=white,rounded corners,
+ right color=gray,
+ opacity=0.7] (-0.1,-0.1) rectangle (-0.9, -0.9);
+ \draw[line width=0.4mm,rounded corners] (-0.1,-0.1) rectangle (-0.9, -0.9);
+ \draw[line width=0.2mm,rounded corners] (-0.2,-0.2) rectangle (-0.8, -0.8);
+ \draw[anchor=mid] (-0.5,-0.6) node {#1};
+ }},
+ pics/king/.style n args={1}{
+ code={%
+ \fill[rounded corners] (-0.1,-0.1) rectangle (-0.9, -0.9);
+ \fill[left color=white,rounded corners,
+ right color=gray,
+ opacity=0.7] (-0.1,-0.1) rectangle (-0.9, -0.9);
+ \draw[line width=0.4mm,rounded corners] (-0.1,-0.1) rectangle (-0.9, -0.9);
+ \draw[line width=0.2mm,rounded corners] (-0.2,-0.2) rectangle (-0.8, -0.8);
+ \draw[anchor=mid] (-0.5,-0.6) node {#1};
+ \draw[anchor=center] (-0.5,-0.25) node {\includegraphics[scale=0.015]{crown.png}};
+ }}
+}
+
\begin{document}
@@ -19,472 +48,515 @@
\mbox{}\\[-18mm]\mbox{}
-\section*{Main Part 4 (Scala, 11 Marks)}
+\section*{Main Part 4:\\ Implementing the Shogun Board Game (7 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.
-\medskip
+You are asked to implement a Scala program for playing the Shogun
+board game.\medskip
-% Note the core, more advanced, part might include material you have not
-%yet seen in the first three lectures. \bigskip
+%The deadline for your submission is on 26th July at
+%16:00. There will be no automated tests for the resit, but there are
+%many testcases in the template and the task description. Make sure
+%you use Scala \textbf{2.13.XX} for the resit---the same version as
+%during the lectures. \medskip
\IMPORTANTNONE{}
\noindent
-Also note that the running time of each part will be restricted to a
+Also note that the running time of each task will be restricted to a
maximum of 30 seconds on my laptop: If you calculate a result once,
-try to avoid to calculate the result again. Feel free to copy any code
-you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and
-\texttt{knight3.scala}.
+try to avoid to calculate the result again.
\DISCLAIMER{}
\subsection*{Background}
-The \textit{Knight's Tour Problem} is about finding a tour such that
-the knight visits every field on an $n\times n$ chessboard once. For
-example on a $5\times 5$ chessboard, a knight's tour is:
+Shogun
+(\faVolumeUp\,[shōgoon]) is a game played by two players on a chess board and is somewhat
+similar to chess and checkers. A real Shogun board looks
+like in the pictures on the left.
-\chessboard[maxfield=d4,
- pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
- text = \small 24, markfield=Z4,
- text = \small 11, markfield=a4,
- text = \small 6, markfield=b4,
- text = \small 17, markfield=c4,
- text = \small 0, markfield=d4,
- text = \small 19, markfield=Z3,
- text = \small 16, markfield=a3,
- text = \small 23, markfield=b3,
- text = \small 12, markfield=c3,
- text = \small 7, markfield=d3,
- text = \small 10, markfield=Z2,
- text = \small 5, markfield=a2,
- text = \small 18, markfield=b2,
- text = \small 1, markfield=c2,
- text = \small 22, markfield=d2,
- text = \small 15, markfield=Z1,
- text = \small 20, markfield=a1,
- text = \small 3, markfield=b1,
- text = \small 8, markfield=c1,
- text = \small 13, markfield=d1,
- text = \small 4, markfield=Z0,
- text = \small 9, markfield=a0,
- text = \small 14, markfield=b0,
- text = \small 21, markfield=c0,
- text = \small 2, markfield=d0
- ]
-
-\noindent
-This tour starts in the right-upper corner, then moves to field
-$(3,2)$, then $(4,0)$ and so on. There are no knight's tours on
-$2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every
-bigger board there is.
-A knight's tour is called \emph{closed}, if the last step in the tour
-is within a knight's move to the beginning of the tour. So the above
-knight's tour is \underline{not} closed because the last
-step on field $(0, 4)$ is not within the reach of the first step on
-$(4, 4)$. It turns out there is no closed knight's tour on a $5\times
-5$ board. But there are on a $6\times 6$ board and on bigger ones, for
-example
-
-\chessboard[maxfield=e5,
- pgfstyle={[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
- text = \small 10, markfield=Z5,
- text = \small 5, markfield=a5,
- text = \small 18, markfield=b5,
- text = \small 25, markfield=c5,
- text = \small 16, markfield=d5,
- text = \small 7, markfield=e5,
- text = \small 31, markfield=Z4,
- text = \small 26, markfield=a4,
- text = \small 9, markfield=b4,
- text = \small 6, markfield=c4,
- text = \small 19, markfield=d4,
- text = \small 24, markfield=e4,
- % 4 11 30 17 8 15
- text = \small 4, markfield=Z3,
- text = \small 11, markfield=a3,
- text = \small 30, markfield=b3,
- text = \small 17, markfield=c3,
- text = \small 8, markfield=d3,
- text = \small 15, markfield=e3,
- %29 32 27 0 23 20
- text = \small 29, markfield=Z2,
- text = \small 32, markfield=a2,
- text = \small 27, markfield=b2,
- text = \small 0, markfield=c2,
- text = \small 23, markfield=d2,
- text = \small 20, markfield=e2,
- %12 3 34 21 14 1
- text = \small 12, markfield=Z1,
- text = \small 3, markfield=a1,
- text = \small 34, markfield=b1,
- text = \small 21, markfield=c1,
- text = \small 14, markfield=d1,
- text = \small 1, markfield=e1,
- %33 28 13 2 35 22
- text = \small 33, markfield=Z0,
- text = \small 28, markfield=a0,
- text = \small 13, markfield=b0,
- text = \small 2, markfield=c0,
- text = \small 35, markfield=d0,
- text = \small 22, markfield=e0,
- vlabel=false,
- hlabel=false
- ]
+\begin{center}
+\begin{tabular}{@{}ccc@{}}
+\raisebox{2mm}{\includegraphics[scale=0.1]{shogun2.jpeg}}
+&
+\raisebox{2mm}{\includegraphics[scale=0.14]{shogun.jpeg}}
+&
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+ \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}
+ \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+% black pieces
+\foreach\x/\y/\e in {1/1/1,2/1/3,3/1/2,4/1/3,6/1/3,7/1/1,8/1/2}
+ \pic[fill=white] at (\x,\y) {piece={\e}};
+% white pieces
+\foreach\x/\y/\e in {1/8/4,2/8/2,3/8/4,5/8/4,6/8/2,7/8/3,8/8/1}
+ \pic[fill=red] at (\x,\y) {piece={\e}};
+\pic[fill=white] at (5.0,1.0) {king={1}};
+\pic[fill=red] at (4.0,8.0) {king={2}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\end{tabular}
+\end{center}
\noindent
-where the 35th move can join up again with the 0th move.
+In what follows we shall use board illustrations as shown on the right. As
+can be seen there are two colours in Shogun for the pieces, red and white. Each
+player has 8 pieces, one of which is a king (the piece with the crown)
+and seven are pawns. At the beginning the pieces are lined up as shown
+above. What sets Shogun apart from chess and checkers is that each
+piece has, what I call, a kind of \textit{energy}---which for pawns is
+a number between 1 and 4, and for kings between 1 and 2. The energy
+determines how far a piece has to move. In the physical version of
+Shogun, the pieces and the board have magnets that can change the
+energy of a piece from move to move---so a piece on one field can have
+energy 2 and on a different field the same piece might have energy
+3. There are some further constraints on legal moves, which are
+explained below. The point of this part is to implement functions
+about moving pieces on the Shogun board.\medskip\medskip
-If you cannot remember how a knight moves in chess, or never played
-chess, below are all potential moves indicated for two knights, one on
-field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):
+%and testing for when a
+%checkmate occurs---i.e.~the king is attacked and cannot move
+%anymore to an ``unattacked'' field (to simplify matters for
+%the resit we leave out the case where the checkmate can be averted by capturing
+%the attacking piece).\medskip
-{\chessboard[maxfield=g7,
- color=blue!50,
- linewidth=0.2em,
- shortenstart=0.5ex,
- shortenend=0.5ex,
- markstyle=cross,
- markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
- color=red!50,
- markfields={f5, e6},
- setpieces={Ng7, Nb2},
- boardfontsize=12pt,labelfontsize=9pt]}
+\noindent
+Like in chess, in Shogun the players take turns of moving and
+possibly capturing opposing pieces.
+There are the following rules on how pieces can move:
-\subsection*{Reference Implementation}
-
-%\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
+\begin{itemize}
+\item The energy of a piece determines how far, that is how many
+ fields, a piece has to move (remember pawns have an energy between 1 --
+ 4, kings have an energy of only 1 -- 2). The energy of a piece might
+ change when the piece moves to new field.
+\item Pieces can move in straight lines (up, down, left, right), or in
+ L-shape moves, meaning a move can make a single
+ 90$^{\circ}$-turn. S-shape moves with more than one turn are not
+ allowed. Also in a single move a piece cannot go forward and then
+ go backward---for example with energy 3 you cannot move 2 fields up and
+ then 1 field down. A piece can never move diagonally.
+\item A piece cannot jump over another piece and cannot stack up on top of your own pieces.
+ But you can capture an opponent's piece if you move to an occupied field. A captured
+ piece is removed from the board.
+\end{itemize}
\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{M4a}, \texttt{M4b}, \texttt{M4c} and \texttt{M4d}.
-Since some of the calls are time sensitive, I included some timing
-information. For example
+Like in chess, checkmate is determined when the king of a player cannot
+move anymore to a field that is not attacked, or a player cannot
+capture or block the attacking piece, or the king is the only
+piece left for a player. A board that is checkmate is the following:
+
+\begin{center}
+\begin{tikzpicture}[scale=0.5,every node/.style={scale=0.5}]
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+ \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}
+ \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+% redpieces
+\pic[fill=red] at (4,2) {king={2}};
+\pic[fill=red] at (6,1) {piece={3}};
+\pic[fill=red] at (4,4) {piece={4}};
+\pic[fill=red] at (5,3) {piece={4}};
+% white pieces
+\pic[fill=white] at (7,1) {king={2}};
+\pic[fill=white] at (8,5) {piece={2}};
+\pic[fill=white] at (4,1) {piece={2}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\end{center}
+
+\noindent
+The reason for the checkmate is that the white king on field (7, 1) is
+attacked by the red pawn on \mbox{(5, 3)}. There is nowhere for the
+white king to go, and no white pawn can be moved into the way of this
+red pawn and white can also not capture it. When determining a possible
+move, you need to be careful with pieces that might be in the
+way. Consider the following position:
-\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
-$ scala -cp knight1.jar
-scala> M4a.enum_tours(5, List((0, 0))).length
-Time needed: 1.722 secs.
-res0: Int = 304
-
-scala> M4a.print_board(8, M4a.first_tour(8, List((0, 0))).get)
-Time needed: 15.411 secs.
+\begin{equation}\label{moves}
+\begin{tikzpicture}[scale=0.5,every node/.style={scale=0.5}]
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+ \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}
+ \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+% redpieces
+\fill[blue!50] (0,2) rectangle ++ (1,1);
+\fill[blue!50] (1,1) rectangle ++ (1,1);
+\fill[blue!50] (0,4) rectangle ++ (1,1);
+\fill[blue!50] (1,5) rectangle ++ (1,1);
+\fill[blue!50] (2,6) rectangle ++ (1,1);
+%%\fill[blue!50] (3,7) rectangle ++ (1,1);
+\fill[blue!50] (4,6) rectangle ++ (1,1);
+\fill[blue!50] (5,5) rectangle ++ (1,1);
+\fill[blue!50] (6,4) rectangle ++ (1,1);
+\fill[blue!50] (6,2) rectangle ++ (1,1);
+\fill[blue!50] (7,3) rectangle ++ (1,1);
+\fill[blue!50] (4,0) rectangle ++ (1,1);
+\fill[blue!50] (2,0) rectangle ++ (1,1);
+\pic[fill=red] at (4,4) {piece={4}};
+\pic[fill=red] at (4,8) {piece={4}};
+\pic[fill=white] at (2,5) {piece={3}};
+\pic[fill=white] at (4,3) {piece={2}};
+\pic[fill=white] at (6,3) {piece={1}};
+\pic[fill=white] at (8,4) {piece={1}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\end{equation}
- 51 46 55 44 53 4 21 12
- 56 43 52 3 22 13 24 5
- 47 50 45 54 25 20 11 14
- 42 57 2 49 40 23 6 19
- 35 48 41 26 61 10 15 28
- 58 1 36 39 32 27 18 7
- 37 34 31 60 9 62 29 16
- 0 59 38 33 30 17 8 63
-\end{lstlisting}%$
+\noindent
+The red piece in the centre on field (4, 4) can move to all the blue fields.
+In particular it can move to (2, 6), because it can move 2 fields up
+and 2 fields to the left---it cannot reach this field by moving two
+fields to the left and then two up, because jumping over the white
+piece at (2, 5) is not allowed. Similarly, the field at (6, 2) is
+unreachable for the red piece because of the two white pieces at (4,
+3) and (6, 3) are in the way and no S-shape move is allowed in
+Shogun. The red piece on (4, 4) cannot move to the field (4, 8) at the
+top, because a red piece is already there; but it can move to (8, 4)
+and capture the white piece there. The moral is we always have to
+explore all possible ways in order to determine whether a piece can be
+moved to a field or not: in general there might be several ways and some of
+them might be blocked.
\subsection*{Hints}
+Useful functions about pieces and boards are defined at the beginning
+of the template file. The function \texttt{.map} applies a function to
+each element of a list or set; \texttt{.flatMap} works like
+\texttt{map} followed by a \texttt{.flatten}---this is useful if a
+function returns a set of sets, which need to be ``unioned up''. Sets
+can be partitioned according to a predicate with the function
+\texttt{.partition}. For example
+
+\begin{lstlisting}
+val (even, odd) = Set(1,2,3,4,5).partition(_ % 2 == 0)
+// --> even = Set(2,4)
+// odd = Set(1,3,5)
+\end{lstlisting}
+
\noindent
-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;
-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
+The function \texttt{.toList} transforms a set into a list. The function
+\texttt{.count} counts elements according to a predicate. For example
+\begin{lstlisting}
+Set(1,2,3,4,5).count(_ % 2 == 0)
+// --> 2
+\end{lstlisting}
-%%\newpage
+%% \newpage
\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
-incredibly large search space---finding a tour is like finding a
-needle in a haystack. In the first task we want to see how far we get
-with exhaustively exploring the complete search space for small
-chessboards.\medskip
+You are asked to implement how pieces can move on a Shogun board. Let
+us first fix the basic datastructures for the implementation. A
+\emph{position} (or field) is a pair of integers, like $(3, 2)$. The
+board's dimension is always 8 $\times$ 8. A \emph{colour} is either
+red (\texttt{Red}) or white (\texttt{Wht}). A \emph{piece} is either
+a pawn or a king, and has a position, a colour and an energy (an
+integer). In the template file there are functions \texttt{incx},
+\texttt{decx}, \texttt{incy} and \texttt{decy} for incrementing and
+decrementing the x- and y-coordinates of positions of pieces.
-\noindent
-Let us first fix the basic datastructures for the implementation. The
-board dimension is an integer.
-A \emph{position} (or field) on the chessboard is
-a pair of integers, like $(0, 0)$. A \emph{path} is a list of
-positions. The first (or 0th move) in a path is the last element in
-this list; and the last move in the path is the first element. For
-example the path for the $5\times 5$ chessboard above is represented
-by
-
-\[
-\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,
- $\underbrace{\texttt{(2, 3)}}_{23}$, ...,
- $\underbrace{\texttt{(3, 2)}}_1$, $\underbrace{\texttt{(4, 4)}}_0$)}
-\]
-
-\noindent
-Suppose the dimension of a chessboard is $n$, then a path is a
-\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*{Task 1 (file knight1.scala)}
+A \emph{board} consists of a set of pieces. We always assume that we
+start with a consistent board and every move generates another
+consistent board. In this way we do not need to check, for example,
+whether pieces are stacked on top of each other or located outside the
+board, or have an energy outside the permitted range. There are
+functions \texttt{-} and \texttt{+} for removing, respectively adding,
+single pieces to a board. The function \texttt{occupied} takes a
+position and a board as arguments, and returns an \texttt{Option} of a
+piece when this position is occupied, otherwise \texttt{None}. The
+function \texttt{occupied\_by} returns the colour of a potential piece
+on that position. The function \texttt{is\_occupied} returns a boolean
+for whether a position is occupied or not; \texttt{print\_board} is a
+rough function that prints out a board on the console. This function
+is meant for testing purposes.
\begin{itemize}
-\item[(1)] Implement an \texttt{is\_legal} function that takes a
- dimension, a path and a position as arguments and tests whether the
- position is inside the board and not yet element in the
- path. \hfill[1 Mark]
+\item[(1)] You need to calculate all possible moves for a piece on a Shogun board. In order to
+ make sure no piece moves forwards and backwards at the same time,
+ and also exclude all S-shape moves, the data-structure \texttt{Move}
+ is introduced. A \texttt{Move} encodes all simple moves (up, down, left,
+ right) and L-shape moves (first right, then up and so on). This is defined
+ as follows:
+
+{\small\begin{lstlisting}
+abstract class Move
+case object U extends Move // up
+case object D extends Move // down
+case object R extends Move // right
+case object L extends Move // left
+case object RU extends Move // ...
+case object LU extends Move
+case object RD extends Move
+case object LD extends Move
+case object UR extends Move
+case object UL extends Move
+case object DR extends Move
+case object DL extends Move
+\end{lstlisting}}
-\item[(2)] Implement a \texttt{legal\_moves} function that calculates for a
- position all legal onward moves. If the onward moves are
- placed on a circle, you should produce them starting from
- ``12-o'clock'' following in clockwise order. For example on an
- $8\times 8$ board for a knight at position $(2, 2)$ and otherwise
- empty board, the legal-moves function should produce the onward
- positions in this order:
+You need to implement an \texttt{eval} function that takes a piece
+\texttt{pc}, a move \texttt{m}, an energy \texttt{en} and a board
+\texttt{b} as arguments. The idea is to recursively calculate all
+fields that can be reached by the move \texttt{m} (there might be more than
+one). The energy acts as a counter and decreases in each recursive
+call until 0 is reached (the final field). The function \texttt{eval} for a piece \texttt{pc}
+should behave as follows:
- \begin{center}
- \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}
- \end{center}
-
- If the board is not empty, then maybe some of the moves need to be
- filtered out from this list. For a knight on field $(7, 7)$ and an
- empty board, the legal moves are
+\begin{itemize}
+\item If the position of a piece is outside the board, then no field can be reached (represented by
+ the empty set \texttt{Set()}).
+\item If the energy is 0 and the position of the piece is \textit{not} occupied, then the field can be reached
+ and the set \texttt{Set(pc)} is returned whereby \texttt{pc} is the piece given as argument.
+\item If the energy is 0 and the position of the piece \textit{is} occupied, but occupied by a piece
+ of the opposite colour, then also the set \texttt{Set(pc)} is returned.
+\item In case the energy is > 0 and the position of the piece
+ \texttt{pc} is occupied, then this move is blocked and the set
+ \texttt{Set()} is returned.
+\item In all other cases we have to analyse the move
+ \texttt{m}. First, the simple moves (that is \texttt{U}, \texttt{D},
+ \texttt{L} and \texttt{R}) we only have to increment / decrement the
+ x- or y-position of the piece, decrease the energy and call eval
+ recursively with the updated arguments. For example for \texttt{U}
+ you need to increase the y-coordinate:
\begin{center}
- \texttt{List((6,5), (5,6))}
+ \texttt{U} $\quad\Rightarrow\quad$ new arguments: \texttt{incy(pc)}, \texttt{U}, energy - 1, same board
\end{center}
- \mbox{}\hfill[1 Mark]
-
-\item[(3)] Implement two recursive functions (\texttt{count\_tours} and
- \texttt{enum\_tours}). They each take a dimension and a path as
- arguments. They exhaustively search for tours starting
- from the given path. The first function counts all possible
- 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[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
-\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
- produces an optional path. So $f$'s type is \texttt{Pos =>
- Option[Path]}. The idea behind the \texttt{first}-function is as follows:
-
- \[
- \begin{array}{lcl}
- \textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\
- \textit{first}(x\!::\!xs, f) & \dn & \begin{cases}
- f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
- \textit{first}(xs, f) & \textit{otherwise}\\
- \end{cases}
- \end{array}
- \]
+ The move \texttt{U} here acts like a ``mode'', meaning if you move
+ up, you can only move up; the mode never changes. Similarly for the other simple moves: if
+ you move right, you can only move right and so on. In this way it is
+ prevented to go first to the right, and then change direction in order to go
+ left (same with up and down).
+
+ For the L-shape moves (\texttt{RU}, \texttt{LU}, \texttt{RD} and so on) you need to calculate two
+ sets of reachable fields. Say we analyse \texttt{RU}, then we first have to calculate all fields
+ reachable by moving to the right; then we have to calculate all moves by changing the mode to \texttt{U}.
+ That means there are two recursive calls to \texttt{eval}:
- \noindent That is, we want to find the first position where the
- result of $f$ is not \texttt{None}, if there is one. Note that
- `inside' \texttt{first}, you do not (need to) know anything about
- the argument $f$ except its type, namely \texttt{Pos =>
- Option[Path]}. If you want to find out what the result of $f$ is
- on a particular argument, say $x$, you can just write $f(x)$.
- There is one additional point however you should
- take into account when implementing \texttt{first}: you will need to
- calculate what the result of $f(x)$ is; your code should do this
- only \textbf{once} and for as \textbf{few} elements in the list as
- possible! Do not calculate $f(x)$ for all elements and then see which
- is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]
-
-\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]
+ \begin{center}
+ \begin{tabular}{@{}lll@{}}
+ \texttt{RU} & $\Rightarrow$ & new args for call 1: \texttt{incx(pc)}, \texttt{RU}, energy - 1, same board\\
+ & & new args for call 2: \texttt{pc}, \texttt{U}, same energy, same board
+ \end{tabular}
+ \end{center}
+
+ In each case we receive some new piece(s) on reachable fields and therefore we return the set
+ containing all these fields. Similarly in the other cases.
\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)}
+For example on the left board below, \texttt{eval} is called with the white
+piece in the centre and the move \texttt{RU} generates then a set of
+new pieces corresponding to the blue fileds. The difference on the
+right board is that \texttt{eval} is called with a red piece and therefore the
+field (4, 8) is not reachable anymore because it is already occupied by
+another red piece.
-\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
-Rule} that can speed up finding a tour. This heuristics states that a
-knight is moved so that it always proceeds to the field from which the
-knight will have the \underline{fewest} onward moves. For example for
-a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible
-onward moves, namely 2.
+\begin{center}
+\begin{tabular}{cc}
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+ \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}
+ \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+\fill[blue!50] (5,5) rectangle ++ (1,1);
+\fill[blue!50] (3,7) rectangle ++ (1,1);
+\fill[blue!50] (4,6) rectangle ++ (1,1);
+\fill[blue!50] (6,4) rectangle ++ (1,1);
+\fill[blue!50] (7,3) rectangle ++ (1,1);
+
+% black pieces
+\foreach\x/\y/\e in {1/1/1,2/1/3,3/1/2,4/1/3,6/1/3,7/1/1,8/1/2}
+ \pic[fill=white] at (\x,\y) {piece={\e}};
+% white pieces
+\foreach\x/\y/\e in {1/8/4,2/8/2,3/8/4,5/8/4,6/8/2,7/8/3,8/8/1}
+ \pic[fill=red] at (\x,\y) {piece={\e}};
+\pic[fill=white] at (5.0,1.0) {king={1}};
+\pic[fill=red] at (4.0,8.0) {king={2}};
-\chessboard[maxfield=g7,
- pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
- text = \small 3, markfield=Z5,
- text = \small 7, markfield=b5,
- text = \small 7, markfield=c4,
- text = \small 7, markfield=c2,
- text = \small 5, markfield=b1,
- text = \small 2, markfield=Z1,
- setpieces={Na3}]
+\pic[fill=white] at (4,4) {piece={4}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+&
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+ \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}
+ \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+\fill[blue!50] (5,5) rectangle ++ (1,1);
+\fill[blue!50] (4,6) rectangle ++ (1,1);
+\fill[blue!50] (6,4) rectangle ++ (1,1);
+\fill[blue!50] (7,3) rectangle ++ (1,1);
-\noindent
-Warnsdorf's Rule states that the moves on the board above should be
-tried in the order
+% black pieces
+\foreach\x/\y/\e in {1/1/1,2/1/3,3/1/2,4/1/3,6/1/3,7/1/1,8/1/2}
+ \pic[fill=white] at (\x,\y) {piece={\e}};
+% white pieces
+\foreach\x/\y/\e in {1/8/4,2/8/2,3/8/4,5/8/4,6/8/2,7/8/3,8/8/1}
+ \pic[fill=red] at (\x,\y) {piece={\e}};
+\pic[fill=white] at (5.0,1.0) {king={1}};
+\pic[fill=red] at (4.0,8.0) {king={2}};
-\[
-(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)
-\]
-
-\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.
+\pic[fill=red] at (4,4) {piece={4}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\\[-5mm]
+\end{tabular}
+\end{center}\hfill[3 Marks]
-\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
- should come first (in order to be tried out first). \hfill[1 Mark]
-
-\item[(7)] Implement a \texttt{first\_closed\_tour\_heuristics}
- function that searches for a single
- \textbf{closed} tour on a $6\times 6$ board. It should try out
- onward moves according to
- the \texttt{ordered\_moves} function from (6). It is more likely to find
- a solution when started in the middle of the board (that is
- position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]
+\item[(2)] Implement an \texttt{all\_moves} function that calculates for a
+ piece and a board, \textit{all} pieces on legal onward positions. For this
+ you have to call \texttt{eval} for all possible moves \texttt{m} (that is \texttt{U},
+ \texttt{D}, \ldots, \texttt{DL}). An example for all moves for the red piece on (4, 4) are
+ shown in \eqref{moves} on page \pageref{moves}.\\
+ \mbox{}\hfill[1 Mark]
+
+\item[(3)] Implement a function \texttt{attacked} that takes a colour and a board
+ and calculates all pieces of the opposite side that are attacked. For example
+ below on the left are all the attacked pieces by red, and on the right for white:
-\item[(8)] Implement a \texttt{first\_tour\_heuristics} function
- for boards up to
- $30\times 30$. It is the same function as in (7) but searches for
- tours (not just closed tours). It might be called with any field on the
- board as starting field.\\
- %You have to be careful to write a
- %tail-recursive function of the \texttt{first\_tour\_heuristics} function
- %otherwise you will get problems with stack-overflows.\\
- \mbox{}\hfill[1 Mark]
-\end{itemize}
+\begin{center}
+\begin{tabular}{cc}
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+ \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}
+ \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+\fill[blue!50] (7,3) rectangle ++ (1,1);
+\fill[blue!50] (6,0) rectangle ++ (1,1);
+
+
+% black pieces
+\foreach\x/\y/\e in {6/1/3,4/4/4,5/3/4,6/5/3}
+ \pic[fill=red] at (\x,\y) {piece={\e}};
+% white pieces
+\foreach\x/\y/\e in {8/4/2,4/1/2,8/7/3}
+ \pic[fill=white] at (\x,\y) {piece={\e}};
+
+\pic[fill=red] at (4,2) {king={2}};
+\pic[fill=white] at (7,1) {king={2}};
-\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
- by starting from field $(0, 0)$. You have to be careful to
- write a tail-recursive function otherwise you will get problems
- with stack-overflows. Please observe the requirements about
- the submissions: no tricks involving \textbf{.par}.\medskip
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+&
+\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]
+% chessboard
+\draw[very thick,gray] (0,0) rectangle (8,8);
+\foreach\x in {0,...,7}\foreach\y in {7,...,0}
+{
+ \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}
+ \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);
+}
+\fill[blue!50] (5,0) rectangle ++ (1,1);
+
+
+% black pieces
+\foreach\x/\y/\e in {6/1/3,4/4/4,5/3/4,6/5/3}
+ \pic[fill=red] at (\x,\y) {piece={\e}};
+% white pieces
+\foreach\x/\y/\e in {8/4/2,4/1/2,8/7/3}
+ \pic[fill=white] at (\x,\y) {piece={\e}};
- The timelimit of 30 seconds is with respect to the laptop on which the
- marking will happen. You can roughly estimate how well your
- implementation performs by running \texttt{knight3.jar} on your
- computer. For example the reference implementation shows
- on my laptop:
-
- \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
-$ scala -cp knight3.jar
-
-scala> M4c.tour_on_mega_board(70, List((0, 0)))
-Time needed: 9.484 secs.
-...<<long_list>>...
-\end{lstlisting}%$
+\pic[fill=red] at (4,2) {king={2}};
+\pic[fill=white] at (7,1) {king={2}};
+% numbers
+\foreach\x in {1,...,8}
+{\draw (\x - 0.5, -0.4) node {\x};
+}
+\foreach\y in {1,...,8}
+{\draw (-0.4, \y - 0.6, -0.4) node {\y};
+}
+\end{tikzpicture}
+\\[-5mm]
+\end{tabular}
+\end{center}\mbox{}\hfill[1 Mark]
+
+\item[(4)] Implement a function \texttt{attackedN} that takes a piece and a board
+ and calculates the number of times this pieces is attacked by pieces of the opposite colour.
+ For example the piece on field (8, 4) above is attacked by 3 red pieces, and
+ the piece on (6, 1) by 1 white piece.
+ \\
+ \mbox{}\hfill[1 Mark]
+
+\item[(5)] Implement a function \texttt{protectedN} that takes a piece and a board
+ and calculates the number of times this pieces is protected by pieces of the same colour.
+ For example the piece on field (8, 4) above is protected by 1 white pieces (the one on (8, 7)),
+ and the piece on (5, 3) is protected by three red pieces ((6, 1), (4, 2), and (6, 5)).
+ \\
\mbox{}\hfill[1 Mark]
\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}
-
-
-
\end{document}
%%% Local Variables:
Binary file cws/main_cw05.pdf has changed
--- a/cws/main_cw05.tex Thu Nov 02 23:34:53 2023 +0000
+++ b/cws/main_cw05.tex Sat Nov 04 18:53:37 2023 +0000
@@ -43,14 +43,14 @@
As usual, this Scala assignment comes with a reference implementation in
form of two \texttt{jar}-files. You can download them from KEATS. They
allow 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 bf.jar}
+can call \texttt{scala-cli} on the command line with the option \texttt{--extra-jars bf.jar}
and then query any function from the \texttt{bf.scala} template file.
You have to prefix the calls with \texttt{M5a} and \texttt{M5b},
respectively. For example
\begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
-$ scala -cp bf.jar
+$ scala-cli --extra-jars bf.jar
scala> import M5a._
scala> run(load_bff("sierpinski.bf")) ; ()
*
Binary file handouts/pep-ho.pdf has changed
--- a/handouts/pep-ho.tex Thu Nov 02 23:34:53 2023 +0000
+++ b/handouts/pep-ho.tex Sat Nov 04 18:53:37 2023 +0000
@@ -180,10 +180,12 @@
in advance!\bigskip
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black]
- I will be using the \textbf{\texttt{scala-cli}} REPL for scala, rather
+ I will be using the \textbf{\texttt{scala-cli}} REPL for Scala 3, rather
than the ``plain'' Scala REPL. This is a batteries included version of
- Scala and is easier to use. In fact \texttt{scala-cli} will replace
- the ``plain'' Scala REPL in future versions. So why not using it now?
+ Scala 3 and is easier to use and install. In fact
+ \texttt{scala-cli} is designated to replace
+ the ``plain'' Scala REPL in future versions of Scala.
+ So why not using it now?
It can be downloaded from:
\begin{center}
@@ -193,13 +195,13 @@
\noindent
-If you are interested, there are also experimental backend of Scala
+If you are interested, there are also experimental backends of Scala
for generating JavaScript code (\url{https://www.scala-js.org}), and
there is work under way to have a native Scala compiler generating
X86-code (\url{http://www.scala-native.org}). There are also some
-tricks you can play with Scala programms running as native
+tricks for Scala programs to run as a native
GraalVM~\hr{https://scala-cli.virtuslab.org/docs/cookbooks/native-images/}
-images. Though be warned these backends are still rather beta or even
+image. Though be warned these backends are still rather beta or even
alpha.
\subsection*{VS Code and Scala}
@@ -241,7 +243,7 @@
\end{boxedminipage}
\end{figure}
-Actually \alert last year I switched to VS Codium, which is VS Code
+Actually \alert last year I switched to VS Codium as IDE for writing Scala programs. VS Codium is VS Code
minus all the telemetry that is normally sent to Microsoft. Apart from
the telemetry (and Copilot, which you are not supposed to use anyway),
it works pretty much the same way as the original but is driven by a
@@ -254,7 +256,7 @@
What I like most about VS Code/Codium is that it provides easy access
-to the Scala REPL. But if you prefer another editor for coding, it is
+to any Scala REPL. But if you prefer another editor for coding, it is
also painless to work with Scala completely on the command line (as
you might have done with \texttt{g++} in the earlier part of PEP). For
the lazybones among us, there are even online editors and environments
@@ -505,13 +507,13 @@
\subsection*{The Very Basics}
-Let us get back to Scala: One advantage of Scala over Java is that it
-includes an interpreter (a REPL, or
+Let us get back to Scala and \texttt{scala-cli}: One advantage of
+Scala over Java is that it includes an interpreter (a REPL, or
\underline{R}ead-\underline{E}val-\underline{P}rint-\underline{L}oop)
with which you can run and test small code snippets without the need
of a compiler. This helps a lot with interactively developing
programs. It is my preferred way of writing small Scala programs. Once
-you installed Scala, you can start the interpreter by typing on the
+you installed \texttt{scala-cli}, you can start the interpreter by typing on the
command line:
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
@@ -522,11 +524,14 @@
scala>
\end{lstlisting}%$
-\noindent The precise response may vary depending
-on the version and platform where you installed Scala. Make sure
-\texttt{scala-cli} uses Scala version 3. At the Scala
-prompt you can type things like \code{2 + 3}\;\keys{Ret} and
-the output will be
+\noindent The precise response may vary depending on the version and
+platform where you installed \texttt{scala-cli}. Make sure however that
+\texttt{scala-cli} uses Scala version 3---you can find the version
+number in the welcome message. Also note that at the first time
+\texttt{scala-cli} runs, it might download various components, for
+example the Scala compiler, Scala runtimes etc. Once
+\texttt{scala-cli} is up and running, you can type at the prompt
+expressions like \code{2 + 3}\;\keys{Ret} and the output will be
\begin{lstlisting}[numbers=none,language={}]
scala> 2 + 3
--- a/main_templates2/README.md Thu Nov 02 23:34:53 2023 +0000
+++ b/main_templates2/README.md Sat Nov 04 18:53:37 2023 +0000
@@ -1,6 +1,6 @@
-# assignment2022scala - Main 2
+# assignment2023scala - Main 2
-* deadline: 19 January, 5pm
+* deadline: 4 January, 4pm
* [coursework description](https://nms.kcl.ac.uk/christian.urban/main_cw02.pdf)
* reference jar:
[wordle.jar](https://nms.kcl.ac.uk/christian.urban/wordle.jar)
\ No newline at end of file
--- a/main_templates3/README.md Thu Nov 02 23:34:53 2023 +0000
+++ b/main_templates3/README.md Sat Nov 04 18:53:37 2023 +0000
@@ -1,6 +1,6 @@
-# assignment2022scala - Main 3
+# assignment2023scala - Main 3
-* deadline: 19 January, 5pm
+* deadline: 4 January, 4pm
* [coursework description](https://nms.kcl.ac.uk/christian.urban/main_cw03.pdf)
* reference jar:
[re.jar](https://nms.kcl.ac.uk/christian.urban/re.jar)
\ No newline at end of file
Binary file main_templates4-old/knight1.jar has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_templates4-old/knight1.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,94 @@
+// Main Part 4 about finding Knight's tours
+//==========================================
+
+
+object M4a {
+
+// If you need any auxiliary functions, feel free to
+// implement them, but do not make any changes to the
+// templates below. Also have a look whether the functions
+// at the end of the file are of any help.
+
+type Pos = (Int, Int) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+// ADD YOUR CODE BELOW
+//======================
+
+
+
+//(1)
+def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ???
+
+
+//(2)
+def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ???
+
+
+//some testcases
+//
+//assert(legal_moves(8, Nil, (2,2)) ==
+// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
+// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+
+
+// (3)
+def count_tours(dim: Int, path: Path) : Int = ???
+
+def enum_tours(dim: Int, path: Path) : List[Path] = ???
+
+// (4)
+def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ???
+
+
+// testcases
+//
+//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
+//
+//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0)))
+//first(List((1, 0),(2, 0),(3, 0)), foo) // None
+
+
+//(5)
+def first_tour(dim: Int, path: Path) : Option[Path] = ???
+
+
+
+/* Helper functions
+
+
+// for measuring time
+def time_needed[T](code: => T) : T = {
+ val start = System.nanoTime()
+ val result = code
+ val end = System.nanoTime()
+ println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
+ result
+}
+
+// can be called for example with
+//
+// time_needed(count_tours(dim, List((0, 0))))
+//
+// in order to print out the time that is needed for
+// running count_tours
+
+
+// for printing a board
+def print_board(dim: Int, path: Path): Unit = {
+ println()
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
+ }
+ println()
+ }
+}
+
+
+*/
+
+}
Binary file main_templates4-old/knight2.jar has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_templates4-old/knight2.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,35 @@
+// Core Part about finding a single tour for a board using the
+// Warnsdorf Rule
+//==============================================================
+
+object M4b {
+
+// !!! Copy any function you need from file knight1.scala !!!
+//
+// If you need any auxiliary functions, feel free to
+// implement them, but do not make any changes to the
+// templates below.
+
+type Pos = (Int, Int) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+// ADD YOUR CODE BELOW
+//======================
+
+//(6)
+def ordered_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ???
+
+
+//(7)
+def first_closed_tour_heuristics(dim: Int, path: Path) : Option[Path] = ???
+
+
+//(8) Same as (7) but searches for *non-closed* tours. This
+// version of the function will be called with dimensions of
+// up to 30 * 30.
+
+def first_tour_heuristics(dim: Int, path: Path) : Option[Path] = ???
+
+
+
+}
Binary file main_templates4-old/knight3.jar has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_templates4-old/knight3.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,24 @@
+// Finding a single tour on a "mega" board
+//=========================================
+
+object M4c {
+
+// !!! Copy any function you need from file knight1.scala !!!
+// !!! or knight2.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) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+// ADD YOUR CODE BELOW
+//======================
+
+
+//(9)
+def tour_on_mega_board(dim: Int, path: Path) : Option[Path] = ???
+
+}
Binary file main_templates4-old/knight4.jar has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_templates4-old/knight4.scala Sat Nov 04 18:53:37 2023 +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_templates4/README.md Thu Nov 02 23:34:53 2023 +0000
+++ b/main_templates4/README.md Sat Nov 04 18:53:37 2023 +0000
@@ -1,9 +1,5 @@
-# assignment2022scala - Main 4
+# assignment2023scala - Main 4
-* deadline: 19 January, 5pm
+* deadline: 4 January, 4pm
* [coursework description](https://nms.kcl.ac.uk/christian.urban/main_cw04.pdf)
-* reference jar:
- [knight1.jar](https://nms.kcl.ac.uk/christian.urban/knight1.jar),
- [knight2.jar](https://nms.kcl.ac.uk/christian.urban/knight2.jar),
- [knight3.jar](https://nms.kcl.ac.uk/christian.urban/knight3.jar),
- [knight4.jar](https://nms.kcl.ac.uk/christian.urban/knight4.jar)
\ No newline at end of file
+* reference jar: [shogun.jar](https://nms.kcl.ac.uk/christian.urban/shogun.jar)
Binary file main_templates4/knight1.jar has changed
--- a/main_templates4/knight1.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,94 +0,0 @@
-// Main Part 4 about finding Knight's tours
-//==========================================
-
-
-object M4a {
-
-// If you need any auxiliary functions, feel free to
-// implement them, but do not make any changes to the
-// templates below. Also have a look whether the functions
-// at the end of the file are of any help.
-
-type Pos = (Int, Int) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-// ADD YOUR CODE BELOW
-//======================
-
-
-
-//(1)
-def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ???
-
-
-//(2)
-def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ???
-
-
-//some testcases
-//
-//assert(legal_moves(8, Nil, (2,2)) ==
-// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
-// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-
-
-// (3)
-def count_tours(dim: Int, path: Path) : Int = ???
-
-def enum_tours(dim: Int, path: Path) : List[Path] = ???
-
-// (4)
-def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ???
-
-
-// testcases
-//
-//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
-//
-//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0)))
-//first(List((1, 0),(2, 0),(3, 0)), foo) // None
-
-
-//(5)
-def first_tour(dim: Int, path: Path) : Option[Path] = ???
-
-
-
-/* Helper functions
-
-
-// for measuring time
-def time_needed[T](code: => T) : T = {
- val start = System.nanoTime()
- val result = code
- val end = System.nanoTime()
- println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
- result
-}
-
-// can be called for example with
-//
-// time_needed(count_tours(dim, List((0, 0))))
-//
-// in order to print out the time that is needed for
-// running count_tours
-
-
-// for printing a board
-def print_board(dim: Int, path: Path): Unit = {
- println()
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
- }
- println()
- }
-}
-
-
-*/
-
-}
Binary file main_templates4/knight2.jar has changed
--- a/main_templates4/knight2.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,35 +0,0 @@
-// Core Part about finding a single tour for a board using the
-// Warnsdorf Rule
-//==============================================================
-
-object M4b {
-
-// !!! Copy any function you need from file knight1.scala !!!
-//
-// If you need any auxiliary functions, feel free to
-// implement them, but do not make any changes to the
-// templates below.
-
-type Pos = (Int, Int) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-// ADD YOUR CODE BELOW
-//======================
-
-//(6)
-def ordered_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ???
-
-
-//(7)
-def first_closed_tour_heuristics(dim: Int, path: Path) : Option[Path] = ???
-
-
-//(8) Same as (7) but searches for *non-closed* tours. This
-// version of the function will be called with dimensions of
-// up to 30 * 30.
-
-def first_tour_heuristics(dim: Int, path: Path) : Option[Path] = ???
-
-
-
-}
Binary file main_templates4/knight3.jar has changed
--- a/main_templates4/knight3.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,24 +0,0 @@
-// Finding a single tour on a "mega" board
-//=========================================
-
-object M4c {
-
-// !!! Copy any function you need from file knight1.scala !!!
-// !!! or knight2.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) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-// ADD YOUR CODE BELOW
-//======================
-
-
-//(9)
-def tour_on_mega_board(dim: Int, path: Path) : Option[Path] = ???
-
-}
Binary file main_templates4/knight4.jar has changed
--- a/main_templates4/knight4.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,33 +0,0 @@
-// 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_templates5/README.md Thu Nov 02 23:34:53 2023 +0000
+++ b/main_templates5/README.md Sat Nov 04 18:53:37 2023 +0000
@@ -1,6 +1,6 @@
-# assignment2022scala - Main 5
+# assignment2023scala - Main 5
-* deadline: 19 January, 5pm
+* deadline: 4 January, 4pm
* [coursework description](https://nms.kcl.ac.uk/christian.urban/main_cw05.pdf)
* reference jar:
[bf.jar](https://nms.kcl.ac.uk/christian.urban/bf.jar),
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight1.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,171 @@
+// Part 1 about finding and counting Knight's tours
+//==================================================
+
+object M4a { // for preparing the jar
+
+type Pos = (Int, Int) // a position on a chessboard
+type Path = List[Pos] // a path...a list of positions
+
+
+// for measuring time in the JAR
+def time_needed[T](code: => T) : T = {
+ val start = System.nanoTime()
+ val result = code
+ val end = System.nanoTime()
+ println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
+ result
+}
+
+// for printing a board
+def print_board(dim: Int, path: Path): Unit = {
+ println()
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
+ }
+ println()
+ }
+}
+
+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)
+
+// testcases
+//assert(is_legal(8, Nil, (3, 4)) == true)
+//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
+//assert(is_legal(2, Nil, (0, 0)) == true)
+
+
+def add_pair(x: Pos, y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+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, _))
+
+
+
+// testcases
+//assert(legal_moves(8, Nil, (2,2)) ==
+// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
+// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+//assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0)))
+//assert(legal_moves(1, Nil, (0,0)) == List())
+//assert(legal_moves(2, Nil, (0,0)) == List())
+//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
+
+def tcount_tours(dim: Int, path: Path): Int = {
+ if (path.length == dim * dim) 1
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum
+}
+
+def count_tours(dim: Int, path: Path) =
+ time_needed(tcount_tours(dim: Int, path: Path))
+
+
+def tenum_tours(dim: Int, path: Path): List[Path] = {
+ if (path.length == dim * dim) List(path)
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten
+}
+
+def enum_tours(dim: Int, path: Path) =
+ time_needed(tenum_tours(dim: Int, path: Path))
+
+// test cases
+
+/*
+def count_all_tours(dim: Int) = {
+ for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
+}
+
+def enum_all_tours(dim: Int): List[Path] = {
+ (for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
+}
+
+
+println("Number of tours starting from (0, 0)")
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))
+}
+
+println("Number of tours starting from all fields")
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))
+}
+
+for (dim <- 1 to 5) {
+ val ts = enum_tours(dim, List((0, 0)))
+ println(s"${dim} x ${dim} ")
+ if (ts != Nil) {
+ print_board(dim, ts.head)
+ println(ts.head)
+ }
+}
+*/
+
+
+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)
+ }
+}
+
+// test cases
+//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
+//
+//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)
+//first(List((1, 0),(2, 0),(3, 0)), foo)
+
+
+def tfirst_tour(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim) Some(path)
+ else
+ first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path))
+}
+
+def first_tour(dim: Int, path: Path) =
+ time_needed(tfirst_tour(dim: Int, path: Path))
+
+
+/*
+for (dim <- 1 to 8) {
+ val t = first_tour(dim, List((0, 0)))
+ println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+// 15 secs for 8 x 8
+//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
+//??val ts1 = time_needed(0,first_tour(8, List((1, 1))).get)
+
+// no result for 4 x 4
+//val ts2 = time_needed(0, first_tour(4, List((0, 0))))
+
+// 0.3 secs for 6 x 6
+//val ts3 = time_needed(0, first_tour(6, List((0, 0))))
+
+// 15 secs for 8 x 8
+//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
+
+
+
+
+
+}
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight2.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,93 @@
+// Part 2 about finding a single tour using the Warnsdorf Rule
+//=============================================================
+
+object M4b { // for preparing the jar
+
+type Pos = (Int, Int)
+type Path = List[Pos]
+
+
+// for measuring time in the JAR
+def time_needed[T](code: => T) : T = {
+ val start = System.nanoTime()
+ val result = code
+ val end = System.nanoTime()
+ println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
+ result
+}
+
+
+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, _))
+
+def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
+
+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 tfirst_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path)
+ else
+ first(ordered_moves(dim, path, path.head), (x: Pos) => tfirst_closed_tour_heuristics(dim, x::path))
+}
+
+def first_closed_tour_heuristics(dim: Int, path: Path) =
+ time_needed(tfirst_closed_tour_heuristics(dim: Int, path: Path))
+
+def first_closed_tour_heuristic(dim: Int, path: Path) =
+ time_needed(tfirst_closed_tour_heuristics(dim: Int, path: Path))
+
+// heuristic cannot be used to search for closed tours on 7 x 7 an beyond
+//for (dim <- 1 to 6) {
+// val t = time_needed(0, first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))))
+// println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+//}
+
+
+def tfirst_tour_heuristics(dim: Int, path: Path): Option[Path] = {
+ if (path.length == dim * dim) Some(path)
+ else
+ first(ordered_moves(dim, path, path.head), (x: Pos) => tfirst_tour_heuristics(dim, x::path))
+}
+
+
+def first_tour_heuristics(dim: Int, path: Path) =
+ time_needed(tfirst_tour_heuristics(dim: Int, path: Path))
+
+def first_tour_heuristic(dim: Int, path: Path) =
+ time_needed(tfirst_tour_heuristics(dim: Int, path: Path))
+
+// will be called with boards up to 30 x 30
+
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight3.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,73 @@
+// Part 3 about finding a single tour using the Warnsdorf Rule
+//=============================================================
+
+object M4c { // for preparing the jar
+
+type Pos = (Int, Int)
+type Path = List[Pos]
+
+
+// for measuring time in the JAR
+def time_needed[T](code: => T) : T = {
+ val start = System.nanoTime()
+ val result = code
+ val end = System.nanoTime()
+ println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
+ result
+}
+
+
+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, _))
+
+def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
+
+import scala.annotation.tailrec
+
+@tailrec
+def tour_on_mega_board_aux(dim: Int, paths: List[Path]): Option[Path] = paths match {
+ case Nil => None
+ case (path::rest) =>
+ if (path.length == dim * dim) Some(path)
+ else tour_on_mega_board_aux(dim, ordered_moves(dim, path, path.head).map(_::path) ::: rest)
+}
+
+def ttour_on_mega_board(dim: Int, path: Path): Option[Path] =
+ tour_on_mega_board_aux(dim, List(path))
+
+
+def tour_on_mega_board(dim: Int, path: Path) =
+ time_needed(ttour_on_mega_board(dim: Int, path: Path))
+
+
+// testcases
+//print_board(70, tour_on_mega_board(70, List((0, 0))).get)
+
+
+
+}
+
+
+//val dim = 30 //75
+//M4c.print_board(dim, M4c.tour_on_mega_board(dim, List((0, 0))).get)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test1.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,6 @@
+import M4a._
+
+assert(is_legal(8, Nil, (3, 4)) == true)
+assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
+assert(is_legal(2, Nil, (0, 0)) == true)
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test10.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,29 @@
+import M4d._
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p =>
+ if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+val ts70 = one_tour_pred(8, List((0, 0)), 40, x => x._1 < 5).get
+assert(correct_urban(8)(ts70) == true)
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test2.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,11 @@
+
+import M4a._
+
+assert(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+assert(legal_moves(1, Nil, (0,0)) == List())
+assert(legal_moves(2, Nil, (0,0)) == List())
+assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test3.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,47 @@
+import M4a._
+
+//type Pos = (Int, Int) // a position on a chessboard
+//type Path = List[Pos] // a path...a list of positions
+
+def count_all_tours_urban(dim: Int) = {
+ for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
+}
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p => if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+assert(count_all_tours_urban(1) == List(1))
+assert(count_all_tours_urban(2) == List(0, 0, 0, 0))
+assert(count_all_tours_urban(3) == List(0, 0, 0, 0, 0, 0, 0, 0, 0))
+assert(count_all_tours_urban(4) == List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
+//assert(count_all_tours_urban(5) == List(304, 0, 56, 0, 304, 0, 56, 0, 56, 0, 56, 0, 64, 0, 56, 0, 56, 0, 56, 0, 304, 0, 56, 0, 304))
+
+val ts00_urban = enum_tours(5, List((0, 0)))
+assert(ts00_urban.map(correct_urban(5)).forall(_ == true) == true)
+assert(ts00_urban.length == 304)
+
+val ts01_urban = enum_tours(5, List((0, 1)))
+assert(ts01_urban.map(correct_urban(5)).forall(_ == true) == true)
+assert(ts01_urban.length == 0)
+
+val ts02_urban = enum_tours(5, List((0, 2)))
+assert(ts02_urban.map(correct_urban(5)).forall(_ == true) == true)
+assert(ts02_urban.length == 56)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test4.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,6 @@
+import M4a._
+
+val f_urban = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None
+
+assert(first(List((1,0),(2,0),(3,0),(4,0)), f_urban) == Some(List((4,0))))
+assert(first(List((1,0),(2,0),(3,0)), f_urban) == None)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test5.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,32 @@
+import M4a._
+
+
+//type Pos = (Int, Int) // a position on a chessboard
+//type Path = List[Pos] // a path...a list of positions
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p =>
+ if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+val ts1_urban = first_tour(6, List((0, 0))).get
+assert(correct_urban(6)(ts1_urban) == true)
+
+val ts2_urban = first_tour(4, List((0, 0)))
+assert(ts2_urban == None)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test6.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,19 @@
+import M4b._
+
+assert(ordered_moves(8, List((3,4), (3,2)), (1, 3)) == List((0,1), (0,5), (2,1), (2,5)))
+assert(ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2)))
+assert(ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1)))
+
+
+
+/*
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps
+
+lazy val f = Future {
+}
+
+Await.result(f, 120 second)
+*/
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test7.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,32 @@
+import M4b._
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p =>
+ if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+def correct_closed_urban(dim: Int)(p: Path) =
+ correct_urban(6)(p) && moves_urban(p.head).contains(p.last)
+
+
+val tsc = first_closed_tour_heuristics(6, List((3, 3))).get
+assert(correct_closed_urban(6)(tsc) == true)
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test8.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,33 @@
+import M4b._
+
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p =>
+ if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+val ts8 = first_tour_heuristics(8, List((0,0))).get
+assert(correct_urban(8)(ts8) == true)
+
+val ts30 = first_tour_heuristics(30, List((0,0))).get
+assert(correct_urban(30)(ts30) == true)
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4-old/knight_test9.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,29 @@
+import M4c._
+
+//type Pos = (Int, Int)
+//type Path = List[Pos]
+
+def add_pair_urban(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+def moves_urban(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
+
+def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves_urban(x).filter(is_legal_urban(dim, path))
+
+def correct_urban(dim: Int)(p: Path): Boolean = p match {
+ case Nil => true
+ case x::Nil => true
+ case x::y::p =>
+ if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
+}
+
+
+val ts70 = tour_on_mega_board(70, List((0,0))).get
+assert(correct_urban(70)(ts70) == true)
+
--- a/main_testing4/knight1.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,171 +0,0 @@
-// Part 1 about finding and counting Knight's tours
-//==================================================
-
-object M4a { // for preparing the jar
-
-type Pos = (Int, Int) // a position on a chessboard
-type Path = List[Pos] // a path...a list of positions
-
-
-// for measuring time in the JAR
-def time_needed[T](code: => T) : T = {
- val start = System.nanoTime()
- val result = code
- val end = System.nanoTime()
- println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
- result
-}
-
-// for printing a board
-def print_board(dim: Int, path: Path): Unit = {
- println()
- for (i <- 0 until dim) {
- for (j <- 0 until dim) {
- print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
- }
- println()
- }
-}
-
-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)
-
-// testcases
-//assert(is_legal(8, Nil, (3, 4)) == true)
-//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
-//assert(is_legal(2, Nil, (0, 0)) == true)
-
-
-def add_pair(x: Pos, y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-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, _))
-
-
-
-// testcases
-//assert(legal_moves(8, Nil, (2,2)) ==
-// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
-// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-//assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0)))
-//assert(legal_moves(1, Nil, (0,0)) == List())
-//assert(legal_moves(2, Nil, (0,0)) == List())
-//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
-
-
-def tcount_tours(dim: Int, path: Path): Int = {
- if (path.length == dim * dim) 1
- else
- (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum
-}
-
-def count_tours(dim: Int, path: Path) =
- time_needed(tcount_tours(dim: Int, path: Path))
-
-
-def tenum_tours(dim: Int, path: Path): List[Path] = {
- if (path.length == dim * dim) List(path)
- else
- (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten
-}
-
-def enum_tours(dim: Int, path: Path) =
- time_needed(tenum_tours(dim: Int, path: Path))
-
-// test cases
-
-/*
-def count_all_tours(dim: Int) = {
- for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
-}
-
-def enum_all_tours(dim: Int): List[Path] = {
- (for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
-}
-
-
-println("Number of tours starting from (0, 0)")
-
-for (dim <- 1 to 5) {
- println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))
-}
-
-println("Number of tours starting from all fields")
-
-for (dim <- 1 to 5) {
- println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))
-}
-
-for (dim <- 1 to 5) {
- val ts = enum_tours(dim, List((0, 0)))
- println(s"${dim} x ${dim} ")
- if (ts != Nil) {
- print_board(dim, ts.head)
- println(ts.head)
- }
-}
-*/
-
-
-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)
- }
-}
-
-// test cases
-//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
-//
-//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)
-//first(List((1, 0),(2, 0),(3, 0)), foo)
-
-
-def tfirst_tour(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim) Some(path)
- else
- first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path))
-}
-
-def first_tour(dim: Int, path: Path) =
- time_needed(tfirst_tour(dim: Int, path: Path))
-
-
-/*
-for (dim <- 1 to 8) {
- val t = first_tour(dim, List((0, 0)))
- println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-}
-*/
-
-// 15 secs for 8 x 8
-//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
-//??val ts1 = time_needed(0,first_tour(8, List((1, 1))).get)
-
-// no result for 4 x 4
-//val ts2 = time_needed(0, first_tour(4, List((0, 0))))
-
-// 0.3 secs for 6 x 6
-//val ts3 = time_needed(0, first_tour(6, List((0, 0))))
-
-// 15 secs for 8 x 8
-//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
-
-
-
-
-
-}
-
-
--- a/main_testing4/knight2.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,93 +0,0 @@
-// Part 2 about finding a single tour using the Warnsdorf Rule
-//=============================================================
-
-object M4b { // for preparing the jar
-
-type Pos = (Int, Int)
-type Path = List[Pos]
-
-
-// for measuring time in the JAR
-def time_needed[T](code: => T) : T = {
- val start = System.nanoTime()
- val result = code
- val end = System.nanoTime()
- println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
- result
-}
-
-
-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, _))
-
-def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
-
-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 tfirst_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path)
- else
- first(ordered_moves(dim, path, path.head), (x: Pos) => tfirst_closed_tour_heuristics(dim, x::path))
-}
-
-def first_closed_tour_heuristics(dim: Int, path: Path) =
- time_needed(tfirst_closed_tour_heuristics(dim: Int, path: Path))
-
-def first_closed_tour_heuristic(dim: Int, path: Path) =
- time_needed(tfirst_closed_tour_heuristics(dim: Int, path: Path))
-
-// heuristic cannot be used to search for closed tours on 7 x 7 an beyond
-//for (dim <- 1 to 6) {
-// val t = time_needed(0, first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))))
-// println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
-//}
-
-
-def tfirst_tour_heuristics(dim: Int, path: Path): Option[Path] = {
- if (path.length == dim * dim) Some(path)
- else
- first(ordered_moves(dim, path, path.head), (x: Pos) => tfirst_tour_heuristics(dim, x::path))
-}
-
-
-def first_tour_heuristics(dim: Int, path: Path) =
- time_needed(tfirst_tour_heuristics(dim: Int, path: Path))
-
-def first_tour_heuristic(dim: Int, path: Path) =
- time_needed(tfirst_tour_heuristics(dim: Int, path: Path))
-
-// will be called with boards up to 30 x 30
-
-
-}
--- a/main_testing4/knight3.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,73 +0,0 @@
-// Part 3 about finding a single tour using the Warnsdorf Rule
-//=============================================================
-
-object M4c { // for preparing the jar
-
-type Pos = (Int, Int)
-type Path = List[Pos]
-
-
-// for measuring time in the JAR
-def time_needed[T](code: => T) : T = {
- val start = System.nanoTime()
- val result = code
- val end = System.nanoTime()
- println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.")
- result
-}
-
-
-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, _))
-
-def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] =
- legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
-
-import scala.annotation.tailrec
-
-@tailrec
-def tour_on_mega_board_aux(dim: Int, paths: List[Path]): Option[Path] = paths match {
- case Nil => None
- case (path::rest) =>
- if (path.length == dim * dim) Some(path)
- else tour_on_mega_board_aux(dim, ordered_moves(dim, path, path.head).map(_::path) ::: rest)
-}
-
-def ttour_on_mega_board(dim: Int, path: Path): Option[Path] =
- tour_on_mega_board_aux(dim, List(path))
-
-
-def tour_on_mega_board(dim: Int, path: Path) =
- time_needed(ttour_on_mega_board(dim: Int, path: Path))
-
-
-// testcases
-//print_board(70, tour_on_mega_board(70, List((0, 0))).get)
-
-
-
-}
-
-
-//val dim = 30 //75
-//M4c.print_board(dim, M4c.tour_on_mega_board(dim, List((0, 0))).get)
--- a/main_testing4/knight_test.sh Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,355 +0,0 @@
-#!/bin/bash
-set -euo pipefail
-
-out=${1:-output}
-
-echo -e "" > $out
-
-echo -e "Below is the feedback for your submission of knight{1,2,3}.scala" >> $out
-echo -e "" >> $out
-#echo -e "!! Important: !!" >> $out
-#echo -e "Because of limitations with our testing infrastructure, we can only" >> $out
-#echo -e "let code run for 10 seconds and then have to kill it. This might" >> $out
-#echo -e "mean your code is correct, but still marked as Fail. Remember" >> $out
-#echo -e "you can test your code on your own machine and benchmark it" >> $out
-#echo -e "against the reference implementation." >> $out
-#echo -e "" >> $out
-
-
-# compilation tests
-
-function scala_compile {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out)
-}
-
-# functional tests
-
-function scala_assert {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null)
-}
-
-# purity test
-
-function scala_vars {
- (egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' c$out 2> /dev/null 1> /dev/null)
-}
-
-
-
-
-
-# compilation test
-
-
-echo -e "knight1.scala runs?" >> $out
-
-if (scala_compile knight1.scala)
-then
- echo -e " --> passed" >> $out
- tsts1=$(( 0 ))
- else
- echo -e " --> SCALA DID NOT RUN KNIGHT1.SCALA\n" >> $out
- tsts1=$(( 1 ))
-fi
-
-
-# knights1: purity test
-
-if [ $tsts1 -eq 0 ]
-then
- echo -e "knight1.scala does not contain vars, returns etc?" >> $out
-
- if (scala_vars knight1.scala)
- then
- echo -e " --> FAIL (make triple-sure your program conforms to the required format)" >> $out
- tsts1=$(( 1 ))
- else
- echo -e " --> passed" >> $out
- tsts1=$(( 0 ))
- fi
-fi
-
-
-### knight1 test
-
-if [ $tsts1 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " is_legal(8, Nil, (3, 4)) == true " >> $out
- echo -e " is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false " >> $out
- echo -e " is_legal(2, Nil, (0, 0)) == true" >> $out
-
- if (scala_assert "knight1.scala" "knight_test1.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-### knight2 test
-
-if [ $tsts1 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))" >> $out
- echo -e " legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))" >> $out
- echo -e " legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))" >> $out
- echo -e " legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))" >> $out
- echo -e " legal_moves(1, Nil, (0,0)) == Nil" >> $out
- echo -e " legal_moves(2, Nil, (0,0)) == Nil" >> $out
- echo -e " legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))" >> $out
-
- if (scala_assert "knight1.scala" "knight_test2.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-### knight3 test
-
-if [ $tsts1 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " count_tours from every position on the board" >> $out
- echo -e " dim = 1: 1" >> $out
- echo -e " 2: 0,0,0,0" >> $out
- echo -e " 3: 0,0,0,0,0,0,0,0,0" >> $out
- echo -e " 4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" >> $out
- #echo -e " 5: 304,0,56,0,304,0,56,0,56,0,56,0,64,0,56,0,56,0,56,0,304,0,56,0,304" >> $out
- echo -e " enum_tours(5, List((0,0)) ) == 304 and all correct?" >> $out
- echo -e " enum_tours(5, List((0,1)) ) == 0" >> $out
- echo -e " enum_tours(5, List((0,2)) ) == 56 and all correct?" >> $out
-
- if (scala_assert "knight1.scala" "knight_test3.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-### knight4 test
-
-if [ $tsts1 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " >> $out
- echo -e " first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0)))" >> $out
- echo -e " first(List((1,0),(2,0),(3,0)), f) == None" >> $out
-
- if (scala_assert "knight1.scala" "knight_test4.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-### knight5 test
-
-if [ $tsts1 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " is first_tour(6, List((0, 0))) ok? " >> $out
- echo -e " is first_tour(4, List((0, 0))) == None " >> $out
-
- if (scala_assert "knight1.scala" "knight_test5.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-echo -e "" >> $out
-echo -e "" >> $out
-
-
-# compilation test
-echo -e "knight2.scala runs?" >> $out
-
-if (scala_compile knight2.scala)
-then
- echo -e " --> passed" >> $out
- tsts2=$(( 0 ))
-else
- echo -e " --> SCALA DID NOT RUN KNIGHT2.SCALA\n" >> $out
- tsts2=$(( 1 ))
-fi
-
-
-# knights2: purity test
-#
-
-if [ $tsts2 -eq 0 ]
-then
- echo -e "knight2.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
-
- if (scala_vars knight2.scala)
- then
- echo -e " --> Fail (make triple-sure your program conforms to the required format)" >> $out
- tsts2=$(( 1 ))
- else
- echo -e " --> passed" >> $out
- tsts2=$(( 0 ))
- fi
-fi
-
-
-# ordered move test
-
-if [ $tsts2 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " ordered_moves(8, List((3,4), (3,2)), (1,3)) == List((0,1), (0,5), (2,1), (2,5))" >> $out
- echo -e " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" >> $out
- echo -e " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" >> $out
-
- if (scala_assert "knight2.scala" "knight_test6.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-# first-closed-tour test
-
-if [ $tsts2 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " first_closed_tour_heuristics(6, List((3,3))) found and correct?" >> $out
-
- if (scala_assert "knight2.scala" "knight_test7.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-
-if [ $tsts2 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " first_tour_heuristics(8, List((0,0))) found and correct?" >> $out
- echo -e " first_tour_heuristics(30, List((0,0))) found and correct?" >> $out
-
- if (scala_assert "knight2.scala" "knight_test8.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-echo -e "" >> $out
-echo -e "" >> $out
-
-
-
-# compilation test
-
-echo "knight3.scala runs?" >> $out
-
-if (scala_compile knight3.scala)
-then
- echo " --> passed" >> $out
- tsts3=$(( 0 ))
-else
- echo -e " --> SCALA DID NOT RUN KNIGHT3.SCALA\n" >> $out
- tsts3=$(( 1 ))
-fi
-
-# knights3: purity test
-#
-if [ $tsts3 -eq 0 ]
-then
- echo -e "knight3.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
-
- if (scala_vars knight3.scala)
- then
- echo " --> Fail (make triple-sure your program conforms to the required format)" >> $out
- tsts3=$(( 1 ))
- else
- echo " --> passed" >> $out
- tsts3=$(( 0 ))
- fi
-fi
-
-
-if [ $tsts3 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " tour_on_mega_board(70, List((0,0))) found and correct?" >> $out
- START=$(date +%s)
- if (scala_assert "knight3.scala" "knight_test9.scala")
- then
- END=$(date +%s)
- DIFF=$(( $END - $START ))
- echo " This test ran for $DIFF seconds." >> $out
- echo -e " --> success" >> $out
- else
- END=$(date +%s)
- DIFF=$(( $END - $START ))
- echo " This test ran for $DIFF seconds." >> $out
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
-
-
-echo -e "" >> $out
-echo -e "" >> $out
-
-
-
-# compilation test
-
-echo "knight4.scala runs?" >> $out
-
-if (scala_compile knight4.scala)
-then
- echo " --> passed" >> $out
- tsts4=$(( 0 ))
-else
- echo -e " --> SCALA DID NOT RUN KNIGHT4.SCALA\n" >> $out
- tsts4=$(( 1 ))
-fi
-
-# knights4: purity test
-#
-if [ $tsts4 -eq 0 ]
-then
- echo -e "knight4.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
-
- if (scala_vars knight4.scala)
- then
- echo " --> Fail (make triple-sure your program conforms to the required format)" >> $out
- tsts4=$(( 1 ))
- else
- echo " --> passed" >> $out
- tsts4=$(( 0 ))
- fi
-fi
-
-if [ $tsts4 -eq 0 ]
-then
- #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
- echo -e " one_tour_pred(8, List((0, 0)), 40, x => x._1 < 5) is ok?" >> $out
-
- if (scala_assert "knight4.scala" "knight_test10.scala")
- then
- echo -e " --> success" >> $out
- else
- echo -e " --> \n ONE TEST FAILED\n" >> $out
- fi
-fi
--- a/main_testing4/knight_test1.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,6 +0,0 @@
-import M4a._
-
-assert(is_legal(8, Nil, (3, 4)) == true)
-assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
-assert(is_legal(2, Nil, (0, 0)) == true)
-
--- a/main_testing4/knight_test10.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,29 +0,0 @@
-import M4d._
-
-//type Pos = (Int, Int)
-//type Path = List[Pos]
-
-def add_pair_urban(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves_urban(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
-
-def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
- moves_urban(x).filter(is_legal_urban(dim, path))
-
-def correct_urban(dim: Int)(p: Path): Boolean = p match {
- case Nil => true
- case x::Nil => true
- case x::y::p =>
- if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
-}
-
-
-val ts70 = one_tour_pred(8, List((0, 0)), 40, x => x._1 < 5).get
-assert(correct_urban(8)(ts70) == true)
-
--- a/main_testing4/knight_test2.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,11 +0,0 @@
-
-import M4a._
-
-assert(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-assert(legal_moves(1, Nil, (0,0)) == List())
-assert(legal_moves(2, Nil, (0,0)) == List())
-assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
-
--- a/main_testing4/knight_test3.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,47 +0,0 @@
-import M4a._
-
-//type Pos = (Int, Int) // a position on a chessboard
-//type Path = List[Pos] // a path...a list of positions
-
-def count_all_tours_urban(dim: Int) = {
- for (i <- (0 until dim).toList;
- j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
-}
-
-def add_pair_urban(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves_urban(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
-
-def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
- moves_urban(x).filter(is_legal_urban(dim, path))
-
-def correct_urban(dim: Int)(p: Path): Boolean = p match {
- case Nil => true
- case x::Nil => true
- case x::y::p => if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
-}
-
-
-assert(count_all_tours_urban(1) == List(1))
-assert(count_all_tours_urban(2) == List(0, 0, 0, 0))
-assert(count_all_tours_urban(3) == List(0, 0, 0, 0, 0, 0, 0, 0, 0))
-assert(count_all_tours_urban(4) == List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
-//assert(count_all_tours_urban(5) == List(304, 0, 56, 0, 304, 0, 56, 0, 56, 0, 56, 0, 64, 0, 56, 0, 56, 0, 56, 0, 304, 0, 56, 0, 304))
-
-val ts00_urban = enum_tours(5, List((0, 0)))
-assert(ts00_urban.map(correct_urban(5)).forall(_ == true) == true)
-assert(ts00_urban.length == 304)
-
-val ts01_urban = enum_tours(5, List((0, 1)))
-assert(ts01_urban.map(correct_urban(5)).forall(_ == true) == true)
-assert(ts01_urban.length == 0)
-
-val ts02_urban = enum_tours(5, List((0, 2)))
-assert(ts02_urban.map(correct_urban(5)).forall(_ == true) == true)
-assert(ts02_urban.length == 56)
--- a/main_testing4/knight_test4.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,6 +0,0 @@
-import M4a._
-
-val f_urban = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None
-
-assert(first(List((1,0),(2,0),(3,0),(4,0)), f_urban) == Some(List((4,0))))
-assert(first(List((1,0),(2,0),(3,0)), f_urban) == None)
--- a/main_testing4/knight_test5.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,32 +0,0 @@
-import M4a._
-
-
-//type Pos = (Int, Int) // a position on a chessboard
-//type Path = List[Pos] // a path...a list of positions
-
-def add_pair_urban(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves_urban(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
-
-def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
- moves_urban(x).filter(is_legal_urban(dim, path))
-
-def correct_urban(dim: Int)(p: Path): Boolean = p match {
- case Nil => true
- case x::Nil => true
- case x::y::p =>
- if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
-}
-
-
-val ts1_urban = first_tour(6, List((0, 0))).get
-assert(correct_urban(6)(ts1_urban) == true)
-
-val ts2_urban = first_tour(4, List((0, 0)))
-assert(ts2_urban == None)
--- a/main_testing4/knight_test6.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,19 +0,0 @@
-import M4b._
-
-assert(ordered_moves(8, List((3,4), (3,2)), (1, 3)) == List((0,1), (0,5), (2,1), (2,5)))
-assert(ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2)))
-assert(ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1)))
-
-
-
-/*
-import scala.concurrent._
-import scala.concurrent.duration._
-import ExecutionContext.Implicits.global
-import scala.language.postfixOps
-
-lazy val f = Future {
-}
-
-Await.result(f, 120 second)
-*/
--- a/main_testing4/knight_test7.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,32 +0,0 @@
-import M4b._
-
-//type Pos = (Int, Int)
-//type Path = List[Pos]
-
-def add_pair_urban(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves_urban(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
-
-def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
- moves_urban(x).filter(is_legal_urban(dim, path))
-
-def correct_urban(dim: Int)(p: Path): Boolean = p match {
- case Nil => true
- case x::Nil => true
- case x::y::p =>
- if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
-}
-
-def correct_closed_urban(dim: Int)(p: Path) =
- correct_urban(6)(p) && moves_urban(p.head).contains(p.last)
-
-
-val tsc = first_closed_tour_heuristics(6, List((3, 3))).get
-assert(correct_closed_urban(6)(tsc) == true)
-
--- a/main_testing4/knight_test8.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,33 +0,0 @@
-import M4b._
-
-
-//type Pos = (Int, Int)
-//type Path = List[Pos]
-
-def add_pair_urban(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves_urban(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
-
-def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
- moves_urban(x).filter(is_legal_urban(dim, path))
-
-def correct_urban(dim: Int)(p: Path): Boolean = p match {
- case Nil => true
- case x::Nil => true
- case x::y::p =>
- if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
-}
-
-
-val ts8 = first_tour_heuristics(8, List((0,0))).get
-assert(correct_urban(8)(ts8) == true)
-
-val ts30 = first_tour_heuristics(30, List((0,0))).get
-assert(correct_urban(30)(ts30) == true)
-
--- a/main_testing4/knight_test9.scala Thu Nov 02 23:34:53 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,29 +0,0 @@
-import M4c._
-
-//type Pos = (Int, Int)
-//type Path = List[Pos]
-
-def add_pair_urban(x: Pos)(y: Pos): Pos =
- (x._1 + y._1, x._2 + y._2)
-
-def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean =
- 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-
-def moves_urban(x: Pos): List[Pos] =
- List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
- (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x))
-
-def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] =
- moves_urban(x).filter(is_legal_urban(dim, path))
-
-def correct_urban(dim: Int)(p: Path): Boolean = p match {
- case Nil => true
- case x::Nil => true
- case x::y::p =>
- if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
-}
-
-
-val ts70 = tour_on_mega_board(70, List((0,0))).get
-assert(correct_urban(70)(ts70) == true)
-
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4/shogun.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,271 @@
+// Main Part 4 about the Shogun Board Game
+//=========================================
+
+object M4 {
+
+type Pos = (Int, Int) // a position on a chessboard
+
+// Colours: Red or White
+abstract class Colour
+case object Red extends Colour
+case object Wht extends Colour
+
+// Pieces: Either Pawns or Kings
+//===============================
+abstract class Piece {
+ def pos : Pos
+ def col : Colour
+ def en : Int // energy for Pawns 1 - 4, for Kings 1 - 2
+}
+
+case class Pawn(en: Int, col: Colour, pos: Pos) extends Piece
+case class King(en: Int, col: Colour, pos: Pos) extends Piece
+
+//val p = Pawn(4, Wht, (3,2))
+//assert(p.pos == (3,2))
+//assert(p.col == Wht)
+//assert(p.en == 4)
+
+// checks if a piece is a king
+def is_king(pc: Piece) : Boolean = pc match {
+ case King(_, _, _) => true
+ case _ => false
+}
+
+// incrementing and decrementing the position of a piece
+def incx(pc: Piece) : Piece = pc match {
+ case Pawn(en, c, (x,y)) => Pawn(en, c, (x+1,y))
+ case King(en, c, (x,y)) => King(en, c, (x+1,y))
+}
+
+def incy(pc: Piece) : Piece = pc match {
+ case Pawn(en, c, (x,y)) => Pawn(en, c, (x,y+1))
+ case King(en, c, (x,y)) => King(en, c, (x,y+1))
+}
+
+def decx(pc: Piece) : Piece = pc match {
+ case Pawn(en, c, (x,y)) => Pawn(en, c, (x-1,y))
+ case King(en, c, (x,y)) => King(en, c, (x-1,y))
+}
+
+def decy(pc: Piece) : Piece = pc match {
+ case Pawn(en, c, (x,y)) => Pawn(en, c, (x,y-1))
+ case King(en, c, (x,y)) => King(en, c, (x,y-1))
+}
+
+//pretty printing colours and pieces
+def pp_color(c: Colour) : String = c match {
+ case Red => "R"
+ case Wht => "W"
+}
+
+def pp(pc: Piece) : String = pc match {
+ case Pawn(n, c, _) => s"P${pp_color(c)}$n"
+ case King(n, c, _) => s"K${pp_color(c)}$n"
+}
+
+// Boards are sets of pieces
+//===========================
+case class Board(pces: Set[Piece]) {
+ def +(pc: Piece) : Board = Board(pces + pc)
+ def -(pc: Piece) : Board = Board(pces - pc)
+}
+
+// checking whether a position is occupied in a board
+def occupied(p: Pos, b: Board) : Option[Piece] =
+ b.pces.find(p == _.pos)
+
+def occupied_by(p: Pos, b: Board) : Option[Colour] =
+ occupied(p, b).map(_.col)
+
+def is_occupied(p: Pos, b: Board) : Boolean =
+ occupied(p, b).isDefined
+
+// is a position inside a board
+def inside(p: Pos, b: Board): Boolean =
+ 1 <= p._1 && 1 <= p._2 && p._1 <= 8 && p._2 <= 8
+
+// pretty printing a board
+def print_board(b: Board): Unit = {
+ println()
+ for (i <- 8 to 1 by -1) {
+ println("+" ++ "-" * 31 ++ "+")
+ for (j <- 1 to 8) {
+ val opc = occupied((j,i), b)
+ if (opc.isDefined) print(s"|${pp(opc.get)}")
+ else print("| ")
+ }
+ println("|")
+ }
+ println("+" ++ "-" * 31 ++ "+")
+}
+
+// example board: initial board
+val b_init = Board(Set(King(2,Wht,(4,1)), King(1,Red,(5,8)),
+ Pawn(4,Wht,(1,1)), Pawn(4,Red,(1,8)),
+ Pawn(3,Wht,(2,1)), Pawn(2,Red,(2,8)),
+ Pawn(2,Wht,(3,1)), Pawn(3,Red,(3,8)),
+ Pawn(1,Wht,(5,1)), Pawn(1,Red,(4,8)),
+ Pawn(4,Wht,(6,1)), Pawn(3,Red,(6,8)),
+ Pawn(3,Wht,(7,1)), Pawn(1,Red,(7,8)),
+ Pawn(2,Wht,(8,1)), Pawn(3,Red,(8,8))))
+
+//print_board(b_init)
+// --------------------------------
+// |PR4|PR2|PR3|PR1|KR1|PR3|PR1|PR3|
+// --------------------------------
+// | | | | | | | | |
+// --------------------------------
+// | | | | | | | | |
+// --------------------------------
+// | | | | | | | | |
+// --------------------------------
+// | | | | | | | | |
+// --------------------------------
+// | | | | | | | | |
+// --------------------------------
+// | | | | | | | | |
+// --------------------------------
+// |PW4|PW3|PW2|KW2|PW1|PW4|PW3|PW2|
+// --------------------------------
+
+
+// Moves
+//=======
+abstract class Move
+case object U extends Move // up
+case object D extends Move // down
+case object R extends Move // right
+case object L extends Move // left
+case object RU extends Move // ...
+case object LU extends Move
+case object RD extends Move
+case object LD extends Move
+case object UR extends Move
+case object UL extends Move
+case object DR extends Move
+case object DL extends Move
+
+// Task 1: calculates all next possible positions according to a move
+def eval(pc: Piece, m: Move, en: Int, b: Board) : Set[Piece] = {
+ val p = pc.pos
+ val c = pc.col
+ if (!inside(p, b)) Set()
+ else if (en == 0 && !is_occupied(p, b)) Set(pc)
+ else if (en == 0 && is_occupied(p, b) && c != occupied_by(p, b).get) Set(pc)
+ else if (is_occupied(p, b)) Set()
+ else m match {
+ case U => eval(incy(pc), U, en - 1, b)
+ case D => eval(decy(pc), D, en - 1, b)
+ case R => eval(incx(pc), R, en - 1, b)
+ case L => eval(decx(pc), L, en - 1, b)
+ case RU => eval(incx(pc), RU, en - 1, b) ++ eval(pc, U, en, b)
+ case LU => eval(decx(pc), LU, en - 1, b) ++ eval(pc, U, en, b)
+ case RD => eval(incx(pc), RD, en - 1, b) ++ eval(pc, D, en, b)
+ case LD => eval(decx(pc), LD, en - 1, b) ++ eval(pc, D, en, b)
+ case UR => eval(incy(pc), UR, en - 1, b) ++ eval(pc, R, en, b)
+ case UL => eval(incy(pc), UL, en - 1, b) ++ eval(pc, L, en, b)
+ case DR => eval(decy(pc), DR, en - 1, b) ++ eval(pc, R, en, b)
+ case DL => eval(decy(pc), DL, en - 1, b) ++ eval(pc, L, en, b)
+}}
+
+/*
+// test cases
+val pw_a = Pawn(4, Wht, (4,4))
+println(eval(pw_a, U, 4, b_init)) // Set(Pawn(4,Wht,(4,8)))
+println(eval(pw_a, U, 3, b_init)) // Set(Pawn(4,Wht,(4,7)))
+println(eval(pw_a, RU, 4, b_init)) // Set(Pawn(4,Wht,(6,6)), Pawn(4,Wht,(4,8)),
+ // Pawn(4,Wht,(5,7)), Pawn(4,Wht,(7,5)),
+ // Pawn(4,Wht,(8,4)))
+val pw_b = Pawn(4, Red, (4,4))
+println(eval(pw_b, RU, 4, b_init)) // Set(Pawn(4,Red,(8,4)), Pawn(4,Red,(7,5)),
+ Pawn(4,Red,(6,6)), Pawn(4,Red,(5,7)))
+*/
+
+
+// Task 2: calculates all possible moves for a piece
+def all_moves(pc: Piece, b: Board) : Set[Piece] = {
+ Set(U,D,L,R,RU,LU,RD,LD,UR,UL,DR,DL).flatMap(eval(pc, _, pc.en, b - pc))
+}
+
+/*
+// test cases
+val pw_c = Pawn(2, Wht, (4,4))
+val pw_d = Pawn(3, Red, (4,4))
+println(all_moves(pw_c, b_init))
+ // Set(Pawn(2,Wht,(3,5)), Pawn(2,Wht,(2,4)), Pawn(2,Wht,(3,3)), Pawn(2,Wht,(5,5)),
+ // Pawn(2,Wht,(6,4)), Pawn(2,Wht,(4,6)), Pawn(2,Wht,(4,2)), Pawn(2,Wht,(5,3)))
+println(all_moves(pw_d, b_init))
+ // Set(Pawn(3,Red,(4,7)), Pawn(3,Red,(5,2)), Pawn(3,Red,(3,2)), Pawn(3,Red,(1,4)),
+ // Pawn(3,Red,(6,3)), Pawn(3,Red,(3,6)), Pawn(3,Red,(2,5)), Pawn(3,Red,(2,3)),
+ // Pawn(3,Red,(4,1)), Pawn(3,Red,(5,6)), Pawn(3,Red,(7,4)), Pawn(3,Red,(6,5)))
+*/
+
+
+// Task 3: calculates all pieces that are attacked by colour
+def attacked(c: Colour, b: Board) : Set[Piece] = {
+ val (me, opponent) = b.pces.partition(_.col == c)
+ val all = me.flatMap(all_moves(_, b))
+ opponent.filter(pc => is_occupied(pc.pos, Board(all)))
+}
+
+// test cases
+val b_checkmate = Board(Set(King(2, Red, (4,2)), King(2, Wht, (7,1)),
+ Pawn(3, Red, (6,1)), Pawn(2, Wht, (8,4)),
+ Pawn(4, Red, (4,4)), Pawn(2, Wht, (4,1)),
+ Pawn(4, Red, (5,3)), Pawn(3, Wht, (8,7)),
+ Pawn(3, Red, (6,5))))
+print_board(b_checkmate)
+println(attacked(Red, b_checkmate)) // Set(Pawn(2,Wht,(8,4)), King(2,Wht,(7,1)))
+println(attacked(Wht, b_checkmate)) // Set(Pawn(3,Red,(6,1)))
+println(attacked(Wht, b_init)) // Set()
+println(attacked(Red, b_init)) // Set()
+
+// Task 4: calculates the number of pieces that attack a piece
+def attackedN(pc: Piece, b: Board) : Int = {
+ val (me, opponent) = b.pces.partition(_.col == pc.col)
+ val all = opponent.toList.flatMap(all_moves(_, b))
+ all.count(_.pos == pc.pos)
+}
+
+// test cases
+println(attackedN(Pawn(2, Wht, (8,4)), b_checkmate)) // 3
+println(attackedN(King(2, Wht, (7,1)), b_checkmate)) // 1
+println(attackedN(Pawn(3, Red, (6,1)), b_checkmate)) // 1
+
+
+// Task 5: calculates the number of pieces that protect a piece
+def protectedN(pc: Piece, b: Board) : Int = {
+ val (me, opponent) = b.pces.partition(_.col == pc.col)
+ val all = (me - pc).toList.flatMap(all_moves(_, (b - pc)))
+ all.count(_.pos == pc.pos)
+}
+
+println(protectedN(Pawn(2, Wht, (8,4)), b_checkmate)) // 1
+println(protectedN(Pawn(4, Red, (5,3)), b_checkmate)) // 3
+
+
+
+//
+val pw1 = Pawn(4, Wht, (4,6))
+val pw2 = Pawn(4, Wht, (2,4))
+val pw3 = Pawn(3, Red, (6,8))
+val pw4 = Pawn(2, Red, (2,8))
+val bt = b_init + pw1 + pw2
+
+print_board(bt)
+println(s"Capture Red: ${attacked(Wht, bt)}")
+ // Set(Pawn(2,Red,(2,8)), Pawn(3,Red,(6,8)))
+println(s"Capture Wht: ${attacked(Red, bt)}")
+ // Set(Pawn(4,Wht,(4,6)))
+println(s"ProtectedN: ${protectedN(pw3, bt)}")
+ // 2
+println(s"AttackedN: ${attackedN(pw4, bt)}")
+ // 2
+println(s"all moves: ${all_moves(pw2, bt)}")
+ // Set(Pawn(4,Wht,(4,2)), Pawn(4,Wht,(1,7)), Pawn(4,Wht,(5,3)), Pawn(4,Wht,(5,5)),
+ // Pawn(4,Wht,(2,8)), Pawn(4,Wht,(3,7)), Pawn(4,Wht,(6,4)))
+
+}
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4/shogun_test.sh Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,174 @@
+#!/bin/bash
+set -euo pipefail
+
+out=${1:-output}
+
+echo -e "" > $out
+
+echo -e "Below is the feedback for your submission of shogun.scala" >> $out
+echo -e "" >> $out
+#echo -e "!! Important: !!" >> $out
+#echo -e "Because of limitations with our testing infrastructure, we can only" >> $out
+#echo -e "let code run for 10 seconds and then have to kill it. This might" >> $out
+#echo -e "mean your code is correct, but still marked as Fail. Remember" >> $out
+#echo -e "you can test your code on your own machine and benchmark it" >> $out
+#echo -e "against the reference implementation." >> $out
+#echo -e "" >> $out
+
+# compilation tests
+
+function scala_compile {
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli compile "$1" 2> c$out 1> c$out)
+}
+
+# functional tests
+
+function scala_assert {
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null)
+}
+
+# purity test
+function scala_vars {
+ (sed 's/immutable/ok/g' c$out > cb$out;
+ egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null)
+}
+
+
+# compilation test
+
+
+echo -e "shogun.scala runs?" >> $out
+
+if (scala_compile shogun.scala)
+then
+ echo -e " --> passed" >> $out
+ tsts1=$(( 0 ))
+ else
+ echo -e " --> SCALA DID NOT RUN SHOGUN.SCALA\n" >> $out
+ tsts1=$(( 1 ))
+fi
+
+
+# shogun: purity test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e "shogun.scala does not contain vars, returns etc?" >> $out
+
+ if (scala_vars shogun.scala)
+ then
+ echo -e " --> FAIL (make triple-sure your program conforms to the required format)" >> $out
+ tsts1=$(( 1 ))
+ else
+ echo -e " --> passed" >> $out
+ tsts1=$(( 0 ))
+ fi
+fi
+
+
+### shogun eval test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e " val pw_a = Pawn(4, Wht, (4,4)) " >> $out
+ echo -e " eval(pw_a, U, 4, b_init) == Set(Pawn(4,Wht,(4,8)))" >> $out
+ echo -e " eval(pw_a, U, 3, b_init) == Set(Pawn(4,Wht,(4,7)))" >> $out
+ echo -e " eval(pw_a, RU, 4, b_init) == Set(Pawn(4,Wht,(6,6)), Pawn(4,Wht,(4,8)), " >> $out
+ echo -e " Pawn(4,Wht,(5,7)), Pawn(4,Wht,(7,5)), " >> $out
+ echo -e " Pawn(4,Wht,(8,4)))" >> $out
+ echo -e " " >> $out
+ echo -e " val pw_b = Pawn(4, Red, (4,4))" >> $out
+ echo -e " eval(pw_b, RU, 4, b_init) == Set(Pawn(4,Red,(8,4)), Pawn(4,Red,(7,5)), " >> $out
+ echo -e " Pawn(4,Red,(6,6)), Pawn(4,Red,(5,7)))" >> $out
+ echo -e " " >> $out
+
+ if (scala_assert "shogun.scala" "shogun_test1.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
+### shogun all_moves test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e " val pw_c = Pawn(2, Wht, (4,4))" >> $out
+ echo -e " val pw_d = Pawn(3, Red, (4,4))" >> $out
+ echo -e " all_moves(pw_c, b_init) == " >> $out
+ echo -e " Set(Pawn(2,Wht,(3,5)), Pawn(2,Wht,(2,4)), Pawn(2,Wht,(3,3)), Pawn(2,Wht,(5,5))," >> $out
+ echo -e " Pawn(2,Wht,(6,4)), Pawn(2,Wht,(4,6)), Pawn(2,Wht,(4,2)), Pawn(2,Wht,(5,3)))" >> $out
+ echo -e " all_moves(pw_d, b_init) == " >> $out
+ echo -e " Set(Pawn(3,Red,(4,7)), Pawn(3,Red,(5,2)), Pawn(3,Red,(3,2)), Pawn(3,Red,(1,4))," >> $out
+ echo -e " Pawn(3,Red,(6,3)), Pawn(3,Red,(3,6)), Pawn(3,Red,(2,5)), Pawn(3,Red,(2,3)), " >> $out
+ echo -e " Pawn(3,Red,(4,1)), Pawn(3,Red,(5,6)), Pawn(3,Red,(7,4)), Pawn(3,Red,(6,5))))" >> $out
+
+
+ if (scala_assert "shogun.scala" "shogun_test2.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
+
+### attacked test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e " val b2 = Board(Set(King(2, Red, (4,2)), King(2, Wht, (7,1))," >> $out
+ echo -e " Pawn(3, Red, (6,1)), Pawn(2, Wht, (8,4))," >> $out
+ echo -e " Pawn(4, Red, (4,4)), Pawn(2, Wht, (4,1))," >> $out
+ echo -e " Pawn(4, Red, (5,3)), Pawn(3, Wht, (8,7))," >> $out
+ echo -e " Pawn(3, Red, (6,5))))" >> $out
+ echo -e " attacked(Red, b2) == Set(Pawn(2,Wht,(8,4)), King(2,Wht,(7,1)))" >> $out
+ echo -e " attacked(Wht, b2) == Set(Pawn(3,Red,(6,1)))" >> $out
+ echo -e " attacked(Wht, b_init) == Set()" >> $out
+ echo -e " attacked(Red, b_init) == Set()" >> $out
+
+ if (scala_assert "shogun.scala" "shogun_test3.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
+### attackedN test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e " attackedN(Pawn(2, Wht, (8,4)), b2) == 3" >> $out
+ echo -e " attackedN(King(2, Wht, (7,1)), b2) == 1" >> $out
+ echo -e " attackedN(Pawn(3, Red, (6,1)), b2) == 1" >> $out
+
+ if (scala_assert "shogun.scala" "shogun_test4.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
+
+### protectedN test
+
+if [ $tsts1 -eq 0 ]
+then
+ echo -e " protectedN(Pawn(2, Wht, (8,4)), b2) == 1" >> $out
+ echo -e " protectedN(Pawn(4, Red, (5,3)), b2) == 3" >> $out
+
+ if (scala_assert "shogun.scala" "shogun_test5.scala")
+ then
+ echo -e " --> success" >> $out
+ else
+ echo -e " --> \n ONE TEST FAILED\n" >> $out
+ fi
+fi
+
+
+echo -e "" >> $out
+echo -e "" >> $out
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4/shogun_test1.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,24 @@
+def urbanmain() = {
+ import M4._
+
+ val b_init = Board(Set(King(2,Wht,(4,1)), King(1,Red,(5,8)),
+ Pawn(4,Wht,(1,1)), Pawn(4,Red,(1,8)),
+ Pawn(3,Wht,(2,1)), Pawn(2,Red,(2,8)),
+ Pawn(2,Wht,(3,1)), Pawn(3,Red,(3,8)),
+ Pawn(1,Wht,(5,1)), Pawn(1,Red,(4,8)),
+ Pawn(4,Wht,(6,1)), Pawn(3,Red,(6,8)),
+ Pawn(3,Wht,(7,1)), Pawn(1,Red,(7,8)),
+ Pawn(2,Wht,(8,1)), Pawn(3,Red,(8,8))))
+
+ val pw_a = Pawn(4, Wht, (4,4))
+ assert(eval(pw_a, U, 4, b_init) == Set(Pawn(4,Wht,(4,8))))
+ assert(eval(pw_a, U, 3, b_init) == Set(Pawn(4,Wht,(4,7))))
+ assert(eval(pw_a, RU, 4, b_init) == Set(Pawn(4,Wht,(6,6)), Pawn(4,Wht,(4,8)),
+ Pawn(4,Wht,(5,7)), Pawn(4,Wht,(7,5)),
+ Pawn(4,Wht,(8,4))))
+ val pw_b = Pawn(4, Red, (4,4))
+ println(eval(pw_b, RU, 4, b_init) == Set(Pawn(4,Red,(8,4)), Pawn(4,Red,(7,5)),
+ Pawn(4,Red,(6,6)), Pawn(4,Red,(5,7))))
+
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4/shogun_test2.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,25 @@
+def urbanmain() = {
+ import M4._
+
+ val b_init = Board(Set(King(2,Wht,(4,1)), King(1,Red,(5,8)),
+ Pawn(4,Wht,(1,1)), Pawn(4,Red,(1,8)),
+ Pawn(3,Wht,(2,1)), Pawn(2,Red,(2,8)),
+ Pawn(2,Wht,(3,1)), Pawn(3,Red,(3,8)),
+ Pawn(1,Wht,(5,1)), Pawn(1,Red,(4,8)),
+ Pawn(4,Wht,(6,1)), Pawn(3,Red,(6,8)),
+ Pawn(3,Wht,(7,1)), Pawn(1,Red,(7,8)),
+ Pawn(2,Wht,(8,1)), Pawn(3,Red,(8,8))))
+
+ val pw_c = Pawn(2, Wht, (4,4))
+ val pw_d = Pawn(3, Red, (4,4))
+
+ assert(all_moves(pw_c, b_init) ==
+ Set(Pawn(2,Wht,(3,5)), Pawn(2,Wht,(2,4)), Pawn(2,Wht,(3,3)), Pawn(2,Wht,(5,5)),
+ Pawn(2,Wht,(6,4)), Pawn(2,Wht,(4,6)), Pawn(2,Wht,(4,2)), Pawn(2,Wht,(5,3))))
+
+ assert(all_moves(pw_d, b_init) ==
+ Set(Pawn(3,Red,(4,7)), Pawn(3,Red,(5,2)), Pawn(3,Red,(3,2)), Pawn(3,Red,(1,4)),
+ Pawn(3,Red,(6,3)), Pawn(3,Red,(3,6)), Pawn(3,Red,(2,5)), Pawn(3,Red,(2,3)),
+ Pawn(3,Red,(4,1)), Pawn(3,Red,(5,6)), Pawn(3,Red,(7,4)), Pawn(3,Red,(6,5))))
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4/shogun_test3.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,24 @@
+def urbanmain() = {
+ import M4._
+
+ val b_init = Board(Set(King(2,Wht,(4,1)), King(1,Red,(5,8)),
+ Pawn(4,Wht,(1,1)), Pawn(4,Red,(1,8)),
+ Pawn(3,Wht,(2,1)), Pawn(2,Red,(2,8)),
+ Pawn(2,Wht,(3,1)), Pawn(3,Red,(3,8)),
+ Pawn(1,Wht,(5,1)), Pawn(1,Red,(4,8)),
+ Pawn(4,Wht,(6,1)), Pawn(3,Red,(6,8)),
+ Pawn(3,Wht,(7,1)), Pawn(1,Red,(7,8)),
+ Pawn(2,Wht,(8,1)), Pawn(3,Red,(8,8))))
+
+ val b2 = Board(Set(King(2, Red, (4,2)), King(2, Wht, (7,1)),
+ Pawn(3, Red, (6,1)), Pawn(2, Wht, (8,4)),
+ Pawn(4, Red, (4,4)), Pawn(2, Wht, (4,1)),
+ Pawn(4, Red, (5,3)), Pawn(3, Wht, (8,7)),
+ Pawn(3, Red, (6,5))))
+
+ assert(attacked(Red, b2) == Set(Pawn(2,Wht,(8,4)), King(2,Wht,(7,1))))
+ assert(attacked(Wht, b2) == Set(Pawn(3,Red,(6,1))))
+ assert(attacked(Wht, b_init) == Set())
+ assert(attacked(Red, b_init) == Set())
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4/shogun_test4.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,23 @@
+def urbanmain() = {
+ import M4._
+
+ val b_init = Board(Set(King(2,Wht,(4,1)), King(1,Red,(5,8)),
+ Pawn(4,Wht,(1,1)), Pawn(4,Red,(1,8)),
+ Pawn(3,Wht,(2,1)), Pawn(2,Red,(2,8)),
+ Pawn(2,Wht,(3,1)), Pawn(3,Red,(3,8)),
+ Pawn(1,Wht,(5,1)), Pawn(1,Red,(4,8)),
+ Pawn(4,Wht,(6,1)), Pawn(3,Red,(6,8)),
+ Pawn(3,Wht,(7,1)), Pawn(1,Red,(7,8)),
+ Pawn(2,Wht,(8,1)), Pawn(3,Red,(8,8))))
+
+ val b2 = Board(Set(King(2, Red, (4,2)), King(2, Wht, (7,1)),
+ Pawn(3, Red, (6,1)), Pawn(2, Wht, (8,4)),
+ Pawn(4, Red, (4,4)), Pawn(2, Wht, (4,1)),
+ Pawn(4, Red, (5,3)), Pawn(3, Wht, (8,7)),
+ Pawn(3, Red, (6,5))))
+
+ assert(attackedN(Pawn(2, Wht, (8,4)), b2) == 3)
+ assert(attackedN(King(2, Wht, (7,1)), b2) == 1)
+ assert(attackedN(Pawn(3, Red, (6,1)), b2) == 1)
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4/shogun_test5.scala Sat Nov 04 18:53:37 2023 +0000
@@ -0,0 +1,13 @@
+def urbanmain() = {
+ import M4._
+
+ val b2 = Board(Set(King(2, Red, (4,2)), King(2, Wht, (7,1)),
+ Pawn(3, Red, (6,1)), Pawn(2, Wht, (8,4)),
+ Pawn(4, Red, (4,4)), Pawn(2, Wht, (4,1)),
+ Pawn(4, Red, (5,3)), Pawn(3, Wht, (8,7)),
+ Pawn(3, Red, (6,5))))
+
+ assert(protectedN(Pawn(2, Wht, (8,4)), b2) == 1)
+ assert(protectedN(Pawn(4, Red, (5,3)), b2) == 3)
+
+}