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