79 % BF IDE

    10 \setchessboard{smallboard,

    80 % https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5

    11                zero,

    12                showmover=false,

    13                boardfontencoding=LSBC4,

    14                hlabelformat=\arabic{ranklabel},

    15                vlabelformat=\arabic{filelabel}}

    16 

    17 \mbox{}\\[-18mm]\mbox{}

    18 

    19 \section*{Coursework 7 (Scala)}

    20 

    21 This coursework is worth 10\%. It is about searching and

    22 backtracking. The first part is due on 29 November at 11pm; the

    23 second, more advanced part, is due on 20 December at 11pm. You are

    24 asked to implement Scala programs that solve various versions of the

    25 \textit{Knight's Tour Problem} on a chessboard. Note the second, more

    26 advanced, part might include material you have not yet seen in the

    27 first two lectures. \bigskip

    28 

    29 \IMPORTANT{}

    30 Also note that the running time of each part will be restricted to a

    31 maximum of 360 seconds on my laptop: If you calculate a result once,

    32 try to avoid to calculate the result again. Feel free to copy any code

    33 you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and

    34 \texttt{knight3.scala}.

    35 

    36 \DISCLAIMER{}

    37 

    38 \subsection*{Background}

    39 

    40 The \textit{Knight's Tour Problem} is about finding a tour such that

    41 the knight visits every field on an $n\times n$ chessboard once. For

    42 example on a $5\times 5$ chessboard, a knight's tour is:

    43 

    44 \chessboard[maxfield=d4, 

    45             pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},

    46             text = \small 24, markfield=Z4,

    47             text = \small 11, markfield=a4,

    48             text = \small  6, markfield=b4,

    49             text = \small 17, markfield=c4,

    50             text = \small  0, markfield=d4,

    51             text = \small 19, markfield=Z3,

    52             text = \small 16, markfield=a3,

    53             text = \small 23, markfield=b3,

    54             text = \small 12, markfield=c3,

    55             text = \small  7, markfield=d3,

    56             text = \small 10, markfield=Z2,

    57             text = \small  5, markfield=a2,

    58             text = \small 18, markfield=b2,

    59             text = \small  1, markfield=c2,

    60             text = \small 22, markfield=d2,

    61             text = \small 15, markfield=Z1,

    62             text = \small 20, markfield=a1,

    63             text = \small  3, markfield=b1,

    64             text = \small  8, markfield=c1,

    65             text = \small 13, markfield=d1,

    66             text = \small  4, markfield=Z0,

    67             text = \small  9, markfield=a0,

    68             text = \small 14, markfield=b0,

    69             text = \small 21, markfield=c0,

    70             text = \small  2, markfield=d0

    71            ]

    72            

    73 \noindent

    74 This tour starts in the right-upper corner, then moves to field

    75 $(3,2)$, then $(4,0)$ and so on. There are no knight's tours on

    76 $2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every

    77 bigger board there is. 

    78 

    79 A knight's tour is called \emph{closed}, if the last step in the tour

    80 is within a knight's move to the beginning of the tour. So the above

    81 knight's tour is \underline{not} closed because the last

    82 step on field $(0, 4)$ is not within the reach of the first step on

    83 $(4, 4)$. It turns out there is no closed knight's tour on a $5\times

    84 5$ board. But there are on a $6\times 6$ board and on bigger ones, for

    85 example

    86 

    87 \chessboard[maxfield=e5, 

    88             pgfstyle={[base,at={\pgfpoint{0pt}{-0.5ex}}]text},

    89             text = \small 10, markfield=Z5,

    90             text = \small  5, markfield=a5,

    91             text = \small 18, markfield=b5,

    92             text = \small 25, markfield=c5,

    93             text = \small 16, markfield=d5,

    94             text = \small  7, markfield=e5,

    95             text = \small 31, markfield=Z4,

    96             text = \small 26, markfield=a4,

    97             text = \small  9, markfield=b4,

    98             text = \small  6, markfield=c4,

    99             text = \small 19, markfield=d4,

   100             text = \small 24, markfield=e4,

   101             % 4  11  30  17   8  15 

   102             text = \small  4, markfield=Z3,

   103             text = \small 11, markfield=a3,

   104             text = \small 30, markfield=b3,

   105             text = \small 17, markfield=c3,

   106             text = \small  8, markfield=d3,

   107             text = \small 15, markfield=e3,

   108             %29  32  27   0  23  20 

   109             text = \small 29, markfield=Z2,

   110             text = \small 32, markfield=a2,

   111             text = \small 27, markfield=b2,

   112             text = \small  0, markfield=c2,

   113             text = \small 23, markfield=d2,

   114             text = \small 20, markfield=e2,

   115             %12   3  34  21  14   1 

   116             text = \small 12, markfield=Z1,

   117             text = \small  3, markfield=a1,

   118             text = \small 34, markfield=b1,

   119             text = \small 21, markfield=c1,

   120             text = \small 14, markfield=d1,

   121             text = \small  1, markfield=e1,

   122             %33  28  13   2  35  22 

   123             text = \small 33, markfield=Z0,

   124             text = \small 28, markfield=a0,

   125             text = \small 13, markfield=b0,

   126             text = \small  2, markfield=c0,

   127             text = \small 35, markfield=d0,

   128             text = \small 22, markfield=e0,

   129             vlabel=false,

   130             hlabel=false

   131            ]

   132 

   133 

   134 \noindent

   135 where the 35th move can join up again with the 0th move.

   136 

   137 If you cannot remember how a knight moves in chess, or never played

   138 chess, below are all potential moves indicated for two knights, one on

   139 field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):

   140 

   141 

   142 \chessboard[maxfield=g7,

   143             color=blue!50,

   144             linewidth=0.2em,

   145             shortenstart=0.5ex,

   146             shortenend=0.5ex,

   147             markstyle=cross,

   148             markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},

   149             color=red!50,

   150             markfields={f5, e6},

   151             setpieces={Ng7, Nb2}]

   152 

   153 

   154 \noindent

   155 \textbf{Hints:} useful list functions: \texttt{.contains(..)} checks

   156 whether an element is in a list, \texttt{.flatten} turns a list of

   157 lists into just a list, \texttt{\_::\_} puts an element on the head of

   158 the list, \texttt{.head} gives you the first element of a list (make

   159 sure the list is not \texttt{Nil}).

   160 

   161 \noindent

   162 \textbf{Hints:} a useful list function: \texttt{.sortBy} sorts a list

   163 according to a component given by the function; a function can be

   164 tested to be tail recursive by annotation \texttt{@tailrec}, which is

   165 made available by importing \texttt{scala.annotation.tailrec}.

   166 

   167             

   168 \subsection*{Part 1 (7 Marks)}

   169 

   170 You are asked to implement the knight's tour problem such that the

   171 dimension of the board can be changed.  Therefore most functions will

   172 take the dimension of the board as an argument.  The fun with this

   173 problem is that even for small chessboard dimensions it has already an

   174 incredibly large search space---finding a tour is like finding a

   175 needle in a haystack. In the first task we want to see how far we get

   176 with exhaustively exploring the complete search space for small

   177 chessboards.\medskip

   178 

   179 \noindent

   180 Let us first fix the basic datastructures for the implementation.  The

   181 board dimension is an integer (we will never go beyond board sizes of

   182 $40 \times 40$).  A \emph{position} (or field) on the chessboard is

   183 a pair of integers, like $(0, 0)$. A \emph{path} is a list of

   184 positions. The first (or 0th move) in a path is the last element in

   185 this list; and the last move in the path is the first element. For

   186 example the path for the $5\times 5$ chessboard above is represented

   187 by

   188 

   189 \[

   190 \texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,

   191   $\underbrace{\texttt{(2, 3)}}_{23}$, ...,

   192   $\underbrace{\texttt{(3, 2)}}_1$, $\underbrace{\texttt{(4, 4)}}_0$)}

   193 \]

   194 

   195 \noindent

   196 Suppose the dimension of a chessboard is $n$, then a path is a

   197 \emph{tour} if the length of the path is $n \times n$, each element

   198 occurs only once in the path, and each move follows the rules of how a

   199 knight moves (see above for the rules).

   200 

   201 

   202 \subsubsection*{Tasks (file knight1.scala)}

   203 

   204 \begin{itemize}

   205 \item[(1)] Implement an \texttt{is\_legal} function that takes a

   206   dimension, a path and a position as arguments and tests whether the

   207   position is inside the board and not yet element in the

   208   path. \hfill[1 Mark]

   209 

   210 \item[(2)] Implement a \texttt{legal\_moves} function that calculates for a

   211   position all legal onward moves. If the onward moves are

   212   placed on a circle, you should produce them starting from

   213   ``12-o'clock'' following in clockwise order.  For example on an

   214   $8\times 8$ board for a knight at position $(2, 2)$ and otherwise

   215   empty board, the legal-moves function should produce the onward

   216   positions in this order:

   217 

   218   \begin{center}

   219   \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}

   220   \end{center}

   221 

   222   If the board is not empty, then maybe some of the moves need to be

   223   filtered out from this list.  For a knight on field $(7, 7)$ and an

   224   empty board, the legal moves are

   225 

   226   \begin{center}

   227   \texttt{List((6,5), (5,6))}

   228   \end{center}

   229   \mbox{}\hfill[1 Mark]

   230 

   231 \item[(3)] Implement two recursive functions (\texttt{count\_tours} and

   232   \texttt{enum\_tours}). They each take a dimension and a path as

   233   arguments. They exhaustively search for tours starting

   234   from the given path. The first function counts all possible 

   235   tours (there can be none for certain board sizes) and the second

   236   collects all tours in a list of paths.\hfill[2 Marks]

   237 \end{itemize}

   238 

   239 \noindent \textbf{Test data:} For the marking, the functions in (3)

   240 will be called with board sizes up to $5 \times 5$. If you search

   241 for tours on a $5 \times 5$ board starting only from field $(0, 0)$,

   242 there are 304 of tours. If you try out every field of a $5 \times

   243 5$-board as a starting field and add up all tours, you obtain

   244 1728. A $6\times 6$ board is already too large to be searched

   245 exhaustively.\footnote{For your interest, the number of tours on

   246   $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,

   247   19591828170979904, respectively.}\bigskip

   248 

   249 

   250 

   251 \subsubsection*{Tasks (file knight2.scala)}

   252 

   253 \begin{itemize}

   254 \item[(4)] Implement a \texttt{first}-function. This function takes a list of

   255   positions and a function $f$ as arguments; $f$ is the name we give to

   256   this argument). The function $f$ takes a position as argument and

   257   produces an optional path. So $f$'s type is \texttt{Pos =>

   258     Option[Path]}. The idea behind the \texttt{first}-function is as follows:

   259 

   260   \[

   261   \begin{array}{lcl}

   262   \textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\  

   263   \textit{first}(x\!::\!xs, f) & \dn & \begin{cases}

   264     f(x) & \textit{if}\;f(x) \not=\texttt{None}\\

   265     \textit{first}(xs, f) & \textit{otherwise}\\

   266                               \end{cases}

   267   \end{array}

   268   \]

   269 

   270   \noindent That is, we want to find the first position where the

   271   result of $f$ is not \texttt{None}, if there is one. Note that

   272   `inside' \texttt{first}, you do not (need to) know anything about

   273   the argument $f$ except its type, namely \texttt{Pos =>

   274     Option[Path]}. There is one additional point however you should

   275   take into account when implementing \texttt{first}: you will need to

   276   calculate what the result of $f(x)$ is; your code should do this

   277   only \textbf{once} and for as \textbf{few} elements in the list as

   278   possible! Do not calculate $f(x)$ for all elements and then see which 

   279   is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]

    82 \section*{Coursework 8 (Regular Expressions and Brainf***)}

   281 \item[(5)] Implement a \texttt{first\_tour} function that uses the

    83 

   282   \texttt{first}-function from (2a), and searches recursively for a tour.

    84 This coursework is worth 10\%. It is about regular expressions,

   283   As there might not be such a tour at all, the \texttt{first\_tour} function

    85 pattern matching and an interpreter. The first part is due on 30

   284   needs to return a value of type

    86 November at 11pm; the second, more advanced part, is due on 21

   285   \texttt{Option[Path]}.\\\mbox{}\hfill[1 Mark]

    87 December at 11pm. In the first part, you are asked to implement a

   286 \end{itemize}

    88 regular expression matcher based on derivatives of regular

   287 

    89 expressions. The reason is that regular expression matching in Java

   288 \noindent

    90 and Python can sometimes be extremely slow. The advanced part is about

   289 \textbf{Testing:} The \texttt{first\_tour} function will be called with board

    91 an interpreter for a very simple programming language.\bigskip

   290 sizes of up to $8 \times 8$.

    92 

   291 \bigskip

    93 \IMPORTANT{}

   292 

    94 

   293 \noindent

    95 \noindent

   294 \textbf{Hints:} a useful list function: \texttt{.filter(..)} filters a

    96 Also note that the running time of each part will be restricted to a

   295 list according to a boolean function; a useful option function:

    97 maximum of 360 seconds on my laptop.

   296 \texttt{.isDefined} returns true, if an option is \texttt{Some(..)};

    98 

   297 anonymous functions can be constructed using \texttt{(x:Int) => ...},

    99 \DISCLAIMER{}

   298 this functions takes an \texttt{Int} as an argument.

   100 

   299 

   101 

   300 

   102 \subsection*{Part 1 (6 Marks)}

   301 %%\newpage

   103 

   302 \subsection*{Part 2 (3 Marks)}

   104 The task is to implement a regular expression matcher that is based on

   303 

   105 derivatives of regular expressions. Most of the functions are defined by

   304 As you should have seen in Part 1, a naive search for tours beyond

   106 recursion over regular expressions and can be elegantly implemented

   305 $8 \times 8$ boards and also searching for closed tours even on small

   107 using Scala's pattern-matching. The implementation should deal with the

   306 boards takes too much time. There is a heuristic, called \emph{Warnsdorf's

   108 following regular expressions, which have been predefined in the file

   307 Rule} that can speed up finding a tour. This heuristic states that a

   109 \texttt{re.scala}:

   308 knight is moved so that it always proceeds to the field from which the

   110 

   309 knight will have the \underline{fewest} onward moves.  For example for

   111 \begin{center}

   310 a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible

   112 \begin{tabular}{lcll}

   311 onward moves, namely 2.

   113   $r$ & $::=$ & $\ZERO$     & cannot match anything\\

   312 

   114       &   $|$ & $\ONE$      & can only match the empty string\\

   313 \chessboard[maxfield=g7,

   115       &   $|$ & $c$         & can match a single character (in this case $c$)\\

   314             pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},

   116       &   $|$ & $r_1 + r_2$ & can match a string either with $r_1$ or with $r_2$\\

   315             text = \small 3, markfield=Z5,

   117   &   $|$ & $r_1\cdot r_2$ & can match the first part of a string with $r_1$ and\\

   316             text = \small 7, markfield=b5,

   118           &  & & then the second part with $r_2$\\

   317             text = \small 7, markfield=c4,

   119       &   $|$ & $r^*$       & can match zero or more times $r$\\

   318             text = \small 7, markfield=c2,

   120 \end{tabular}

   319             text = \small 5, markfield=b1,

   121 \end{center}

   320             text = \small 2, markfield=Z1,

   122 

   321             setpieces={Na3}]

   123 \noindent 

   322 

   124 Why? Knowing how to match regular expressions and strings will let you

   323 \noindent

   125 solve a lot of problems that vex other humans. Regular expressions are

   324 Warnsdorf's Rule states that the moves on the board above should be

   126 one of the fastest and simplest ways to match patterns in text, and

   325 tried in the order

   127 are endlessly useful for searching, editing and analysing data in all

   326 

   128 sorts of places (for example analysing network traffic in order to

   327 \[

   129 detect security breaches). However, you need to be fast, otherwise you

   328 (0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)

   130 will stumble over problems such as recently reported at

   329 \]

   131 

   330 

   132 {\small

   331 \noindent

   332 Whenever there are ties, the corresponding onward moves can be in any

   333 order.  When calculating the number of onward moves for each field, we

   334 do not count moves that revisit any field already visited.

   335 

   336 \subsubsection*{Tasks (file knight3.scala)}

   337 

   134 \item[$\bullet$] \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}

   339 \item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of

   135 \item[$\bullet$] \url{https://vimeo.com/112065252}

   340   onward moves like in (2) but orders them according to the

   136 \item[$\bullet$] \url{http://davidvgalbraith.com/how-i-fixed-atom/}  

   341   Warnsdorf’s Rule. That means moves with the fewest legal onward moves

   137 \end{itemize}}

   342   should come first (in order to be tried out first). \hfill[1 Mark]

   138 

   139 \subsubsection*{Tasks (file re.scala)}

   140 

   141 The file \texttt{re.scala} has already a definition for regular

   142 expressions and also defines some handy shorthand notation for

   143 regular expressions. The notation in this document matches up

   144 with the code in the file as follows:

   145 

   146 \begin{center}

   147   \begin{tabular}{rcl@{\hspace{10mm}}l}

   148     & & code: & shorthand:\smallskip \\ 

   149   $\ZERO$ & $\mapsto$ & \texttt{ZERO}\\

   150   $\ONE$  & $\mapsto$ & \texttt{ONE}\\

   151   $c$     & $\mapsto$ & \texttt{CHAR(c)}\\

   152   $r_1 + r_2$ & $\mapsto$ & \texttt{ALT(r1, r2)} & \texttt{r1 | r2}\\

   153   $r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)} & \texttt{r1 $\sim$ r2}\\

   154   $r^*$ & $\mapsto$ &  \texttt{STAR(r)} & \texttt{r.\%}

   155 \end{tabular}    

   156 \end{center}  

   157 

   158 

   159 \begin{itemize}

   160 \item[(1a)] Implement a function, called \textit{nullable}, by

   161   recursion over regular expressions. This function tests whether a

   162   regular expression can match the empty string. This means given a

   163   regular expression it either returns true or false. The function

   164   \textit{nullable}

   165   is defined as follows:

   166 

   167 \begin{center}

   168 \begin{tabular}{lcl}

   169 $\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\

   170 $\textit{nullable}(\ONE)$  & $\dn$ & $\textit{true}$\\

   171 $\textit{nullable}(c)$     & $\dn$ & $\textit{false}$\\

   172 $\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\

   173 $\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\

   174 $\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\

   175 \end{tabular}

   176 \end{center}~\hfill[1 Mark]

   177 

   178 \item[(1b)] Implement a function, called \textit{der}, by recursion over

   179   regular expressions. It takes a character and a regular expression

   180   as arguments and calculates the derivative regular expression according

   181   to the rules:

   182 

   183 \begin{center}

   184 \begin{tabular}{lcl}

   185 $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\

   186 $\textit{der}\;c\;(\ONE)$  & $\dn$ & $\ZERO$\\

   187 $\textit{der}\;c\;(d)$     & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\

   188 $\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\

   189 $\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\

   190       & & $\textit{then}\;((\textit{der}\;c\;r_1)\cdot r_2) + (\textit{der}\;c\;r_2)$\\

   191       & & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\

   192 $\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\

   193 \end{tabular}

   194 \end{center}

   195 

   196 For example given the regular expression $r = (a \cdot b) \cdot c$, the derivatives

   197 w.r.t.~the characters $a$, $b$ and $c$ are

   198 

   199 \begin{center}

   200   \begin{tabular}{lcll}

   201     $\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & ($= r'$)\\

   202     $\textit{der}\;b\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$\\

   203     $\textit{der}\;c\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$

   204   \end{tabular}

   205 \end{center}

   206 

   207 Let $r'$ stand for the first derivative, then taking the derivatives of $r'$

   208 w.r.t.~the characters $a$, $b$ and $c$ gives

   209 

   210 \begin{center}

   211   \begin{tabular}{lcll}

   212     $\textit{der}\;a\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ \\

   213     $\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & ($= r''$)\\

   214     $\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$

   215   \end{tabular}

   216 \end{center}

   217 

   218 One more example: Let $r''$ stand for the second derivative above,

   219 then taking the derivatives of $r''$ w.r.t.~the characters $a$, $b$

   220 and $c$ gives

   221 

   222 \begin{center}

   223   \begin{tabular}{lcll}

   224     $\textit{der}\;a\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$ \\

   225     $\textit{der}\;b\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$\\

   226     $\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ &

   227     (is $\textit{nullable}$)                      

   228   \end{tabular}

   229 \end{center}

   230 

   231 Note, the last derivative can match the empty string, that is it is \textit{nullable}.\\

   232 \mbox{}\hfill\mbox{[1 Mark]}

   233 

   234 \item[(1c)] Implement the function \textit{simp}, which recursively

   235   traverses a regular expression from the inside to the outside, and

   236   on the way simplifies every regular expression on the left (see

   237   below) to the regular expression on the right, except it does not

   238   simplify inside ${}^*$-regular expressions.

   239 

   240   \begin{center}

   241 \begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}

   242 $r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ 

   243 $\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ 

   244 $r \cdot \ONE$ & $\mapsto$ & $r$\\ 

   245 $\ONE \cdot r$ & $\mapsto$ & $r$\\ 

   246 $r + \ZERO$ & $\mapsto$ & $r$\\ 

   247 $\ZERO + r$ & $\mapsto$ & $r$\\ 

   248 $r + r$ & $\mapsto$ & $r$\\ 

   249 \end{tabular}

   250   \end{center}

   251 

   252   For example the regular expression

   253   \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\]

   254 

   255   simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be

   256   seen as trees and there are several methods for traversing

   257   trees. One of them corresponds to the inside-out traversal, which is

   258   sometimes also called post-order traversal. Furthermore,

   259   remember numerical expressions from school times: there you had expressions

   260   like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$

   261   and simplification rules that looked very similar to rules

   262   above. You would simplify such numerical expressions by replacing

   263   for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then

   264   look whether more rules are applicable. If you organise the

   265   simplification in an inside-out fashion, it is always clear which

   266   rule should be applied next.\hfill[2 Marks]

   267 

   268 \item[(1d)] Implement two functions: The first, called \textit{ders},

   269   takes a list of characters and a regular expression as arguments, and

   270   builds the derivative w.r.t.~the list as follows:

   271 

   272 \begin{center}

   273 \begin{tabular}{lcl}

   274 $\textit{ders}\;(Nil)\;r$ & $\dn$ & $r$\\

   275   $\textit{ders}\;(c::cs)\;r$  & $\dn$ &

   276     $\textit{ders}\;cs\;(\textit{simp}(\textit{der}\;c\;r))$\\

   277 \end{tabular}

   278 \end{center}

   279 

   280 Note that this function is different from \textit{der}, which only

   281 takes a single character.

   282 

   283 The second function, called \textit{matcher}, takes a string and a

   284 regular expression as arguments. It builds first the derivatives

   285 according to \textit{ders} and after that tests whether the resulting

   286 derivative regular expression can match the empty string (using

   287 \textit{nullable}).  For example the \textit{matcher} will produce

   288 true for the regular expression $(a\cdot b)\cdot c$ and the string

   289 $abc$, but false if you give it the string $ab$. \hfill[1 Mark]

   290 

   291 \item[(1e)] Implement a function, called \textit{size}, by recursion

   292   over regular expressions. If a regular expression is seen as a tree,

   293   then \textit{size} should return the number of nodes in such a

   294   tree. Therefore this function is defined as follows:

   295 

   296 \begin{center}

   297 \begin{tabular}{lcl}

   298 $\textit{size}(\ZERO)$ & $\dn$ & $1$\\

   299 $\textit{size}(\ONE)$  & $\dn$ & $1$\\

   300 $\textit{size}(c)$     & $\dn$ & $1$\\

   301 $\textit{size}(r_1 + r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\

   302 $\textit{size}(r_1 \cdot r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\

   303 $\textit{size}(r^*)$ & $\dn$ & $1 + \textit{size}(r)$\\

   304 \end{tabular}

   305 \end{center}

   306 

   307 You can use \textit{size} in order to test how much the `evil' regular

   308 expression $(a^*)^* \cdot b$ grows when taking successive derivatives

   309 according the letter $a$ without simplification and then compare it to

   310 taking the derivative, but simplify the result.  The sizes

   311 are given in \texttt{re.scala}. \hfill[1 Mark]

   312 \end{itemize}

   313 

   314 \subsection*{Background}

   315 

   316 Although easily implementable in Scala, the idea behind the derivative

   317 function might not so easy to be seen. To understand its purpose

   318 better, assume a regular expression $r$ can match strings of the form

   319 $c\!::\!cs$ (that means strings which start with a character $c$ and have

   320 some rest, or tail, $cs$). If you take the derivative of $r$ with

   321 respect to the character $c$, then you obtain a regular expression

   322 that can match all the strings $cs$.  In other words, the regular

   323 expression $\textit{der}\;c\;r$ can match the same strings $c\!::\!cs$

   324 that can be matched by $r$, except that the $c$ is chopped off.

   325 

   326 Assume now $r$ can match the string $abc$. If you take the derivative

   327 according to $a$ then you obtain a regular expression that can match

   328 $bc$ (it is $abc$ where the $a$ has been chopped off). If you now

   329 build the derivative $\textit{der}\;b\;(\textit{der}\;a\;r)$ you

   330 obtain a regular expression that can match the string $c$ (it is $bc$

   331 where $b$ is chopped off). If you finally build the derivative of this

   332 according $c$, that is

   333 $\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r))$, you obtain

   334 a regular expression that can match the empty string. You can test

   335 whether this is indeed the case using the function nullable, which is

   336 what your matcher is doing.

   337 

   338 The purpose of the $\textit{simp}$ function is to keep the regular

   339 expressions small. Normally the derivative function makes the regular

   340 expression bigger (see the SEQ case and the example in (1b)) and the

   341 algorithm would be slower and slower over time. The $\textit{simp}$

   342 function counters this increase in size and the result is that the

   343 algorithm is fast throughout.  By the way, this algorithm is by Janusz

   344 Brzozowski who came up with the idea of derivatives in 1964 in his PhD

   345 thesis.

   346 

   347 \begin{center}\small

   348 \url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)}

   349 \end{center}

   350 

   351 

   352 If you want to see how badly the regular expression matchers do in

   353 Java\footnote{Version 8 and below; Version 9 does not seem to be as

   354   catastrophic, but still worse than the regular expression matcher

   355 based on derivatives.} and in Python with the `evil' regular

   356 expression $(a^*)^*\cdot b$, then have a look at the graphs below (you

   357 can try it out for yourself: have a look at the file

   358 \texttt{catastrophic.java} and \texttt{catastrophic.py} on

   359 KEATS). Compare this with the matcher you have implemented. How long

   360 can the string of $a$'s be in your matcher and still stay within the

   361 30 seconds time limit?

   362 

   363 \begin{center}

   364 \begin{tabular}{@{}cc@{}}

   365 \multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings 

   366            $\underbrace{a\ldots a}_{n}$}\bigskip\\

   368 \begin{tikzpicture}

   344 \item[(7)] Implement a \texttt{first\_closed-tour\_heuristic}

   369 \begin{axis}[

   345   function that searches for a

   370     xlabel={$n$},

   346   \textbf{closed} tour on a $6\times 6$ board. It should use the

   371     x label style={at={(1.05,0.0)}},

   347   \texttt{first}-function from (4) and tries out onward moves according to

   372     ylabel={time in secs},

   348   the \texttt{ordered\_moves} function from (3a). It is more likely to find

   373     y label style={at={(0.06,0.5)}},

   349   a solution when started in the middle of the board (that is

   374     enlargelimits=false,

   350   position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]

   375     xtick={0,5,...,30},

   351 

   376     xmax=33,

   352 \item[(8)] Implement a \texttt{first\_tour\_heuristic} function

   377     ymax=45,

   353   for boards up to

   378     ytick={0,5,...,40},

   354   $40\times 40$.  It is the same function as in (7) but searches for

   379     scaled ticks=false,

   355   tours (not just closed tours). You have to be careful to write a

   380     axis lines=left,

   356   tail-recursive function of the \texttt{first\_tour\_heuristic} function

   381     width=6cm,

   357   otherwise you will get problems with stack-overflows.\\

   382     height=5.5cm, 

   358   \mbox{}\hfill[1 Mark]

   383     legend entries={Python, Java 8},  

   359 \end{itemize}  

   384     legend pos=north west]

   360 \bigskip

   385 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};

   386 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};

   387 \end{axis}

   388 \end{tikzpicture}

   389   & 

   390 \begin{tikzpicture}

   391 \begin{axis}[

   392     xlabel={$n$},

   393     x label style={at={(1.05,0.0)}},

   394     ylabel={time in secs},

   395     y label style={at={(0.06,0.5)}},

   396     %enlargelimits=false,

   397     %xtick={0,5000,...,30000},

   398     xmax=65000,

   399     ymax=45,

   400     ytick={0,5,...,40},

   401     scaled ticks=false,

   402     axis lines=left,

   403     width=6cm,

   404     height=5.5cm, 

   405     legend entries={Java 9},  

   406     legend pos=north west]

   407 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};

   408 \end{axis}

   409 \end{tikzpicture}

   410 \end{tabular}  

   411 \end{center}

   412 \newpage

   413 

   414 \subsection*{Part 2 (4 Marks)}

   415 

   416 Coming from Java or C++, you might think Scala is a quite esoteric

   417 programming language.  But remember, some serious companies have built

   418 their business on

   419 Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}

   420 And there are far, far more esoteric languages out there. One is

   421 called \emph{brainf***}. You are asked in this part to implement an

   422 interpreter for this language.

   423 

   424 Urban M\"uller developed brainf*** in 1993.  A close relative of this

   425 language was already introduced in 1964 by Corado B\"ohm, an Italian

   426 computer pioneer, who unfortunately died a few months ago. The main

   427 feature of brainf*** is its minimalistic set of instructions---just 8

   428 instructions in total and all of which are single characters. Despite

   429 the minimalism, this language has been shown to be Turing

   430 complete\ldots{}if this doesn't ring any bell with you: it roughly

   431 means that every algorithm we know can, in principle, be implemented in

   432 brainf***. It just takes a lot of determination and quite a lot of

   433 memory resources. Some relatively sophisticated sample programs in

   434 brainf*** are given in the file \texttt{bf.scala}.\bigskip

   435 

   436 \noindent

   437 As mentioned above, brainf*** has 8 single-character commands, namely

   438 \texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'},

   439 \texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is

   440 considered a comment.  Brainf*** operates on memory cells containing

   441 integers. For this it uses a single memory pointer that points at each

   442 stage to one memory cell. This pointer can be moved forward by one

   443 memory cell by using the command \texttt{'>'}, and backward by using

   444 \texttt{'<'}. The commands \texttt{'+'} and \texttt{'-'} increase,

   445 respectively decrease, by 1 the content of the memory cell to which

   446 the memory pointer currently points to. The commands for input/output

   447 are \texttt{','} and \texttt{'.'}. Output works by reading the content

   448 of the memory cell to which the memory pointer points to and printing

   449 it out as an ASCII character. Input works the other way, taking some

   450 user input and storing it in the cell to which the memory pointer

   451 points to. The commands \texttt{'['} and \texttt{']'} are looping

   452 constructs. Everything in between \texttt{'['} and \texttt{']'} is

   453 repeated until a counter (memory cell) reaches zero.  A typical

   454 program in brainf*** looks as follows:

   455 

   456 \begin{center}

   457 \begin{verbatim}

   458  ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++

   459  ..+++.>>.<-.<.+++.------.--------.>>+.>++.

   460 \end{verbatim}

   461 \end{center}  

   462 

   463 \noindent

   464 This one prints out Hello World\ldots{}obviously. 

   465 

   466 \subsubsection*{Tasks (file bf.scala)}

   467 

   468 \begin{itemize}

   469 \item[(2a)] Brainf*** memory is represented by a \texttt{Map} from

   470   integers to integers. The empty memory is represented by

   471   \texttt{Map()}, that is nothing is stored in the

   472   memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly stores \texttt{1} at

   473   memory location \texttt{0}; at \texttt{2} it stores \texttt{3}. The

   474   convention is that if we query the memory at a location that is

   475   \emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write

   476   a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and

   477   a memory pointer (an \texttt{Int}) as argument, and safely reads the

   478   corresponding memory location. If the \texttt{Map} is not defined at

   479   the memory pointer, \texttt{sread} returns \texttt{0}.

   480 

   481   Write another function \texttt{write}, which takes a memory, a

   482   memory pointer and an integer value as argument and updates the

   483   \texttt{Map} with the value at the given memory location. As usual

   484   the \texttt{Map} is not updated `in-place' but a new map is created

   485   with the same data, except the value is stored at the given memory

   486   pointer.\hfill[1 Mark]

   487 

   488 \item[(2b)] Write two functions, \texttt{jumpRight} and

   489   \texttt{jumpLeft} that are needed to implement the loop constructs

   490   of brainf***. They take a program (a \texttt{String}) and a program

   491   counter (an \texttt{Int}) as argument and move right (respectively

   492   left) in the string in order to find the \textbf{matching}

   493   opening/closing bracket. For example, given the following program

   494   with the program counter indicated by an arrow:

   495 

   496   \begin{center}

   497   \texttt{--[\barbelow{.}.+>--],>,++}

   498   \end{center}

   499 

   500   then the matching closing bracket is in 9th position (counting from 0) and

   501   \texttt{jumpRight} is supposed to return the position just after this

   502   

   503   \begin{center}

   504   \texttt{--[..+>--]\barbelow{,}>,++}

   505   \end{center}

   506 

   507   meaning it jumps to after the loop. Similarly, if you are in 8th position

   508   then \texttt{jumpLeft} is supposed to jump to just after the opening

   509   bracket (that is jumping to the beginning of the loop):

   510 

   511   \begin{center}

   512     \texttt{--[..+>-\barbelow{-}],>,++}

   513     \qquad$\stackrel{\texttt{jumpLeft}}{\longrightarrow}$\qquad

   514     \texttt{--[\barbelow{.}.+>--],>,++}

   515   \end{center}

   516 

   517   Unfortunately we have to take into account that there might be

   518   other opening and closing brackets on the `way' to find the

   519   matching bracket. For example in the brainf*** program

   520 

   521   \begin{center}

   522   \texttt{--[\barbelow{.}.[+>]--],>,++}

   523   \end{center}

   524 

   525   we do not want to return the index for the \texttt{'-'} in the 9th

   526   position, but the program counter for \texttt{','} in 12th

   527   position. The easiest to find out whether a bracket is matched is by

   528   using levels (which are the third argument in \texttt{jumpLeft} and

   529   \texttt{jumpLeft}). In case of \texttt{jumpRight} you increase the

   530   level by one whenever you find an opening bracket and decrease by

   531   one for a closing bracket. Then in \texttt{jumpRight} you are looking

   532   for the closing bracket on level \texttt{0}. For \texttt{jumpLeft} you

   533   do the opposite. In this way you can find \textbf{matching} brackets

   534   in strings such as

   535 

   536   \begin{center}

   537   \texttt{--[\barbelow{.}.[[-]+>[.]]--],>,++}

   538   \end{center}

   539 

   540   for which \texttt{jumpRight} should produce the position:

   541 

   542   \begin{center}

   543   \texttt{--[..[[-]+>[.]]--]\barbelow{,}>,++}

   544   \end{center}

   545 

   546   It is also possible that the position returned by \texttt{jumpRight} or

   547   \texttt{jumpLeft} is outside the string in cases where there are

   548   no matching brackets. For example

   549 

   550   \begin{center}

   551   \texttt{--[\barbelow{.}.[[-]+>[.]]--,>,++}

   552   \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad

   553   \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}}

   554   \end{center}

   555   \hfill[1 Mark]

   556 

   557 

   558 \item[(2c)] Write a recursive function \texttt{run} that executes a

   559   brainf*** program. It takes a program, a program counter, a memory

   560   pointer and a memory as arguments. If the program counter is outside

   561   the program string, the execution stops and \texttt{run} returns the

   562   memory. If the program counter is inside the string, it reads the

   563   corresponding character and updates the program counter \texttt{pc},

   564   memory pointer \texttt{mp} and memory \texttt{mem} according to the

   565   rules shown in Figure~\ref{comms}. It then calls recursively

   566   \texttt{run} with the updated data.

   567 

   568   Write another function \texttt{start} that calls \texttt{run} with a

   569   given brainfu** program and memory, and the program counter and memory pointer

   570   set to~$0$. Like \texttt{run} it returns the memory after the execution

   571   of the program finishes. You can test your brainf**k interpreter with the

   572   Sierpinski triangle or the Hello world programs or have a look at

   573 

   574   \begin{center}

   575   \url{https://esolangs.org/wiki/Brainfuck}

   576   \end{center}\hfill[2 Marks]

   577   

   578   \begin{figure}[p]

   579   \begin{center}

   580     \begin{tabular}{|@{}p{0.8cm}|l|}

   581       \hline

   582       \hfill\texttt{'>'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   583                        $\bullet$ & $\texttt{pc} + 1$\\

   584                        $\bullet$ & $\texttt{mp} + 1$\\

   585                        $\bullet$ & \texttt{mem} unchanged

   586                      \end{tabular}\\\hline   

   587       \hfill\texttt{'<'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   588                        $\bullet$ & $\texttt{pc} + 1$\\

   589                        $\bullet$ & $\texttt{mp} - 1$\\

   590                        $\bullet$ & \texttt{mem} unchanged

   591                      \end{tabular}\\\hline   

   592       \hfill\texttt{'+'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   593                        $\bullet$ & $\texttt{pc} + 1$\\

   594                        $\bullet$ & $\texttt{mp}$ unchanged\\

   595                        $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) + 1}\\

   596                      \end{tabular}\\\hline   

   597       \hfill\texttt{'-'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   598                        $\bullet$ & $\texttt{pc} + 1$\\

   599                        $\bullet$ & $\texttt{mp}$ unchanged\\

   600                        $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) - 1}\\

   601                      \end{tabular}\\\hline   

   602       \hfill\texttt{'.'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   603                        $\bullet$ & $\texttt{pc} + 1$\\

   604                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\

   605                        $\bullet$ & print out \,\texttt{mem(mp)} as a character\\

   606                      \end{tabular}\\\hline   

   607       \hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   608                        $\bullet$ & $\texttt{pc} + 1$\\

   609                        $\bullet$ & $\texttt{mp}$ unchanged\\

   610                        $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\

   611                        \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}}

   612                      \end{tabular}\\\hline   

   613       \hfill\texttt{'['} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   614                        \multicolumn{2}{@{}l}{if \texttt{mem(mp) == 0} then}\\

   615                        $\bullet$ & $\texttt{pc = jumpRight(prog, pc + 1, 0)}$\\

   616                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\

   617                        \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) != 0} then}\\

   618                        $\bullet$ & $\texttt{pc} + 1$\\

   619                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\

   620                      \end{tabular}

   621                      \\\hline   

   622       \hfill\texttt{']'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   623                        \multicolumn{2}{@{}l}{if \texttt{mem(mp) != 0} then}\\

   624                        $\bullet$ & $\texttt{pc = jumpLeft(prog, pc - 1, 0)}$\\

   625                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\

   626                        \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\

   627                        $\bullet$ & $\texttt{pc} + 1$\\

   628                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\

   629                      \end{tabular}\\\hline   

   630       any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   631                          $\bullet$ & $\texttt{pc} + 1$\\

   632                          $\bullet$ & \texttt{mp} and \texttt{mem} unchanged

   633                        \end{tabular}\\

   634       \hline                 

   635     \end{tabular}

   636   \end{center}

   637   \caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc},

   638     memory pointer \texttt{mp} and memory \texttt{mem}.\label{comms}}

   639   \end{figure}

   640 \end{itemize}\bigskip