# HG changeset patch # User Christian Urban # Date 1574731356 0 # Node ID ca9c1cf929fac2ebe9d59a709088bdb213f0d650 # Parent 2969ee4a6cee6fae172d641543c3d7995368a0b5 updated diff -r 2969ee4a6cee -r ca9c1cf929fa cws/cw05.tex --- 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} diff -r 2969ee4a6cee -r ca9c1cf929fa marking2/mk --- 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 diff -r 2969ee4a6cee -r ca9c1cf929fa pics/hints.png Binary file pics/hints.png has changed diff -r 2969ee4a6cee -r ca9c1cf929fa progs/lecture3.scala --- 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)) - diff -r 2969ee4a6cee -r ca9c1cf929fa progs/lecture4.scala --- 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)) diff -r 2969ee4a6cee -r ca9c1cf929fa progs/sudoku.scala --- 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 = diff -r 2969ee4a6cee -r ca9c1cf929fa slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 2969ee4a6cee -r ca9c1cf929fa slides/slides04.tex --- 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} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + diff -r 2969ee4a6cee -r ca9c1cf929fa solutions2/danube.scala --- 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 diff -r 2969ee4a6cee -r ca9c1cf929fa testing5/bf.scala --- 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 ']' =>