
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




