# HG changeset patch # User Christian Urban # Date 1479352244 0 # Node ID 6610c1dfa8a9bbb750fa346ee961c6a1bc3e404f # Parent 34153e0485fc727e40dc5e94cb44db7f34ef54a9 updated diff -r 34153e0485fc -r 6610c1dfa8a9 progs/lecture2.scala --- a/progs/lecture2.scala Wed Nov 16 23:34:36 2016 +0000 +++ b/progs/lecture2.scala Thu Nov 17 03:10:44 2016 +0000 @@ -2,6 +2,25 @@ //================= +// Implicits +//=========== +// +// 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 + + // Option type //============= @@ -74,7 +93,6 @@ - // Type abbreviations //==================== @@ -85,7 +103,6 @@ - // No return in Scala //==================== @@ -110,6 +127,8 @@ x * x } + + // Pattern Matching //================== @@ -151,6 +170,65 @@ case _ => "many" } +// User-defined Datatypes +//======================== + +abstract class Tree +case class Node(elem: Int, left: Tree, right: Tree) extends Tree +case class Leaf() extends Tree + +def insert(tr: Tree, n: Int): Tree = tr match { + case Leaf() => Node(n, Leaf(), Leaf()) + case Node(m, left, right) => + if (n == m) Node(m, left, right) + else if (n < m) Node(m, insert(left, n), right) + else Node(m, left, insert(right, n)) +} + + +val t1 = Node(4, Node(2, Leaf(), Leaf()), Node(7, Leaf(), Leaf())) +insert(t1, 3) + +def balance(tr: Tree): Int = tr match { + case Leaf() => 0 + case Node(_, left, right) => balance(left) - balance(right) +} + + +// another example + +abstract class Person +case class King() extends Person +case class Peer(deg: String, terr: String, succ: Int) extends Person +case class Knight(name: String) extends Person +case class Peasant(name: String) extends Person +case class Clown() extends Person + +def title(p: Person): String = p match { + case King() => "His Majesty the King" + case Peer(deg, terr, _) => s"The ${deg} of ${terr}" + case Knight(name) => s"Sir ${name}" + case Peasant(name) => name +} + +def superior(p1: Person, p2: Person): Boolean = (p1, p2) match { + case (King(), _) => true + case (Peer(_,_,_), Knight(_)) => true + case (Peer(_,_,_), Peasant(_)) => true + case (Peer(_,_,_), Clown()) => true + case (Knight(_), Peasant(_)) => true + case (Knight(_), Clown()) => true + case (Clown(), Peasant(_)) => true + case _ => false +} + +val people = List(Knight("David"), + Peer("Duke", "Norfolk", 42), + Peasant("Christian"), + King(), + Clown()) + +println(people.sortWith(superior(_, _))) // Higher-Order Functions //======================== @@ -174,34 +252,141 @@ lst.map(square).filter(_ > 4) +lst.map(square).filter(_ > 4).map(square) +// in my collatz.scala +//(1 to bnd).map(i => (collatz(i), i)).maxBy(_._1) + + +// type of functions +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) +} + +my_map_int(lst, square) + + +def sumOf(f: Int => Int, lst: List[Int]): Int = lst match { + case Nil => 0 + case x::xs => f(x) + sumOf(f, xs) +} + +def sum_squares(lst: List[Int]) = sumOf(square, lst) +def sum_cubes(lst: List[Int]) = sumOf(x => x * x * x, lst) + +sum_squares(lst) +sum_cubes(lst) // Sudoku //======== +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 emptyPosition(game: String) = (empty(game) % MaxValue, empty(game) / MaxValue) +def isDone(game: String) = empty(game) == -1 + +def row(game: String, y: Int): List[Char] = indexes.map(col => game(y * MaxValue + col)) +def col(game: String, x: Int): List[Char] = indexes.map(row => game(x + row * MaxValue)) + +def 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))) +} + + +//row(game0, 0) +//row(game0, 1) +//box(game0, (3,1)) + +def update(game: String, pos: Int, value: Char): String = game.updated(pos, value) + +def toAvoid(game: String, pos: Pos): List[Char] = + (col(game, pos._1) ++ row(game, pos._2) ++ box(game, pos)).distinct + +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 + candidates(game, emptyPosition(game)).par.map(c => search(update(game, empty(game), c))).toList.flatten +} + + +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(game0).map(pretty) +search(game1).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) / i / 1.0e9) + " secs" +} + +search(game2).map(pretty) +search(game3).distinct.map(pretty).length +time_needed(3, search(game2)) +time_needed(3, search(game3)) + -//sorting, higher-order functions -//lexicographic ordering - - -// Implicits -//=========== -// -// 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