# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1478369241 0
# Node ID 48a477fdef2176b85601c8ffa3cc2b56287be55f
# Parent  ab77f6006f1fdb62fcb182eb8949ca7c3ee7edd6
updated

diff -r ab77f6006f1f -r 48a477fdef21 cws/cw01.tex
--- a/cws/cw01.tex	Sat Nov 05 17:11:47 2016 +0000
+++ b/cws/cw01.tex	Sat Nov 05 18:07:21 2016 +0000
@@ -4,18 +4,12 @@
 
 \begin{document}
 
-\section*{Coursework 1 (Strand 1)}
+\section*{Coursework 6 (Scala)}
 
-This coursework is worth 4\% and is due on 25 October at
-16:00. You are asked to implement a regular expression matcher
-and submit a document containing the answers for the questions
-below. You can do the implementation in any programming
-language you like, but you need to submit the source code with
-which you answered the questions, otherwise a mark of 0\% will
-be awarded. You can submit your answers in a txt-file or pdf.
-Code send as code.
-
-
+This coursework is about Scala and is worth 10\%. The first part is
+due on 16 November at 11:00, and the second part on 23 November. You
+are asked to implement a three programs about list manipulations and
+recursion.
 
 \subsubsection*{Disclaimer}
 
@@ -25,189 +19,11 @@
 uploaded to KEATS, which you can freely use.\bigskip
 
 
-\subsubsection*{Task}
-
-The task is to implement a regular expression matcher based on
-derivatives of regular expressions. The implementation should
-be able to deal with the usual (basic) regular expressions
-
-\[
-\ZERO,\; \ONE,\; c,\; r_1 + r_2,\; r_1 \cdot r_2,\; r^*
-\]
-
-\noindent
-but also with the following extended regular expressions:
-
-\begin{center}
-\begin{tabular}{ll}
-$[c_1 c_2 \ldots c_n]$ & a range of characters\\
-$r^+$ & one or more times $r$\\
-$r^?$ & optional $r$\\
-$r^{\{n,m\}}$ & at least $n$-times $r$ but no more than $m$-times\\
-$\sim{}r$ & not-regular expression of $r$\\
-\end{tabular}
-\end{center}
-
-\noindent In the case of $r^{\{n,m\}}$ you can assume the
-convention that $0 \le n \le m$. The meanings of the extended
-regular expressions are
-
-\begin{center}
-\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
-$L([c_1 c_2 \ldots c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ 
-$L(r^+)$                  & $\dn$ & $\bigcup_{1\le i}. L(r)^i$\\
-$L(r^?)$                  & $\dn$ & $L(r) \cup \{[]\}$\\
-$L(r^{\{n,m\}})$           & $\dn$ & $\bigcup_{n\le i \le m}. L(r)^i$\\
-$L(\sim{}r)$              & $\dn$ & $\Sigma^* - L(r)$
-\end{tabular}
-\end{center}
-
-\noindent whereby in the last clause the set $\Sigma^*$ stands
-for the set of \emph{all} strings over the alphabet $\Sigma$
-(in the implementation the alphabet can be just what is
-represented by, say, the type \texttt{Char}). So $\sim{}r$
-means `all the strings that $r$ cannot match'. 
-
-Be careful that your implementation of \textit{nullable} and
-\textit{der} satisfies for every $r$ the following two
-properties (see also Question 2):
-
-\begin{itemize}
-\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
-\item $L(der\,c\,r) = Der\,c\,(L(r))$
-\end{itemize}
-
-\noindent {\bf Important!} Your implementation should have
-explicit cases for the basic regular expressions, but also
-explicit cases for the extended regular expressions. That
-means do not treat the extended regular expressions by just
-translating them into the basic ones. See also Question 2,
-where you are asked to explicitly give the rules for
-\textit{nullable} and \textit{der} for the extended regular
-expressions.
-
-
-\subsection*{Question 1}
-
-What is your King's email address (you will need it in
-Question 3)?
-
-\subsection*{Question 2}
-
-This question does not require any implementation. From the
-lectures you have seen the definitions for the functions
-\textit{nullable} and \textit{der} for the basic regular
-expressions. Give the rules for the extended regular
-expressions:
-
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-$\textit{nullable}([c_1 c_2 \ldots c_n])$  & $\dn$ & $?$\\
-$\textit{nullable}(r^+)$                   & $\dn$ & $?$\\
-$\textit{nullable}(r^?)$                   & $\dn$ & $?$\\
-$\textit{nullable}(r^{\{n,m\}})$            & $\dn$ & $?$\\
-$\textit{nullable}(\sim{}r)$               & $\dn$ & $?$\medskip\\
-$der\, c\, ([c_1 c_2 \ldots c_n])$  & $\dn$ & $?$\\
-$der\, c\, (r^+)$                   & $\dn$ & $?$\\
-$der\, c\, (r^?)$                   & $\dn$ & $?$\\
-$der\, c\, (r^{\{n,m\}})$            & $\dn$ & $?$\\
-$der\, c\, (\sim{}r)$               & $\dn$ & $?$\\
-\end{tabular}
-\end{center}
+\subsubsection*{Part 1 (3 Marks)}
 
-\noindent
-Remember your definitions have to satisfy the two properties
-
-\begin{itemize}
-\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
-\item $L(der\,c\,r)) = Der\,c\,(L(r))$
-\end{itemize}
-
-\subsection*{Question 3}
-
-Implement the following regular expression for email addresses
-
-\[
-([a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}})
-\]
-
-\noindent and calculate the derivative according to your email
-address. When calculating the derivative, simplify all regular
-expressions as much as possible by applying the
-following 7 simplification rules:
-
-\begin{center}
-\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}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}
-
-\noindent Write down your simplified derivative in a readable
-notation using parentheses where necessary. That means you
-should use the infix notation $+$, $\cdot$, $^*$ and so on,
-instead of code.
- 
-\subsection*{Question 4}
-
-Suppose \textit{[a-z]} stands for the range regular expression
-$[a,b,c,\ldots,z]$.  Consider the regular expression $/ \cdot * \cdot
-(\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot *
-\cdot /$ and decide wether the following four strings are matched by
-this regular expression. Answer yes or no.
+\subsubsection*{Part 2 (3 Marks)}
 
-\begin{enumerate}
-\item \texttt{"/**/"}
-\item \texttt{"/*foobar*/"}
-\item \texttt{"/*test*/test*/"}
-\item \texttt{"/*test/*test*/"}
-\end{enumerate}
-
-\noindent
-Also test your regular expression matcher with the regular
-expression $a^{\{3,5\}}$ and the strings
-
-\begin{enumerate}
-\setcounter{enumi}{4}
-\item \texttt{aa}
-\item \texttt{aaa}
-\item \texttt{aaaaa}
-\item \texttt{aaaaaa}
-\end{enumerate}
-
-\noindent
-Does your matcher produce the expected results?
-
-\subsection*{Question 5}
-
-Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
-$(a^{\{19,19\}}) \cdot (a^?)$.  Decide whether the following three
-strings consisting of $a$s only can be matched by $(r_1^+)^+$.
-Similarly test them with $(r_2^+)^+$. Again answer in all six cases
-with yes or no. \medskip
-
-\noindent
-These are strings are meant to be entirely made up of $a$s. Be careful
-when copy-and-pasting the strings so as to not forgetting any $a$ and
-to not introducing any other character.
-
-\begin{enumerate}
-\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
-\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
-\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
-\end{enumerate}
-
+\subsubsection*{Part 3 (4 Marks)}
 
 \end{document}
 
diff -r ab77f6006f1f -r 48a477fdef21 progs/knight.scala
--- a/progs/knight.scala	Sat Nov 05 17:11:47 2016 +0000
+++ b/progs/knight.scala	Sat Nov 05 18:07:21 2016 +0000
@@ -43,7 +43,7 @@
   if (steps.length ==  n * n && moves(n)(steps.head).contains(steps.last))
     print_board(n)(steps)
   else 
-    for (x <- moves(n)(steps.head).par; if (!steps.contains(x))) ctour(n)(x :: steps)
+    for (x <- moves(n)(steps.head); if (!steps.contains(x))) ctour(n)(x :: steps)
 }
 
 
@@ -51,7 +51,7 @@
   if (steps.length ==  n * n && moves(n)(steps.head).contains(steps.last))
     print_board(n)(steps)
   else 
-    for (x <- ordered_moves(n)(steps)(steps.head).par; if (!steps.contains(x))) faster_tour(n)(x :: steps)
+    for (x <- ordered_moves(n)(steps)(steps.head); if (!steps.contains(x))) faster_tour(n)(x :: steps)
 }
 
 
@@ -65,7 +65,6 @@
 }
 
 
-/*
 val n2 = 6
 println(s"circle tour: n = $n2")
 
@@ -74,9 +73,9 @@
     ctour(n2)(List((i, j))) 
   }
 }
-*/
+
 
-val n3 = 9
+val n3 = 8
 println(s"fast circle tour: n = $n3")
 
 Try {
diff -r ab77f6006f1f -r 48a477fdef21 progs/live.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/live.scala	Sat Nov 05 18:07:21 2016 +0000
@@ -0,0 +1,34 @@
+import scala.annotation.tailrec   
+
+
+def collatz(n: Int): List[Int] =
+  if (n == 1) List(1) else
+    if (n % 2 == 0) (n::collatz(n / 2)) else 
+      (n::collatz(3 * n + 1))
+
+def collatz1(n: Int): Int =
+  if (n == 1) 1 else
+    if (n % 2 == 0) (1 + collatz1(n / 2)) else 
+      (1 + collatz1(3 * n + 1))
+
+@tailrec
+def collatz2(n: BigInt, acc: Int): Int =
+  if (n == 1) acc else
+    if (n % 2 == 0) collatz2(n / 2, acc + 1) else 
+      collatz2(3 * n + 1, acc + 1)
+
+collatz(1)
+collatz(2)
+collatz(3)
+collatz(4)
+collatz(5)
+collatz(6)
+collatz(7)
+collatz(8)
+collatz(9)
+collatz(100000)
+println((for (i <- 1 to 100000) yield collatz(i).length).max)
+println((for (i <- 1 to 100000) yield collatz1(i)).max)
+println((for (i <- 1 to 1000000) yield collatz2(i, 1)).max)
+println((for (i <- (1 to 10000000).par) yield collatz2(i, 1)).max)
+println((for (i <- (1 to 100000000).par) yield collatz2(i, 1)).max)