--- a/cws/cw05.tex Fri Nov 22 17:01:55 2019 +0000
+++ b/cws/cw05.tex Tue Nov 26 01:22:36 2019 +0000
@@ -10,6 +10,8 @@
%% \usepackage{accents}
\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}
+%% change Console to scala.io.StdIn.readByte()
+
\begin{document}
--- a/marking2/mk Fri Nov 22 17:01:55 2019 +0000
+++ b/marking2/mk Tue Nov 26 01:22:36 2019 +0000
@@ -1,34 +1,27 @@
-#!/bin/sh
-###set -e
+#!/bin/bash
+set -euo pipefail
+
trap "exit" INT
-files=${1:-assignment20187-*}
+files=${1:-assignment2019scala-*/Part7}
for sd in $files; do
cd $sd
echo $sd
touch .
- cp ../../../marking2/*.sh .
- cp ../../../marking2/danube_test1.scala .
- cp ../../../marking2/danube_test2.scala .
- cp ../../../marking2/docdiff_test1.scala .
- cp ../../../marking2/docdiff_test2.scala .
- cp ../../../marking2/docdiff_test3.scala .
- cp ../../../marking2/docdiff_test4.scala .
- cp ../../../marking2/movies.csv .
- cp ../../../marking2/ratings.csv .
+ cp ../../../../../marking2/docdiff_test.sh .
+ cp ../../../../../marking2/docdiff_test1.scala .
+ cp ../../../../../marking2/docdiff_test2.scala .
+ cp ../../../../../marking2/docdiff_test3.scala .
+ cp ../../../../../marking2/docdiff_test4.scala .
./docdiff_test.sh output
- ./danube_test.sh output
- rm *.sh
- rm danube_test1.scala
- rm danube_test2.scala
+ rm docdiff_test.sh
rm docdiff_test1.scala
rm docdiff_test2.scala
rm docdiff_test3.scala
rm docdiff_test4.scala
- rm ratings.csv
- rm movies.csv
+ cd ..
cd ..
done
Binary file pics/hints.png has changed
--- a/progs/lecture3.scala Fri Nov 22 17:01:55 2019 +0000
+++ b/progs/lecture3.scala Tue Nov 26 01:22:36 2019 +0000
@@ -300,215 +300,6 @@
// User-defined Datatypes and Pattern Matching
//=============================================
-// trees
-
-
-
-// expressions
-
-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
-
-def string(e: Exp) : String = e match {
- case N(n) => s"$n"
- case Plus(e1, e2) => s"(${string(e1)} + ${string(e2)})"
- case Times(e1, e2) => s"(${string(e1)} * ${string(e2)})"
-}
-
-val e = Plus(N(9), Times(N(3), N(4)))
-println(string(e))
-
-def eval(e: Exp) : Int = e match {
- case N(n) => n
- case Plus(e1, e2) => eval(e1) + eval(e2)
- case Times(e1, e2) => eval(e1) * eval(e2)
-}
-
-println(eval(e))
-
-def simp(e: Exp) : Exp = e match {
- case N(n) => N(n)
- case Plus(e1, e2) => (simp(e1), simp(e2)) match {
- case (N(0), e2s) => e2s
- case (e1s, N(0)) => e1s
- case (e1s, e2s) => Plus(e1s, e2s)
- }
- case Times(e1, e2) => (simp(e1), simp(e2)) match {
- case (N(0), _) => N(0)
- case (_, N(0)) => N(0)
- case (N(1), e2s) => e2s
- case (e1s, N(1)) => e1s
- case (e1s, e2s) => Times(e1s, e2s)
- }
-}
-
-
-val e2 = Times(Plus(N(0), N(1)), Plus(N(0), N(9)))
-println(string(e2))
-println(string(simp(e2)))
-
-
-// Tokens and Reverse Polish Notation
-sealed abstract class Token
-case class T(n: Int) extends Token
-case object PL extends Token
-case object TI extends Token
-
-def rp(e: Exp) : List[Token] = e match {
- case N(n) => List(T(n))
- case Plus(e1, e2) => rp(e1) ::: rp(e2) ::: List(PL)
- case Times(e1, e2) => rp(e1) ::: rp(e2) ::: List(TI)
-}
-println(string(e2))
-println(rp(e2))
-
-def comp(ls: List[Token], st: List[Int]) : Int = (ls, st) match {
- case (Nil, st) => st.head
- case (T(n)::rest, st) => comp(rest, n::st)
- case (PL::rest, n1::n2::st) => comp(rest, n1 + n2::st)
- case (TI::rest, n1::n2::st) => comp(rest, n1 * n2::st)
-}
-
-comp(rp(e), Nil)
-
-def proc(s: String) : Token = s match {
- case "+" => PL
- case "*" => TI
- case _ => T(s.toInt)
-}
-
-comp("1 2 + 4 * 5 + 3 +".split(" ").toList.map(proc), Nil)
-
-
-
-
-// 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
-
-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) =
- (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))
-
-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)))
-}
-
-//get_row(game0, 0)
-//get_row(game0, 1)
-//get_col(game0, 0)
-//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 candidates(game: String, pos: Pos): List[Char] =
- allValues.diff(toAvoid(game, pos))
-
-//candidates(game0, (0,0))
-
-def pretty(game: String): String =
- "\n" + (game.sliding(MaxValue, MaxValue).mkString("\n"))
-
-
-def search(game: String): List[String] = {
- if (isDone(game)) List(game)
- else {
- val cs = candidates(game, emptyPosition(game))
- cs.map(c => search(update(game, empty(game), c))).toList.flatten
- }
-}
-
-search(game0).map(pretty)
-
-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", "")
-
-
-// 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", "")
-
-// 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(game1).map(pretty)
-search(game3).map(pretty)
-search(game2).map(pretty)
-
-// 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()
- ((end - start) / 1.0e9) + " secs"
-}
-
-time_needed(1, search(game2))
-
--- a/progs/lecture4.scala Fri Nov 22 17:01:55 2019 +0000
+++ b/progs/lecture4.scala Tue Nov 26 01:22:36 2019 +0000
@@ -2,6 +2,321 @@
//=================
+// expressions (essentially trees)
+
+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
+
+def string(e: Exp) : String = e match {
+ case N(n) => s"$n"
+ case Plus(e1, e2) => s"(${string(e1)} + ${string(e2)})"
+ case Times(e1, e2) => s"(${string(e1)} * ${string(e2)})"
+}
+
+val e = Plus(N(9), Times(N(3), N(4)))
+println(string(e))
+
+def eval(e: Exp) : Int = e match {
+ case N(n) => n
+ case Plus(e1, e2) => eval(e1) + eval(e2)
+ case Times(e1, e2) => eval(e1) * eval(e2)
+}
+
+println(eval(e))
+
+// simplification rules:
+// e + 0, 0 + e => e
+// e * 0, 0 * e => 0
+// e * 1, 1 * e => e
+
+def simp(e: Exp) : Exp = e match {
+ case N(n) => N(n)
+ case Plus(e1, e2) => (simp(e1), simp(e2)) match {
+ case (N(0), e2s) => e2s
+ case (e1s, N(0)) => e1s
+ case (e1s, e2s) => Plus(e1s, e2s)
+ }
+ case Times(e1, e2) => (simp(e1), simp(e2)) match {
+ case (N(0), _) => N(0)
+ case (_, N(0)) => N(0)
+ case (N(1), e2s) => e2s
+ case (e1s, N(1)) => e1s
+ case (e1s, e2s) => Times(e1s, e2s)
+ }
+}
+
+
+val e2 = Times(Plus(N(0), N(1)), Plus(N(0), N(9)))
+println(string(e2))
+println(string(simp(e2)))
+
+
+// Tokens and Reverse Polish Notation
+abstract class Token
+case class T(n: Int) extends Token
+case object PL extends Token
+case object TI extends Token
+
+// transfroming an Exp into a list of tokens
+def rp(e: Exp) : List[Token] = e match {
+ case N(n) => List(T(n))
+ case Plus(e1, e2) => rp(e1) ::: rp(e2) ::: List(PL)
+ case Times(e1, e2) => rp(e1) ::: rp(e2) ::: List(TI)
+}
+println(string(e2))
+println(rp(e2))
+
+def comp(ls: List[Token], st: List[Int]) : Int = (ls, st) match {
+ case (Nil, st) => st.head
+ case (T(n)::rest, st) => comp(rest, n::st)
+ case (PL::rest, n1::n2::st) => comp(rest, n1 + n2::st)
+ case (TI::rest, n1::n2::st) => comp(rest, n1 * n2::st)
+}
+
+comp(rp(e), Nil)
+
+def proc(s: String) : Token = s match {
+ case "+" => PL
+ case "*" => TI
+ case _ => T(s.toInt)
+}
+
+comp("1 2 + 4 * 5 + 3 +".split(" ").toList.map(proc), Nil)
+
+
+
+
+// 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
+
+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) =
+ (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))
+
+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)))
+}
+
+//get_row(game0, 0)
+//get_row(game0, 1)
+//get_col(game0, 0)
+//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 candidates(game: String, pos: Pos): List[Char] =
+ allValues.diff(toAvoid(game, pos))
+
+//candidates(game0, (0,0))
+
+def pretty(game: String): String =
+ "\n" + (game.sliding(MaxValue, MaxValue).mkString("\n"))
+
+
+def search(game: String): List[String] = {
+ if (isDone(game)) List(game)
+ else {
+ val cs = candidates(game, emptyPosition(game))
+ cs.map(c => search(update(game, empty(game), c))).toList.flatten
+ }
+}
+
+search(game0).map(pretty)
+
+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(1, search(game2))
+
+
+
+// Tail recursion
+//================
+
+
+def fact(n: Long): Long =
+ if (n == 0) 1 else n * fact(n - 1)
+
+
+fact(10) // ok
+fact(1000) // silly
+fact(10000) // produces a stackoverflow
+
+def factB(n: BigInt): BigInt =
+ if (n == 0) 1 else n * factB(n - 1)
+
+factB(1000)
+
+
+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
+
+// tail recursive version that searches
+// for all Sudoku solutions
+
+
+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)
+ }
+ }
+}
+
+searchT(List(game3), List()).map(pretty)
+
+
+// tail recursive version that searches
+// for a single solution
+
+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)
+ }
+ }
+}
+
+search1T(List(game3)).map(pretty)
+time_needed(1, search1T(List(game3)))
+time_needed(1, search1T(List(game2)))
+
+// 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", "")
+
+searchT(List(game3), Nil).map(pretty)
+search1T(List(game3)).map(pretty)
+
+// 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.
+
+
+
+
// Polymorphic Types
//===================
@@ -38,9 +353,6 @@
map(List(1, 2, 3, 4), (x: Int) => x.toString)
-// Remember?
-def first[A, B](xs: List[A], f: A => Option[B]) : Option[B] = ...
-
// distinct / distinctBy
@@ -106,6 +418,111 @@
+// Cool Stuff in Scala
+//=====================
+
+
+// Implicits 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.
+
+
+implicit class MyString(s: String) {
+ def increment = s.map(c => (c + 1).toChar)
+}
+
+"HAL".increment
+
+
+// Abstract idea:
+// In that version implicit conversions were used to solve the
+// late extension problem; namely, given a class C and a class T,
+// how to have C extend T without touching or recompiling C.
+// Conversions add a wrapper when a member of T is requested
+// from an instance of C.
+
+//Another example (TimeUnit in 2.13?)
+
+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)
+}
+
+implicit class Int2Duration(that: Int) {
+ def seconds = new Duration(that, SECONDS)
+ def minutes = new Duration(that, MINUTES)
+}
+
+5.seconds + 2.minutes //Duration(125L, SECONDS )
+2.minutes + 60.seconds
+
+
+
+
+// Regular expressions - the power of DSLs in Scala
+//==================================================
+
+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*
+
+
+
+// writing (ab)* in the format above is
+// tedious
+val r0 = STAR(SEQ(CHAR('a'), CHAR('b')))
+
+
+// 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))
+}
+implicit def string2rexp(s: String): Rexp =
+ charlist2rexp(s.toList)
+
+
+val r1 = STAR("ab")
+val r2 = STAR(ALT("ab", "baa baa black sheep"))
+val r3 = STAR(SEQ("ab", ALT("a", "b")))
+
+implicit def RexpOps (r: Rexp) = new {
+ 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
+val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
+val sign = "+" | "-" | ""
+val number = sign ~ digit ~ digit.%
+
+
//
// Object Oriented Programming in Scala
//
@@ -403,107 +820,6 @@
-// Cool Stuff in Scala
-//=====================
-
-
-// Implicits or How to Pimp my 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.
-
-
-implicit class MyString(s: String) {
- def increment = for (c <- s) yield (c + 1).toChar
-}
-
-"HAL".increment
-
-
-// Abstract idea:
-// In that version implicit conversions were used to solve the
-// late extension problem; namely, given a class C and a class T,
-// how to have C extend T without touching or recompiling C.
-// Conversions add a wrapper when a member of T is requested
-// from an instance of C.
-
-//Another example (TimeUnit in 2.13?)
-
-case class Duration(time: Long, unit: TimeUnit) {
- def +(o: Duration) = Duration(time + unit.convert(o.time, o.unit), unit)
-}
-
-implicit class Int2Duration(that: Int) {
- def seconds = new Duration(that, SECONDS)
- def minutes = new Duration(that, MINUTES)
-}
-
-5.seconds + 2.minutes //Duration(125L, SECONDS )
-
-
-
-// Regular expressions - the power of DSLs in Scala
-//==================================================
-
-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*
-
-
-
-// writing (ab)* in the format above is
-// tedious
-val r0 = STAR(SEQ(CHAR('a'), CHAR('b')))
-
-
-// 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))
-}
-implicit def string2rexp(s: String): Rexp =
- charlist2rexp(s.toList)
-
-
-val r1 = STAR("ab")
-val r2 = STAR(ALT("ab", "baa baa black sheep"))
-val r3 = STAR(SEQ("ab", ALT("a", "b")))
-
-implicit def RexpOps (r: Rexp) = new {
- 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
-val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
-val sign = "+" | "-" | ""
-val number = sign ~ digit ~ digit.%
-
-
// Lazy Evaluation
//=================
@@ -519,13 +835,19 @@
(end - start)/(i * 1.0e9)
}
+
+// Mind-Blowing Regular Expressions
+
// same examples using the internal regexes
val evil = "(a*)*b"
+
+println("a" * 100)
+
("a" * 10 ++ "b").matches(evil)
("a" * 10).matches(evil)
("a" * 10000).matches(evil)
("a" * 20000).matches(evil)
("a" * 50000).matches(evil)
-time_needed(1, ("a" * 50000).matches(evil))
+time_needed(1, ("a" * 10000).matches(evil))
--- a/progs/sudoku.scala Fri Nov 22 17:01:55 2019 +0000
+++ b/progs/sudoku.scala Tue Nov 26 01:22:36 2019 +0000
@@ -53,6 +53,17 @@
map(c => search(update(game, empty(game), c))).toList.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)
+ }
+ }
+}
+
// a list of hard games according to Andrew Coles and Peter Norvig
val hard_games =
Binary file slides/slides04.pdf has changed
--- a/slides/slides04.tex Fri Nov 22 17:01:55 2019 +0000
+++ b/slides/slides04.tex Tue Nov 26 01:22:36 2019 +0000
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
@@ -145,9 +146,11 @@
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Office: & N\liningnums{7.07} (North Wing, Bush House)\\
- Slides \& Code: & KEATS\medskip\\
- Office Hours: & Mondays 12:00 -- 14:00\\
+ Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\
+ Slides \& Code: & KEATS\\
+ & \onslide<2>{\alert{A Crash-Course in Scala}}\bigskip\\
+ Office Hours: & Thursdays 12:00 -- 14:00\\
+ Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\
\end{tabular}
\end{center}
@@ -155,88 +158,54 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Somewhere Remote}
-
-\begin{center}
-\includegraphics[scale=0.37]{../pics/sahara.jpg}
-\end{center}
-
-\end{frame}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\frametitle{Hints in CW}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-\begin{frame}[t]
-\frametitle{This is a bit harsh\ldots}
-
-\mbox{}\\[-22mm]\mbox{}
-
-\begin{center}
-\begin{bubble}[10.5cm]
- ...trying a new method because the fucking github reports dont tell me
- which test failed. It's not really helpful when the inline tests work
- and it compiles but all i get is 'one test failed'... really helpful my dude.
-\end{bubble}
+\begin{center}
+\includegraphics[scale=0.4]{../pics/hints.png}
\end{center}
-\begin{center}
-\begin{bubble}[10.5cm]
- ...Reverted back and finished part 5, this is ridiculous how one test works
- and all I get is 'ONE TEST FAILED'. Fix your reports before giving us
- assignments like this...
-\end{bubble}
-\end{center}
+\small
+\begin{itemize}
+ \item Scala Library, e.g.~\texttt{span} in \\
+ \url{https://www.scala-lang.org/api/current/scala/collection/immutable/List.html}
+\end{itemize}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
-\end{frame}
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-\begin{frame}[t,fragile]
-\frametitle{Needless to say I tried it out}
-
-\mbox{}\\[-7mm]\mbox{}\footnotesize
+\begin{frame}[c]
+\frametitle{Preliminary 7}
-\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-4mm]
-> legal_moves(8, Nil, (2,2))
- = List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))
-
-> legal_moves(8, Nil, (7,7))
- = List((6,5), (5,6))
+Raw marks (261 submissions):\bigskip
-> legal_moves(8, List((4,1), (1,0)), (2,2))
- = List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))
-
-> legal_moves(1, Nil, (0,0))
- = List((-1,-2), (-2,-1))
+\begin{itemize}
+\item 4\%: \hspace{4mm}236
+\item 3\%: \hspace{4mm}10
+\item 2\%: \hspace{4mm}1
+\item 1\%: \hspace{4mm}0
+\item 0\%: \hspace{4mm}15
+\end{itemize}\bigskip\bigskip
-> legal_moves(2, Nil, (0,0))
- = List((1,-2), (-1,-2), (-2,-1), (-2,1))
-
-> legal_moves(3, Nil, (0,0))
- = List((1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2))
-\end{lstlisting}
-
-\LEFTarrow{1}{9}{9}
-\LEFTarrow{1}{12}{11}
-\DOWNarrow{1}{10}{13}
+\footnotesize
+(interviews ongoing!)
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\small
-\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm]
-def is_legal(dim: Int, p: Path, x: Pos): Boolean = {
- if (......some_really_long_condition.....) false
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]
+def is_legal(dim: Int, p: Path, x: Pos) = {
+ if (...some_really_long_condition...) false
else true
}
\end{lstlisting}
@@ -246,16 +215,130 @@
\rule{11cm}{0.3mm}
\bigskip
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]
+def is_legal(dim: Int, p: Path, x: Pos) =
+ !(...some_really_long_condition...)
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\small
+
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]
+def foobar(...) = {
+ val cs = for (c <- str) yield c.toLowerCase
+ ...
+}
+\end{lstlisting}
+
+\pause
+\bigskip
+\rule{11cm}{0.3mm}
+\bigskip
+
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=1mm]
+def foobar(...) = {
+ val cs = str.map(_.toLowerCase)
+ ...
+}
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\small
+
\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm]
-def is_legal(dim: Int, p: Path, x: Pos): Boolean =
- !......some_really_long_condition.....
-\end{lstlisting}\pause
-
+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)
+ }
+\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Last Week: Pattern Matching}
+\small
+
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=3mm]
+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
+ }
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Reverse Polish Notation}
+
+{\Large\bl{$(3 + 1) * (2 + 9)$}}\bigskip
+
+{\Large$\Rightarrow$}\bigskip
+
+{\;\;\Large\bl{$3\;\;1\;+\;2\;\;9\;+\;*$}}
+
+\begin{textblock}{3}(11,4)
+\begin{onlyenv}<2>
+\begin{lstlisting}[language=JVMIS]
+ldc 3
+ldc 1
+iadd
+ldc 2
+ldc 9
+iadd
+imul
+\end{lstlisting}
+\end{onlyenv}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Sudoku}
+
+A very simple-minded version on 110 problems:\bigskip
+
+\begin{itemize}
+\item 1 core: 800 secs
+\item 2 cores: 400 secs
+\item 8 cores: 290 secs
+\item 18 cores: 142 secs
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{DFAs}
@@ -349,12 +432,50 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{frame}[t]
+
+ \begin{center}
+ \includegraphics[scale=0.3]{../pics/blow.png}
+ \end{center}
+
+ \begin{textblock}{14}(2,11.4)
+ \large\bf{}Mind-Blowing Regular Expressions:\\
+ \centering in Python, JavaScript, Java
+ \end{textblock}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
- \frametitle{CW\liningnums{9} (\liningnums{1} Part): Regexes}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Regular Expressions}
+
+Suppose you have a regular expression
+\only<1-3>{\alert{\texttt{(a*)b}}}%
+\only<4->{\alert{\texttt{(a*)*b}}} :\bigskip
+
+\begin{center}
+\only<1>{\code{"aaaaaaaaaaaaaaab"}}
+\only<2>{\code{"aaaaa...........aaaaaaaaaaaaaaaaaaaab"}}
+\only<3>{\code{"aaaaa...........aaaaaaaaaaaaaaaaaaaa"}}
+\only<4>{\code{"aaaaa...........aaaaaaaaaaaaaaaaaaaab"}}
+\only<5->{\code{"aaaaa...........aaaaaaaaaaaaaaaaaaaa"}}
+\end{center}
+
+\only<6>{
+\begin{textblock}{13}(5,12)
+How long does Python need to find out?
+\end{textblock}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}<1>[c]
+ \frametitle{CW 9: Regexes}
\begin{center}
- Graphs: $(a^*)^* b$ and strings $\underbrace{\;a\ldots a\;}_{n}$\bigskip
+ Graphs: \alert{\texttt{(a*)*b}} and strings $\underbrace{\;\texttt{a}\ldots \texttt{a}\;}_{n}$\bigskip
\begin{tabular}[t]{@{\hspace{-8mm}}c@{\hspace{-4mm}}c@{}}
\only<1>{\raisebox{6mm}{\begin{tikzpicture}
@@ -421,26 +542,43 @@
\hfill\small\url{https://vimeo.com/112065252}
\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Hint}
\begin{center}
-\LARGE\textbf{\alert{Pattern-Matching}}
+ \includegraphics[angle=90,scale=0.35]{/Users/cu/vote.pdf}
\end{center}
\end{frame}
-
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{center}
+ \includegraphics[scale=0.25]{/Users/cu/dresden.png}
+\end{center}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c,fragile]
-\frametitle{\alert{Questions?}}
+\begin{textblock}{13}(2,12)
+\includegraphics[scale=0.08]{/Users/cu/kiss.jpg}
+\end{textblock}
+
+\begin{textblock}{13}(6.8,12)
+\includegraphics[scale=0.079]{/Users/cu/pioniere.jpg}
+\end{textblock}
+
+\begin{textblock}{13}(11,12)
+\includegraphics[scale=0.20]{/Users/cu/iron.jpg}
+\end{textblock}
+
+\DOWNarrow{1}{11}{8.6}
\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
--- a/solutions2/danube.scala Fri Nov 22 17:01:55 2019 +0000
+++ b/solutions2/danube.scala Tue Nov 26 01:22:36 2019 +0000
@@ -2,10 +2,12 @@
// at Danube.co.uk
//========================================
+
+object CW7b { // for purposes of generating a jar
+
import io.Source
import scala.util._
-object CW7b { // for purposes of generating a jar
// (1) Implement the function get_csv_url which takes an url-string
// as argument and requests the corresponding file. The two urls
--- a/testing5/bf.scala Fri Nov 22 17:01:55 2019 +0000
+++ b/testing5/bf.scala Tue Nov 26 01:22:36 2019 +0000
@@ -93,7 +93,7 @@
case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
- case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+ case ',' => (pc + 1, mp, write(mem, mp, scala.io.StdIn.readByte()))
case '[' =>
if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem)
case ']' => 
