--- a/TAs Tue Nov 20 13:42:32 2018 +0000
+++ b/TAs Tue Nov 20 14:31:14 2018 +0000
@@ -10,28 +10,29 @@
robert.greener@kcl.ac.uk
tania.copocean@kcl.ac.uk
-
+CW6, Part 1 + 2
+ late
+163 => 6 163
+29 => 5 28
+3 => 4 4
+13 => 3 12
+3 => 2 4
+0 => 1 0
+23 => 0 23
+--------
+234 submissions
-daniil.baryshnikov@kcl.ac.uk
- andrew.coles@kcl.ac.uk
- oliver.hohn@kcl.ac.uk
- fahad.ausaf@icloud.com
- fares.alaboud@kcl.ac.uk
- sara.boutamina@kcl.ac.uk
- mark.ormesher@kcl.ac.uk
- clarence.ji@kcl.ac.uk
- andrei.nae_-_stroie@kcl.ac.uk
- alexander.hanbury-Botherway@kcl.ac.uk
- rosen.dangov@kcl.ac.uk
- diana.ghitun@kcl.ac.uk
- andrei.juganaru@kcl.ac.uk
- ainur.makhmet@kcl.ac.uk
scala -Dscala.color
+
+2017 RESULTS
+============
+
+
CW6, Part 1 + 2
late
154 => 6 (155)
--- a/cws/cw02-bak.tex Tue Nov 20 13:42:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,365 +0,0 @@
-\documentclass{article}
-\usepackage{chessboard}
-\usepackage[LSBC4,T1]{fontenc}
-\let\clipbox\relax
-\usepackage{../style}
-\usepackage{disclaimer}
-
-\begin{document}
-
-\setchessboard{smallboard,
- zero,
- showmover=false,
- boardfontencoding=LSBC4,
- hlabelformat=\arabic{ranklabel},
- vlabelformat=\arabic{filelabel}}
-
-\mbox{}\\[-18mm]\mbox{}
-
-\section*{Coursework 7 (Scala, Knight's Tour)}
-
-This coursework is worth 10\%. It is about searching and
-backtracking. The first part is due on 23 November at 11pm; the
-second, more advanced part, is due on 21 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 part
-might include material you have not yet seen in the first two
-lectures. \bigskip
-
-\IMPORTANT{}
-Also note that the running time of each part will be restricted to a
-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*{Background}
-
-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
-The 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.
-
-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
-
-\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
- ]
-
-
-\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):
-
-
-\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 1 (7 Marks)}
-
-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
-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
-
-\[
-\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[(1a)] Implement an \texttt{is\_legal\_move} 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]
-
-\item[(1b)] 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{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}
- \end{center}
-
- 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{List((6,5), (5,6))}
- \end{center}
- \mbox{}\hfill[1 Mark]
-
-\item[(1c)] 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 (1c)
-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
-
-\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}).
-
-\subsubsection*{Tasks (file knight2.scala)}
-
-\begin{itemize}
-\item[(2a)] 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:
-
- \[
- \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}
- \]
-
- \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]
-
-\item[(2b)] 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[2 Marks]
-\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[(3a)] Write a function \texttt{ordered\_moves} that calculates a list of
- onward moves like in (1b) 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[(3b)] 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 (2a) 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[(3c)] Implement a \texttt{first\_tour\_heuristic} function
- for boards up to
- $40\times 40$. It is the same function as in (3b) 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
-
-\noindent
-\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}.
-
-
-
-\end{document}
-
-%%% Local Variables:
-%%% mode: latex
-%%% TeX-master: t
-%%% End:
Binary file cws/cw03.pdf has changed
--- 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
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw04-new.tex Tue Nov 20 14:31:14 2018 +0000
@@ -0,0 +1,651 @@
+\documentclass{article}
+\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***)}
+
+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
+
+\IMPORTANT{}
+
+\noindent
+Also note that the running time of each part will be restricted to a
+maximum of 360 seconds on my laptop.
+
+\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.
+
+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.
+
+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}
+
+
+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?
+
+\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
+
+\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
+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:
+
+\begin{center}
+\begin{verbatim}
+ ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+ ..+++.>>.<-.<.+++.------.--------.>>+.>++.
+\end{verbatim}
+\end{center}
+
+\noindent
+This one prints out Hello World\ldots{}obviously.
+
+\subsubsection*{Tasks (file bf.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}.
+
+ 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:
+
+ \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{,}>,++}
+ \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
+
+ \begin{center}
+ \texttt{--[\barbelow{.}.[[-]+>[.]]--,>,++}
+ \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad
+ \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}}
+ \end{center}
+ \hfill[1 Mark]
+
+
+\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.
+
+ 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{center}
+ \url{https://esolangs.org/wiki/Brainfuck}
+ \end{center}\hfill[2 Marks]
+
+ \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
+
+
+
+
+\end{document}
+
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
--- a/cws/disclaimer.sty Tue Nov 20 13:42:32 2018 +0000
+++ b/cws/disclaimer.sty Tue Nov 20 14:31:14 2018 +0000
@@ -12,8 +12,8 @@
functions or to any types. You are free to implement any auxiliary
function you might need.
-\item Do not leave any test cases running in your code because this might slow
- down your program! Comment test cases out before submission, otherwise you
+\item \textbf{Do not leave any test cases running in your code because this might slow
+ down your program!} Comment test cases out before submission, otherwise you
might hit a time-out.
\item Do not use any mutable data structures in your
--- a/marking1/collatz_test.sh Tue Nov 20 13:42:32 2018 +0000
+++ b/marking1/collatz_test.sh Tue Nov 20 14:31:14 2018 +0000
@@ -100,7 +100,8 @@
echo " collatz_max(10000) == (261, 6171)" | tee -a $out
echo " collatz_max(100000) == (350, 77031)" | tee -a $out
echo " collatz_max(1000000) == (524, 837799)" | tee -a $out
- echo " collatz_max(2) == (1, 2) || collatz_max(2) == (0, 1)" | tee -a $out
+ # echo " collatz_max(2) == (1, 2) || collatz_max(2) == (0, 1)" | tee -a $out
+ echo " collatz_max(2) == (1, 2)" | tee -a $out
echo " collatz_max(77000) == (339, 52527)" | tee -a $out
if (scala_assert "collatz.scala" "collatz_test2.scala")
--- a/marking1/collatz_test2.scala Tue Nov 20 13:42:32 2018 +0000
+++ b/marking1/collatz_test2.scala Tue Nov 20 14:31:14 2018 +0000
@@ -12,6 +12,6 @@
assert(collatz_max(1000000) == (524, 837799))
-assert(collatz_max(2) == (1, 2) || collatz_max(2) == (0, 1))
-
+//assert(collatz_max(2) == (1, 2) || collatz_max(2) == (0, 1))
+assert(collatz_max(2) == (1, 2))
assert(collatz_max(77000) == (339, 52527))
--- a/marking1/mk Tue Nov 20 13:42:32 2018 +0000
+++ b/marking1/mk Tue Nov 20 14:31:14 2018 +0000
@@ -9,26 +9,22 @@
cd $sd
echo $sd
touch .
- cp ../../../marking1/collatz_test.sh .
+ cp ../../../marking1/*.sh .
cp ../../../marking1/collatz_test1.scala .
cp ../../../marking1/collatz_test2.scala .
- cp ../../../marking1/alcohol_test.sh .
- cp ../../../marking1/alcohol.csv .
- cp ../../../marking1/population.csv .
- cp ../../../marking1/alcohol_test1.scala .
- cp ../../../marking1/alcohol_test2.scala .
- cp ../../../marking1/alcohol_test3.scala .
+ cp ../../../marking1/drumb_test1.scala .
+ cp ../../../marking1/drumb_test2.scala .
+ cp ../../../marking1/drumb_test3.scala .
+ cp ../../../marking1/*.csv .
./collatz_test.sh output
- ./alcohol_test.sh output
- rm collatz_test.sh
+ ./drumb_test.sh output
+ rm *.sh
rm collatz_test1.scala
rm collatz_test2.scala
- rm alcohol_test.sh
- rm alcohol.csv
- rm population.csv
- rm alcohol_test1.scala
- rm alcohol_test2.scala
- rm alcohol_test3.scala
+ rm drumb_test1.scala
+ rm drumb_test2.scala
+ rm drumb_test3.scala
+ rm *.csv
cd ..
done
--- a/progs/knight1.scala Tue Nov 20 13:42:32 2018 +0000
+++ b/progs/knight1.scala Tue Nov 20 14:31:14 2018 +0000
@@ -4,33 +4,95 @@
type Pos = (Int, Int) // a position on a chessboard
type Path = List[Pos] // a path...a list of positions
-//(1a) Complete the function that tests whether the position
-// is inside the board and not yet element in the path.
+def print_board(dim: Int, path: Path): Unit = {
+ println
+ for (i <- 0 until dim) {
+ for (j <- 0 until dim) {
+ print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
+ }
+ println
+ }
+}
-def is_legal(dim: Int, path: Path)(x: Pos): Boolean = ...
+
+// 1 mark
+
+def is_legal(dim: Int, path: Path, x: Pos): Boolean =
+ 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
+
+assert(is_legal(8, Nil)((3,4)) == true)
+assert(is_legal(8, List((4,1), (1,0)))((4,1)) == false)
+assert(is_legal(2, Nil)((0,0)) == true)
-//(1b) Complete the function that calculates for a position
-// all legal onward moves that are not already in the path.
-// The moves should be ordered in a "clockwise" order.
-
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = ...
+def add_pair(x: Pos)(y: Pos): Pos =
+ (x._1 + y._1, x._2 + y._2)
+
+def moves(x: Pos): List[Pos] =
+ List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
+ (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
+
+// 1 mark
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+ moves(x).filter(is_legal(dim, path))
-//assert(legal_moves(8, Nil, (2,2)) ==
-// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
-// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+assert(legal_moves(8, Nil, (2,2)) ==
+ List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
+ List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+assert(legal_moves(1, Nil, (0,0)) == List())
+assert(legal_moves(2, Nil, (0,0)) == List())
+assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
+// 2 marks
+
+def count_tours(dim: Int, path: Path): Int = {
+ if (path.length == dim * dim) 1
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum
+}
+
+def enum_tours(dim: Int, path: Path): List[Path] = {
+ if (path.length == dim * dim) List(path)
+ else
+ (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten
+}
+
+// as far as tasks go
-//(1c) Complete the two recursive functions below.
-// They exhaustively search for open tours starting from the
-// given path. The first function counts all possible open tours,
-// and the second collects all open tours in a list of paths.
-def count_tours(dim: Int, path: Path): Int = ...
+def count_all_tours(dim: Int) = {
+ for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
+}
-def enum_tours(dim: Int, path: Path): List[Path] = ...
+def enum_all_tours(dim: Int): List[Path] = {
+ (for (i <- (0 until dim).toList;
+ j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
+}
+println("Number of tours starting from (0, 0)")
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0))))
+}
+
+for (dim <- 1 to 5) {
+ println(s"${dim} x ${dim} " + count_all_tours(dim))
+}
+
+for (dim <- 1 to 5) {
+ val ts = enum_tours(dim, List((0, 0)))
+ println(s"${dim} x ${dim} ")
+ if (ts != Nil) {
+ print_board(dim, ts.head)
+ println(ts.head)
+ }
+}
+
+
--- a/progs/lecture2.scala Tue Nov 20 13:42:32 2018 +0000
+++ b/progs/lecture2.scala Tue Nov 20 14:31:14 2018 +0000
@@ -18,15 +18,20 @@
time_needed(10, for (n <- list) yield n + 42)
time_needed(10, for (n <- list.par) yield n + 42)
+// (ONLY WORKS OUT-OF-THE-BOX IN SCALA 2.11.8, not in SCALA 2.12)
+// (would need to have this wrapped into a function, or
+// REPL called with scala -Yrepl-class-based)
-// Just for "Fun": Mutable vs Immutable
-//=======================================
+
+// Just for Fun: Mutable vs Immutable
+//====================================
//
// - no vars, no ++i, no +=
// - no mutable data-structures (no Arrays, no ListBuffers)
-// Q: Count how many elements are in the intersections of two sets?
+// Q: Count how many elements are in the intersections of
+// two sets?
def count_intersection(A: Set[Int], B: Set[Int]) : Int = {
var count = 0
@@ -84,10 +89,18 @@
lst.count(even)
-lst.find(_ > 8)
+
+lst.find(even)
+
+val ps = List((3, 0), (3, 2), (4, 2), (2, 2), (2, 0), (1, 1), (1, 0))
+lst.sortWith(_ > _)
+lst.sortWith(_ < _)
-val ps = List((3, 0), (3, 2), (4, 2), (2, 0), (1, 1), (1, 0))
+def lex(x: (Int, Int), y: (Int, Int)) : Boolean =
+ if (x._1 == y._1) x._2 < y._2 else x._1 < y._1
+
+ps.sortWith(lex)
ps.sortBy(_._1)
ps.sortBy(_._2)
@@ -97,13 +110,18 @@
-// maps
-//=====
+// maps (lower-case)
+//===================
+def double(x: Int): Int = x + x
def square(x: Int): Int = x * x
+
+
val lst = (1 to 10).toList
+lst.map(x => (double(x), square(x)))
+
lst.map(square)
// this is actually what for is defined at in Scala
@@ -121,6 +139,8 @@
// lets define our own functions
// type of functions, for example f: Int => Int
+lst.tail
+
def my_map_int(lst: List[Int], f: Int => Int) : List[Int] = {
if (lst == Nil) Nil
else f(lst.head) :: my_map_int(lst.tail, f)
@@ -143,7 +163,7 @@
// f1: (Int, Int) => Int
// f2: List[String] => Option[Int]
// ...
-
+val lst = (1 to 10).toList
def sumOf(f: Int => Int, lst: List[Int]): Int = lst match {
case Nil => 0
@@ -157,7 +177,8 @@
sum_cubes(lst)
// lets try it factorial
-def fact(n: Int) : Int = ...
+def fact(n: Int) : Int =
+ if (n == 0) 1 else n * fact(n - 1)
def sum_fact(lst: List[Int]) = sumOf(fact, lst)
sum_fact(lst)
@@ -166,8 +187,8 @@
-// Map type
-//==========
+// Map type (upper-case)
+//=======================
// Note the difference between map and Map
@@ -188,12 +209,12 @@
facs.toMap.get(4)
-facs.toMap.getOrElse(4, Nil)
+facs.toMap.getOrElse(42, Nil)
val facsMap = facs.toMap
val facsMap0 = facsMap + (0 -> List(1,2,3,4,5))
-facsMap0.get(0)
+facsMap0.get(1)
val facsMap4 = facsMap + (1 -> List(1,2,3,4,5))
facsMap.get(1)
@@ -202,7 +223,7 @@
val ls = List("one", "two", "three", "four", "five")
ls.groupBy(_.length)
-ls.groupBy(_.length).get(3)
+ls.groupBy(_.length).get(2)
@@ -226,10 +247,14 @@
lst.flatten
Some(1).get
+None.get
Some(1).isDefined
None.isDefined
+
+None.isDefined
+
val ps = List((3, 0), (3, 2), (4, 2), (2, 0), (1, 0), (1, 1))
for ((x, y) <- ps) yield {
@@ -252,7 +277,8 @@
import scala.util._
import io.Source
-Source.fromURL("""http://www.inf.kcl.ac.uk/staff/urbanc/""").mkString
+
+Source.fromURL("""http://www.inf.ucl.ac.uk/staff/urbanc/""").mkString
Try(Source.fromURL("""http://www.inf.kcl.ac.uk/staff/urbanc/""").mkString).getOrElse("")
@@ -260,7 +286,7 @@
// a function that turns strings into numbers (similar to .toInt)
-Integer.parseInt("1234")
+Integer.parseInt("12u34")
def get_me_an_int(s: String) : Option[Int] =
@@ -271,11 +297,11 @@
// summing all the numbers
-lst.map(get_me_an_int)
+lst.map(get_me_an_int).flatten.sum
lst.map(get_me_an_int).flatten.sum
-val sum = lst.flatMap(get_me_an_int).sum
+lst.flatMap(get_me_an_int).map(_.toString)
// This may not look any better than working with null in Java, but to
@@ -294,7 +320,7 @@
List(5,6,7,8,9).indexOf(7)
List(5,6,7,8,9).indexOf(10)
-
+List(5,6,7,8,9)(-1)
@@ -321,29 +347,24 @@
val lst = List(None, Some(1), Some(2), None, Some(3)).flatten
-def my_flatten(xs: List[Option[Int]]): List[Int] = {
- ...
-}
-
-
-
-def my_flatten(lst: List[Option[Int]]): List[Int] = lst match {
- case Nil => Nil
- case None::xs => my_flatten(xs)
- case Some(n)::xs => n::my_flatten(xs)
+def my_flatten(xs: List[Option[Int]]): List[Int] = xs match {
+ case Nil => Nil
+ case None::rest => my_flatten(rest)
+ case Some(v)::foo => {
+ v :: my_flatten(foo)
+ }
}
// another example
def get_me_a_string(n: Int): String = n match {
- case 0 => "zero"
- case 1 => "one"
- case 2 => "two"
- case _ => "many"
+ case 0 | 1 | 2 => "small"
+ case _ => "big"
}
get_me_a_string(0)
+
// you can also have cases combined
def season(month: String) = month match {
case "March" | "April" | "May" => "It's spring"
@@ -356,8 +377,8 @@
println(season("November"))
// What happens if no case matches?
+println(season("foobar"))
-println(season("foobar"))
// Silly: fizz buzz
def fizz_buzz(n: Int) : String = (n % 3, n % 5) match {
@@ -402,6 +423,19 @@
type RomanNumeral = List[RomanDigit]
+List(X,I)
+
+I -> 1
+II -> 2
+III -> 3
+IV -> 4
+V -> 5
+VI -> 6
+VII -> 7
+VIII -> 8
+IX -> 9
+X -> X
+
def RomanNumeral2Int(rs: RomanNumeral): Int = rs match {
case Nil => 0
case M::r => 1000 + RomanNumeral2Int(r)
@@ -430,7 +464,8 @@
// another example
//=================
-// Once upon a time, in a complete fictional country there were Persons...
+// Once upon a time, in a complete fictional
+// country there were Persons...
abstract class Person
@@ -438,7 +473,7 @@
case class Peer(deg: String, terr: String, succ: Int) extends Person
case class Knight(name: String) extends Person
case class Peasant(name: String) extends Person
-case object Clown extends Person
+
def title(p: Person): String = p match {
case King => "His Majesty the King"
@@ -464,7 +499,9 @@
King,
Clown)
-println(people.sortWith(superior(_, _)).mkString(", "))
+println(people.sortWith(superior).mkString("\n"))
+
+print("123\\n456")
// Tail recursion
@@ -499,11 +536,12 @@
// functions
-// A Web Crawler
-//===============
+// A Web Crawler / Email Harvester
+//=================================
//
-// the idea is to look for dead links using the
-// regular expression "https?://[^"]*"
+// the idea is to look for links using the
+// regular expression "https?://[^"]*" and for
+// email addresses using another regex.
import io.Source
import scala.util._
@@ -518,6 +556,9 @@
val http_pattern = """"https?://[^"]*"""".r
val email_pattern = """([a-z0-9_\.-]+)@([\da-z\.-]+)\.([a-z\.]{2,6})""".r
+//email_pattern.findAllIn
+// ("foo bla christian@kcl.ac.uk 1234567").toList
+
// drops the first and last character from a string
def unquote(s: String) = s.drop(1).dropRight(1)
@@ -533,7 +574,7 @@
println(s" Visiting: $n $url")
val page = get_page(url)
val new_emails = email_pattern.findAllIn(page).toSet
- new_emails ++ (for (u <- get_all_URLs(page).par) yield crawl(u, n - 1)).flatten
+ new_emails ++ (for (u <- get_all_URLs(page)) yield crawl(u, n - 1)).flatten
}
}
--- a/templates3-bak/knight1.scala Tue Nov 20 13:42:32 2018 +0000
+++ b/templates3-bak/knight1.scala Tue Nov 20 14:31:14 2018 +0000
@@ -9,7 +9,7 @@
//(1a) Complete the function that tests whether the position
// is inside the board and not yet element in the path.
-//def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = ...
+//def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ...
//(1b) Complete the function that calculates for a position
--- a/testing3/bf.scala Tue Nov 20 13:42:32 2018 +0000
+++ b/testing3/bf.scala Tue Nov 20 14:31:14 2018 +0000
@@ -240,7 +240,9 @@
def compile(name: String, prog: String) = {
val fw = new java.io.FileWriter(name + ".c")
- fw.write(compile_str(prog))
+ val is = compile_str(prog)
+ println(is)
+ fw.write(is)
fw.close()
}