--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/resit2.tex Thu Jun 13 13:13:33 2024 +0100
@@ -0,0 +1,640 @@
+% !TEX program = xelatex
+\documentclass{article}
+\usepackage{chessboard}
+\usepackage[LSBC4,T1]{fontenc}
+\let\clipbox\relax
+\usepackage{../styles/style}
+\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}
+
+\setchessboard{smallboard,
+ zero,
+ showmover=false,
+ boardfontencoding=LSBC4,
+ hlabelformat=\arabic{ranklabel},
+ vlabelformat=\arabic{filelabel}}
+
+\mbox{}\\[-18mm]\mbox{}
+
+\section*{Resit:\\ Implementing the Shogun Board Game\\ (Scala, 8 Marks)}
+
+\noindent
+You are asked to implement a Scala program for playing the Shogun
+board game. The deadline for your submission is on XXX at
+16:00. Make sure you use \texttt{scala-cli} and Scala version \textbf{3.XX}
+for the resit---the same version as during the lectures. \medskip
+
+\IMPORTANTNONE{}
+
+\noindent
+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.
+
+\DISCLAIMER{}
+
+\subsection*{Background}
+
+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.
+
+
+\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
+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 the resit is to implement functions
+about moving pieces on the Shogun board.\medskip\medskip
+
+%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
+
+\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:
+
+\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
+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 non-trivial 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{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}
+
+\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
+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
+
+\subsection*{Tasks}
+
+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.
+
+A \emph{board} consists of a set of pieces. We always assume that we
+start with a consistent board and every move only 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)] 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}}
+
+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{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. Otherwise the empty set
+ \texttt{Set()} 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} (up)
+ you need to increase the y-coordinate:
+
+ \begin{center}
+ \texttt{U} $\quad\Rightarrow\quad$ new arguments: \texttt{incy(pc)}, \texttt{U}, energy - 1, same board
+ \end{center}
+
+ The move \texttt{U} here acts like a ``mode'', meaning if you move
+ up, you can only move up; the mode never changes for simple moves. 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}:
+
+ \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}
+
+For example in 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 fields. The difference with 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. But (7, 5) becomes reachable because it is occupied
+by a piece of the opposite colour.
+
+\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 {2/1/3,3/1/2,4/1/3,6/1/3,7/1/1,7/5/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}};
+
+\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);
+
+
+% 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,7/5/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}
+ \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}};
+
+\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]
+
+\item[(2)] Implement an \texttt{all\_moves} function that calculates for a
+ piece and a board, \textit{all} possible 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) is
+ shown in \eqref{moves} on page \pageref{moves}. Be careful about possible modifications
+ you need to apply to the board before you call the \texttt{eval} function.
+ Also for this task, ignore the fact that a king cannot move onto an attacked field.\\
+ \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 in the left board are all the attacked pieces by red, and on the right all for white:
+
+
+\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);
+
+
+% red 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/1,4/1/2,8/7/3,6/7/2}
+ \pic[fill=white] at (\x,\y) {piece={\e}};
+
+\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}
+&
+\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);
+\fill[blue!50] (5,4) rectangle ++ (1,1);
+
+% red 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/1,4/1/2,8/7/3,6/7/2}
+ \pic[fill=white] at (\x,\y) {piece={\e}};
+
+\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. In this number also include kings even
+ if they cannot move to this field because the would be in ``check''.
+ \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)).
+ Similarly to \texttt{attackedN}, include in the calculated number here also the king provided it
+ can reach the given piece.
+ \\
+ \mbox{}\hfill[1 Mark]
+
+ \item[(6)] Implement a function \texttt{legal\_moves} that behaves like \texttt{all\_moves} from (2) for
+ pawns, but for kings, in addition, makes sure that they do not move to an attacked field.
+ For example in the board below on the left, there are three possible fields the white king can
+ reach, but all of them are attacked by red pieces. In the board on the right where the
+ white king has an energy of 1, there is only one legal move, namely to move to field (8, 1).
+ The field (7, 2) is reachable, but is attacked; similarly capturing the red piece on field (6, 1) is
+ not possible because it is protected by at least another red piece.
+ %
+ \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,1) rectangle ++ (1,1);
+ \fill[blue!50] (6,2) rectangle ++ (1,1);
+ \fill[blue!50] (7,1) rectangle ++ (1,1);
+
+
+ % red 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/1,4/1/2,8/7/3,6/7/2}
+ \pic[fill=white] at (\x,\y) {piece={\e}};
+
+ \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} &
+ \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);
+ \fill[blue!50] (6,1) rectangle ++ (1,1);
+ \fill[blue!50] (7,0) rectangle ++ (1,1);
+
+
+ % red pieces
+ \foreach\x/\y/\e in {6/1/3,4/4/4,5/3/3,6/5/3}
+ \pic[fill=red] at (\x,\y) {piece={\e}};
+ % white pieces
+ \foreach\x/\y/\e in {8/4/1,4/1/2,8/7/3,6/7/2}
+ \pic[fill=white] at (\x,\y) {piece={\e}};
+
+ \pic[fill=red] at (4,2) {king={2}};
+ \pic[fill=white] at (7,1) {king={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{tabular}
+ \end{center}
+ \mbox{}\hfill[1 Mark]
+
+\end{itemize}
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
--- a/progs/mandelbrot.scala Thu Jun 06 22:18:15 2024 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,192 +0,0 @@
-// Mandelbrot pictures
-//=====================
-//
-// see https://en.wikipedia.org/wiki/Mandelbrot_set
-//
-// needs to be called with
-//
-// scala-cli --extra-jars scala-parallel-collections_3-1.0.4.jar
-//
-// the jar-file is uploaded to KEATS
-//
-//
-// !! UPDATE ON TIMING: On my faster Mac-M1 machine
-// !! the times for the first example are ca. 4 secs for
-// !! the sequential version and around 0.7 secs for the
-// !! par-version.
-
-
-import javax.swing.{JFrame, JPanel, WindowConstants}
-import java.awt.{Color, Dimension, Graphics, Graphics2D}
-import java.awt.image.BufferedImage
-
-import scala.language.implicitConversions
-import scala.collection.parallel.CollectionConverters.*
-
-// complex numbers
-// represents the complex number re + im * i
-case class Complex(val re: Double, val im: Double) {
-
- def +(that: Complex) = Complex(this.re + that.re, this.im + that.im)
- def -(that: Complex) = Complex(this.re - that.re, this.im - that.im)
- def *(that: Complex) = Complex(this.re * that.re - this.im * that.im,
- this.re * that.im + that.re * this.im)
- def *(that: Double) = Complex(this.re * that, this.im * that)
- def abs() = Math.sqrt(this.re * this.re + this.im * this.im)
-}
-
-// to allow the usual mathmo notation n + m * i
-object i extends Complex(0, 1)
-
-// implicit conversion from Doubles to Complex
-given Conversion[Double, Complex] = Complex(_, 0)
-
-// some customn colours for the "sliding effect"
-val colours = List(
- Color(66, 30, 15), Color(25, 7, 26),
- Color(9, 1, 47), Color(4, 4, 73),
- Color(0, 7, 100), Color(12, 44, 138),
- Color(24, 82, 177), Color(57, 125, 209),
- Color(134, 181, 229), Color(211, 236, 248),
- Color(241, 233, 191), Color(248, 201, 95),
- Color(255, 170, 0), Color(204, 128, 0),
- Color(153, 87, 0), Color(106, 52, 3))
-
-// the viewer panel with an image canvas
-class Viewer(width: Int, height: Int) extends JPanel {
- val canvas = BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB)
-
- override def paintComponent(g: Graphics) =
- g.asInstanceOf[Graphics2D].drawImage(canvas, null, null)
-
- override def getPreferredSize() =
- Dimension(width, height)
-
- def clearCanvas(color: Color) = {
- for (x <- 0 to width - 1; y <- 0 to height - 1)
- canvas.setRGB(x, y, color.getRGB())
- repaint()
- }
-}
-
-// initialising the viewer panel
-def openViewer(width: Int, height: Int) : Viewer = {
- val frame = JFrame("XYPlane")
- val viewer = Viewer(width, height)
- frame.add(viewer)
- frame.pack()
- frame.setVisible(true)
- frame.setResizable(false)
- frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE)
- viewer
-}
-
-// some hardcoded parameters
-val W = 900 // width
-val H = 800 // height
-val black = Color.black
-val viewer = openViewer(W, H)
-
-// draw a pixel on the canvas
-def pixel(x: Int, y: Int, color: Color) =
- viewer.canvas.setRGB(x, y, color.getRGB())
-
-
-// calculates the number of iterations using lazy lists (streams)
-// the iteration goes on for a maximum of max steps,
-// but might leave early when the pred is satisfied
-def iterations(c: Complex, max: Int) : Int = {
- def next(z: Complex) = z * z + c
- def pred(z: Complex) = z.abs() < 2 // exit condition
- LazyList.iterate(0.0 * i, max)(next).takeWhile(pred).size
-}
-
-// main function
-// start and end are the upper-left and lower-right corners,
-// max is the number of maximum iterations
-def mandelbrot(start: Complex, end: Complex, max: Int) : Unit = {
- viewer.clearCanvas(black)
-
- // deltas for each grid step
- val d_x = (end.re - start.re) / W
- val d_y = (end.im - start.im) / H
-
- for (y <- (0 until H).par) {
- for (x <- (0 until W).par) {
-
- val c = start + x * d_x + y * d_y * i
- val iters = iterations(c, max)
- val colour =
- if (iters == max) black
- else colours(iters % 16)
-
- pixel(x, y, colour)
- }
- viewer.updateUI()
- }
-}
-
-
-// Examples
-//==========
-
-//for measuring time
-def time_needed[T](code: => T) = {
- val start = System.nanoTime()
- code
- val end = System.nanoTime()
- (end - start) / 1.0e9
-}
-
-
-
-// example 1
-val exa1 = -2.0 + -1.5 * i
-val exa2 = 1.0 + 1.5 * i
-
-println(s"${time_needed(mandelbrot(exa1, exa2, 1000))} secs")
-
-// example 2
-val exb1 = -0.37465401 + 0.659227668 * i
-val exb2 = -0.37332410 + 0.66020767 * i
-
-//time_needed(mandelbrot(exb1, exb2, 1000))
-
-// example 3
-val exc1 = 0.435396403 + 0.367981352 * i
-val exc2 = 0.451687191 + 0.380210061 * i
-
-//time_needed(mandelbrot(exc1, exc2, 1000))
-
-
-
-// some more computations with example 3
-
-val delta = (exc2 - exc1) * 0.0333
-
-println(s"${time_needed(
- for (n <- (0 to 25))
- mandelbrot(exc1 + delta * n,
- exc2 - delta * n, 1000))} secs")
-
-
-
-// Larry Paulson's example
-val exl1 = -0.74364990 + 0.13188170 * i
-val exl2 = -0.74291189 + 0.13261971 * i
-
-//println(s"${time_needed(mandelbrot(exl1, exl2, 1000))} secs")
-
-
-// example by Jorgen Villadsen
-val exj1 = 0.10284 - 0.63275 * i
-val exj2 = 0.11084 - 0.64075 * i
-
-//time_needed(mandelbrot(exj1, exj2, 1000))
-
-
-// another example
-val exA = 0.3439274 + 0.6516478 * i
-val exB = 0.3654477 + 0.6301795 * i
-
-//time_needed(mandelbrot(exA, exB, 1000))
--- a/progs/mandelbrot2.scala Thu Jun 06 22:18:15 2024 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,186 +0,0 @@
-// Mandelbrot pictures
-//=====================
-//
-// see https://en.wikipedia.org/wiki/Mandelbrot_set
-//
-// under scala 2.13.XX needs to be called with
-//
-// scala -cp scala-parallel-collections_2.13-0.2.0.jar mandelbrot.scala
-
-import java.awt.Color
-import java.awt.Dimension
-import java.awt.Graphics
-import java.awt.Graphics2D
-import java.awt.image.BufferedImage
-import javax.swing.JFrame
-import javax.swing.JPanel
-import javax.swing.WindowConstants
-import scala.language.implicitConversions
-import scala.collection.parallel.CollectionConverters._
-
-// complex numbers
-case class Complex(val re: Double, val im: Double) {
- // represents the complex number re + im * i
- def +(that: Complex) = Complex(this.re + that.re, this.im + that.im)
- def -(that: Complex) = Complex(this.re - that.re, this.im - that.im)
- def *(that: Complex) = Complex(this.re * that.re - this.im * that.im,
- this.re * that.im + that.re * this.im)
- def *(that: Double) = Complex(this.re * that, this.im * that)
- def abs() = Math.sqrt(this.re * this.re + this.im * this.im)
-}
-
-// to allow the notation n + m * i
-object i extends Complex(0, 1)
-implicit def double2complex(re: Double) = Complex(re, 0)
-
-
-// some customn colours for the "sliding effect"
-val colours = List(
- new Color(66, 30, 15), new Color(25, 7, 26),
- new Color(9, 1, 47), new Color(4, 4, 73),
- new Color(0, 7, 100), new Color(12, 44, 138),
- new Color(24, 82, 177), new Color(57, 125, 209),
- new Color(134, 181, 229), new Color(211, 236, 248),
- new Color(241, 233, 191), new Color(248, 201, 95),
- new Color(255, 170, 0), new Color(204, 128, 0),
- new Color(153, 87, 0), new Color(106, 52, 3))
-
-// the viewer panel with an image canvas
-class Viewer(width: Int, height: Int) extends JPanel {
- val canvas = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB)
-
- override def paintComponent(g: Graphics) =
- g.asInstanceOf[Graphics2D].drawImage(canvas, null, null)
-
- override def getPreferredSize() =
- new Dimension(width, height)
-
- def clearCanvas(color: Color) = {
- for (x <- 0 to width - 1; y <- 0 to height - 1)
- canvas.setRGB(x, y, color.getRGB())
- repaint()
- }
-}
-
-// initialising the viewer panel
-def openViewer(width: Int, height: Int) : Viewer = {
- val frame = new JFrame("XYPlane")
- val viewer = new Viewer(width, height)
- frame.add(viewer)
- frame.pack()
- frame.setVisible(true)
- frame.setResizable(false)
- frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE)
- viewer
-}
-
-// some hardcoded parameters
-val W = 900 // width
-val H = 800 // height
-val black = Color.black
-val viewer = openViewer(W, H)
-
-// draw a pixel on the canvas
-def pixel(x: Int, y: Int, color: Color) =
- viewer.canvas.setRGB(x, y, color.getRGB())
-
-
-// calculates the number of iterations using lazy lists (streams)
-// the iteration goes on for a maximum of max steps,
-// but might leave early when the pred is satisfied
-def iterations(c: Complex, max: Int) : Int = {
- def next(z: Complex) = z * z + c
- def pred(z: Complex) = z.abs() < 2 // exit condition
- LazyList.iterate(0.0 * i, max)(next).takeWhile(pred).size
-}
-
-// main function
-// start and end are the upper-left and lower-right corners,
-// max is the number of maximum iterations
-def mandelbrot(start: Complex, end: Complex, max: Int) : Unit = {
- viewer.clearCanvas(black)
-
- // deltas for each grid step
- val d_x = (end.re - start.re) / W
- val d_y = (end.im - start.im) / H
-
- for (y <- (0 until H).par) {
- for (x <- (0 until W).par) {
-
- val c = start +
- (x * d_x + y * d_y * i)
- val iters = iterations(c, max)
- val col =
- if (iters == max) black
- else colours(iters % 16)
-
- pixel(x, y, col)
- }
- viewer.updateUI()
- }
-}
-
-
-// Examples
-//==========
-
-//for measuring time
-def time_needed[T](code: => T) = {
- val start = System.nanoTime()
- code
- val end = System.nanoTime()
- (end - start) / 1.0e9
-}
-
-
-
-// example 1
-val exa1 = -2.0 + -1.5 * i
-val exa2 = 1.0 + 1.5 * i
-
-println(s"${time_needed(mandelbrot(exa1, exa2, 1000))} secs")
-
-// example 2
-val exb1 = -0.37465401 + 0.659227668 * i
-val exb2 = -0.37332410 + 0.66020767 * i
-
-//time_needed(mandelbrot(exb1, exb2, 1000))
-
-// example 3
-val exc1 = 0.435396403 + 0.367981352 * i
-val exc2 = 0.451687191 + 0.380210061 * i
-
-//time_needed(mandelbrot(exc1, exc2, 1000))
-
-
-
-// some more computations with example 3
-
-val delta = (exc2 - exc1) * 0.0333
-
-//println(s"${time_needed(
-// for (n <- (0 to 12))
-// mandelbrot(exc1 + delta * n,
-// exc2 - delta * n, 100))} secs")
-
-
-
-// Larry Paulson's example
-val exl1 = -0.74364990 + 0.13188170 * i
-val exl2 = -0.74291189 + 0.13261971 * i
-
-//println(s"${time_needed(mandelbrot(exl1, exl2, 1000))} secs")
-
-
-// example by Jorgen Villadsen
-val exj1 = 0.10284 - 0.63275 * i
-val exj2 = 0.11084 - 0.64075 * i
-
-//time_needed(mandelbrot(exj1, exj2, 1000))
-
-
-// another example
-val exA = 0.3439274 + 0.6516478 * i
-val exB = 0.3654477 + 0.6301795 * i
-
-//time_needed(mandelbrot(exA, exB, 1000))