# HG changeset patch # User Christian Urban # Date 1718280813 -3600 # Node ID e2ffe8642f552cbb358ea8e2ae3615a22653e991 # Parent 4778fefecd0cfa909e606de72d835b9bb9943a62 updated diff -r 4778fefecd0c -r e2ffe8642f55 cws/resit2.tex --- /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: diff -r 4778fefecd0c -r e2ffe8642f55 cws/upload --- a/cws/upload Thu Jun 06 22:18:15 2024 +0100 +++ b/cws/upload Thu Jun 13 13:13:33 2024 +0100 @@ -1,7 +1,7 @@ #!/bin/bash set -euo pipefail -fls=${1:-"core_cw01.pdf core_cw02.pdf core_cw03.pdf main_cw01.pdf main_cw02.pdf main_cw03.pdf main_cw04.pdf main_cw05.pdf resit.pdf"} +fls=${1:-"core_cw01.pdf core_cw02.pdf core_cw03.pdf main_cw01.pdf main_cw02.pdf main_cw03.pdf main_cw04.pdf main_cw05.pdf resit2024.pdf"} for f in $fls; do echo -e "uploading $f" diff -r 4778fefecd0c -r e2ffe8642f55 progs/mandelbrot.sc --- a/progs/mandelbrot.sc Thu Jun 06 22:18:15 2024 +0100 +++ b/progs/mandelbrot.sc Thu Jun 13 13:13:33 2024 +0100 @@ -3,30 +3,34 @@ // // see https://en.wikipedia.org/wiki/Mandelbrot_set // -// needs to be called with +// You can run on the file one the commandline with // -// scala-cli --extra-jars scala-parallel-collections_3-1.0.4.jar +// scala-cli mandelbrot.sc // -// 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 +// !! 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. +// for parallel collections +//> using dep org.scala-lang.modules::scala-parallel-collections:1.0.4 +import scala.language.implicitConversions +import scala.collection.parallel.CollectionConverters.* +// for graphics 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 +// 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, @@ -41,7 +45,8 @@ // implicit conversion from Doubles to Complex given Conversion[Double, Complex] = Complex(_, 0) -// some customn colours for the "sliding effect" +// some customn colours for the "sliding effect" outside +// the mandelbrot set val colours = List( Color(66, 30, 15), Color(25, 7, 26), Color(9, 1, 47), Color(4, 4, 73), @@ -71,8 +76,8 @@ // initialising the viewer panel def openViewer(width: Int, height: Int) : Viewer = { + val viewer = Viewer(width, height) val frame = JFrame("XYPlane") - val viewer = Viewer(width, height) frame.add(viewer) frame.pack() frame.setVisible(true) @@ -116,7 +121,7 @@ val c = start + x * d_x + y * d_y * i val iters = iterations(c, max) - val colour = + val colour = if (iters == max) black else colours(iters % 16) @@ -127,6 +132,8 @@ } + + // Examples //========== @@ -158,11 +165,9 @@ //time_needed(mandelbrot(exc1, exc2, 1000)) - - // some more computations with example 3 -val delta = (exc2 - exc1) * 0.0333 +val delta = (exc2 - exc1) * 0.01 println(s"${time_needed( for (n <- (0 to 25)) diff -r 4778fefecd0c -r e2ffe8642f55 progs/mandelbrot.scala --- 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)) diff -r 4778fefecd0c -r e2ffe8642f55 progs/mandelbrot2.scala --- 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))