# HG changeset patch # User Christian Urban # Date 1479339245 0 # Node ID 9f875191256090b9fd2cbfbaa33ef47fa7c8e719 # Parent 0e60e6c24b99b43666a9c7a73d80139012c2f9da updated diff -r 0e60e6c24b99 -r 9f8751912560 TAs --- a/TAs Wed Nov 16 15:05:40 2016 +0000 +++ b/TAs Wed Nov 16 23:34:05 2016 +0000 @@ -11,4 +11,8 @@ rosen.dangov@kcl.ac.uk, diana.ghitun@kcl.ac.uk, andrei.juganaru@kcl.ac.uk, - ainur.makhmet@kcl.ac.uk \ No newline at end of file + ainur.makhmet@kcl.ac.uk + + + +scala -Dscala.color \ No newline at end of file diff -r 0e60e6c24b99 -r 9f8751912560 progs/knight1.scala --- a/progs/knight1.scala Wed Nov 16 15:05:40 2016 +0000 +++ b/progs/knight1.scala Wed Nov 16 23:34:05 2016 +0000 @@ -24,7 +24,7 @@ //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) -//(1c) Complement the two recursive functions below. +//(1c) Complete the two recursive functions below. // They exhaustively search for open tours starting from the // given path. The first function counts all possible open tours, // and the second collects all open tours in a list of paths. diff -r 0e60e6c24b99 -r 9f8751912560 progs/knight3.scala --- a/progs/knight3.scala Wed Nov 16 15:05:40 2016 +0000 +++ b/progs/knight3.scala Wed Nov 16 23:34:05 2016 +0000 @@ -1,65 +1,24 @@ // Part 3 about finding a single tour using the Warnsdorf Rule //============================================================= - -type Pos = (Int, Int) -type Path = List[Pos] - -def print_board(dim: Int, path: Path): Unit = { - println - for (i <- 0 until dim) { - for (j <- 0 until dim) { - print(f"${path.reverse.indexOf((i, j))}%3.0f ") - } - println - } -} +// copy any function you need from files knight1.scala and +// knight2.scala -def add_pair(x: Pos)(y: Pos): Pos = - (x._1 + y._1, x._2 + y._2) - -def is_legal(dim: Int, path: Path)(x: Pos): Boolean = - 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) +type Pos = (Int, Int) // a position on a chessboard +type Path = List[Pos] // a path...a list of positions -def moves(x: Pos): List[Pos] = - List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), - (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)) - -def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = - moves(x).filter(is_legal(dim, path)) - -def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = - legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) - +//(3a) Complete the function that calculates a list of onward +// moves like in (1b) but orders them according to the Warnsdorf’s +// rule. That means moves with the fewest legal onward moves +// should come first. -def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { - case Nil => None - case x::xs => { - val result = f(x) - if (result.isDefined) result else first(xs, f) - } -} +def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = .. - -def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = { - if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path) - else - first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path)) -} +//(3b) Complete the function that searches for a single *closed* +// tour using the ordered moves function. -for (dim <- 1 to 6) { - val t = first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))) - println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) -} - +def first_closed_tour_heuristic(dim: Int, path: Path): Option[Path] = ... -def first_tour_heuristics(dim: Int, path: Path): Option[Path] = { - if (path.length == dim * dim) Some(path) - else - first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path)) -} +//(3c) Same as (3b) but searches for *open* tours. -for (dim <- 1 to 50) { - val t = first_tour_heuristics(dim, List((dim / 2, dim / 2))) - println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) -} +def first_tour_heuristic(dim: Int, path: Path): Option[Path] = ... diff -r 0e60e6c24b99 -r 9f8751912560 progs/knight3_sol.scala --- a/progs/knight3_sol.scala Wed Nov 16 15:05:40 2016 +0000 +++ b/progs/knight3_sol.scala Wed Nov 16 23:34:05 2016 +0000 @@ -1,24 +1,65 @@ // Part 3 about finding a single tour using the Warnsdorf Rule //============================================================= -// copy any function you need from files knight1.scala and -// knight2.scala + +type Pos = (Int, Int) +type Path = List[Pos] + +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((i, j))}%3.0f ") + } + println + } +} -type Pos = (Int, Int) // a position on a chessboard -type Path = List[Pos] // a path...a list of positions +def add_pair(x: Pos)(y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +def is_legal(dim: Int, path: Path)(x: Pos): Boolean = + 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) -//(3a) Complete the function that calculates a list of onward -// moves like in (1b) but orders them according to the Warnsdorf’s -// rule. That means moves with the fewest legal onward moves -// should come first. +def moves(x: Pos): List[Pos] = + List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), + (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x)) + +def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = + moves(x).filter(is_legal(dim, path)) + +def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = + legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length) + -def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = .. +def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { + case Nil => None + case x::xs => { + val result = f(x) + if (result.isDefined) result else first(xs, f) + } +} -//(3b) Complete the function that searches for a single *closed* -// tour using the ordered moves function. + +def first_closed_tour_heuristics(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path) + else + first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristics(dim, x::path)) +} -def first_closed_tour_heuristic(dim: Int, path: Path): Option[Path] = ... +for (dim <- 1 to 6) { + val t = first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))) + println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) +} + -//(3c) Sama as (3b) but searches for *open* tours. +def first_tour_heuristics(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim) Some(path) + else + first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristics(dim, x::path)) +} -def first_tour_heuristic(dim: Int, path: Path): Option[Path] = ... +for (dim <- 1 to 50) { + val t = first_tour_heuristics(dim, List((dim / 2, dim / 2))) + println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) +} diff -r 0e60e6c24b99 -r 9f8751912560 progs/lecture2.scala --- a/progs/lecture2.scala Wed Nov 16 15:05:40 2016 +0000 +++ b/progs/lecture2.scala Wed Nov 16 23:34:05 2016 +0000 @@ -2,25 +2,187 @@ //================= + // Option type //============= + +//in Java if something unusually happens, you return null +//in Scala you use Option +// - if the value is present, you use Some(value) +// - if no value is present, you use None + + +List(7,2,3,4,5,6).find(_ < 4) +List(5,6,7,8,9).find(_ < 4) + val lst = List(None, Some(1), Some(2), None, Some(3)) lst.flatten + Some(1).get +Some(1).isDefined +None.isDefined + val ps = List((3, 0), (3, 2), (4, 2), (2, 0), (1, 0), (1, 1)) for ((x, y) <- ps) yield { if (y == 0) None else Some(x / y) } -// sudoku -// some none -// pattern matching +// getOrElse is to set a default value + +val lst = List(None, Some(1), Some(2), None, Some(3)) +for (x <- lst) yield x getOrElse 0 + + +import scala.util._ +import io.Source +// error handling with option +// +// Try(something).getOrElse(what_to_do_in_an_exception) + +Source.fromURL("""http://www.inf.kcl.ac.uk/staff/urbanccc/""").mkString + +Try(Source.fromURL("""http://www.inf.kcl.ac.uk/staff/urbanc/""").mkString).getOrElse("") + +Try(Some(Source.fromURL("""http://www.inf.kcl.ac.uk/staff/urbanc/""").mkString)).getOrElse(None) + + +Integer.parseInt("12u34") + +def get_me_an_int(s: String): Option[Int] = + Try(Some(Integer.parseInt(s))).getOrElse(None) + +val lst = List("12345", "foo", "5432", "bar", "x21") +for (x <- lst) yield get_me_an_int(x) + +// summing all the numbers +val sum = lst.flatMap(get_me_an_int(_)).sum + + +// This may not look any better than working with null in Java, but to +// see the value, you have to put yourself in the shoes of the +// consumer of the get_me_an_int function, and imagine you didn't +// write that function. +// +// In Java, if you didn't write this function, you'd have to depend on +// the Javadoc of the get_me_an_int. If you didn't look at the Javadoc +// for the Java, you might not know that get_me_an_int could return a +// null, and your code could potentially throw a NullPointerException. + + + + + +// Type abbreviations +//==================== + +// some syntactic convenience +type Pos = (int, Int) + +type Board = List[List[Int]] + + + + +// No return in Scala +//==================== + +//You should not use "return" in Scala: +// +// A return expression, when evaluated, abandons the +// current computation and returns to the caller of the +// function in which return appears." + +def sq1(x: Int): Int = x * x +def sq2(x: Int): Int = return x * x + +def sumq(ls: List[Int]): Int = { + (for (x <- ls) yield (return x * x)).sum[Int] +} + +sumq(List(1,2,3,4)) -//type abbreviations -type Pos = (int, Int) +// last expression in a function is the return statement +def square(x: Int): Int = { + println(s"The argument is ${x}.") + x * x +} + +// Pattern Matching +//================== + +// A powerful tool which is supposed to come to Java in a few years +// time (https://www.youtube.com/watch?v=oGll155-vuQ)...Scala already +// has it for many years ;o) + +// The general schema: +// +// expression match { +// case pattern1 => expression1 +// case pattern2 => expression2 +// ... +// case patternN => expressionN +// } + + +// remember +val lst = List(None, Some(1), Some(2), None, Some(3)).flatten + + +def my_flatten(xs: List[Option[Int]]): List[Int] = { + ... +} + + +def my_flatten(lst: List[Option[Int]]): List[Int] = lst match { + case Nil => Nil + case None::xs => my_flatten(xs) + case Some(n)::xs => n::my_flatten(xs) +} + + +// another example +def get_me_a_string(n: Int): String = n match { + case 0 => "zero" + case 1 => "one" + case 2 => "two" + case _ => "many" +} + + +// Higher-Order Functions +//======================== + +// functions can take functions as arguments + +val lst = (1 to 10).toList + +def even(x: Int): Boolean = x % 2 == 0 +def odd(x: Int): Boolean = x % 2 == 1 + +lst.filter(x => even(x)) +lst.filter(even(_)) +lst.filter(even) + +lst.find(_ > 8) + +def square(x: Int): Int = x * x + +lst.map(square) + +lst.map(square).filter(_ > 4) + + + + +// Sudoku +//======== + + + + //sorting, higher-order functions //lexicographic ordering diff -r 0e60e6c24b99 -r 9f8751912560 progs/lecture3.scala --- a/progs/lecture3.scala Wed Nov 16 15:05:40 2016 +0000 +++ b/progs/lecture3.scala Wed Nov 16 23:34:05 2016 +0000 @@ -1,2 +1,18 @@ // regular expressions // ?? polymorphism + +A function should do one thing, and only one thing. + +Make your variables immutable, unless there's a good reason not to. + +You can be productive on Day 1, but the language is deep, so as you go +along you’ll keep learning, and finding newer, better ways to write +code. Scala will change the way you think about programming (and +that’s a good thing). + +Of all of Scala’s benefits, what I like best is that it lets you write +concise, readable code + + + +ScalaTest download page: http://www.scalatest.org/download