--- a/cws/cw03.tex Thu Nov 23 10:56:47 2017 +0000
+++ b/cws/cw03.tex Fri Nov 24 01:26:01 2017 +0000
@@ -4,6 +4,9 @@
\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
@@ -45,7 +48,8 @@
\begin{document}
-\section*{Coursework 8 (Scala, Regular Expressions, Brainf***)}
+
+\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
@@ -328,7 +332,7 @@
at the graphs below (you can try it out for yourself: have a look at
the file \texttt{catastrophic.java} on KEATS). Compare this with the
matcher you have implemented. How long can the string of $a$'s be
-in your matcher and stay within the 30 seconds time limit?
+in your matcher and still stay within the 30 seconds time limit?
\begin{center}
\begin{tikzpicture}
@@ -358,29 +362,225 @@
\subsection*{Part 2 (4 Marks)}
-Comming from Java or C++, you might think Scala is a quite
-esotheric programming language. But remember, some serious companies
-have built their business on Scala. And there are far more esotheric
-languages out there. One is called \emph{brainf***}. Urban M\"uller
-developed this language in 1993. A close relative was already
-introduced in ... by Corado B\"ohm, an Italian computer pionier, who
-unfortunately died a few months ago. One feature of brainf*** is its
-minimalistic set of instructions. It has just 8 instructions, all of
-which are single characters. Despite this minimalism, this language,
-given enough memory, has been shown to be Turing complete. In this
-part you will implement an interpreter for this language.
+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 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 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 example 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)]
+\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 has stored \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 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 map is not
+ defined at the memory pointer it returns \texttt{0}.
+
+ Write another function \texttt{write}, which takes a memory, a
+ memory pointer and a integer value as argument and updates the map
+ with the value at the given memory location. As usual the 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 after the loop. Similarly, if you 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
+ another opening and closing bracket 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 to
+ use 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
-\item[(2b)]
+ \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
+ counter 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 the calls recursively \texttt{run} with the updated
+ data.
-\item[(2c)]
-
+ Write another function \texttt{start} that calls \texttt{run} with a
+ given brainfu** program and memory, and the program counter and memory counter
+ 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.\\\mbox{}\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}{input 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 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,
+ memory counter and memory.\label{comms}}
+ \end{figure}
\end{itemize}\bigskip
--- a/testing2/knight1.scala Thu Nov 23 10:56:47 2017 +0000
+++ b/testing2/knight1.scala Fri Nov 24 01:26:01 2017 +0000
@@ -41,6 +41,18 @@
(for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum
}
+def count_tours(dim: Int, path : Path) : Int = {
+
+ if (path.length == dim * dim) {1}
+ else
+ val x = for (m <- legal_moves(dim,path,path.head)) yield {
+
+ count_tours(dim,m::path)
+ }
+ x.sum
+
+}
+
def enum_tours(dim: Int, path: Path): List[Path] = {
if (path.length == dim * dim) List(path)
else