# HG changeset patch # User Christian Urban # Date 1511281871 0 # Node ID 114a89518aea5fe06d758e2b5c1e2dcee16d32f2 # Parent c5ca7f8e21a57478af9d48a3a7b4b34bd1ba5c9e updated diff -r c5ca7f8e21a5 -r 114a89518aea cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r c5ca7f8e21a5 -r 114a89518aea cws/cw01.tex --- a/cws/cw01.tex Fri Nov 17 14:11:58 2017 +0000 +++ b/cws/cw01.tex Tue Nov 21 16:31:11 2017 +0000 @@ -21,8 +21,8 @@ \mbox{\texttt{scala <>}} on the commandline. \item Do not use any mutable data structures in your -submissions! They are not needed. This means you cannot use -\texttt{ListBuffer}s, for example. +submissions! They are not needed. This means you cannot create new +\texttt{Array}s or \texttt{ListBuffer}s, for example. \item Do not use \texttt{return} in your code! It has a different meaning in Scala, than in Java. diff -r c5ca7f8e21a5 -r 114a89518aea cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r c5ca7f8e21a5 -r 114a89518aea cws/cw02.tex --- a/cws/cw02.tex Fri Nov 17 14:11:58 2017 +0000 +++ b/cws/cw02.tex Tue Nov 21 16:31:11 2017 +0000 @@ -32,13 +32,9 @@ \item Make sure the files you submit can be processed by just calling\\ \mbox{\texttt{scala <>}} on the commandline. -%\item If you use \textbf{offending} words, like \texttt{var} or -% \texttt{return}, in comments, please write them as \texttt{vvar}, -% \texttt{Var}, \texttt{rreturn}, \texttt{Return} or anything - \item Do not use any mutable data structures in your -submissions! They are not needed. This means you cannot use -\texttt{ListBuffer}s, for example. +submissions! They are not needed. This means you cannot create new +\texttt{Array}s or \texttt{ListBuffer}s, for example. \item Do not use \texttt{return} in your code! It has a different meaning in Scala, than in Java. diff -r c5ca7f8e21a5 -r 114a89518aea cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r c5ca7f8e21a5 -r 114a89518aea cws/cw03.tex --- a/cws/cw03.tex Fri Nov 17 14:11:58 2017 +0000 +++ b/cws/cw03.tex Tue Nov 21 16:31:11 2017 +0000 @@ -8,22 +8,39 @@ This coursework is worth 10\%. It is about regular expressions, pattern matching and polymorphism. The first part is due on 30 -November at 11pm; the second, more advanced part, is due on 7 December -at 11pm. You are asked to implement a regular expression matcher. Make -sure the files you submit can be processed by just calling -\texttt{scala <>}.\bigskip +November at 11pm; the second, more advanced part, is due on 21 +December at 11pm. You are asked to implement a regular expression +matcher based on derivatives of regular expressions. The reason is +that regular expression matching in Java can be extremely slow +sometimes.\bigskip \noindent -\textbf{Important:} Do not use any mutable data structures in your -submission! They are not needed. This menas you cannot use -\texttt{ListBuffer}s, for example. Do not use \texttt{return} in your -code! It has a different meaning in Scala, than in Java. Do not use -\texttt{var}! This declares a mutable variable. Make sure the -functions you submit are defined on the ``top-level'' of Scala, not -inside a class or object. Also note that the running time of -each part will be restricted to a maximum of 360 seconds on my -laptop. +\textbf{Important:} + +\begin{itemize} +\item Make sure the files you submit can be processed by just calling\\ + \mbox{\texttt{scala <>}} on the commandline. Use the + template files provided and do not make any changes to arguments of + functions or to any types. You are free to implement any auxiliary + function you might need. + +\item Do not use any mutable data structures in your +submissions! They are not needed. This means you cannot create new +\texttt{Array}s or \texttt{ListBuffer}s, for example. +\item Do not use \texttt{return} in your code! It has a different + meaning in Scala, than in Java. + +\item Do not use \texttt{var}! This declares a mutable variable. Only + use \texttt{val}! + +\item Do not use any parallel collections! No \texttt{.par} therefore! + Our testing and marking infrastructure is not set up for it. +\end{itemize} + +\noindent +Also note that the running time of each part will be restricted to a +maximum of 360 seconds on my laptop \subsection*{Disclaimer} @@ -54,12 +71,13 @@ \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 text in all sorts of places. However, you need to be -fast, otherwise you will stumble over problems such as recently reported at +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} @@ -71,9 +89,10 @@ \subsubsection*{Tasks (file re.scala)} \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. +\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, that is given a + regular expression it either returns true or false. \begin{center} \begin{tabular}{lcl} @@ -134,7 +153,8 @@ \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$ + $\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ & + (is $\textit{nullable}$) \end{tabular} \end{center} @@ -165,12 +185,12 @@ simplifies to just $r_1$. \textbf{Hints:} Regular expressions can be seen as trees and there are several methods for traversing trees. One of them corresponds to the inside-out traversal. Also - remember numerical expressions from school: there you had exprssions - like $u + \ldots + (1 \cdot x) * \ldots (z + (y \cdot 0)) \ldots$ + remember numerical expressions from school: 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 if more rules are applicable. If you organise this + look whether more rules are applicable. If you organise the simplification in an inside-out fashion, it is always clear which rule should applied next.\\\mbox{}\hfill[1 Mark] @@ -333,7 +353,7 @@ 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 +$c\!::\!cs$ (that means strings which start with a character $c$ and have some rest, or tail, $cs$). If you now take the derivative of $r$ with respect to the character $c$, then you obtain a regular expressions that can match all the strings $cs$. In other words, the regular diff -r c5ca7f8e21a5 -r 114a89518aea handouts/pep-ho.pdf Binary file handouts/pep-ho.pdf has changed diff -r c5ca7f8e21a5 -r 114a89518aea handouts/pep-ho.tex --- a/handouts/pep-ho.tex Fri Nov 17 14:11:58 2017 +0000 +++ b/handouts/pep-ho.tex Tue Nov 21 16:31:11 2017 +0000 @@ -826,13 +826,13 @@ there have also been two forks of the Scala compiler. It needs to be seen what the future brings for Scala. -So all in all, Scala might not be a great teaching language, -but I hope this is mitigated by the fact that I never require -you to write any Scala code. You only need to be able to read -it. In the coursework you can use any programming language you -like. If you want to use Scala for this, then be my guest; if -you do not want, stick with the language you are most familiar -with. +%So all in all, Scala might not be a great teaching language, +%but I hope this is mitigated by the fact that I never require +%you to write any Scala code. You only need to be able to read +%it. In the coursework you can use any programming language you +%like. If you want to use Scala for this, then be my guest; if +%you do not want, stick with the language you are most familiar +%with. diff -r c5ca7f8e21a5 -r 114a89518aea progs/lecture3.scala --- a/progs/lecture3.scala Fri Nov 17 14:11:58 2017 +0000 +++ b/progs/lecture3.scala Tue Nov 21 16:31:11 2017 +0000 @@ -1,6 +1,55 @@ // Scala Lecture 3 //================= +// adding two binary strings very, very lazy manner + +def badd(s1: String, s2: String) : String = + (BigInt(s1, 2) + BigInt(s2, 2)).toString(2) + + +// collatz function on binary numbers + +def bcollatz(s: String) : Long = (s.dropRight(1), s.last) match { + case ("", '1') => 1 // we reached 1 + case (rest, '0') => 1 + bcollatz(rest) // even number => divide by two + case (rest, '1') => 1 + bcollatz(badd(s + '1', s)) // odd number => s + '1' is 2 * s + 1 + // add another s gives 3 * s + 1 +} + +bcollatz(9.toBinaryString) +bcollatz(837799.toBinaryString) +bcollatz(100000000000000000L.toBinaryString) +bcollatz(BigInt("1000000000000000000000000000000000000000000000000000000000000000000000000000").toString(2)) + +def conv(c: Char) : Int = c match { + case '0' => 0 + case '1' => 1 +} + +def badds(s1: String, s2: String, carry: Int) : String = (s1, s2, carry) match { + case ("", "", 1) => "1" + case ("", "", 0) => "" + case (cs1, cs2, carry) => (conv(cs1.last) + conv(cs2.last) + carry) match { + case 3 => badds(cs1.dropRight(1), cs2.dropRight(1), 1) + '1' + case 2 => badds(cs1.dropRight(1), cs2.dropRight(1), 1) + '0' + case 1 => badds(cs1.dropRight(1), cs2.dropRight(1), 0) + '1' + case 0 => badds(cs1.dropRight(1), cs2.dropRight(1), 0) + '0' + } +} + +def bcollatz2(s: String) : Long = (s.dropRight(1), s.last) match { + case ("", '1') => 1 // we reached 1 + case (rest, '0') => 1 + bcollatz2(rest) // even number => divide by two + case (rest, '1') => 1 + bcollatz2(badds(s + '1', '0' + s, 0)) // odd number => s + '1' is 2 * s + 1 + // add another s gives 3 * s + 1 +} + +bcollatz2(9.toBinaryString) +bcollatz2(837799.toBinaryString) +bcollatz2(100000000000000000L.toBinaryString) +bcollatz2(BigInt("1000000000000000000000000000000000000000000000000000000000000000000000000000").toString(2)) + + // One of only two places where I conceded to mutable // data structures: The following function generates diff -r c5ca7f8e21a5 -r 114a89518aea testing1/alcohol.scala --- a/testing1/alcohol.scala Fri Nov 17 14:11:58 2017 +0000 +++ b/testing1/alcohol.scala Tue Nov 21 16:31:11 2017 +0000 @@ -28,7 +28,6 @@ val alcs = get_csv_page(url_alcohol) val pops = get_csv_file(file_population) - def process_alcs(lines: List[String]) : List[(String, Double)] = for (l <- lines) yield { val entries = l.split(",").toList @@ -42,6 +41,9 @@ }).toMap +process_alcs(alcs.drop(1))(1) +process_pops(pops.drop(1))("Albania") + def sorted_country_consumption() : List[(String, Long)] = { val alcs2 = process_alcs(alcs.drop(1)) val pops2 = process_pops(pops.drop(1)) diff -r c5ca7f8e21a5 -r 114a89518aea testing2/knight1_test.sh --- a/testing2/knight1_test.sh Fri Nov 17 14:11:58 2017 +0000 +++ b/testing2/knight1_test.sh Tue Nov 21 16:31:11 2017 +0000 @@ -170,8 +170,8 @@ if [ $tsts1 -eq 0 ] then - echo " is first_tour(8, (0, 0)) ok? " >> $out - echo " is first_tour(4, (0, 0)) == None " >> $out + echo " is first_tour(8, List((0, 0))) ok? " >> $out + echo " is first_tour(4, List((0, 0))) == None " >> $out if (scala_assert "knight2.scala" "knight2b_test.scala") then diff -r c5ca7f8e21a5 -r 114a89518aea testing2/knight2.scala --- a/testing2/knight2.scala Fri Nov 17 14:11:58 2017 +0000 +++ b/testing2/knight2.scala Tue Nov 21 16:31:11 2017 +0000 @@ -6,7 +6,7 @@ type Pos = (Int, Int) // a position on a chessboard type Path = List[Pos] // a path...a list of positions -def print_board(dim: Int, path: Path): Unit = { +def print_board(dim: Int, path: Path) : Unit = { println for (i <- 0 until dim) { for (j <- 0 until dim) { @@ -16,21 +16,21 @@ } } -def add_pair(x: Pos)(y: Pos): Pos = +def add_pair(x: Pos)(y: Pos) : Pos = (x._1 + y._1, x._2 + y._2) -def is_legal(dim: Int, path: Path)(x: Pos): Boolean = +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) -def moves(x: Pos): List[Pos] = +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)) -def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = +def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = moves(x).filter(is_legal(dim, path)) -def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { +def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = xs match { case Nil => None case x::xs => { val result = f(x) @@ -41,7 +41,7 @@ //first(List((1, 0),(2, 0),(3, 0),(4, 0)), (x => if (x._1 > 3) Some(List(x)) else None)) //first(List((1, 0),(2, 0),(3, 0)), (x => if (x._1 > 3) Some(List(x)) else None)) -def first_tour(dim: Int, path: Path): Option[Path] = { +def first_tour(dim: Int, path: Path) : Option[Path] = { if (path.length == dim * dim) Some(path) else first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))