--- a/core_testing2/docdiff.scala Mon Nov 06 21:49:55 2023 +0000
+++ b/core_testing2/docdiff.scala Fri Dec 08 00:54:36 2023 +0000
@@ -1,57 +1,41 @@
-// Preliminary Part about Code Similarity
-//========================================
+// Core Part 2 about Code Similarity
+//===================================
object C2 {
-//(1) Complete the clean function below. It should find
-// all words in a string using the regular expression
-// \w+ and the library function
-//
-// some_regex.findAllIn(some_string)
-//
-// The words should be Returned as a list of strings.
+// ADD YOUR CODE BELOW
+//======================
+
+//(1)
+def clean(s: String) : List[String] = """(\w+)""".r.findAllIn(s).toList
+
-def clean(s: String) : List[String] =
- ("""\w+""".r).findAllIn(s).toList
+
+//(2)
+def occurrences(xs: List[String]): Map[String, Int] = {
+ val ls = xs.distinct
+ val occLs = for (s <- ls) yield (s, xs.count(_.equals(s)))
+ occLs.toMap
+}
-//(2) The function occurrences calculates the number of times
-// strings occur in a list of strings. These occurrences should
-// be calculated as a Map from strings to integers.
-
-def occurrences(xs: List[String]): Map[String, Int] =
- (for (x <- xs.distinct) yield (x, xs.count(_ == x))).toMap
-
-//(3) This functions calculates the dot-product of two documents
-// (list of strings). For this it calculates the occurrence
-// maps from (2) and then multiplies the corresponding occurrences.
-// If a string does not occur in a document, the product is zero.
-// The function finally sums up all products.
-
+//(3)
def prod(lst1: List[String], lst2: List[String]) : Int = {
- val words = (lst1 ::: lst2).distinct
- val occs1 = occurrences(lst1)
- val occs2 = occurrences(lst2)
- words.map{ w => occs1.getOrElse(w, 0) * occs2.getOrElse(w, 0) }.sum
-}
-
-//(4) Complete the functions overlap and similarity. The overlap of
-// two documents is calculated by the formula given in the assignment
-// description. The similarity of two strings is given by the overlap
-// of the cleaned (see (1)) strings.
-
-def overlap(lst1: List[String], lst2: List[String]) : Double = {
- val m1 = prod(lst1, lst1)
- val m2 = prod(lst2, lst2)
- prod(lst1, lst2).toDouble / (List(m1, m2).max)
+ val occM1 = occurrences(lst1)
+ val occM2 = occurrences(lst2)
+ (for (s <- occM1) yield s._2 * occM2.getOrElse(s._1,0)).sum
}
-def similarity(s1: String, s2: String) : Double =
- overlap(clean(s1), clean(s2))
+
+//(4)
+def overlap(lst1: List[String], lst2: List[String]) : Double = prod(lst1,lst2) / prod(lst1,lst1).max(prod(lst2,lst2))
+
+def similarity(s1: String, s2: String) : Double = overlap(clean(s1), clean(s2))
-/*
+
+/* Test cases
val list1 = List("a", "b", "b", "c", "d")
@@ -81,7 +65,7 @@
heritage which ensures Australia's capacity to attract international
ecotourists."""
-similarity(orig1, plag1)
+similarity(orig1, plag1) // 0.8679245283018868
// Plagiarism examples from
@@ -105,13 +89,14 @@
recovery: a controversial tactic that is often implemented immediately
following an oil spill."""
-overlap(clean(orig2), clean(plag2))
-similarity(orig2, plag2)
+overlap(clean(orig2), clean(plag2)) // 0.728
+similarity(orig2, plag2) // 0.728
+
+
// The punchline: everything above 0.6 looks suspicious and
-// should be looked at by staff.
+// should be investigated by staff.
*/
-
}
--- a/core_testing3/postfix_test.sh Mon Nov 06 21:49:55 2023 +0000
+++ b/core_testing3/postfix_test.sh Fri Dec 08 00:54:36 2023 +0000
@@ -19,7 +19,7 @@
# functional tests
function scala_assert {
- (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null)
+ (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()") # 2> /dev/null 1> /dev/null)
}
# purity test
Binary file cws/core_cw01.pdf has changed
Binary file cws/core_cw02.pdf has changed
Binary file cws/core_cw03.pdf has changed
Binary file cws/main_cw01.pdf has changed
Binary file cws/main_cw02.pdf has changed
Binary file cws/main_cw03.pdf has changed
--- a/cws/main_cw03.tex Mon Nov 06 21:49:55 2023 +0000
+++ b/cws/main_cw03.tex Fri Dec 08 00:54:36 2023 +0000
@@ -158,8 +158,8 @@
$ scala-cli --extra-jars re.jar
scala> import M3._
scala> for (i <- 0 to 5000000 by 500000) {
- | println(f"$i: ${time_needed(2, matcher(EVIL, "a" * i))}%.5f secs.")
- | }
+ println(s"$i: ${time_needed(2, matcher(EVIL, "a" * i))}")
+}
0: 0.00002 secs.
500000: 0.10608 secs.
1000000: 0.22286 secs.
@@ -173,6 +173,9 @@
5000000: 1.29659 secs.
\end{lstlisting}%$
+\noindent
+For this you need to copy the \texttt{time\_needed} function and the \texttt{EVIL} regular
+expression from the comments given in \texttt{re.scala}.
\subsection*{Preliminaries}
Binary file cws/main_cw04.pdf has changed
--- a/cws/main_cw04.tex Mon Nov 06 21:49:55 2023 +0000
+++ b/cws/main_cw04.tex Fri Dec 08 00:54:36 2023 +0000
@@ -130,7 +130,7 @@
energy of a piece from move to move---so a piece on one field can have
energy 2 and on a different field the same piece might have energy
3. There are some further constraints on legal moves, which are
-explained below. The point of this part is to implement functions
+explained below. The point of this coursework part is to implement functions
about moving pieces on the Shogun board.\medskip\medskip
%and testing for when a
@@ -162,9 +162,9 @@
\noindent
Like in chess, checkmate is determined when the king of a player cannot
-move anymore to a field that is not attacked, or a player cannot
+move anymore to a field that is not attacked, or cannot
capture or block the attacking piece, or the king is the only
-piece left for a player. A board that is checkmate is the following:
+piece left for a player. A non-trivial board that is checkmate is the following:
\begin{center}
\begin{tikzpicture}[scale=0.5,every node/.style={scale=0.5}]
@@ -297,7 +297,7 @@
decrementing the x- and y-coordinates of positions of pieces.
A \emph{board} consists of a set of pieces. We always assume that we
-start with a consistent board and every move generates another
+start with a consistent board and every move only generates another
consistent board. In this way we do not need to check, for example,
whether pieces are stacked on top of each other or located outside the
board, or have an energy outside the permitted range. There are
@@ -351,7 +351,8 @@
\item If the energy is 0 and the position of the piece is \textit{not} occupied, then the field can be reached
and the set \texttt{Set(pc)} is returned whereby \texttt{pc} is the piece given as argument.
\item If the energy is 0 and the position of the piece \textit{is} occupied, but occupied by a piece
- of the opposite colour, then also the set \texttt{Set(pc)} is returned.
+ of the opposite colour, then also the set \texttt{Set(pc)} is returned. Otherwise the empty set
+ \texttt{Set()} is returned.
\item In case the energy is > 0 and the position of the piece
\texttt{pc} is occupied, then this move is blocked and the set
\texttt{Set()} is returned.
@@ -359,7 +360,7 @@
\texttt{m}. First, the simple moves (that is \texttt{U}, \texttt{D},
\texttt{L} and \texttt{R}) we only have to increment / decrement the
x- or y-position of the piece, decrease the energy and call eval
- recursively with the updated arguments. For example for \texttt{U}
+ recursively with the updated arguments. For example for \texttt{U} (up)
you need to increase the y-coordinate:
\begin{center}
@@ -367,7 +368,7 @@
\end{center}
The move \texttt{U} here acts like a ``mode'', meaning if you move
- up, you can only move up; the mode never changes. Similarly for the other simple moves: if
+ up, you can only move up; the mode never changes for simple moves. Similarly for the other simple moves: if
you move right, you can only move right and so on. In this way it is
prevented to go first to the right, and then change direction in order to go
left (same with up and down).
@@ -472,7 +473,7 @@
\texttt{D}, \ldots, \texttt{DL}). An example for all moves for the red piece on (4, 4) is
shown in \eqref{moves} on page \pageref{moves}. Be careful about possible modifications
you need to apply to the board before you call the \texttt{eval} function.
- Also for this task ignore the fact that a king cannot move onto an attacked field.\\
+ Also for this task, ignore the fact that a king cannot move onto an attacked field.\\
\mbox{}\hfill[1 Mark]
\item[(3)] Implement a function \texttt{attacked} that takes a colour and a board
@@ -548,7 +549,8 @@
\item[(4)] Implement a function \texttt{attackedN} that takes a piece and a board
and calculates the number of times this pieces is attacked by pieces of the opposite colour.
For example the piece on field (8, 4) above is attacked by 3 red pieces, and
- the piece on (6, 1) by 1 white piece.
+ the piece on (6, 1) by 1 white piece. In this number also include kings even
+ if they cannot move to this field because the would be in ``check''.
\\
\mbox{}\hfill[1 Mark]
@@ -556,7 +558,8 @@
and calculates the number of times this pieces is protected by pieces of the same colour.
For example the piece on field (8, 4) above is protected by 1 white pieces (the one on (8, 7)),
and the piece on (5, 3) is protected by three red pieces ((6, 1), (4, 2), and (6, 5)).
- \\
+ Similarly to \texttt{attackedN}, include in the calculated number here also the king provided it
+ can reach the given piece.\\
\mbox{}\hfill[1 Mark]
\item[(6)] Implement a function \texttt{legal\_moves} that behaves like \texttt{all\_moves} from (2) for
Binary file cws/main_cw05.pdf has changed
Binary file handouts/pep-ho.pdf has changed
--- a/handouts/pep-ho.tex Mon Nov 06 21:49:55 2023 +0000
+++ b/handouts/pep-ho.tex Fri Dec 08 00:54:36 2023 +0000
@@ -539,7 +539,7 @@
\end{lstlisting}
\noindent The answer means that he result of the addition is of type
-\code{Int} and the actual result is 5; \code{res0} is a name that
+0\code{Int} and the actual result is 5; \code{res0} is a name that
Scala gives automatically to the result. You can reuse this name later
on, for example
--- a/main_solution5/bfc.scala Mon Nov 06 21:49:55 2023 +0000
+++ b/main_solution5/bfc.scala Fri Dec 08 00:54:36 2023 +0000
@@ -305,9 +305,11 @@
}
/*
-import CW10b._
-println(time_needed(1, run(load_bff("collatz.bf"))))
-println(time_needed(1, run2(load_bff("collatz.bf"))))
-println(time_needed(1, run3(load_bff("collatz.bf"))))
-println(time_needed(1, run4(load_bff("collatz.bf"))))
+@main def main() = {
+ import M5b._
+ println(time_needed(1, run(load_bff("mandelbrot.bf"))))
+ println(time_needed(1, run2(load_bff("mandelbrot.bf"))))
+ println(time_needed(1, run3(load_bff("mandelbrot.bf"))))
+ println(time_needed(1, run4(load_bff("mandelbrot.bf"))))
+}
*/
--- a/progs/lecture1.scala Mon Nov 06 21:49:55 2023 +0000
+++ b/progs/lecture1.scala Fri Dec 08 00:54:36 2023 +0000
@@ -1,7 +1,7 @@
// Scala Lecture 1
//=================
-// - List, Sets, Strings, ...
+// - List, Sets, Ints, Strings, ...
// - Value assignments (val vs var)
// - How to define functions? (What is returned?)
// - If-Conditions
@@ -19,31 +19,14 @@
val x = 42
val y = 3 + 4
val z = x / y
-val x = 70
+val x = 0
println(z)
// (you cannot reassign values: z = 9 will give an error)
-//var z = 9
-//z = 10
-
-
-// Hello World
-//=============
-
-// an example of a stand-alone Scala file
-// (in the assignments you must submit a plain Scala script)
+var z = 9
+z = 10
-object Hello extends App {
- println("hello world")
-}
-
-// can then be called with
-//
-// $> scalac hello-world.scala
-// $> scala Hello
-//
-// $> java -cp /usr/local/src/scala/lib/scala-library.jar:. Hello
@@ -56,6 +39,7 @@
// picking an element in a list
val lst = List(1, 2, 3, 1)
+
lst(0)
lst(2)
@@ -84,7 +68,7 @@
// Equality in Scala is structural
//=================================
-val a = "Dave"
+val a = "Dave2"
val b = "Dave"
if (a == b) println("Equal") else println("Unequal")
@@ -159,7 +143,6 @@
"1,2,3,4,5".split(",").toList
"1,2,3,4,5".split(",3,").mkString("\n")
-"abcdefg".startsWith("abc")
// Types (see slide)
@@ -241,6 +224,36 @@
// }
+// > LENGTH OF LIST EXAMPLE
+def len(xs: List[Int], acc: Int) : Int = {
+ if (xs == Nil) acc
+ else foo(xs.tail, acc + 1)
+}
+
+def len(xs: List[Int]) : Int = foo(xs, 0)
+
+len(List(1,2,3,4,1))
+
+
+def len(xs: List[Int]) : Int = {
+ if (xs == Nil) 0
+ else (1 + len(xs.tail))
+}
+
+
+
+len(List(1,2,3,4,1))
+
+
+
+def len(xs: List[Int]) : Int = xs match {
+ case Nil => 0
+ case x :: xs => 1 + len(xs)
+}
+
+len(List(1,2,3,4,1))
+
+
// If-Conditionals
//=================
@@ -318,7 +331,7 @@
}
for (n <- (1 to 10).toList;
- m <- (1 to 5).toList) yield (n, m, n * m)
+ m <- (1 to 5).toList) yield (n, m)
// you can assign the result of a for-comprehension
@@ -327,8 +340,11 @@
for (n <- (1 to 10).toList;
m <- (1 to 10).toList) yield n * m
-println(mult_table.mkString)
-mult_table.sliding(10,10).mkString("\n")
+println(mult_table.mkString(","))
+mult_table.sliding(10,10).toList
+
+
+.mkString("\n")
// for-comprehensions also work for other
// collections
@@ -336,11 +352,17 @@
for (n <- Set(10,12,4,5,7,8,10)) yield n * n
for (n <- (1 to 10)) yield {
+
n * n
}
// with if-predicates / filters
+val xs = for (n <- (1 to 3).toList;
+ m <- (1 to 3).toList) yield (n,m)
+
+xs.filter{case (m, n) => (n + m) % 2 == 0}
+
for (n <- (1 to 3).toList;
m <- (1 to 3).toList;
if (n + m) % 2 == 0) yield (n, m)
@@ -350,7 +372,7 @@
val lst = List((1, 4), (2, 3), (3, 2), (4, 1))
-for ((m, n) <- lst) yield m + n
+` yield m + n
for (p <- lst) yield p._1 + p._2
@@ -369,9 +391,11 @@
// with only a side-effect (no list is produced),
// has no "yield"
-for (n <- (1 to 10).toList) println(n * n)
+val xs = for (n <- (1 to 10).toList) yield println(n * n)
-for (n <- (1 to 10).toList) yield n * n
+xs.tail
+
+val foo = for (n <- (1 to 10).toList) yield n * n
// BTW: a roundabout way of printing out a list, say
@@ -450,15 +474,21 @@
// - no mutable data-structures (no Arrays, no ListBuffers)
// But what the heck....lets try to count to 1 Mio in parallel
+//
+// requires
+// scala-cli --extra-jars scala- parallel-collections_3-1.0.4.jar
+
import scala.collection.parallel.CollectionConverters._
-var cnt = 0
+def test() = {
+ var cnt = 0
-for(i <- (1 to 100_000).par) cnt += 1
+ for(i <- (1 to 100_000)) cnt += 1
-println(s"Should be 100000: $cnt")
+ println(s"Should be 100000: $cnt")
+}
-
+test()
// Or
// Q: Count how many elements are in the intersections of
--- a/progs/lecture2.scala Mon Nov 06 21:49:55 2023 +0000
+++ b/progs/lecture2.scala Fri Dec 08 00:54:36 2023 +0000
@@ -33,16 +33,12 @@
def safe_div(x: Int, y: Int) : Option[Int] =
if (y == 0) None else Some(x / y)
-safe_div(10 + 5, 4 - 1)
+safe_div(10 + 5, 0)
List(1,2,3,4,5,6).indexOf(7)
List[Int]().min
-List[Int]().minOption
+List[Int](3,4,5).minOption
-def my_min(ls: List[Int]) : Option[Int] =
- ls.minOption
-
-my_min(List(1,2,3,4))
// better error handling with Options (no exceptions)
@@ -53,7 +49,7 @@
import scala.util._ // Try,...
import io.Source // fromURL
-val my_url = "https://nms.kcl.ac.uk/christian.urban/"
+val my_url = "https://nms.kcl.ac.uk/christian.urban2/"
Source.fromURL(my_url)("ISO-8859-1").mkString
Source.fromURL(my_url)("ISO-8859-1").getLines().toList
@@ -174,9 +170,10 @@
def even(x: Int) : Boolean = x % 2 == 0
def odd(x: Int) : Boolean = x % 2 == 1
+def inc(x: Int) : Int = x + 1
val lst = (1 to 10).toList
-lst.filter(even)
+lst.filter(_ % 2 == 0)
lst.count(odd)
lst.find(even)
lst.exists(even)
@@ -184,9 +181,11 @@
lst.find(_ < 4)
lst.filter(_ < 4)
+val x = 3 < 4
+
def less4(x: Int) : Boolean = x < 4
lst.find(less4)
-lst.find(_ < 4)
+lst.find(x => !(x < 4))
lst.filter(x => x % 2 == 0)
lst.filter(_ % 2 == 0)
@@ -230,7 +229,7 @@
// works also for strings
def tweet(c: Char) = c.toUpper
-"Hello World".map(tweet)
+"Hello\nWorld".map(tweet)
// this can be iterated
@@ -351,6 +350,19 @@
val grps = lst.groupBy(_.length)
grps.keySet
+// naive quicksort with "On" function
+
+def sortOn(f: Int => Int, xs: List[Int]) : List[Int] = {
+ if (xs.size < 2) xs
+ else {
+ val pivot = xs.head
+ val (left, right) = xs.partition(f(_) < f(pivot))
+ sortOn(f, left) ::: pivot :: sortOn(f, right.tail)
+ }
+}
+
+sortOn(identity, List(99,99,99,98,10,-3,2))
+sortOn(n => - n, List(99,99,99,98,10,-3,2))
--- a/progs/lecture3.scala Mon Nov 06 21:49:55 2023 +0000
+++ b/progs/lecture3.scala Fri Dec 08 00:54:36 2023 +0000
@@ -1,37 +1,218 @@
// Scala Lecture 3
//=================
-// - Higher-Order functions
-// - maps (behind for-comprehensions)
+// last week:
+// higher-order functions
+// maps
+// - recursion
+// - Sudoku
+// - string interpolations
// - Pattern-Matching
-def fib(n: Int) : Int = n match {
- case 0 => 1
- case 1 => 1
- case n => fib(n - 1) + fib(n - 2)
+// A Recursive Web Crawler / Email Harvester
+//===========================================
+//
+// 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._
+
+// gets the first 10K of a web-page
+def get_page(url: String) : String = {
+ Try(Source.fromURL(url)("ISO-8859-1").take(10000).mkString).
+ getOrElse { println(s" Problem with: $url"); ""}
+}
+
+// regex for URLs and emails
+val http_pattern = """"https?://[^"]*"""".r
+val email_pattern = """([a-z0-9_\.-]+)@([\da-z\.-]+)\.([a-z\.]{2,6})""".r
+
+//test case:
+//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)
+
+def get_all_URLs(page: String): Set[String] =
+ http_pattern.findAllIn(page).map(unquote).toSet
+
+// naive version of crawl - searches until a given depth,
+// visits pages potentially more than once
+def crawl(url: String, n: Int) : Unit = {
+ if (n == 0) ()
+ else {
+ println(s" Visiting: $n $url")
+ for (u <- get_all_URLs(get_page(url))) crawl(u, n - 1)
+ }
+}
+
+// some starting URLs for the crawler
+val startURL = """https://nms.kcl.ac.uk/christian.urban/"""
+
+crawl(startURL, 2)
+
+
+// a primitive email harvester
+def emails(url: String, n: Int) : Set[String] = {
+ if (n == 0) Set()
+ else {
+ 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)) yield emails(u, n - 1)).flatten
+ }
+}
+
+emails(startURL, 2)
+
+
+
+// Sudoku
+//========
+
+// THE POINT OF THIS CODE IS NOT TO BE SUPER
+// EFFICIENT AND FAST, just explaining exhaustive
+// depth-first search
+
+
+val game0 = """.14.6.3..
+ |62...4..9
+ |.8..5.6..
+ |.6.2....3
+ |.7..1..5.
+ |5....9.6.
+ |..6.2..3.
+ |1..5...92
+ |..7.9.41.""".stripMargin.replaceAll("\\n", "")
+
+type Pos = (Int, Int)
+val EmptyValue = '.'
+val MaxValue = 9
+
+def pretty(game: String): String =
+ "\n" + (game.grouped(MaxValue).mkString("\n"))
+
+pretty(game0)
+
+
+val allValues = "123456789".toList
+val indexes = (0 to 8).toList
+
+def empty(game: String) = game.indexOf(EmptyValue)
+def isDone(game: String) = empty(game) == -1
+def emptyPosition(game: String) : Pos = {
+ val e = empty(game)
+ (e % MaxValue, e / MaxValue)
+}
+
+def get_row(game: String, y: Int) =
+ indexes.map(col => game(y * MaxValue + col))
+def get_col(game: String, x: Int) =
+ indexes.map(row => game(x + row * MaxValue))
+
+//get_row(game0, 0)
+//get_row(game0, 1)
+//get_col(game0, 0)
+
+def get_box(game: String, pos: Pos): List[Char] = {
+ def base(p: Int): Int = (p / 3) * 3
+ val x0 = base(pos._1)
+ val y0 = base(pos._2)
+ val ys = (y0 until y0 + 3).toList
+ (x0 until x0 + 3).toList
+ .flatMap(x => ys.map(y => game(x + y * MaxValue)))
}
-abstract class Rexp
-case object ZERO extends Rexp // matches nothing
-case object ONE extends Rexp // matches the empty string
-case class CHAR(c: Char) extends Rexp // matches a character c
-case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
-case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
-case class STAR(r: Rexp) extends Rexp // star
+//get_box(game0, (3, 1))
+
+
+// this is not mutable!!
+def update(game: String, pos: Int, value: Char): String =
+ game.updated(pos, value)
+
+def toAvoid(game: String, pos: Pos): List[Char] =
+ (get_col(game, pos._1) ++
+ get_row(game, pos._2) ++
+ get_box(game, pos))
-def depth(r: Rexp) : Int = r match {
- case ZERO => 1
- case ONE => 1
- case CHAR(_) => 1
- case ALT(r1, r2) => 1 + List(depth(r1), depth(r2)).max
- case SEQ(r1, r2) => 1 + List(depth(r1), depth(r2)).max
- case STAR(r1) => 1 + depth(r1)
+def candidates(game: String, pos: Pos): List[Char] =
+ allValues.diff(toAvoid(game, pos))
+
+//candidates(game0, (0,0))
+
+
+def search(game: String): List[String] = {
+ if (isDone(game)) List(game)
+ else {
+ val cs = candidates(game, emptyPosition(game))
+ cs.par.map(c => search(update(game, empty(game), c))).flatten.toList
+ }
}
+pretty(game0)
+search(game0).map(pretty)
-// - String-Interpolations
+val game1 = """23.915...
+ |...2..54.
+ |6.7......
+ |..1.....9
+ |89.5.3.17
+ |5.....6..
+ |......9.5
+ |.16..7...
+ |...329..1""".stripMargin.replaceAll("\\n", "")
+
+search(game1).map(pretty)
+
+// a game that is in the hard category
+val game2 = """8........
+ |..36.....
+ |.7..9.2..
+ |.5...7...
+ |....457..
+ |...1...3.
+ |..1....68
+ |..85...1.
+ |.9....4..""".stripMargin.replaceAll("\\n", "")
+
+search(game2).map(pretty)
+
+// game with multiple solutions
+val game3 = """.8...9743
+ |.5...8.1.
+ |.1.......
+ |8....5...
+ |...8.4...
+ |...3....6
+ |.......7.
+ |.3.5...8.
+ |9724...5.""".stripMargin.replaceAll("\\n", "")
+
+search(game3).map(pretty).foreach(println)
+
+// for measuring time
+def time_needed[T](i: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (j <- 1 to i) code
+ val end = System.nanoTime()
+ s"${(end - start) / 1.0e9} secs"
+}
+
+time_needed(2, search(game2))
+
+
+// concurrency
+// scala-cli --extra-jars scala-parallel-collections_3-1.0.4.jar
+// import scala.collection.parallel.CollectionConverters._
+
+
+
// String Interpolations
//=======================
@@ -63,19 +244,6 @@
gcd_db(48, 18)
-// naive quicksort with "On" function
-
-def sortOn(f: Int => Int, xs: List[Int]) : List[Int] = {
- if (xs.size < 2) xs
- else {
- val pivot = xs.head
- val (left, right) = xs.partition(f(_) < f(pivot))
- sortOn(f, left) ::: pivot :: sortOn(f, right.tail)
- }
-}
-
-sortOn(identity, List(99,99,99,98,10,-3,2))
-sortOn(n => - n, List(99,99,99,98,10,-3,2))
// Recursion Again ;o)
@@ -101,8 +269,103 @@
-// User-defined Datatypes
-//========================
+// Pattern Matching
+//==================
+
+// A powerful tool which has even landed in Java during
+// the last few years (https://inside.java/2021/06/13/podcast-017/).
+// ...Scala already has it for many years and the concept is
+// older than your friendly lecturer, that is stone old ;o)
+
+// The general schema:
+//
+// expression match {
+// case pattern1 => expression1
+// case pattern2 => expression2
+// ...
+// case patternN => expressionN
+// }
+
+
+// recall
+def len(xs: List[Int]) : Int = {
+ if (xs == Nil) 0
+ else 1 + len(xs.tail)
+}
+
+def len(xs: List[Int]) : Int = xs match {
+ case Nil => 0
+ case hd::tail => 1 + len(tail)
+}
+
+
+def my_map_int(lst: List[Int], f: Int => Int) : List[Int] =
+ lst match {
+ case Nil => Nil
+ case x::xs => f(x)::my_map_int(xs, f)
+ }
+
+def my_map_option(opt: Option[Int], f: Int => Int) : Option[Int] =
+ opt match {
+ case None => None
+ case Some(x) => Some(f(x))
+ }
+
+my_map_option(None, x => x * x)
+my_map_option(Some(8), x => x * x)
+
+
+// you can also have cases combined
+def season(month: String) : String = month match {
+ case "March" | "April" | "May" => "It's spring"
+ case "June" | "July" | "August" => "It's summer"
+ case "September" | "October" | "November" => "It's autumn"
+ case "December" => "It's winter"
+ case "January" | "February" => "It's unfortunately winter"
+ case _ => "Wrong month"
+}
+
+// pattern-match on integers
+
+def fib(n: Int) : Int = n match {
+ case 0 | 1 => 1
+ case n => fib(n - 1) + fib(n - 2)
+}
+
+fib(10)
+
+// pattern-match on results
+
+// Silly: fizz buzz
+def fizz_buzz(n: Int) : String = (n % 3, n % 5) match {
+ case (0, 0) => "fizz buzz"
+ case (0, _) => "fizz"
+ case (_, 0) => "buzz"
+ case _ => n.toString
+}
+
+for (n <- 1 to 20)
+ println(fizz_buzz(n))
+
+// guards in pattern-matching
+
+def foo(xs: List[Int]) : String = xs match {
+ case Nil => s"this list is empty"
+ case x :: xs if x % 2 == 0
+ => s"the first elemnt is even"
+ case x :: y :: rest if x == y
+ => s"this has two elemnts that are the same"
+ case hd :: tl => s"this list is standard $hd::$tl"
+}
+
+foo(Nil)
+foo(List(1,2,3))
+foo(List(1,2))
+foo(List(1,1,2,3))
+foo(List(2,2,2,3))
+
+
+// Trees
abstract class Tree
case class Leaf(x: Int) extends Tree
@@ -182,6 +445,27 @@
RomanNumeral2Int(List(M,M,X,V,I,I)) // 2017
+abstract class Rexp
+case object ZERO extends Rexp // matches nothing
+case object ONE extends Rexp // matches the empty string
+case class CHAR(c: Char) extends Rexp // matches a character c
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
+case class STAR(r: Rexp) extends Rexp // star
+
+def depth(r: Rexp) : Int = r match {
+ case ZERO => 1
+ case ONE => 1
+ case CHAR(_) => 1
+ case ALT(r1, r2) => 1 + List(depth(r1), depth(r2)).max
+ case SEQ(r1, r2) => 1 + List(depth(r1), depth(r2)).max
+ case STAR(r1) => 1 + depth(r1)
+}
+
+
+
+
+
// expressions (essentially trees)
abstract class Exp
@@ -254,22 +538,44 @@
parse_date("26.11.2019")
-// guards in pattern-matching
+
+
+// Map type (upper-case)
+//=======================
+
+// Note the difference between map and Map
+
+val m = Map(1 -> "one", 2 -> "two", 10 -> "many")
+
+List((1, "one"), (2, "two"), (10, "many")).toMap
+
+m.get(1)
+m.get(4)
+
+m.getOrElse(1, "")
+m.getOrElse(4, "")
+
+val new_m = m + (10 -> "ten")
-def foo(xs: List[Int]) : String = xs match {
- case Nil => s"this list is empty"
- case x :: xs if x % 2 == 0
- => s"the first elemnt is even"
- case x :: y :: rest if x == y
- => s"this has two elemnts that are the same"
- case hd :: tl => s"this list is standard $hd::$tl"
-}
+new_m.get(10)
+
+val m2 = for ((k, v) <- m) yield (k, v.toUpperCase)
+
+
+
+// groupBy function on Maps
+val lst = List("one", "two", "three", "four", "five")
+lst.groupBy(_.head)
-foo(Nil)
-foo(List(1,2,3))
-foo(List(1,2))
-foo(List(1,1,2,3))
-foo(List(2,2,2,3))
+lst.groupBy(_.length)
+
+lst.groupBy(_.length).get(3)
+
+val grps = lst.groupBy(_.length)
+grps.keySet
+
+
+
// Tail recursion
//================
@@ -316,125 +622,89 @@
lengthT(List.fill(10000000)(1), 0)
-// Sudoku
-//========
-
-// uses Strings for games
-
-type Pos = (Int, Int)
-val emptyValue = '.'
-val maxValue = 9
-
-val allValues = "123456789".toList
-val indexes = (0 to 8).toList
-def empty(game: String) = game.indexOf(emptyValue)
-def isDone(game: String) = empty(game) == -1
-def emptyPosition(game: String) : Pos =
- (empty(game) % maxValue, empty(game) / maxValue)
+
-def get_row(game: String, y: Int) = indexes.map(col => game(y * maxValue + col))
-def get_col(game: String, x: Int) = indexes.map(row => game(x + row * maxValue))
+// Aside: concurrency
+// scala-cli --extra-jars scala-parallel-collections_3-1.0.4.jar
-def get_box(game: String, pos: Pos): List[Char] = {
- def base(p: Int): Int = (p / 3) * 3
- val x0 = base(pos._1)
- val y0 = base(pos._2)
- for (x <- (x0 until x0 + 3).toList;
- y <- (y0 until y0 + 3).toList) yield game(x + y * maxValue)
-}
+for (n <- (1 to 10)) println(n)
+
+import scala.collection.parallel.CollectionConverters._
+
+for (n <- (1 to 10).par) println(n)
-def update(game: String, pos: Int, value: Char): String =
- game.updated(pos, value)
-
-def toAvoid(game: String, pos: Pos): List[Char] =
- (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos))
-
-def candidates(game: String, pos: Pos): List[Char] =
- allValues.diff(toAvoid(game, pos))
-
-def search(game: String): List[String] = {
- if (isDone(game)) List(game)
- else
- candidates(game, emptyPosition(game)).
- map(c => search(update(game, empty(game), c))).flatten
-}
-
-
-def search1T(games: List[String]): Option[String] = games match {
- case Nil => None
- case game::rest => {
- if (isDone(game)) Some(game)
- else {
- val cs = candidates(game, emptyPosition(game))
- search1T(cs.map(c => update(game, empty(game), c)) ::: rest)
- }
- }
+// for measuring time
+def time_needed[T](n: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (i <- (0 to n)) code
+ val end = System.nanoTime()
+ (end - start) / 1.0e9
}
-def pretty(game: String): String =
- "\n" + (game.sliding(maxValue, maxValue).mkString(",\n"))
+val list = (1L to 10_000_000L).toList
+time_needed(10, for (n <- list) yield n + 42)
+time_needed(10, for (n <- list.par) yield n + 42)
-
-// tail recursive version that searches
-// for all solutions
+// ...but par does not make everything faster
-def searchT(games: List[String], sols: List[String]): List[String] = games match {
- case Nil => sols
- case game::rest => {
- if (isDone(game)) searchT(rest, game::sols)
- else {
- val cs = candidates(game, emptyPosition(game))
- searchT(cs.map(c => update(game, empty(game), c)) ::: rest, sols)
- }
- }
-}
+list.sum
+list.par.sum
-searchT(List(game3), List()).map(pretty)
+time_needed(10, list.sum)
+time_needed(10, list.par.sum)
-// tail recursive version that searches
-// for a single solution
+// Mutable vs Immutable
+//======================
+//
+// Remember:
+// - no vars, no ++i, no +=
+// - no mutable data-structures (no Arrays, no ListBuffers)
-def search1T(games: List[String]): Option[String] = games match {
- case Nil => None
- case game::rest => {
- if (isDone(game)) Some(game)
- else {
- val cs = candidates(game, emptyPosition(game))
- search1T(cs.map(c => update(game, empty(game), c)) ::: rest)
- }
- }
+// But what the heck....lets try to count to 1 Mio in parallel
+//
+// requires
+// scala-cli --extra-jars scala- parallel-collections_3-1.0.4.jar
+
+import scala.collection.parallel.CollectionConverters._
+
+def test() = {
+ var cnt = 0
+
+ for(i <- (1 to 100_000).par) cnt += 1
+
+ println(s"Should be 100000: $cnt")
}
-search1T(List(game3)).map(pretty)
-time_needed(10, search1T(List(game3)))
+test()
+
+// Or
+// Q: Count how many elements are in the intersections of
+// two sets?
+// A; IMPROPER WAY (mutable counter)
+
+def count_intersection(A: Set[Int], B: Set[Int]) : Int = {
+ var count = 0
+ for (x <- A.par; if B contains x) count += 1
+ count
+}
+
+val A = (0 to 999).toSet
+val B = (0 to 999 by 4).toSet
+
+count_intersection(A, B)
+
+// but do not try to add .par to the for-loop above
-// game with multiple solutions
-val game3 = """.8...9743
- |.5...8.1.
- |.1.......
- |8....5...
- |...8.4...
- |...3....6
- |.......7.
- |.3.5...8.
- |9724...5.""".stripMargin.replaceAll("\\n", "")
+//propper parallel version
+def count_intersection2(A: Set[Int], B: Set[Int]) : Int =
+ A.par.count(x => B contains x)
-searchT(List(game3), Nil).map(pretty)
-search1T(List(game3)).map(pretty)
+count_intersection2(A, B)
-// Moral: Whenever a recursive function is resource-critical
-// (i.e. works with large recursion depth), then you need to
-// write it in tail-recursive fashion.
-//
-// Unfortuantely, Scala because of current limitations in
-// the JVM is not as clever as other functional languages. It can
-// only optimise "self-tail calls". This excludes the cases of
-// multiple functions making tail calls to each other. Well,
-// nothing is perfect.
--- a/progs/lecture4.scala Mon Nov 06 21:49:55 2023 +0000
+++ b/progs/lecture4.scala Fri Dec 08 00:54:36 2023 +0000
@@ -1,38 +1,227 @@
// Scala Lecture 4
//=================
+// pattern-matching
// tail-recursion
// polymorphic types
-// implicits
+
+
+
+// Pattern Matching
+//==================
+
+// A powerful tool which has even landed in Java during
+// the last few years (https://inside.java/2021/06/13/podcast-017/).
+// ...Scala already has it for many years and the concept is
+// older than your friendly lecturer, that is stone old ;o)
-import scala.annotation.tailrec
+// The general schema:
+//
+// expression match {
+// case pattern1 => expression1
+// case pattern2 => expression2
+// ...
+// case patternN => expressionN
+// }
+
+
+// recall
+def len(xs: List[Int]) : Int = {
+ if (xs == Nil) 0
+ else 1 + len(xs.tail)
+}
-def fact(n: BigInt): BigInt =
- if (n == 0) 1 else n * fact(n - 1)
-
-
-def factT(n: BigInt, acc: BigInt): BigInt =
- if (n == 0) acc else factT(n - 1, n * acc)
+def len(xs: List[Int]) : Int = xs match {
+ case Nil => 0
+ case _::xs => 1 + len(xs)
+}
+
+len(Nil)
+len(List(1,2,3,4))
+
+
+List(1,2,3,4).map(x => x * x)
+
+def my_map_int(lst: List[Int], f: Int => Int) : List[Int] =
+ lst match {
+ case Nil => Nil
+ case foo::xs => f(foo) :: my_map_int(xs, f)
+ }
+
+def my_map_option(opt: Option[Int], f: Int => Int) : Option[Int] =
+ opt match {
+ case None => None
+ case Some(x) => {
+ Some(f(x))
+ }
+ }
+
+my_map_option(None, x => x * x)
+my_map_option(Some(8), x => x * x)
-println(factT(1000000), 1))
+// you can also have cases combined
+def season(month: String) : String = month match {
+ case "March" | "April" | "May" => "It's spring"
+ case "June" | "July" | "August" => "It's summer"
+ case "September" | "October" | "November" => "It's autumn"
+ case "December" => "It's winter"
+ case "January" | "February" => "It's unfortunately winter"
+ case _ => "Wrong month"
+}
+
+// pattern-match on integers
+
+def fib(n: Int) : Int = n match {
+ case 0 | 1 => 1
+ case _ => fib(n - 1) + fib(n - 2)
+}
+
+fib(10)
+
+// pattern-match on results
+
+// Silly: fizz buzz
+def fizz_buzz(n: Int) : String = (n % 3, n % 5) match {
+ case (0, 0) => "fizz buzz"
+ case (0, _) => "fizz"
+ case (_, 0) => "buzz"
+ case _ => n.toString
+}
+
+for (n <- 1 to 20)
+ println(fizz_buzz(n))
+
+// guards in pattern-matching
+
+def foo(xs: List[Int]) : String = xs match {
+ case Nil => s"this list is empty"
+ case x :: xs if x % 2 == 0
+ => s"the first elemnt is even"
+ case x if len(x) ==
+ => s"this list has exactly two elements"
+ case x :: y :: rest if x == y
+ => s"this has two elemnts that are the same"
+ case hd :: tl => s"this list is standard $hd::$tl"
+}
+
+foo(Nil)
+foo(List(1,2,3))
+foo(List(1,1))
+foo(List(1,1,2,3))
+foo(List(2,2,2,3))
+
+
+
+
+abstract class Colour
+case object Red extends Colour
+case object Green extends Colour
+case object Blue extends Colour
+case object Yellow extends Colour
+
+
+def fav_colour(c: Colour) : Boolean = c match {
+ case Green => true
+ case Red => true
+ case _ => false
+}
+
+fav_colour(Blue)
-def foo[A](args: List[A]) = ???
+// ... a tiny bit more useful: Roman Numerals
+
+sealed abstract class RomanDigit
+case object I extends RomanDigit
+case object V extends RomanDigit
+case object X extends RomanDigit
+case object L extends RomanDigit
+case object C extends RomanDigit
+case object D extends RomanDigit
+case object M extends RomanDigit
+
+type RomanNumeral = List[RomanDigit]
+
+List(I, M,C,D,X,X,V,I,I, A)
+
+/*
+I -> 1
+II -> 2
+III -> 3
+IV -> 4
+V -> 5
+VI -> 6
+VII -> 7
+VIII -> 8
+IX -> 9
+X -> 10
+*/
-foo(List("1","2","3","4"))
+def RomanNumeral2Int(rs: RomanNumeral): Int = rs match {
+ case Nil => 0
+ case M::r => 1000 + RomanNumeral2Int(r)
+ case C::M::r => 900 + RomanNumeral2Int(r)
+ case D::r => 500 + RomanNumeral2Int(r)
+ case C::D::r => 400 + RomanNumeral2Int(r)
+ case C::r => 100 + RomanNumeral2Int(r)
+ case X::C::r => 90 + RomanNumeral2Int(r)
+ case L::r => 50 + RomanNumeral2Int(r)
+ case X::L::r => 40 + RomanNumeral2Int(r)
+ case X::r => 10 + RomanNumeral2Int(r)
+ case I::X::r => 9 + RomanNumeral2Int(r)
+ case V::r => 5 + RomanNumeral2Int(r)
+ case I::V::r => 4 + RomanNumeral2Int(r)
+ case I::r => 1 + RomanNumeral2Int(r)
+}
+
+RomanNumeral2Int(List(I,V)) // 4
+RomanNumeral2Int(List(I,I,I,I)) // 4 (invalid Roman number)
+RomanNumeral2Int(List(V,I)) // 6
+RomanNumeral2Int(List(I,X)) // 9
+RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979
+RomanNumeral2Int(List(M,M,X,V,I,I)) // 2017
+
+abstract class Tree
+case class Leaf(x: Int)
+case class Branch(tl: Tree, tr: Tree)
-// from knight1.scala
-def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ???
+abstract class Rexp
+case object ZERO extends Rexp // matches nothing
+case object ONE extends Rexp // matches the empty string
+case class CHAR(c: Char) extends Rexp // matches a character c
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
+case class STAR(r: Rexp) extends Rexp // star
-// should be
-def first[A, B](xs: List[A], f: A => Option[B]) : Option[B] = ???
+def depth(r: Rexp) : Int = r match {
+ case ZERO => 1
+ case ONE => 1
+ case CHAR(_) => 1
+ case ALT(r1, r2) => 1 + List(depth(r1), depth(r2)).max
+ case SEQ(r1, r2) => 1 + List(depth(r1), depth(r2)).max
+ case STAR(r1) => 1 + depth(r1)
+}
+
+
+// Trees (example of an Algebraic Datatype)
+
+
+abstract class Tree
+case class Leaf(x: Int) extends Tree
+case class Node(s: String, left: Tree, right: Tree) extends Tree
+
+val lf = Leaf(20)
+val tr = Node("foo", Leaf(10), Leaf(23))
+
+val lst : List[Tree] = List(lf, tr)
+
// expressions (essentially trees)
-abstract class Exp
+sealed abstract class Exp
case class N(n: Int) extends Exp // for numbers
case class Plus(e1: Exp, e2: Exp) extends Exp
case class Times(e1: Exp, e2: Exp) extends Exp
@@ -44,6 +233,7 @@
}
val e = Plus(N(9), Times(N(3), N(4)))
+println(e.toString)
println(string(e))
def eval(e: Exp) : Int = e match {
@@ -59,7 +249,7 @@
// e * 0, 0 * e => 0
// e * 1, 1 * e => e
//
-// (....0 ....)
+// (....9 ....)
def simp(e: Exp) : Exp = e match {
case N(n) => N(n)
@@ -83,6 +273,11 @@
println(string(simp(e2)))
+
+
+
+
+
// Tokens and Reverse Polish Notation
abstract class Token
case class T(n: Int) extends Token
@@ -116,6 +311,53 @@
comp("1 2 + 4 * 5 + 3 +".split(" ").toList.map(proc), Nil)
+// Tail recursion
+//================
+
+def fact(n: BigInt): BigInt =
+ if (n == 0) 1 else n * fact(n - 1)
+
+
+fact(10)
+fact(1000)
+fact(100000)
+
+
+def factT(n: BigInt, acc: BigInt): BigInt =
+ if (n == 0) acc else factT(n - 1, n * acc)
+
+
+factT(10, 1)
+println(factT(100000, 1))
+
+
+// there is a flag for ensuring a function is tail recursive
+import scala.annotation.tailrec
+
+@tailrec
+def factT(n: BigInt, acc: BigInt): BigInt =
+ if (n == 0) acc else factT(n - 1, n * acc)
+
+factT(100000, 1)
+
+// for tail-recursive functions the Scala compiler
+// generates loop-like code, which does not need
+// to allocate stack-space in each recursive
+// call; Scala can do this only for tail-recursive
+// functions
+
+// Moral: Whenever a recursive function is resource-critical
+// (i.e. works with a large recursion depth), then you need to
+// write it in tail-recursive fashion.
+//
+// Unfortuantely, Scala because of current limitations in
+// the JVM is not as clever as other functional languages. It can
+// only optimise "self-tail calls". This excludes the cases of
+// multiple functions making tail calls to each other. Well,
+// nothing is perfect.
+
+
+
// Polymorphic Types
//===================
@@ -158,9 +400,6 @@
map(List(1, 2, 3, 4), (x: Int) => x.toString)
-// from knight1.scala
-def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ???
-
// should be
def first[A, B](xs: List[A], f: A => Option[B]) : Option[B] = ???
@@ -278,55 +517,6 @@
// Source.fromFile(name)(encoding)
-// Tail recursion
-//================
-
-def fact(n: Int): Int =
- if (n == 0) 1 else n * fact(n - 1)
-
-
-fact(10)
-fact(1000)
-fact(100000)
-
-def factB(n: BigInt): BigInt =
- if (n == 0) 1 else n * factB(n - 1)
-
-def factT(n: BigInt, acc: BigInt): BigInt =
- if (n == 0) acc else factT(n - 1, n * acc)
-
-
-factB(1000)
-
-
-factT(10, 1)
-println(factT(500000, 1))
-
-
-// there is a flag for ensuring a function is tail recursive
-import scala.annotation.tailrec
-
-@tailrec
-def factT(n: BigInt, acc: BigInt): BigInt =
- if (n == 0) acc else factT(n - 1, n * acc)
-
-factT(100000, 1)
-
-// for tail-recursive functions the Scala compiler
-// generates loop-like code, which does not need
-// to allocate stack-space in each recursive
-// call; Scala can do this only for tail-recursive
-// functions
-
-// Moral: Whenever a recursive function is resource-critical
-// (i.e. works with a large recursion depth), then you need to
-// write it in tail-recursive fashion.
-//
-// Unfortuantely, Scala because of current limitations in
-// the JVM is not as clever as other functional languages. It can
-// only optimise "self-tail calls". This excludes the cases of
-// multiple functions making tail calls to each other. Well,
-// nothing is perfect.
--- a/progs/lecture5.scala Mon Nov 06 21:49:55 2023 +0000
+++ b/progs/lecture5.scala Fri Dec 08 00:54:36 2023 +0000
@@ -1,7 +1,91 @@
// Scala Lecture 5
//=================
-// (Immutable)
+// extension methods
+// implicit conversions
+// (Immutable) OOP
+
+// Cool Stuff in Scala
+//=====================
+
+
+// Extensions or How to Pimp your Library
+//======================================
+//
+// For example adding your own methods to Strings:
+// Imagine you want to increment strings, like
+//
+// "HAL".increment
+//
+// you can avoid ugly fudges, like a MyString, by
+// using implicit conversions.
+
+extension (s: String) {
+ def increment = s.map(c => (c + 1).toChar)
+}
+
+"HAL".increment
+
+
+
+
+import scala.concurrent.duration.{TimeUnit,SECONDS,MINUTES}
+
+case class Duration(time: Long, unit: TimeUnit) {
+ def +(o: Duration) =
+ Duration(time + unit.convert(o.time, o.unit), unit)
+}
+
+extension (that: Int) {
+ def seconds = Duration(that, SECONDS)
+ def minutes = Duration(that, MINUTES)
+}
+
+2.minutes + 60.seconds
+5.seconds + 2.minutes //Duration(125, SECONDS )
+
+
+// Regular expressions - the power of DSLs in Scala
+// and Laziness
+//==================================================
+
+abstract class Rexp
+case object ZERO extends Rexp // nothing
+case object ONE extends Rexp // the empty string
+case class CHAR(c: Char) extends Rexp // a character c
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative r1 + r2
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence r1 . r2
+case class STAR(r: Rexp) extends Rexp // star r*
+
+
+// some convenience for typing in regular expressions
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+
+def charlist2rexp(s: List[Char]): Rexp = s match {
+ case Nil => ONE
+ case c::Nil => CHAR(c)
+ case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+
+given Conversion[String, Rexp] = (s => charlist2rexp(s.toList))
+
+extension (r: Rexp) {
+ def | (s: Rexp) = ALT(r, s)
+ def % = STAR(r)
+ def ~ (s: Rexp) = SEQ(r, s)
+}
+
+
+
+//example regular expressions
+val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
+val sign = "+" | "-" | ""
+val number = sign ~ digit ~ digit.%
+
+
+
+
// Object Oriented Programming in Scala
// =====================================
@@ -38,9 +122,15 @@
def denom = y
}
-val half = new Fraction(1, 2)
+val half = Fraction(1, 2)
half.numer
+// does not work with "vanilla" classes
+half match {
+ case Fraction(x, y) => x / y
+}
+
+
case class Fraction(numer: Int, denom: Int)
val half = Fraction(1, 2)
@@ -48,6 +138,11 @@
half.numer
half.denom
+// works with case classes
+half match {
+ case Fraction(x, y) => x / y
+}
+
// In mandelbrot.scala I used complex (imaginary) numbers
// and implemented the usual arithmetic operations for complex
@@ -55,7 +150,7 @@
case class Complex(re: Double, im: Double) {
// represents the complex number re + im * i
- def foo(that: Complex) = Complex(this.re + that.re, this.im + that.im)
+ def +(that: Complex) = Complex(this.re + that.re, this.im + that.im)
def -(that: Complex) = Complex(this.re - that.re, this.im - that.im)
def *(that: Complex) = Complex(this.re * that.re - this.im * that.im,
this.re * that.im + that.re * this.im)
@@ -63,9 +158,11 @@
def abs = Math.sqrt(this.re * this.re + this.im * this.im)
}
-object.method(....)
+// usual way to reference methods
+//object.method(....)
-val test = Complex(1, 2) + Complex (3, 4)
+val test = Complex(1, 2) + (Complex (3, 4))
+
import scala.language.postfixOps
(List(5,4,3,2,1) sorted) reverse
@@ -84,8 +181,8 @@
import scala.language.implicitConversions
val i = Complex(0, 1)
-implicit def double2complex(re: Double) = Complex(re, 0)
+given Conversion[Double, Complex] = (re => Complex(re, 0))
val inum1 = -2.0 + -1.5 * i
val inum2 = 1.0 + 1.5 * i
@@ -126,10 +223,11 @@
def +(other: Fraction) =
Fraction(numer * other.denom + other.numer * denom,
denom * other.denom)
- def *(other: Fraction) = Fraction(numer * other.numer, denom * other.denom)
+ def *(other: Fraction) =
+ Fraction(numer * other.numer, denom * other.denom)
}
-implicit def Int2Fraction(x: Int) = Fraction(x, 1)
+given Conversion[Int, Fraction] = (x => Fraction(x, 1))
val half = Fraction(1, 2)
val third = Fraction (1, 3)
@@ -255,8 +353,6 @@
subset(nfa).accepts("aaaaabbbaaa".toList) // false
subset(nfa).accepts("ac".toList) // false
-import scala.math.pow
-
// Laziness with style
//=====================
@@ -350,24 +446,15 @@
case c::Nil => CHAR(c)
case c::s => SEQ(CHAR(c), charlist2rexp(s))
}
-implicit def string2rexp(s: String): Rexp =
- charlist2rexp(s.toList)
-implicit def RexpOps (r: Rexp) = new {
+given Conversion[String, Rexp] = (s => charlist2rexp(s.toList))
+
+extension (r: Rexp) {
def | (s: Rexp) = ALT(r, s)
def % = STAR(r)
def ~ (s: Rexp) = SEQ(r, s)
}
-implicit def stringOps (s: String) = new {
- def | (r: Rexp) = ALT(s, r)
- def | (r: String) = ALT(s, r)
- def % = STAR(s)
- def ~ (r: Rexp) = SEQ(s, r)
- def ~ (r: String) = SEQ(s, r)
-}
-
-
//example regular expressions
--- a/progs/mandelbrot.scala Mon Nov 06 21:49:55 2023 +0000
+++ b/progs/mandelbrot.scala Fri Dec 08 00:54:36 2023 +0000
@@ -114,8 +114,8 @@
val d_x = (end.re - start.re) / W
val d_y = (end.im - start.im) / H
- for (y <- (0 until H)) {
- for (x <- (0 until W)) {
+ for (y <- (0 until H).par) {
+ for (x <- (0 until W).par) {
val c = start +
(x * d_x + y * d_y * i)
--- a/slides/Point.scala Mon Nov 06 21:49:55 2023 +0000
+++ b/slides/Point.scala Fri Dec 08 00:54:36 2023 +0000
@@ -1,1 +1,1 @@
-case class Point(val x: Int, val y: Int)
+case class Point(x: Int, y: Int)
Binary file slides/slides01.pdf has changed
--- a/slides/slides01.tex Mon Nov 06 21:49:55 2023 +0000
+++ b/slides/slides01.tex Fri Dec 08 00:54:36 2023 +0000
@@ -157,9 +157,10 @@
\end{textblock}
\begin{textblock}{6}(11,3)
-\begin{tabular}{l}
+\begin{tabular}{c}
\includegraphics[scale=0.08]{../pics/lichess.png}\\[-1mm]
-{\footnotesize lichess engine (open source)}
+ {\footnotesize lichess engine (open source)}\\[-2mm]
+ {\footnotesize \url{lichess.org}}\\
\end{tabular}
\end{textblock}
@@ -280,8 +281,7 @@
\includegraphics[scale=0.10]{../pics/vscode.png}\\[-10mm]\mbox{}
\end{center}\bigskip
-\item there is a plugin for Eclipse (called Scala IDE)\medskip
-\item there is also a plugin for IntelliJ\medskip
+\item there is also a plugin for IntelliJ, but I do not recommend it\medskip
\end{itemize}
\end{minipage}
@@ -1021,6 +1021,19 @@
\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t,fragile]
+\frametitle{\mbox{}\hspace{40mm}\textbf{???}}
+
+\begin{textblock}{5}(2,6)
+\includegraphics[scale=0.35]{../pics/commits.png}
+\end{textblock}
+
+\end{frame}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
\end{document}
%%% Local Variables:
Binary file slides/slides02.pdf has changed
--- a/slides/slides02.tex Mon Nov 06 21:49:55 2023 +0000
+++ b/slides/slides02.tex Fri Dec 08 00:54:36 2023 +0000
@@ -33,16 +33,14 @@
\end{textblock}}
\begin{document}
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[5mm]
- \huge PEP Scala (2)
+ \hspace{7mm}\huge PEP Scala (\liningnums{2})
\end{tabular}}
-
\normalsize
\begin{center}
\begin{tabular}{ll}
@@ -50,14 +48,24 @@
%Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\
Slides \& Code: & KEATS\bigskip\\
- Office Hour: & Fridays 11:00 -- 12:00\\
+ Office Hour: & Fridays 13:00 -- 14:00\\
Location: & N7.07 (North Wing, Bush House)\bigskip\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\ \\
+ %Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\
\end{tabular}
\end{center}
+ %\tiny
+ %developed since 2004 bv Martin Odersky
+ %picture about assignments
+
+\begin{textblock}{6}(0.5,0.5)
+\includegraphics[scale=0.035]{../pics/assign.jpg}\\[-1mm]
+\end{textblock}
+
\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Binary file slides/slides03.pdf has changed
--- a/slides/slides03.tex Mon Nov 06 21:49:55 2023 +0000
+++ b/slides/slides03.tex Fri Dec 08 00:54:36 2023 +0000
@@ -7,8 +7,17 @@
\usetikzlibrary{shapes}
\usepackage[export]{adjustbox}
+
\hfuzz=220pt
+\usepackage{tcolorbox}
+\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
+\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
+\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
+
+
+
+
%\setmonofont[Scale=.88]{Consolas}
%\newfontfamily{\consolas}{Consolas}
@@ -45,7 +54,7 @@
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[5mm]
- \huge PEP Scala (3)
+ \hspace{7mm}\huge PEP Scala (\liningnums{3})
\end{tabular}}
\normalsize
@@ -55,16 +64,27 @@
%Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\
Slides \& Code: & KEATS\bigskip\\
- Office Hour: & Fridays 11:00 -- 12:00\\
+ Office Hour: & Fridays 13:00 -- 14:00\\
Location: & N7.07 (North Wing, Bush House)\bigskip\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\ \\
+ %Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\
\end{tabular}
\end{center}
+ %\tiny
+ %developed since 2004 bv Martin Odersky
+ %picture about assignments
+
+\begin{textblock}{6}(0.5,0.5)
+\includegraphics[scale=0.035]{../pics/assign.jpg}\\[-1mm]
+\end{textblock}
+
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \frametitle{Preliminary 6}
@@ -84,30 +104,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
-
-\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
-def collatz(n: Long) : Long =
- {
- val toReturn = collatzHelper(n, 0)
- toReturn
- }
-\end{lstlisting}
-
-\pause
-\bigskip
-\rule{11cm}{0.3mm}
-\bigskip
-
-\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
-def collatz(n: Long) : Long =
- collatzHelper(n, 0)
-\end{lstlisting}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c,fragile]
\frametitle{Default Arguments}
\small
@@ -408,6 +404,150 @@
\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+{
+\setbeamercolor{background canvas}{bg=cream}
+\begin{frame}[c]
+ \frametitle{\mbox{}\hspace{40mm}\textbf{Feedback in
+ \textcolor{red}{\underline{CFL}!}}}
+
+\begin{minipage}{1.3\textwidth}
+\begin{mybox3}{End-of-year feedback for 6CCS3CFL in 2019}\it\small
+Unequivocally the worst module I've taken on this course. The subject
+matter is fascinating, however the insistence on the use of this
+abomination of a language "Scala" completely ruins it. If you're going
+to teach something as complex as this, use a proper language, not some
+"object oriented functional" abomination. Use C, you know, the
+language that real compilers are written in. I will go to the end of
+the earth to dissuade others from taking this module so long as Scala
+is still being used.\\
+\mbox{}\hfill-- Lone voice in the end-of-year feedback in 2019
+\end{mybox3}
+\end{minipage}\bigskip
+
+\end{frame}
+}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+{\definecolor{rred}{HTML}{C0504D}
+\setbeamercolor{background canvas}{bg=cream}
+\begin{frame}[c]
+\frametitle{Students in CFL}
+
+\begin{center}
+\begin{tikzpicture}
+ \begin{axis}[symbolic x coords={2016,2017,2018,2019,2020,2021,2022,2023},
+ width = \textwidth,
+ height = 5cm,
+ bar width=8mm,
+ nodes near coords,
+ axis lines = left,
+ text=black,
+ ymin=0,
+ clip=false,
+ hide y axis,
+ axis line style={-},
+ name=mygraph
+ ]
+
+\addplot[ybar,style={rred,fill=rred!75,mark=none},text=black] coordinates {
+(2023,183)
+(2022,112)
+(2021,98)
+(2020,59)
+(2019,38)
+(2018,20)
+(2017,22)
+(2016,8)};
+\end{axis}
+\node[anchor=north, yshift=-10mm] at (mygraph.south) {\small{}Student numbers since the start of the compiler module.};
+
+\end{tikzpicture}
+\end{center}
+
+\begin{textblock}{5}(12, 2.5)
+ \includegraphics[scale=0.15]{../pics/cfl.png}\\
+ \hspace{5mm}2021
+\end{textblock}
+
+\begin{textblock}{5}(12, 9)
+ \includegraphics[scale=0.15]{../pics/cfl2021.png}\\
+ \hspace{5mm}2022
+\end{textblock}
+\end{frame}
+}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+{
+\setbeamercolor{background canvas}{bg=cream}
+\begin{frame}[c]
+
+\mbox{}\\[-4mm]
+
+\begin{minipage}{1.3\textwidth}
+\begin{mybox3}{One comment from this year}\it\small
+ I feel like the module's point is to help us experience what it is
+ like to program very challenging problems, it's not very realistic
+ as in a realistic scenario we would have access to the internet, and
+ other people's code and may collaborate. I feel like the point of
+ the module is taken away due to how the plagiarism and collusion
+ rules are put into place.
+\end{mybox3}
+\end{minipage}\smallskip
+
+\begin{minipage}{1.3\textwidth}
+\begin{mybox3}{Another comment from this year}\it\small
+To prepare students for the C++ coursework better, for example introducing recursion and/or backtracking, because that is a big part of the coursework but wasn't even touched upon in the videos
+\end{mybox3}
+\end{minipage}\smallskip
+
+\begin{minipage}{1.3\textwidth}
+\begin{mybox3}{Even another comment from this year}\it\small
+The coursework is too difficult.
+\end{mybox3}
+\end{minipage}
+
+
+
+\end{frame}
+}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+{
+\setbeamercolor{background canvas}{bg=cream}
+\begin{frame}[c]
+
+\begin{itemize}
+\item we reduced the amount of work this year and gave more time for C++ CW
+\item we recruited TA's for\bigskip
+
+installation problems:
+\begin{itemize}
+\item Oscar Sjostedt (\texttt{\small{}oscar.sjostedt@kcl.ac.uk})
+\item Nicole Lehchevska (\texttt{\small{}nicole.lehchevska@kcl.ac.uk})\bigskip
+\end{itemize}
+github problems:
+\begin{itemize}
+\item Quan Tran (\texttt{\small{}anh.tran@kcl.ac.uk})\bigskip
+\end{itemize}
+discussion forum / general problems:
+\begin{itemize}
+\item Ruben Ticehurst-James (\texttt{\small{}ruben.ticehurst-james@kcl.ac.uk})
+\end{itemize}
+\end{itemize}
+
+\only<2->{
+\begin{textblock}{7}(9, 8)
+ \textcolor{red}{\Large\bf Could you
+ please spend the next 10 mins to fill
+ out the end-of-year feedback.}
+ \includegraphics[scale=0.035]{thanks.png}
+\end{textblock}}
+
+\end{frame}
+}
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Binary file slides/slides04.pdf has changed
--- a/slides/slides04.tex Mon Nov 06 21:49:55 2023 +0000
+++ b/slides/slides04.tex Fri Dec 08 00:54:36 2023 +0000
@@ -175,10 +175,10 @@
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- %Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\
+ %%Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\
Slides \& Code: & KEATS\bigskip\\
- Office Hour: & Fridays 11:00 -- 12:00\\
+ Office Hour: & Fridays 13:00 -- 14:00\\
Location: & N7.07 (North Wing, Bush House)\bigskip\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\ \\