diff -r 092e0879a5ae -r 4bda49ec24da cws/cw03.tex --- a/cws/cw03.tex Tue Nov 20 13:42:32 2018 +0000 +++ b/cws/cw03.tex Tue Nov 20 14:31:14 2018 +0000 @@ -1,650 +1,369 @@ \documentclass{article} +\usepackage{chessboard} +\usepackage[LSBC4,T1]{fontenc} +\let\clipbox\relax \usepackage{../style} -\usepackage{../langs} \usepackage{disclaimer} -\usepackage{tikz} -\usepackage{pgf} -\usepackage{pgfplots} -\usepackage{stackengine} -%% \usepackage{accents} -\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}} - -\begin{filecontents}{re-python2.data} -1 0.033 -5 0.036 -10 0.034 -15 0.036 -18 0.059 -19 0.084 -20 0.141 -21 0.248 -22 0.485 -23 0.878 -24 1.71 -25 3.40 -26 7.08 -27 14.12 -28 26.69 -\end{filecontents} - -\begin{filecontents}{re-java.data} -5 0.00298 -10 0.00418 -15 0.00996 -16 0.01710 -17 0.03492 -18 0.03303 -19 0.05084 -20 0.10177 -21 0.19960 -22 0.41159 -23 0.82234 -24 1.70251 -25 3.36112 -26 6.63998 -27 13.35120 -28 29.81185 -\end{filecontents} - -\begin{filecontents}{re-java9.data} -1000 0.01410 -2000 0.04882 -3000 0.10609 -4000 0.17456 -5000 0.27530 -6000 0.41116 -7000 0.53741 -8000 0.70261 -9000 0.93981 -10000 0.97419 -11000 1.28697 -12000 1.51387 -14000 2.07079 -16000 2.69846 -20000 4.41823 -24000 6.46077 -26000 7.64373 -30000 9.99446 -34000 12.966885 -38000 16.281621 -42000 19.180228 -46000 21.984721 -50000 26.950203 -60000 43.0327746 -\end{filecontents} - \begin{document} -% BF IDE -% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5 - -\section*{Coursework 8 (Regular Expressions and Brainf***)} +\setchessboard{smallboard, + zero, + showmover=false, + boardfontencoding=LSBC4, + hlabelformat=\arabic{ranklabel}, + vlabelformat=\arabic{filelabel}} + +\mbox{}\\[-18mm]\mbox{} -This coursework is worth 10\%. It is about regular expressions, -pattern matching and an interpreter. The first part is due on 30 -November at 11pm; the second, more advanced part, is due on 21 -December at 11pm. In the first part, you are asked to implement a -regular expression matcher based on derivatives of regular -expressions. The reason is that regular expression matching in Java -and Python can sometimes be extremely slow. The advanced part is about -an interpreter for a very simple programming language.\bigskip +\section*{Coursework 7 (Scala)} + +This coursework is worth 10\%. It is about searching and +backtracking. The first part is due on 29 November at 11pm; the +second, more advanced part, is due on 20 December at 11pm. You are +asked to implement Scala programs that solve various versions of the +\textit{Knight's Tour Problem} on a chessboard. Note the second, more +advanced, part might include material you have not yet seen in the +first two lectures. \bigskip \IMPORTANT{} - -\noindent Also note that the running time of each part will be restricted to a -maximum of 360 seconds on my laptop. +maximum of 360 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*{Part 1 (6 Marks)} - -The task is to implement a regular expression matcher that is based on -derivatives of regular expressions. Most of the functions are defined by -recursion over regular expressions and can be elegantly implemented -using Scala's pattern-matching. The implementation should deal with the -following regular expressions, which have been predefined in the file -\texttt{re.scala}: - -\begin{center} -\begin{tabular}{lcll} - $r$ & $::=$ & $\ZERO$ & cannot match anything\\ - & $|$ & $\ONE$ & can only match the empty string\\ - & $|$ & $c$ & can match a single character (in this case $c$)\\ - & $|$ & $r_1 + r_2$ & can match a string either with $r_1$ or with $r_2$\\ - & $|$ & $r_1\cdot r_2$ & can match the first part of a string with $r_1$ and\\ - & & & then the second part with $r_2$\\ - & $|$ & $r^*$ & can match zero or more times $r$\\ -\end{tabular} -\end{center} - -\noindent -Why? Knowing how to match regular expressions and strings will let you -solve a lot of problems that vex other humans. Regular expressions are -one of the fastest and simplest ways to match patterns in text, and -are endlessly useful for searching, editing and analysing data in all -sorts of places (for example analysing network traffic in order to -detect security breaches). However, you need to be fast, otherwise you -will stumble over problems such as recently reported at - -{\small -\begin{itemize} -\item[$\bullet$] \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016} -\item[$\bullet$] \url{https://vimeo.com/112065252} -\item[$\bullet$] \url{http://davidvgalbraith.com/how-i-fixed-atom/} -\end{itemize}} - -\subsubsection*{Tasks (file re.scala)} - -The file \texttt{re.scala} has already a definition for regular -expressions and also defines some handy shorthand notation for -regular expressions. The notation in this document matches up -with the code in the file as follows: - -\begin{center} - \begin{tabular}{rcl@{\hspace{10mm}}l} - & & code: & shorthand:\smallskip \\ - $\ZERO$ & $\mapsto$ & \texttt{ZERO}\\ - $\ONE$ & $\mapsto$ & \texttt{ONE}\\ - $c$ & $\mapsto$ & \texttt{CHAR(c)}\\ - $r_1 + r_2$ & $\mapsto$ & \texttt{ALT(r1, r2)} & \texttt{r1 | r2}\\ - $r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)} & \texttt{r1 $\sim$ r2}\\ - $r^*$ & $\mapsto$ & \texttt{STAR(r)} & \texttt{r.\%} -\end{tabular} -\end{center} - - -\begin{itemize} -\item[(1a)] Implement a function, called \textit{nullable}, by - recursion over regular expressions. This function tests whether a - regular expression can match the empty string. This means given a - regular expression it either returns true or false. The function - \textit{nullable} - is defined as follows: - -\begin{center} -\begin{tabular}{lcl} -$\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\ -$\textit{nullable}(\ONE)$ & $\dn$ & $\textit{true}$\\ -$\textit{nullable}(c)$ & $\dn$ & $\textit{false}$\\ -$\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\ -$\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\ -$\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\ -\end{tabular} -\end{center}~\hfill[1 Mark] - -\item[(1b)] Implement a function, called \textit{der}, by recursion over - regular expressions. It takes a character and a regular expression - as arguments and calculates the derivative regular expression according - to the rules: - -\begin{center} -\begin{tabular}{lcl} -$\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\ -$\textit{der}\;c\;(\ONE)$ & $\dn$ & $\ZERO$\\ -$\textit{der}\;c\;(d)$ & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\ -$\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\ -$\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\ - & & $\textit{then}\;((\textit{der}\;c\;r_1)\cdot r_2) + (\textit{der}\;c\;r_2)$\\ - & & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\ -$\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\ -\end{tabular} -\end{center} - -For example given the regular expression $r = (a \cdot b) \cdot c$, the derivatives -w.r.t.~the characters $a$, $b$ and $c$ are - -\begin{center} - \begin{tabular}{lcll} - $\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & ($= r'$)\\ - $\textit{der}\;b\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$\\ - $\textit{der}\;c\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$ - \end{tabular} -\end{center} - -Let $r'$ stand for the first derivative, then taking the derivatives of $r'$ -w.r.t.~the characters $a$, $b$ and $c$ gives - -\begin{center} - \begin{tabular}{lcll} - $\textit{der}\;a\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ \\ - $\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & ($= r''$)\\ - $\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ - \end{tabular} -\end{center} - -One more example: Let $r''$ stand for the second derivative above, -then taking the derivatives of $r''$ w.r.t.~the characters $a$, $b$ -and $c$ gives - -\begin{center} - \begin{tabular}{lcll} - $\textit{der}\;a\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$ \\ - $\textit{der}\;b\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$\\ - $\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ & - (is $\textit{nullable}$) - \end{tabular} -\end{center} - -Note, the last derivative can match the empty string, that is it is \textit{nullable}.\\ -\mbox{}\hfill\mbox{[1 Mark]} - -\item[(1c)] Implement the function \textit{simp}, which recursively - traverses a regular expression from the inside to the outside, and - on the way simplifies every regular expression on the left (see - below) to the regular expression on the right, except it does not - simplify inside ${}^*$-regular expressions. - - \begin{center} -\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll} -$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ -$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ -$r \cdot \ONE$ & $\mapsto$ & $r$\\ -$\ONE \cdot r$ & $\mapsto$ & $r$\\ -$r + \ZERO$ & $\mapsto$ & $r$\\ -$\ZERO + r$ & $\mapsto$ & $r$\\ -$r + r$ & $\mapsto$ & $r$\\ -\end{tabular} - \end{center} - - For example the regular expression - \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\] - - simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be - seen as trees and there are several methods for traversing - trees. One of them corresponds to the inside-out traversal, which is - sometimes also called post-order traversal. Furthermore, - remember numerical expressions from school times: there you had expressions - like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$ - and simplification rules that looked very similar to rules - above. You would simplify such numerical expressions by replacing - for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then - look whether more rules are applicable. If you organise the - simplification in an inside-out fashion, it is always clear which - rule should be applied next.\hfill[2 Marks] - -\item[(1d)] Implement two functions: The first, called \textit{ders}, - takes a list of characters and a regular expression as arguments, and - builds the derivative w.r.t.~the list as follows: - -\begin{center} -\begin{tabular}{lcl} -$\textit{ders}\;(Nil)\;r$ & $\dn$ & $r$\\ - $\textit{ders}\;(c::cs)\;r$ & $\dn$ & - $\textit{ders}\;cs\;(\textit{simp}(\textit{der}\;c\;r))$\\ -\end{tabular} -\end{center} - -Note that this function is different from \textit{der}, which only -takes a single character. - -The second function, called \textit{matcher}, takes a string and a -regular expression as arguments. It builds first the derivatives -according to \textit{ders} and after that tests whether the resulting -derivative regular expression can match the empty string (using -\textit{nullable}). For example the \textit{matcher} will produce -true for the regular expression $(a\cdot b)\cdot c$ and the string -$abc$, but false if you give it the string $ab$. \hfill[1 Mark] - -\item[(1e)] Implement a function, called \textit{size}, by recursion - over regular expressions. If a regular expression is seen as a tree, - then \textit{size} should return the number of nodes in such a - tree. Therefore this function is defined as follows: - -\begin{center} -\begin{tabular}{lcl} -$\textit{size}(\ZERO)$ & $\dn$ & $1$\\ -$\textit{size}(\ONE)$ & $\dn$ & $1$\\ -$\textit{size}(c)$ & $\dn$ & $1$\\ -$\textit{size}(r_1 + r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\ -$\textit{size}(r_1 \cdot r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\ -$\textit{size}(r^*)$ & $\dn$ & $1 + \textit{size}(r)$\\ -\end{tabular} -\end{center} - -You can use \textit{size} in order to test how much the `evil' regular -expression $(a^*)^* \cdot b$ grows when taking successive derivatives -according the letter $a$ without simplification and then compare it to -taking the derivative, but simplify the result. The sizes -are given in \texttt{re.scala}. \hfill[1 Mark] -\end{itemize} - \subsection*{Background} -Although easily implementable in Scala, the idea behind the derivative -function might not so easy to be seen. To understand its purpose -better, assume a regular expression $r$ can match strings of the form -$c\!::\!cs$ (that means strings which start with a character $c$ and have -some rest, or tail, $cs$). If you take the derivative of $r$ with -respect to the character $c$, then you obtain a regular expression -that can match all the strings $cs$. In other words, the regular -expression $\textit{der}\;c\;r$ can match the same strings $c\!::\!cs$ -that can be matched by $r$, except that the $c$ is chopped off. +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. -Assume now $r$ can match the string $abc$. If you take the derivative -according to $a$ then you obtain a regular expression that can match -$bc$ (it is $abc$ where the $a$ has been chopped off). If you now -build the derivative $\textit{der}\;b\;(\textit{der}\;a\;r)$ you -obtain a regular expression that can match the string $c$ (it is $bc$ -where $b$ is chopped off). If you finally build the derivative of this -according $c$, that is -$\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r))$, you obtain -a regular expression that can match the empty string. You can test -whether this is indeed the case using the function nullable, which is -what your matcher is doing. +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 -The purpose of the $\textit{simp}$ function is to keep the regular -expressions small. Normally the derivative function makes the regular -expression bigger (see the SEQ case and the example in (1b)) and the -algorithm would be slower and slower over time. The $\textit{simp}$ -function counters this increase in size and the result is that the -algorithm is fast throughout. By the way, this algorithm is by Janusz -Brzozowski who came up with the idea of derivatives in 1964 in his PhD -thesis. - -\begin{center}\small -\url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)} -\end{center} +\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 + ] -If you want to see how badly the regular expression matchers do in -Java\footnote{Version 8 and below; Version 9 does not seem to be as - catastrophic, but still worse than the regular expression matcher -based on derivatives.} and in Python with the `evil' regular -expression $(a^*)^*\cdot b$, then have a look at the graphs below (you -can try it out for yourself: have a look at the file -\texttt{catastrophic.java} and \texttt{catastrophic.py} on -KEATS). Compare this with the matcher you have implemented. How long -can the string of $a$'s be in your matcher and still stay within the -30 seconds time limit? +\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): + -\begin{center} -\begin{tabular}{@{}cc@{}} -\multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings - $\underbrace{a\ldots a}_{n}$}\bigskip\\ - -\begin{tikzpicture} -\begin{axis}[ - xlabel={$n$}, - x label style={at={(1.05,0.0)}}, - ylabel={time in secs}, - y label style={at={(0.06,0.5)}}, - enlargelimits=false, - xtick={0,5,...,30}, - xmax=33, - ymax=45, - ytick={0,5,...,40}, - scaled ticks=false, - axis lines=left, - width=6cm, - height=5.5cm, - legend entries={Python, Java 8}, - legend pos=north west] -\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; -\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; -\end{axis} -\end{tikzpicture} - & -\begin{tikzpicture} -\begin{axis}[ - xlabel={$n$}, - x label style={at={(1.05,0.0)}}, - ylabel={time in secs}, - y label style={at={(0.06,0.5)}}, - %enlargelimits=false, - %xtick={0,5000,...,30000}, - xmax=65000, - ymax=45, - ytick={0,5,...,40}, - scaled ticks=false, - axis lines=left, - width=6cm, - height=5.5cm, - legend entries={Java 9}, - legend pos=north west] -\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data}; -\end{axis} -\end{tikzpicture} -\end{tabular} -\end{center} -\newpage +\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}] -\subsection*{Part 2 (4 Marks)} -Coming from Java or C++, you might think Scala is a quite esoteric -programming language. But remember, some serious companies have built -their business on -Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}} -And there are far, far more esoteric languages out there. One is -called \emph{brainf***}. You are asked in this part to implement an -interpreter for this language. - -Urban M\"uller developed brainf*** in 1993. A close relative of this -language was already introduced in 1964 by Corado B\"ohm, an Italian -computer pioneer, who unfortunately died a few months ago. The main -feature of brainf*** is its minimalistic set of instructions---just 8 -instructions in total and all of which are single characters. Despite -the minimalism, this language has been shown to be Turing -complete\ldots{}if this doesn't ring any bell with you: it roughly -means that every algorithm we know can, in principle, be implemented in -brainf***. It just takes a lot of determination and quite a lot of -memory resources. Some relatively sophisticated sample programs in -brainf*** are given in the file \texttt{bf.scala}.\bigskip +\noindent +\textbf{Hints:} 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}). \noindent -As mentioned above, brainf*** has 8 single-character commands, namely -\texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'}, -\texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is -considered a comment. Brainf*** operates on memory cells containing -integers. For this it uses a single memory pointer that points at each -stage to one memory cell. This pointer can be moved forward by one -memory cell by using the command \texttt{'>'}, and backward by using -\texttt{'<'}. The commands \texttt{'+'} and \texttt{'-'} increase, -respectively decrease, by 1 the content of the memory cell to which -the memory pointer currently points to. The commands for input/output -are \texttt{','} and \texttt{'.'}. Output works by reading the content -of the memory cell to which the memory pointer points to and printing -it out as an ASCII character. Input works the other way, taking some -user input and storing it in the cell to which the memory pointer -points to. The commands \texttt{'['} and \texttt{']'} are looping -constructs. Everything in between \texttt{'['} and \texttt{']'} is -repeated until a counter (memory cell) reaches zero. A typical -program in brainf*** looks as follows: +\textbf{Hints:} 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}. + + +\subsection*{Part 1 (7 Marks)} -\begin{center} -\begin{verbatim} - ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ - ..+++.>>.<-.<.+++.------.--------.>>+.>++. -\end{verbatim} -\end{center} +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 -This one prints out Hello World\ldots{}obviously. +Let us first fix the basic datastructures for the implementation. The +board dimension is an integer (we will never go beyond board sizes of +$40 \times 40$). 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 -\subsubsection*{Tasks (file bf.scala)} +\[ +\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*{Tasks (file knight1.scala)} \begin{itemize} -\item[(2a)] Brainf*** memory is represented by a \texttt{Map} from - integers to integers. The empty memory is represented by - \texttt{Map()}, that is nothing is stored in the - memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly stores \texttt{1} at - memory location \texttt{0}; at \texttt{2} it stores \texttt{3}. The - convention is that if we query the memory at a location that is - \emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write - a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and - a memory pointer (an \texttt{Int}) as argument, and safely reads the - corresponding memory location. If the \texttt{Map} is not defined at - the memory pointer, \texttt{sread} returns \texttt{0}. +\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] - Write another function \texttt{write}, which takes a memory, a - memory pointer and an integer value as argument and updates the - \texttt{Map} with the value at the given memory location. As usual - the \texttt{Map} is not updated `in-place' but a new map is created - with the same data, except the value is stored at the given memory - pointer.\hfill[1 Mark] - -\item[(2b)] Write two functions, \texttt{jumpRight} and - \texttt{jumpLeft} that are needed to implement the loop constructs - of brainf***. They take a program (a \texttt{String}) and a program - counter (an \texttt{Int}) as argument and move right (respectively - left) in the string in order to find the \textbf{matching} - opening/closing bracket. For example, given the following program - with the program counter indicated by an arrow: +\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{--[\barbelow{.}.+>--],>,++} - \end{center} - - then the matching closing bracket is in 9th position (counting from 0) and - \texttt{jumpRight} is supposed to return the position just after this - - \begin{center} - \texttt{--[..+>--]\barbelow{,}>,++} + \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))} \end{center} - meaning it jumps to after the loop. Similarly, if you are in 8th position - then \texttt{jumpLeft} is supposed to jump to just after the opening - bracket (that is jumping to the beginning of the loop): - - \begin{center} - \texttt{--[..+>-\barbelow{-}],>,++} - \qquad$\stackrel{\texttt{jumpLeft}}{\longrightarrow}$\qquad - \texttt{--[\barbelow{.}.+>--],>,++} - \end{center} - - Unfortunately we have to take into account that there might be - other opening and closing brackets on the `way' to find the - matching bracket. For example in the brainf*** program - - \begin{center} - \texttt{--[\barbelow{.}.[+>]--],>,++} - \end{center} - - we do not want to return the index for the \texttt{'-'} in the 9th - position, but the program counter for \texttt{','} in 12th - position. The easiest to find out whether a bracket is matched is by - using levels (which are the third argument in \texttt{jumpLeft} and - \texttt{jumpLeft}). In case of \texttt{jumpRight} you increase the - level by one whenever you find an opening bracket and decrease by - one for a closing bracket. Then in \texttt{jumpRight} you are looking - for the closing bracket on level \texttt{0}. For \texttt{jumpLeft} you - do the opposite. In this way you can find \textbf{matching} brackets - in strings such as - - \begin{center} - \texttt{--[\barbelow{.}.[[-]+>[.]]--],>,++} - \end{center} - - for which \texttt{jumpRight} should produce the position: - - \begin{center} - \texttt{--[..[[-]+>[.]]--]\barbelow{,}>,++} - \end{center} - - It is also possible that the position returned by \texttt{jumpRight} or - \texttt{jumpLeft} is outside the string in cases where there are - no matching brackets. For example + 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{--[\barbelow{.}.[[-]+>[.]]--,>,++} - \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad - \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}} + \texttt{List((6,5), (5,6))} \end{center} - \hfill[1 Mark] + \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.\hfill[2 Marks] +\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.}\bigskip + -\item[(2c)] Write a recursive function \texttt{run} that executes a - brainf*** program. It takes a program, a program counter, a memory - pointer and a memory as arguments. If the program counter is outside - the program string, the execution stops and \texttt{run} returns the - memory. If the program counter is inside the string, it reads the - corresponding character and updates the program counter \texttt{pc}, - memory pointer \texttt{mp} and memory \texttt{mem} according to the - rules shown in Figure~\ref{comms}. It then calls recursively - \texttt{run} with the updated data. +\subsubsection*{Tasks (file knight2.scala)} + +\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: - Write another function \texttt{start} that calls \texttt{run} with a - given brainfu** program and memory, and the program counter and memory pointer - set to~$0$. Like \texttt{run} it returns the memory after the execution - of the program finishes. You can test your brainf**k interpreter with the - Sierpinski triangle or the Hello world programs or have a look at + \[ + \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} + \] - \begin{center} - \url{https://esolangs.org/wiki/Brainfuck} - \end{center}\hfill[2 Marks] + \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]}. 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] - \begin{figure}[p] - \begin{center} - \begin{tabular}{|@{}p{0.8cm}|l|} - \hline - \hfill\texttt{'>'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & $\texttt{mp} + 1$\\ - $\bullet$ & \texttt{mem} unchanged - \end{tabular}\\\hline - \hfill\texttt{'<'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & $\texttt{mp} - 1$\\ - $\bullet$ & \texttt{mem} unchanged - \end{tabular}\\\hline - \hfill\texttt{'+'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & $\texttt{mp}$ unchanged\\ - $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) + 1}\\ - \end{tabular}\\\hline - \hfill\texttt{'-'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & $\texttt{mp}$ unchanged\\ - $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) - 1}\\ - \end{tabular}\\\hline - \hfill\texttt{'.'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\ - $\bullet$ & print out \,\texttt{mem(mp)} as a character\\ - \end{tabular}\\\hline - \hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & $\texttt{mp}$ unchanged\\ - $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\ - \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}} - \end{tabular}\\\hline - \hfill\texttt{'['} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - \multicolumn{2}{@{}l}{if \texttt{mem(mp) == 0} then}\\ - $\bullet$ & $\texttt{pc = jumpRight(prog, pc + 1, 0)}$\\ - $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\ - \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) != 0} then}\\ - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\ - \end{tabular} - \\\hline - \hfill\texttt{']'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - \multicolumn{2}{@{}l}{if \texttt{mem(mp) != 0} then}\\ - $\bullet$ & $\texttt{pc = jumpLeft(prog, pc - 1, 0)}$\\ - $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\ - \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\ - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\ - \end{tabular}\\\hline - any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & \texttt{mp} and \texttt{mem} unchanged - \end{tabular}\\ - \hline - \end{tabular} - \end{center} - \caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc}, - memory pointer \texttt{mp} and memory \texttt{mem}.\label{comms}} - \end{figure} -\end{itemize}\bigskip +\item[(5)] Implement a \texttt{first\_tour} function that uses the + \texttt{first}-function from (2a), and searches recursively for a 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 + +\noindent +\textbf{Hints:} a useful list function: \texttt{.filter(..)} filters a +list according to a boolean function; a useful option function: +\texttt{.isDefined} returns true, if an option is \texttt{Some(..)}; +anonymous functions can be constructed using \texttt{(x:Int) => ...}, +this functions takes an \texttt{Int} as an argument. + + +%%\newpage +\subsection*{Part 2 (3 Marks)} + +As you should have seen in Part 1, 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 heuristic, called \emph{Warnsdorf's +Rule} that can speed up finding a tour. This heuristic 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. + +\subsubsection*{Tasks (file knight3.scala)} + +\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 the + 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\_heuristic} + function that searches for a + \textbf{closed} tour on a $6\times 6$ board. It should use the + \texttt{first}-function from (4) and tries out onward moves according to + the \texttt{ordered\_moves} function from (3a). 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\_heuristic} function + for boards up to + $40\times 40$. It is the same function as in (7) but searches for + tours (not just closed tours). You have to be careful to write a + tail-recursive function of the \texttt{first\_tour\_heuristic} function + otherwise you will get problems with stack-overflows.\\ + \mbox{}\hfill[1 Mark] +\end{itemize} +\bigskip \end{document} - %%% Local Variables: %%% mode: latex %%% TeX-master: t