# HG changeset patch # User Christian Urban # Date 1606208646 0 # Node ID 1c829680503e19b192c689da731285d02db064ba # Parent fc118ee0fce4e816335ea78c221ead3b8329f812 updated diff -r fc118ee0fce4 -r 1c829680503e progs/lecture2.scala --- a/progs/lecture2.scala Mon Nov 23 02:43:03 2020 +0000 +++ b/progs/lecture2.scala Tue Nov 24 09:04:06 2020 +0000 @@ -592,11 +592,11 @@ def moves(xs: List[Int], n: Int) : List[List[Int]] = (xs, n) match { case (Nil, _) => Nil - case (xs, 0) => Nil + case (_, 0) => Nil case (x::xs, n) => (x::xs) :: moves(xs, n - 1) } - +// List(5,5,1,0) -> moves(List(5,1,0), 5) moves(List(5,1,0), 1) moves(List(5,1,0), 2) moves(List(5,1,0), 5) @@ -605,8 +605,9 @@ def search(xs: List[Int]) : Boolean = xs match { case Nil => true - case (x::xs) => - if (xs.length < x) true else moves(xs, x).exists(search(_)) + case x::xs => + if (xs.length < x) true + else moves(xs, x).exists(search(_)) } @@ -621,6 +622,11 @@ search(List(5,1,1)) search(List(3,5,1,0,0,0,0,0,0,0,0,1)) + +import scala.util._ +List.fill(100)(Random.nextInt(2)) +search(List.fill(100)(Random.nextInt(10))) + // generate *all* jump tours // if we are only interested in the shortes one, we could // shortcircut the calculation and only return List(x) in @@ -630,9 +636,10 @@ def jumps(xs: List[Int]) : List[List[Int]] = xs match { case Nil => Nil - case (x::xs) => { + case x::xs => { val children = moves(xs, x) - val results = children.map(cs => jumps(cs).map(x :: _)).flatten + val results = + children.map(cs => jumps(cs).map(x :: _)).flatten if (xs.length < x) List(x) :: results else results } } diff -r fc118ee0fce4 -r 1c829680503e progs/lecture3.scala --- a/progs/lecture3.scala Mon Nov 23 02:43:03 2020 +0000 +++ b/progs/lecture3.scala Tue Nov 24 09:04:06 2020 +0000 @@ -1,38 +1,6 @@ // Scala Lecture 3 //================= -// - last week -// -// option type -// higher-order function - - -def add(x: Int, y: Int) : Int = x + y - -def plus5(x: Int) : Int = add(5, x) - -plus5(6) - -def add2(x: Int)(y: Int) : Int = x + y - -def plus3(y: Int) : Int => Int = add2(3)(y) - -plus3(9) - -List(1,2,3,4,5).map(add2(3)) -List(1,2,3,4,5).map(add(3, _)) - -type Pos = (Int, Int) - -def test(p: Pos) = { - if (p._1 < 5 && p._2 < 5) { - Some(p) - } -} - -val l = List((1,2), (5,3), (2,5), (1,3)) - -l.map(test).flatten // naive quicksort with "On" function @@ -49,83 +17,12 @@ sortOn(n => - n, List(99,99,99,98,10,-3,2)) - - // Recursion Again ;o) //==================== -// A Web Crawler / Email Harvester -//================================= -// -// the idea is to look for links using the -// regular expression "https?://[^"]*" and for -// email addresses using yet 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 - -// val s = "foo bla christian@kcl.ac.uk 1234567" -// email_pattern.findAllIn(s).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 - -// a 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") - val page = get_page(url) - for (u <- get_all_URLs(page)) crawl(u, n - 1) - } -} - -// some starting URLs for the crawler -val startURL = """https://nms.kcl.ac.uk/christian.urban/""" - -crawl(startURL, 2) - -for (x <- List(1,2,3,4,5,6)) println(x) - -// 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).par) yield emails(u, n - 1)).flatten - } -} - -emails(startURL, 3) - - -// if we want to explore the internet "deeper", then we -// first have to parallelise the request of webpages: -// -// scala -cp scala-parallel-collections_2.13-0.2.0.jar -// import scala.collection.parallel.CollectionConverters._ - - - -// another well-known example -//============================ +// another well-known example: Towers of Hanoi +//============================================= def move(from: Char, to: Char) = println(s"Move disc from $from to $to!") @@ -143,84 +40,6 @@ -// Jumping Towers -//================ - - -// the first n prefixes of xs -// for 1 => include xs - -def moves(xs: List[Int], n: Int) : List[List[Int]] = (xs, n) match { - case (Nil, _) => Nil - case (_, 0) => Nil - case (y::ys, n) => xs :: moves(ys, n - 1) -} - - -moves(List(5,1,0), 1) -moves(List(5,1,0), 2) -moves(List(5,1,0), 5) - -// checks whether a jump tour exists at all - -def search(xs: List[Int]) : Boolean = xs match { - case Nil => true - case x::xs => - if (xs.length < x) true - else moves(xs, x).exists(search(_)) -} - - -search(List(5,3,2,5,1,1)) -search(List(3,5,1,0,0,0,1)) -search(List(3,5,1,0,0,0,0,1)) -search(List(3,5,1,0,0,0,1,1)) -search(List(3,5,1)) -search(List(5,1,1)) -search(Nil) -search(List(1)) -search(List(5,1,1)) -search(List(3,5,1,0,0,0,0,0,0,0,0,1)) - -// generates *all* jump tours -// if we are only interested in the shortest one, we could -// shortcircut the calculation and only return List(x) in -// case where xs.length < x, because no tour can be shorter -// than 1 -// - -def jumps(xs: List[Int]) : List[List[Int]] = xs match { - case Nil => Nil - case x::xs => { - val children = moves(xs, x) - val results = children.map(cs => jumps(cs).map(x :: _)).flatten - if (xs.length < x) List(x)::results else results - } -} - -jumps(List(5,3,2,5,1,1)).minBy(_.length) -jumps(List(3,5,1,2,1,2,1)) -jumps(List(3,5,1,2,3,4,1)) -jumps(List(3,5,1,0,0,0,1)) -jumps(List(3,5,1)) -jumps(List(5,1,1)) -jumps(Nil) -jumps(List(1)) -jumps(List(5,1,2)) -moves(List(1,2), 5) -jumps(List(1,5,1,2)) -jumps(List(3,5,1,0,0,0,0,0,0,0,0,1)) - -jumps(List(5,3,2,5,1,1)).minBy(_.length) -jumps(List(1,3,5,8,9,2,6,7,6,8,9)).minBy(_.length) -jumps(List(1,3,6,1,0,9)).minBy(_.length) -jumps(List(2,3,1,1,2,4,2,0,1,1)).minBy(_.length) - - - - - - // User-defined Datatypes //======================== @@ -228,9 +47,13 @@ case class Leaf(x: Int) extends Tree case class Node(s: String, left: Tree, right: Tree) extends Tree -List(Leaf(20), Node("foo", Leaf(1), Leaf(2))) +val lf = Leaf(20) +val tr = Node("foo", Leaf(10), Leaf(23)) -sealed abstract class Colour +val lst : List[Tree] = List(lf, tr) + + +abstract class Colour case object Red extends Colour case object Green extends Colour case object Blue extends Colour @@ -242,7 +65,8 @@ case _ => false } -fav_colour(Green) +fav_colour(Blue) + // ... a tiny bit more useful: Roman Numerals @@ -257,7 +81,7 @@ type RomanNumeral = List[RomanDigit] -List(X,I,M,D) +List(X,I,M,A) /* I -> 1 @@ -297,6 +121,61 @@ RomanNumeral2Int(List(M,M,X,V,I,I)) // 2017 +// 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))) +e.toString +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 +// +// (....9 ....) + +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))) + + + // String interpolations as patterns val date = "2019-11-26" @@ -314,9 +193,6 @@ parse_date("26.11.2019") -// User-defined Datatypes and Pattern Matching -//============================================= - @@ -356,6 +232,70 @@ // call; Scala can do this only for tail-recursive // functions + + + +// Sudoku +//======== + + +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)) + +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) +} + + +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)).par. + 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) + } + } +} + +def pretty(game: String): String = + "\n" + (game.sliding(maxValue, maxValue).mkString(",\n")) + + // tail recursive version that searches // for all solutions diff -r fc118ee0fce4 -r 1c829680503e slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r fc118ee0fce4 -r 1c829680503e slides/slides03.tex --- a/slides/slides03.tex Mon Nov 23 02:43:03 2020 +0000 +++ b/slides/slides03.tex Tue Nov 24 09:04:06 2020 +0000 @@ -274,7 +274,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{``Children'' / moves} +\frametitle{next moves} \begin{center} \begin{tikzpicture} @@ -289,6 +289,10 @@ \end{tikzpicture} \end{center} +\begin{textblock}{4}(13,12) +\includegraphics[scale=0.06]{../pics/chess.jpg} +\end{textblock} + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%