--- 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
}
}
--- 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