# HG changeset patch # User Christian Urban # Date 1575336136 0 # Node ID e5453add7df6d6cddba992ef75230e06f4971d20 # Parent ca9c1cf929fac2ebe9d59a709088bdb213f0d650 updated diff -r ca9c1cf929fa -r e5453add7df6 marking3/knight1_test.sh --- a/marking3/knight1_test.sh Tue Nov 26 01:22:36 2019 +0000 +++ b/marking3/knight1_test.sh Tue Dec 03 01:22:16 2019 +0000 @@ -8,7 +8,7 @@ echo "" > $out echo "Below is the feedback and provisional marks for your submission" >> $out -echo "for assignment 8 Part 1. Please note all marks are provisional until" >> $out +echo "for Preliminary 8. Please note all marks are provisional until" >> $out echo "ratified by the assessment board -- this is not an official" >> $out echo "results transcript." >> $out echo "" >> $out @@ -19,27 +19,36 @@ marks=$(( 0 )) -# compilation tests (used to be 30 secs) - function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc "$1" 2> /dev/null 1> /dev/null) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) } # functional tests +function scala_assert_slow { + (ulimit -t 120; JAVA_OPTS="-Xmx1g" scala -i "$1" "-- $2" 2> /dev/null 1> /dev/null) +} + +function scala_assert_thirty { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null) +} + +function scala_assert_quick { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null) +} + function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" "$2" -e "") #2> /dev/null 1> /dev/null) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null) } function scala_assert_long { - (ulimit -t 60; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" "$2" -e "") #2> /dev/null 1> /dev/null) + (ulimit -t 60; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -2> /dev/null 1> /dev/null) } function scala_assert_elong { - (ulimit -t 90; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" "$2" -e "") #2> /dev/null 1> /dev/null) + (ulimit -t 90; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null) } - # purity test function scala_vars { @@ -53,7 +62,7 @@ if (scala_vars knight1.scala) then - echo " --> fail" | tee -a $out + echo " --> FAIL" | tee -a $out tsts0=$(( 1 )) else echo " --> success" | tee -a $out @@ -72,7 +81,7 @@ echo " --> success " | tee -a $out tsts1=$(( 0 )) else - echo " --> scala did not run knight1.scala" | tee -a $out + echo -e " --> SCALA DID NOT RUN KNIGHT1.SCALA\n" | tee -a $out tsts1=$(( 1 )) fi else @@ -89,10 +98,10 @@ if (scala_assert "knight1.scala" "knight1_test1.scala") then - echo " --> success" | tee -a $out + echo -e " --> success\n" | tee -a $out marks=$(( marks + 1 )) else - echo " --> test failed" | tee -a $out + echo -e " --> \n ONE TEST FAILED\n"| tee -a $out fi fi @@ -103,6 +112,7 @@ echo " legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))" | tee -a $out echo " legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))" | tee -a $out echo " legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))" | tee -a $out + echo " legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0))" | tee -a $out echo " legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))" | tee -a $out echo " legal_moves(1, Nil, (0,0)) == Nil" | tee -a $out echo " legal_moves(2, Nil, (0,0)) == Nil" | tee -a $out @@ -110,10 +120,10 @@ if (scala_assert "knight1.scala" "knight1_test2.scala") then - echo " --> success" | tee -a $out + echo -e " --> success\n" | tee -a $out marks=$(( marks + 1 )) else - echo " --> test failed" | tee -a $out + echo -e " --> \n ONE TEST FAILED\n" | tee -a $out fi fi @@ -128,67 +138,47 @@ echo " 3: 0,0,0,0,0,0,0,0,0" | tee -a $out echo " 4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" | tee -a $out echo " 5: 304,0,56,0,304,0,56,0,56,0,56,0,64,0,56,0,56,0,56,0,304,0,56,0,304" | tee -a $out + START=$(date +%s) - if (time scala_assert_elong "knight1.scala" "knight1_test3a.scala") + if (scala_assert_elong "knight1.scala" "knight1_test3a.scala") then - echo " --> success" | tee -a $out + END=$(date +%s) + DIFF=$(( $END - $START )) + echo " It took $DIFF seconds" | tee -a $out + echo -e " --> success\n" | tee -a $out marks=$(( marks + 1 )) else - echo " --> test failed" | tee -a $out + END=$(date +%s) + DIFF=$(( $END - $START )) + echo " It took $DIFF seconds" | tee -a $out + echo -e " --> \n ONE TEST FAILED\n" | tee -a $out fi fi if [ $tsts1 -eq 0 ] then echo " enum_tours(5, List((0,2)) ) => 56 tours? and all correct?" | tee -a $out + echo " enum_tours(5, List((0,0)) ) => 304 tours? and all correct?" | tee -a $out + START=$(date +%s) - if (time scala_assert "knight1.scala" "knight1_test3b.scala") + if (scala_assert "knight1.scala" "knight1_test3b.scala") then - echo " --> success" | tee -a $out + END=$(date +%s) + DIFF=$(( $END - $START )) + echo " It took $DIFF seconds" | tee -a $out + echo -e " --> success\n" | tee -a $out marks=$(( marks + 1 )) else - echo " --> test failed" | tee -a $out - fi -fi - - -### knight4 test - -if [ $tsts1 -eq 0 ] -then - echo " val f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " | tee -a $out - echo " first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0)))" | tee -a $out - echo " first(List((1,0),(2,0),(3,0)), f) == None" | tee -a $out - - if (scala_assert "knight1.scala" "knight1_test4.scala") - then - echo " --> success" | tee -a $out - marks=$(( marks + 1 )) - else - echo " --> test failed" | tee -a $out - fi -fi - - -### knight5 test - -if [ $tsts1 -eq 0 ] -then - echo " is first_tour(8, List((0, 0))) ok? " | tee -a $out - echo " is first_tour(4, List((0, 0))) == None " | tee -a $out - - if (time scala_assert_long "knight1.scala" "knight1_test5.scala") - then - echo " --> success" | tee -a $out - marks=$(( marks + 1 )) - else - echo " --> test failed" | tee -a $out + END=$(date +%s) + DIFF=$(( $END - $START )) + echo " It took $DIFF seconds" | tee -a $out + echo -e " --> \n ONE TEST FAILED\n" | tee -a $out fi fi ## final marks -echo "Overall mark for Part 1" | tee -a $out +echo "Overall mark for Preliminary 8" | tee -a $out echo "$marks" | tee -a $out diff -r ca9c1cf929fa -r e5453add7df6 marking3/knight1_test1.scala --- a/marking3/knight1_test1.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/marking3/knight1_test1.scala Tue Dec 03 01:22:16 2019 +0000 @@ -1,6 +1,9 @@ +import CW8a._ assert(is_legal(8, Nil, (3, 4)) == true) assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false) assert(is_legal(2, Nil, (0, 0)) == true) + + diff -r ca9c1cf929fa -r e5453add7df6 marking3/knight1_test2.scala --- a/marking3/knight1_test2.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/marking3/knight1_test2.scala Tue Dec 03 01:22:16 2019 +0000 @@ -1,9 +1,11 @@ +import CW8a._ assert(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) +assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0))) assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) assert(legal_moves(1, Nil, (0,0)) == Nil) assert(legal_moves(2, Nil, (0,0)) == Nil) diff -r ca9c1cf929fa -r e5453add7df6 marking3/knight1_test3a.scala --- a/marking3/knight1_test3a.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/marking3/knight1_test3a.scala Tue Dec 03 01:22:16 2019 +0000 @@ -1,4 +1,4 @@ - +import CW8a._ //type Pos = (Int, Int) // a position on a chessboard //type Path = List[Pos] // a path...a list of positions diff -r ca9c1cf929fa -r e5453add7df6 marking3/knight1_test3b.scala --- a/marking3/knight1_test3b.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/marking3/knight1_test3b.scala Tue Dec 03 01:22:16 2019 +0000 @@ -1,3 +1,4 @@ +import CW8a._ //type Pos = (Int, Int) // a position on a chessboard //type Path = List[Pos] // a path...a list of positions @@ -22,6 +23,10 @@ } +val ts00_urban = enum_tours(5, List((0, 0))) +assert(ts00_urban.map(correct_urban(5)).forall(_ == true) == true) +assert(ts00_urban.length == 304) + val ts_urban = enum_tours(5, List((0, 2))) assert(ts_urban.map(correct_urban(5)).forall(_ == true) == true) diff -r ca9c1cf929fa -r e5453add7df6 marking3/mk --- a/marking3/mk Tue Nov 26 01:22:36 2019 +0000 +++ b/marking3/mk Tue Dec 03 01:22:16 2019 +0000 @@ -3,27 +3,28 @@ trap "exit" INT -files=${1:-assignment20188-*} +files=${1:-assignment2019scala-*/Part8} for sd in $files; do cd $sd echo $sd touch . - cp ../../../marking3/knight1_test.sh . - cp ../../../marking3/knight1_test1.scala . - cp ../../../marking3/knight1_test2.scala . - cp ../../../marking3/knight1_test3a.scala . - cp ../../../marking3/knight1_test3b.scala . - cp ../../../marking3/knight1_test4.scala . - cp ../../../marking3/knight1_test5.scala . - ./knight1_test.sh output + cp ../../../../../marking3/knight1_test.sh . + cp ../../../../../marking3/knight1_test1.scala . + cp ../../../../../marking3/knight1_test2.scala . + cp ../../../../../marking3/knight1_test3a.scala . + cp ../../../../../marking3/knight1_test3b.scala . + #cp ../../../../../marking3/knight1_test4.scala . + #cp ../../../../../marking3/knight1_test5.scala . + ./knight1_test.sh output1 rm knight1_test.sh rm knight1_test1.scala rm knight1_test2.scala rm knight1_test3a.scala rm knight1_test3b.scala - rm knight1_test4.scala - rm knight1_test5.scala + #rm knight1_test4.scala + #rm knight1_test5.scala + cd .. cd .. done diff -r ca9c1cf929fa -r e5453add7df6 progs/lecture4.scala --- a/progs/lecture4.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/progs/lecture4.scala Tue Dec 03 01:22:16 2019 +0000 @@ -30,6 +30,8 @@ // e + 0, 0 + e => e // e * 0, 0 * e => 0 // e * 1, 1 * e => e +// +// (....0 ....) def simp(e: Exp) : Exp = e match { case N(n) => N(n) @@ -68,14 +70,14 @@ println(string(e2)) println(rp(e2)) -def comp(ls: List[Token], st: List[Int]) : Int = (ls, st) match { +def comp(ls: List[Token], st: List[Int] = Nil) : 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) +comp(rp(e)) def proc(s: String) : Token = s match { case "+" => PL @@ -106,6 +108,8 @@ |1..5...92 |..7.9.41.""".stripMargin.replaceAll("\\n", "") +candidates(game0, (0, 0)) + type Pos = (Int, Int) val EmptyValue = '.' val MaxValue = 9 @@ -125,6 +129,8 @@ def get_col(game: String, x: Int) = indexes.map(row => game(x + row * MaxValue)) +get_row(game0, 0) + def get_box(game: String, pos: Pos): List[Char] = { def base(p: Int): Int = (p / 3) * 3 val x0 = base(pos._1) @@ -154,7 +160,6 @@ def pretty(game: String): String = "\n" + (game.sliding(MaxValue, MaxValue).mkString("\n")) - def search(game: String): List[String] = { if (isDone(game)) List(game) else { @@ -163,6 +168,8 @@ } } +List(List("sol1"), List("sol2", "sol3")).flatten + search(game0).map(pretty) val game1 = """23.915... @@ -218,26 +225,33 @@ // Tail recursion //================ - -def fact(n: Long): Long = +@tailrec +def fact(n: BigInt): BigInt = if (n == 0) 1 else n * fact(n - 1) -fact(10) // ok -fact(1000) // silly -fact(10000) // produces a stackoverflow +fact(10) +fact(1000) +fact(100000) def factB(n: BigInt): BigInt = if (n == 0) 1 else n * factB(n - 1) +def factT(n: BigInt, acc: BigInt): BigInt = + if (n == 0) acc else factT(n - 1, n * acc) + + 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)) +println(factT(500000, 1)) + + + + // there is a flag for ensuring a function is tail recursive import scala.annotation.tailrec @@ -257,7 +271,7 @@ // tail recursive version that searches // for all Sudoku solutions - +@tailrec def searchT(games: List[String], sols: List[String]): List[String] = games match { case Nil => sols case game::rest => { @@ -305,7 +319,7 @@ search1T(List(game3)).map(pretty) // Moral: Whenever a recursive function is resource-critical -// (i.e. works with large recursion depth), then you need to +// (i.e. works with a large recursion depth), then you need to // write it in tail-recursive fashion. // // Unfortuantely, Scala because of current limitations in @@ -317,104 +331,6 @@ -// Polymorphic Types -//=================== - -// You do not want to write functions like contains, first, -// length and so on for every type of lists. - - -def length_string_list(lst: List[String]): Int = lst match { - case Nil => 0 - case x::xs => 1 + length_string_list(xs) -} - -def length_int_list(lst: List[Int]): Int = lst match { - case Nil => 0 - case x::xs => 1 + length_int_list(xs) -} - -length_string_list(List("1", "2", "3", "4")) -length_int_list(List(1, 2, 3, 4)) - -def length[A](lst: List[A]): Int = lst match { - case Nil => 0 - case x::xs => 1 + length(xs) -} -length(List("1", "2", "3", "4")) -length(List(1, 2, 3, 4)) - - -def map[A, B](lst: List[A], f: A => B): List[B] = lst match { - case Nil => Nil - case x::xs => f(x)::map(xs, f) -} - -map(List(1, 2, 3, 4), (x: Int) => x.toString) - - - -// distinct / distinctBy - -val ls = List(1,2,3,3,2,4,3,2,1) -ls.distinct - -ls.minBy(_._2) -ls.sortBy(_._1) - -def distinctBy[B, C](xs: List[B], - f: B => C, - acc: List[C] = Nil): List[B] = xs match { - case Nil => Nil - case x::xs => { - val res = f(x) - if (acc.contains(res)) distinctBy(xs, f, acc) - else x::distinctBy(xs, f, res::acc) - } -} - -// distinctBy with the identity function is -// just distinct -distinctBy(ls, (x: Int) => x) - - -val cs = List('A', 'b', 'a', 'c', 'B', 'D', 'd') - -distinctBy(cs, (c:Char) => c.toUpper) - - - -// Type inference is local in Scala - -def id[T](x: T) : T = x - -val x = id(322) // Int -val y = id("hey") // String -val z = id(Set[Int](1,2,3,4)) // Set[Int] - - - -// The type variable concept in Scala can get really complicated. -// -// - variance (OO) -// - bounds (subtyping) -// - quantification - -// Java has issues with this too: Java allows -// to write the following incorrect code, and -// only recovers by raising an exception -// at runtime. - -// Object[] arr = new Integer[10]; -// arr[0] = "Hello World"; - - -// Scala gives you a compile-time error, which -// is much better. - -var arr = Array[Int]() -arr(0) = "Hello World" - @@ -495,12 +411,14 @@ case c::Nil => CHAR(c) case c::s => SEQ(CHAR(c), charlist2rexp(s)) } + implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) +"(a|b)" val r1 = STAR("ab") -val r2 = STAR(ALT("ab", "baa baa black sheep")) +val r2 = (STAR("ab")) | (STAR("ba")) val r3 = STAR(SEQ("ab", ALT("a", "b"))) implicit def RexpOps (r: Rexp) = new { @@ -518,323 +436,12 @@ } //example regular expressions -val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" +val digit = ("0" | "1" | "2" | "3" | "4" | + "5" | "6" | "7" | "8" | "9") val sign = "+" | "-" | "" val number = sign ~ digit ~ digit.% -// -// Object Oriented Programming in Scala -// -// ===================================== - -abstract class Animal -case class Bird(name: String) extends Animal { - override def toString = name -} -case class Mammal(name: String) extends Animal -case class Reptile(name: String) extends Animal - -Bird("Sparrow") - -println(Bird("Sparrow")) -println(Bird("Sparrow").toString) - - -// you can override methods -case class Bird(name: String) extends Animal { - override def toString = name -} - - -// There is a very convenient short-hand notation -// for constructors: - -class Fraction(x: Int, y: Int) { - def numer = x - def denom = y -} - - -case class Fraction(numer: Int, denom: Int) - -val half = Fraction(1, 2) - -half.denom - - -// In mandelbrot.scala I used complex (imaginary) numbers -// and implemented the usual arithmetic operations for complex -// numbers. - -case class Complex(re: Double, im: Double) { - // represents the complex number re + im * i - def +(that: Complex) = Complex(this.re + that.re, this.im + that.im) - def -(that: Complex) = Complex(this.re - that.re, this.im - that.im) - def *(that: Complex) = Complex(this.re * that.re - this.im * that.im, - this.re * that.im + that.re * this.im) - def *(that: Double) = Complex(this.re * that, this.im * that) - def abs = Math.sqrt(this.re * this.re + this.im * this.im) -} - -val test = Complex(1, 2) + Complex (3, 4) - -// this could have equally been written as -val test = Complex(1, 2).+(Complex (3, 4)) - -// this applies to all methods, but requires -import scala.language.postfixOps - -List(5, 2, 3, 4).sorted -List(5, 2, 3, 4) sorted - - -// ...to allow the notation n + m * i -import scala.language.implicitConversions - -val i = Complex(0, 1) -implicit def double2complex(re: Double) = Complex(re, 0) - - -val inum1 = -2.0 + -1.5 * i -val inum2 = 1.0 + 1.5 * i - - - -// All is public by default....so no public is needed. -// You can have the usual restrictions about private -// values and methods, if you are MUTABLE !!! - -case class BankAccount(init: Int) { - - private var balance = init - - def deposit(amount: Int): Unit = { - if (amount > 0) balance = balance + amount - } - - def withdraw(amount: Int): Int = - if (0 < amount && amount <= balance) { - balance = balance - amount - balance - } else throw new Error("insufficient funds") -} - -// BUT since we are completely IMMUTABLE, this is -// virtually of not concern to us. - - - -// another example about Fractions -import scala.language.implicitConversions -import scala.language.reflectiveCalls - - -case class Fraction(numer: Int, denom: Int) { - override def toString = numer.toString + "/" + denom.toString - - def +(other: Fraction) = Fraction(numer + other.numer, denom + other.denom) - def /(other: Fraction) = Fraction(numer * other.denom, denom * other.numer) - def /% (other: Fraction) = Fraction(numer * other.denom, denom * other.numer) - -} - -implicit def Int2Fraction(x: Int) = Fraction(x, 1) - - -val half = Fraction(1, 2) -val third = Fraction (1, 3) - -half + third -half / third - -// not sure if one can get this to work -// properly, since Scala just cannot find out -// if / is for ints or for Fractions -(1 / 3) + half -(1 / 2) + third - -// either you have to force the Fraction-type by -// using a method that is not defined for ints -(1 /% 3) + half -(1 /% 2) + third - - -// ...or explicitly give the type in order to allow -// Scala to do the conversion to Fractions -((1:Fraction) / 3) + half -(1 / (3: Fraction)) + half - - - -// DFAs in Scala -//=============== -import scala.util.Try - - -// A is the state type -// C is the input (usually characters) - -case class DFA[A, C](start: A, // starting state - delta: (A, C) => A, // transition function - fins: A => Boolean) { // final states (Set) - - def deltas(q: A, s: List[C]) : A = s match { - case Nil => q - case c::cs => deltas(delta(q, c), cs) - } - - def accepts(s: List[C]) : Boolean = - Try(fins(deltas(start, s))) getOrElse false -} - -// the example shown in the handout -abstract class State -case object Q0 extends State -case object Q1 extends State -case object Q2 extends State -case object Q3 extends State -case object Q4 extends State - -val delta : (State, Char) => State = - { case (Q0, 'a') => Q1 - case (Q0, 'b') => Q2 - case (Q1, 'a') => Q4 - case (Q1, 'b') => Q2 - case (Q2, 'a') => Q3 - case (Q2, 'b') => Q2 - case (Q3, 'a') => Q4 - case (Q3, 'b') => Q0 - case (Q4, 'a') => Q4 - case (Q4, 'b') => Q4 - case _ => throw new Exception("Undefined") } - -val dfa = DFA(Q0, delta, Set[State](Q4)) - -dfa.accepts("abaaa".toList) // true -dfa.accepts("bbabaab".toList) // true -dfa.accepts("baba".toList) // false -dfa.accepts("abc".toList) // false - -// another DFA with a Sink state -abstract class S -case object S0 extends S -case object S1 extends S -case object S2 extends S -case object Sink extends S - -// transition function with a sink state -val sigma : (S, Char) => S = - { case (S0, 'a') => S1 - case (S1, 'a') => S2 - case _ => Sink - } - -val dfa2 = DFA(S0, sigma, Set[S](S2)) - -dfa2.accepts("aa".toList) // true -dfa2.accepts("".toList) // false -dfa2.accepts("ab".toList) // false - -// we could also have a dfa for numbers -val sigmai : (S, Int) => S = - { case (S0, 1) => S1 - case (S1, 1) => S2 - case _ => Sink - } - -val dfa3 = DFA(S0, sigmai, Set[S](S2)) - -dfa3.accepts(List(1, 1)) // true -dfa3.accepts(Nil) // false -dfa3.accepts(List(1, 2)) // false - - - - -// NFAs (Nondeterministic Finite Automata) - - -case class NFA[A, C](starts: Set[A], // starting states - delta: (A, C) => Set[A], // transition function - fins: A => Boolean) { // final states - - // given a state and a character, what is the set of - // next states? if there is none => empty set - def next(q: A, c: C) : Set[A] = - Try(delta(q, c)) getOrElse Set[A]() - - def nexts(qs: Set[A], c: C) : Set[A] = - qs.flatMap(next(_, c)) - - // depth-first version of accepts - def search(q: A, s: List[C]) : Boolean = s match { - case Nil => fins(q) - case c::cs => next(q, c).exists(search(_, cs)) - } - - def accepts(s: List[C]) : Boolean = - starts.exists(search(_, s)) -} - - - -// NFA examples - -val nfa_trans1 : (State, Char) => Set[State] = - { case (Q0, 'a') => Set(Q0, Q1) - case (Q0, 'b') => Set(Q2) - case (Q1, 'a') => Set(Q1) - case (Q2, 'b') => Set(Q2) } - -val nfa = NFA(Set[State](Q0), nfa_trans1, Set[State](Q2)) - -nfa.accepts("aa".toList) // false -nfa.accepts("aaaaa".toList) // false -nfa.accepts("aaaaab".toList) // true -nfa.accepts("aaaaabbb".toList) // true -nfa.accepts("aaaaabbbaaa".toList) // false -nfa.accepts("ac".toList) // false - - -// Q: Why the kerfuffle about the polymorphic types in DFAs/NFAs? -// A: Subset construction. Here the state type for the DFA is -// sets of states. - -def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = { - DFA(nfa.starts, - { case (qs, c) => nfa.nexts(qs, c) }, - _.exists(nfa.fins)) -} - -subset(nfa1).accepts("aa".toList) // false -subset(nfa1).accepts("aaaaa".toList) // false -subset(nfa1).accepts("aaaaab".toList) // true -subset(nfa1).accepts("aaaaabbb".toList) // true -subset(nfa1).accepts("aaaaabbbaaa".toList) // false -subset(nfa1).accepts("ac".toList) // false - - - - - - - - -// Lazy Evaluation -//================= -// -// Do not evaluate arguments just yet: -// this uses the => in front of the type -// of the code-argument - -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) -} - // Mind-Blowing Regular Expressions @@ -844,10 +451,10 @@ println("a" * 100) -("a" * 10 ++ "b").matches(evil) +("a" * 10000).matches(evil) ("a" * 10).matches(evil) ("a" * 10000).matches(evil) ("a" * 20000).matches(evil) ("a" * 50000).matches(evil) -time_needed(1, ("a" * 10000).matches(evil)) +time_needed(1, ("a" * 50000).matches(evil)) diff -r ca9c1cf929fa -r e5453add7df6 progs/lecture5.scala --- a/progs/lecture5.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/progs/lecture5.scala Tue Dec 03 01:22:16 2019 +0000 @@ -7,29 +7,30 @@ //===================== // The concept of lazy evaluation doesn’t really -// exist in non-functional languages, but it is -// pretty easy to grasp. Consider first +// exist in non-functional languages. C-like languages +// are strict. To see the difference, consider def square(x: Int) = x * x square(42 + 8) -// this is called strict evaluation +// This is called "strict evaluation". -// say we have a pretty expensive operation +// In contrast, say we have a pretty expensive operation: + def peop(n: BigInt): Boolean = peop(n + 1) val a = "foo" -val b = "bar" +val b = "foo" if (a == b || peop(0)) println("true") else println("false") -// this is called lazy evaluation +// This is called "lazy evaluation": // you delay compuation until it is really -// needed; once calculated though, does not -// need to be re-calculated +// needed. Once calculated though, the result +// does not need to be re-calculated. -// a useful example is +// A useful example is def time_needed[T](i: Int, code: => T) = { val start = System.nanoTime() for (j <- 1 to i) code @@ -37,42 +38,38 @@ f"${(end - start) / (i * 1.0e9)}%.6f secs" } +// A slightly less obvious example: Prime Numbers. +// (I do not care how many) primes: 2, 3, 5, 7, 9, 11, 13 .... -// streams (I do not care how many) -// primes: 2, 3, 5, 7, 9, 11, 13 .... - -def generatePrimes (s: Stream[Int]): Stream[Int] = +def generatePrimes (s: LazyList[Int]): LazyList[Int] = s.head #:: generatePrimes(s.tail.filter(_ % s.head != 0)) -val primes = generatePrimes(Stream.from(2)) +val primes = generatePrimes(LazyList.from(2)) // the first 10 primes -primes.take(10).par.toList +primes.take(10).toList time_needed(1, primes.filter(_ > 100).take(3000).toList) -time_needed(1, primes.filter(_ > 100).take(1000).toList) +time_needed(1, primes.filter(_ > 100).take(3000).toList) -// a stream of successive numbers +// A Stream (LazyList) of successive numbers: -Stream.from(2).print -Stream.from(2).take(10).force -Stream.from(2).take(10).print -Stream.from(10).take(10).print +LazyList.from(2).take(10) +LazyList.from(2).take(10).force -Stream.from(2).take(10).force - -// iterative version of the Fibonacci numbers -def fibIter(a: BigInt, b: BigInt): Stream[BigInt] = +// An Iterative version of the Fibonacci numbers +def fibIter(a: BigInt, b: BigInt): LazyList[BigInt] = a #:: fibIter(b, a + b) fibIter(1, 1).take(10).force fibIter(8, 13).take(10).force -fibIter(1, 1).drop(10000).take(1).print +fibIter(1, 1).drop(10000).take(1) +fibIter(1, 1).drop(10000).take(1).force -// good for testing +// LazyLists are good for testing // Regular expressions - the power of DSLs in Scala @@ -100,7 +97,6 @@ implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) - implicit def RexpOps (r: Rexp) = new { def | (s: Rexp) = ALT(r, s) def % = STAR(r) @@ -130,7 +126,7 @@ val sign = "+" | "-" | "" val number = sign ~ digit ~ digit.% -// task: enumerate exhaustively regular expression +// Task: enumerate exhaustively regular expressions // starting from small ones towards bigger ones. // 1st idea: enumerate them all in a Set @@ -149,154 +145,365 @@ enuml(1, "a") enuml(1, "a").size enuml(2, "a").size -enuml(3, "a").size -enuml(4, "a").size // out of heap space +enuml(3, "a").size // out of heap space -def enum(rs: Stream[Rexp]) : Stream[Rexp] = + +def enum(rs: LazyList[Rexp]) : LazyList[Rexp] = rs #::: enum( (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) #::: (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) #::: (for (r1 <- rs) yield STAR(r1)) ) -enum(ZERO #:: ONE #:: "ab".toStream.map(CHAR)).take(200).force -enum(ZERO #:: ONE #:: "ab".toStream.map(CHAR)).take(5000000) +enum(LazyList(ZERO, ONE, CHAR('a'), CHAR('b'))).take(200).force +enum(LazyList(ZERO, ONE, CHAR('a'), CHAR('b'))).take(5000000) val is = - (enum(ZERO #:: ONE #:: "ab".toStream.map(CHAR)) + (enum(LazyList(ZERO, ONE, CHAR('a'), CHAR('b'))) .dropWhile(depth(_) < 3) .take(10).foreach(println)) +// Polymorphic Types +//=================== -// Parsing - The Solved Problem That Isn't -//========================================= -// -// https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html -// -// Or, A topic of endless "fun"(?) +// You do not want to write functions like contains, first, +// length and so on for every type of lists. + + +def length_string_list(lst: List[String]): Int = lst match { + case Nil => 0 + case x::xs => 1 + length_string_list(xs) +} + +def length_int_list(lst: List[Int]): Int = lst match { + case Nil => 0 + case x::xs => 1 + length_int_list(xs) +} + +length_string_list(List("1", "2", "3", "4")) +length_int_list(List(1, 2, 3, 4)) + +// you can make the function parametric in type(s) + +def length[A](lst: List[A]): Int = lst match { + case Nil => 0 + case x::xs => 1 + length(xs) +} +length(List("1", "2", "3", "4")) +length(List(1, 2, 3, 4)) + + +def map[A, B](lst: List[A], f: A => B): List[B] = lst match { + case Nil => Nil + case x::xs => f(x)::map(xs, f) +} + +map(List(1, 2, 3, 4), (x: Int) => x.toString) + -// input type: String -// output type: Int -Integer.parseInt("123u456") +// distinct / distinctBy + +val ls = List(1,2,3,3,2,4,3,2,1) +ls.distinct + +// .minBy(_._2) +// .sortBy(_._1) + +def distinctBy[B, C](xs: List[B], + f: B => C, + acc: List[C] = Nil): List[B] = xs match { + case Nil => Nil + case x::xs => { + val res = f(x) + if (acc.contains(res)) distinctBy(xs, f, acc) + else x::distinctBy(xs, f, res::acc) + } +} + +val cs = List('A', 'b', 'a', 'c', 'B', 'D', 'd') + +distinctBy(cs, (c:Char) => c.toUpper) + +// since 2.13 + +cs.distinctBy((c:Char) => c.toUpper) + + +// Type inference is local in Scala + +def id[T](x: T) : T = x + +val x = id(322) // Int +val y = id("hey") // String +val z = id(Set(1,2,3,4)) // Set[Int] + + + +// The type variable concept in Scala can get really complicated. +// +// - variance (OO) +// - bounds (subtyping) +// - quantification -/* Note, in the previous lectures I did not show the type consraint - * I <% Seq[_] , which means that the input type I can be - * treated, or seen, as a sequence. */ +// Java has issues with this too: Java allows +// to write the following incorrect code, and +// only recovers by raising an exception +// at runtime. + +// Object[] arr = new Integer[10]; +// arr[0] = "Hello World"; + + +// Scala gives you a compile-time error, which +// is much better. + +var arr = Array[Int]() +arr(0) = "Hello World" + + + +// (Immutable) +// Object Oriented Programming in Scala +// +// ===================================== -abstract class Parser[I <% Seq[_], T] { - def parse(ts: I): Set[(T, I)] +abstract class Animal +case class Bird(name: String) extends Animal { + override def toString = name +} +case class Mammal(name: String) extends Animal +case class Reptile(name: String) extends Animal + +Mammal("Zebra") +println(Mammal("Zebra")) +println(Mammal("Zebra").toString) + - def parse_all(ts: I) : Set[T] = - for ((head, tail) <- parse(ts); - if (tail.isEmpty)) yield head +Bird("Sparrow") +println(Bird("Sparrow")) +println(Bird("Sparrow").toString) + + +// There is a very convenient short-hand notation +// for constructors: + +class Fraction(x: Int, y: Int) { + def numer = x + def denom = y } -// the idea is that a parser can parse something -// from the input and leaves something unparsed => pairs +val half = new Fraction(1, 2) + +case class Fraction(numer: Int, denom: Int) + +val half = Fraction(1, 2) + +half.denom + + +// In mandelbrot.scala I used complex (imaginary) numbers +// and implemented the usual arithmetic operations for complex +// numbers. + +case class Complex(re: Double, im: Double) { + // represents the complex number re + im * i + def +(that: Complex) = Complex(this.re + that.re, this.im + that.im) + def -(that: Complex) = Complex(this.re - that.re, this.im - that.im) + def *(that: Complex) = Complex(this.re * that.re - this.im * that.im, + this.re * that.im + that.re * this.im) + def *(that: Double) = Complex(this.re * that, this.im * that) + def abs = Math.sqrt(this.re * this.re + this.im * this.im) +} + +val test = Complex(1, 2) + Complex (3, 4) + +// this could have equally been written as +val test = Complex(1, 2).+(Complex (3, 4)) + +// this applies to all methods, but requires +import scala.language.postfixOps + +List(5, 2, 3, 4).sorted +List(5, 2, 3, 4) sorted + + +// ...to allow the notation n + m * i +import scala.language.implicitConversions + +val i = Complex(0, 1) +implicit def double2complex(re: Double) = Complex(re, 0) + -class AltParser[I <% Seq[_], T]( - p: => Parser[I, T], - q: => Parser[I, T]) extends Parser[I, T] { +val inum1 = -2.0 + -1.5 * i +val inum2 = 1.0 + 1.5 * i + + + +// All is public by default....so no public is needed. +// You can have the usual restrictions about private +// values and methods, if you are MUTABLE !!! + +case class BankAccount(init: Int) { + + private var balance = init + + def deposit(amount: Int): Unit = { + if (amount > 0) balance = balance + amount + } - def parse(sb: I) = p.parse(sb) ++ q.parse(sb) + def withdraw(amount: Int): Int = + if (0 < amount && amount <= balance) { + balance = balance - amount + balance + } else throw new Error("insufficient funds") } +// BUT since we are completely IMMUTABLE, this is +// virtually of not concern to us. + + + +// another example about Fractions +import scala.language.implicitConversions +import scala.language.reflectiveCalls + + +case class Fraction(numer: Int, denom: Int) { + override def toString = numer.toString + "/" + denom.toString + + def +(other: Fraction) = Fraction(numer + other.numer, denom + other.denom) + def /(other: Fraction) = Fraction(numer * other.denom, denom * other.numer) + } + +implicit def Int2Fraction(x: Int) = Fraction(x, 1) + -class SeqParser[I <% Seq[_], T, S]( - p: => Parser[I, T], - q: => Parser[I, S]) extends Parser[I, (T, S)] { +val half = Fraction(1, 2) +val third = Fraction (1, 3) + +half + third +half / third + +(1 / 3) + half +(1 / 2) + third + + + + +// DFAs in Scala +//=============== +import scala.util.Try - def parse(sb: I) = - for ((head1, tail1) <- p.parse(sb); - (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) + +// A is the state type +// C is the input (usually characters) + +case class DFA[A, C](start: A, // starting state + delta: (A, C) => A, // transition function + fins: A => Boolean) { // final states (Set) + + def deltas(q: A, s: List[C]) : A = s match { + case Nil => q + case c::cs => deltas(delta(q, c), cs) + } + + def accepts(s: List[C]) : Boolean = + Try(fins(deltas(start, s))) getOrElse false } +// the example shown in the handout +abstract class State +case object Q0 extends State +case object Q1 extends State +case object Q2 extends State +case object Q3 extends State +case object Q4 extends State -class FunParser[I <% Seq[_], T, S]( - p: => Parser[I, T], - f: T => S) extends Parser[I, S] { +val delta : (State, Char) => State = + { case (Q0, 'a') => Q1 + case (Q0, 'b') => Q2 + case (Q1, 'a') => Q4 + case (Q1, 'b') => Q2 + case (Q2, 'a') => Q3 + case (Q2, 'b') => Q2 + case (Q3, 'a') => Q4 + case (Q3, 'b') => Q0 + case (Q4, 'a') => Q4 + case (Q4, 'b') => Q4 + case _ => throw new Exception("Undefined") } + +val dfa = DFA(Q0, delta, Set[State](Q4)) + +dfa.accepts("abaaa".toList) // true +dfa.accepts("bbabaab".toList) // true +dfa.accepts("baba".toList) // false +dfa.accepts("abc".toList) // false + - def parse(sb: I) = - for ((head, tail) <- p.parse(sb)) yield (f(head), tail) +// NFAs (Nondeterministic Finite Automata) + + +case class NFA[A, C](starts: Set[A], // starting states + delta: (A, C) => Set[A], // transition function + fins: A => Boolean) { // final states + + // given a state and a character, what is the set of + // next states? if there is none => empty set + def next(q: A, c: C) : Set[A] = + Try(delta(q, c)) getOrElse Set[A]() + + def nexts(qs: Set[A], c: C) : Set[A] = + qs.flatMap(next(_, c)) + + // depth-first version of accepts + def search(q: A, s: List[C]) : Boolean = s match { + case Nil => fins(q) + case c::cs => next(q, c).exists(search(_, cs)) + } + + def accepts(s: List[C]) : Boolean = + starts.exists(search(_, s)) } -// atomic parsers -case class CharParser(c: Char) extends Parser[String, Char] { - def parse(sb: String) = - if (sb != "" && sb.head == c) Set((c, sb.tail)) else Set() -} + +// NFA examples + +val nfa_trans1 : (State, Char) => Set[State] = + { case (Q0, 'a') => Set(Q0, Q1) + case (Q0, 'b') => Set(Q2) + case (Q1, 'a') => Set(Q1) + case (Q2, 'b') => Set(Q2) } -import scala.util.matching.Regex -case class RegexParser(reg: Regex) extends Parser[String, String] { - def parse(sb: String) = reg.findPrefixMatchOf(sb) match { - case None => Set() - case Some(m) => Set((m.matched, m.after.toString)) - } -} +val nfa = NFA(Set[State](Q0), nfa_trans1, Set[State](Q2)) -val NumParser = RegexParser("[0-9]+".r) -def StringParser(s: String) = RegexParser(Regex.quote(s).r) - -NumParser.parse_all("12u345") -println(NumParser.parse_all("12u45")) +nfa.accepts("aa".toList) // false +nfa.accepts("aaaaa".toList) // false +nfa.accepts("aaaaab".toList) // true +nfa.accepts("aaaaabbb".toList) // true +nfa.accepts("aaaaabbbaaa".toList) // false +nfa.accepts("ac".toList) // false -// convenience -implicit def string2parser(s: String) = StringParser(s) -implicit def char2parser(c: Char) = CharParser(c) +// Q: Why the kerfuffle about the polymorphic types in DFAs/NFAs? +// A: Subset construction. Here the state type for the DFA is +// sets of states. -implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { - def | (q : => Parser[I, T]) = new AltParser[I, T](p, q) - def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) - def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) +def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = { + DFA(nfa.starts, + { case (qs, c) => nfa.nexts(qs, c) }, + _.exists(nfa.fins)) } -implicit def StringOps(s: String) = new { - def | (q : => Parser[String, String]) = new AltParser[String, String](s, q) - def | (r: String) = new AltParser[String, String](s, r) - def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f) - def ~[S] (q : => Parser[String, S]) = - new SeqParser[String, String, S](s, q) - def ~ (r: String) = - new SeqParser[String, String, String](s, r) -} - - -val NumParserInt = NumParser ==> (s => 2 * s.toInt) - -NumParser.parse_all("12345") -NumParserInt.parse_all("12345") -NumParserInt.parse_all("12u45") - - -// grammar for arithmetic expressions -// -// E ::= T + E | T - E | T -// T ::= F * T | F -// F ::= ( E ) | Number - - -lazy val E: Parser[String, Int] = - (T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } | - (T ~ "-" ~ E) ==> { case ((x, y), z) => x - z } | T -lazy val T: Parser[String, Int] = - (F ~ "*" ~ T) ==> { case ((x, y), z) => x * z } | F -lazy val F: Parser[String, Int] = - ("(" ~ E ~ ")") ==> { case ((x, y), z) => y } | NumParserInt - - -println(E.parse_all("4*2+3")) -println(E.parse_all("4*(2+3)")) -println(E.parse_all("(4)*((2+3))")) -println(E.parse_all("4/2+3")) -println(E.parse_all("(1+2)+3")) -println(E.parse_all("1+2+3")) - - +subset(nfa).accepts("aa".toList) // false +subset(nfa).accepts("aaaaa".toList) // false +subset(nfa).accepts("aaaaab".toList) // true +subset(nfa).accepts("aaaaabbb".toList) // true +subset(nfa).accepts("aaaaabbbaaa".toList) // false +subset(nfa).accepts("ac".toList) // false @@ -308,9 +515,9 @@ // A function should do one thing, and only one thing. // Make your variables immutable, unless there's a good -// reason not to. +// reason not to. Usually there is not. -// I did it, but this is actually not a good reason: +// I did it once, but this is actually not a good reason: // generating new labels: var counter = -1 @@ -325,15 +532,69 @@ -// You can be productive on Day 1, but the language is deep. +// I think you can be productive on Day 1, but the +// language is deep. // // http://scalapuzzlers.com // // http://www.latkin.org/blog/2017/05/02/when-the-scala-compiler-doesnt-help/ -List(1, 2, 3).contains("your mom") +List(1, 2, 3).contains("your cup") + // I like best about Scala that it lets me often write // concise, readable code. And it hooks up with the -// Isabelle theorem prover. +// Isabelle theorem prover. + + +// Puzzlers + +val MONTH = 12 +val DAY = 24 +val (HOUR, MINUTE, SECOND) = (12, 0, 0) + +// use lowercase names for variable + + +//================== +val oneTwo = Seq(1, 2, 3).permutations + +if (oneTwo.length > 0) { + println("Permutations of 1 and 2:") + oneTwo.foreach(println) +} + +val threeFour = Seq(3, 4, 5).permutations + +if (!threeFour.isEmpty) { + println("Permutations of 3 and 4:") + threeFour.foreach(println) +} +//================== +val (a, b, c) = + if (4 < 5) { + "bar" + } else { + Some(10) + } + +//Because when an expression has multiple return branches, Scala tries to +//be helpful, by picking the first common ancestor type of all the +//branches as the type of the whole expression. +// +//In this case, one branch has type String and the other has type +//Option[Int], so the compiler decides that what the developer really +//wants is for the whole if/else expression to have type Serializable, +//since that’s the most specific type to claim both String and Option as +//descendants. +// +//And guess what, Tuple3[A, B, C] is also Serializable, so as far as the +//compiler is concerned, the assignment of the whole mess to (a, b, c) +//can’t be proven invalid. So it gets through with a warning, +//destined to fail at runtime. + + +//================ +// does not work anymore in 2.13.0 +val numbers = List("1", "2").toSet() + "3" \ No newline at end of file diff -r ca9c1cf929fa -r e5453add7df6 slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r ca9c1cf929fa -r e5453add7df6 slides/slides04.tex --- a/slides/slides04.tex Tue Nov 26 01:22:36 2019 +0000 +++ b/slides/slides04.tex Tue Dec 03 01:22:16 2019 +0000 @@ -148,7 +148,7 @@ Email: & christian.urban at kcl.ac.uk\\ Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\ Slides \& Code: & KEATS\\ - & \onslide<2>{\alert{A Crash-Course in Scala}}\bigskip\\ + & \onslide<2>{\alert{PDF: A Crash-Course in Scala}}\bigskip\\ Office Hours: & Thursdays 12:00 -- 14:00\\ Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\ \end{tabular} @@ -174,7 +174,16 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Discussion Forum} +\begin{center} +\includegraphics[scale=0.38]{/Users/cu/discussion.png} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -191,7 +200,7 @@ \end{itemize}\bigskip\bigskip \footnotesize -(interviews ongoing!) +(plagiarism/collusion interviews ongoing!) \end{frame} @@ -450,7 +459,7 @@ \begin{frame}[c,fragile] \frametitle{Regular Expressions} -Suppose you have a regular expression +Suppose you have the regular expression \only<1-3>{\alert{\texttt{(a*)b}}}% \only<4->{\alert{\texttt{(a*)*b}}} :\bigskip @@ -551,6 +560,11 @@ \begin{center} \includegraphics[angle=90,scale=0.35]{/Users/cu/vote.pdf} \end{center} + + \only<2>{% +\begin{textblock}{13}(10,10) +\includegraphics[scale=0.2]{/Users/cu/goodvote.png} +\end{textblock}} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% diff -r ca9c1cf929fa -r e5453add7df6 solutions3/knight1.scala --- a/solutions3/knight1.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/solutions3/knight1.scala Tue Dec 03 01:22:16 2019 +0000 @@ -48,6 +48,8 @@ def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = moves(x).filter(is_legal(dim, path, _)) + + // testcases //assert(legal_moves(8, Nil, (2,2)) == // List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) @@ -55,6 +57,7 @@ //assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == // List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) +//assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0))) //assert(legal_moves(1, Nil, (0,0)) == List()) //assert(legal_moves(2, Nil, (0,0)) == List()) //assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))) diff -r ca9c1cf929fa -r e5453add7df6 testing2/danube.scala --- a/testing2/danube.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/testing2/danube.scala Tue Dec 03 01:22:16 2019 +0000 @@ -2,114 +2,118 @@ // at Danube.co.uk //=========================================== +object CW7b { + 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 // of interest are ratings_url and movies_url, which correspond // to CSV-files. -// The function should ReTurn the CSV file appropriately broken +// +// The function should ReTurn the CSV-file appropriately broken // up into lines, and the first line should be dropped (that is without -// the header of the CSV file). The result is a list of strings (lines +// the header of the CSV-file). The result is a list of strings (lines // in the file). def get_csv_url(url: String) : List[String] = { - val csv = Source.fromURL(url)("ISO-8859-1") - csv.mkString.split("\n").toList.drop(1) + Try(Source.fromURL(url)("UTF-8").mkString.split("\n").toList.tail).getOrElse(List()) } + val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv""" val movies_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv""" -// test cases - -//val ratings = get_csv_url(ratings_url) -//val movies = get_csv_url(movies_url) +// testcases +//----------- +// val ratings = get_csv_url(ratings_url) +// val movies = get_csv_url(movies_url) //ratings.length // 87313 //movies.length // 9742 -// (2) Implement two functions that process the CSV files. The ratings + + +// (2) Implement two functions that process the CSV-files from (1). The ratings // function filters out all ratings below 4 and ReTurns a list of // (userID, movieID) pairs. The movies function just ReTurns a list -// of (movieId, title) pairs. +// of (movieID, title) pairs. def process_ratings(lines: List[String]) : List[(String, String)] = { - for (cols <- lines.map(_.split(",").toList); - if (cols(2).toFloat >= 4)) yield (cols(0), cols(1)) + val filteredLines = lines.filter(line => line.split(",")(2).toInt >= 4) + filteredLines.map(line => (line.split(",")(0), line.split(",")(1))) } def process_movies(lines: List[String]) : List[(String, String)] = { - for (cols <- lines.map(_.split(",").toList)) yield (cols(0), cols(1)) + lines.map(line => (line.split(",")(0), line.split(",")(1))) } -// test cases -//val good_ratings = process_ratings(ratings) -//val movie_names = process_movies(movies) +// testcases +//----------- +// val good_ratings = process_ratings(ratings) +// val movie_names = process_movies(movies) //good_ratings.length //48580 //movie_names.length // 9742 -//============================================== -// Do not change anything below, unless you want -// to submit the file for the advanced part 3! -//============================================== - - -// (3) Implement a grouping function that calulates a map -// containing the userIds and all the corresponding recommendations -// (list of movieIds). This should be implemented in a tail -// recursive fashion, using a map m as accumulator. This map -// is set to Map() at the beginning of the claculation. - -def groupById(ratings: List[(String, String)], - m: Map[String, List[String]]) : Map[String, List[String]] = ratings match { - case Nil => m - case (id, mov) :: rest => { - val old_ratings = m.getOrElse (id, Nil) - val new_ratings = m + (id -> (mov :: old_ratings)) - groupById(rest, new_ratings) - } -} - -// -//val ls = List(("1", "a"), ("2", "a"), ("1", "c"), ("2", "a"), ("1", "c")) -// -//val m = groupById(ls, Map()) -// -//m.getOrElse("1", Nil).count(_ == "c") // => 2 -//m.getOrElse("1", Nil).count(_ == "a") // => 1 - -// test cases -//val ratings_map = groupById(good_ratings, Map()) -//groupById(good_ratings, Map()).get("214") -//groupById(good_ratings, Map()).toList.minBy(_._2.length) -//val movies_map = movie_names.toMap - -//ratings_map.get("414").get.map(movies_map.get(_)) // most prolific recommender with 1227 positive ratings -//ratings_map.get("474").get.map(movies_map.get(_)) // second-most prolific recommender with 787 positive ratings -//ratings_map.get("214").get.map(movies_map.get(_)) // least prolific recommender with only 1 positive rating -//(4) Implement a function that takes a ratings map and a movie_name as argument. -// The function calculates all suggestions containing -// the movie mov in its recommendations. It ReTurns a list of all these -// recommendations (each of them is a list and needs to have mov deleted, -// otherwise it might happen we recommend the same movie). +// (3) Implement a grouping function that calculates a Map +// containing the userIDs and all the corresponding recommendations +// (list of movieIDs). This should be implemented in a tail +// recursive fashion, using a Map m as accumulator. This Map m +// is set to Map() at the beginning of the calculation. -def favourites(m: Map[String, List[String]], mov: String) : List[List[String]] = - (for (id <- m.keys.toList; - if m(id).contains(mov)) yield m(id).filter(_ != mov)) +def groupById(ratings: List[(String, String)], + m: Map[String, List[String]]) : Map[String, List[String]] = { + if (ratings.length == 0) m + else { + val firstUser = ratings(0)._1 + val userRatings = ratings.filter(r => r._1 == firstUser) + val movieIds = userRatings.map(r => r._2) + val newMap = m + (firstUser -> movieIds) + groupById(ratings.filter(r => r._1 != firstUser), newMap) + } +} + + +// testcases +//----------- +//val ratings_map = groupById(good_ratings, Map()) +//val movies_map = movie_names.toMap + +//ratings_map.get("414").get.map(movies_map.get(_)) +// => most prolific recommender with 1227 positive ratings + +//ratings_map.get("474").get.map(movies_map.get(_)) +// => second-most prolific recommender with 787 positive ratings + +//ratings_map.get("214").get.map(movies_map.get(_)) +// => least prolific recommender with only 1 positive rating -// test cases +// (4) Implement a function that takes a ratings map and a movie_name as argument. +// The function calculates all suggestions containing +// the movie in its recommendations. It ReTurns a list of all these +// recommendations (each of them is a list and needs to have the movie deleted, +// otherwise it might happen we recommend the same movie). + + +def favourites(m: Map[String, List[String]], mov: String) : List[List[String]] = { + val movieLists = m.map(r => r._2).toList.filter(_.contains(mov)) + for (movieList <- movieLists) yield { + movieList.filter(_!=mov) + } +} + + +// testcases +//----------- // movie ID "912" -> Casablanca (1942) // "858" -> Godfather // "260" -> Star Wars: Episode IV - A New Hope (1977) @@ -121,45 +125,53 @@ // 52 a good rating to movies 260, 318, 593. -// (5) Implement a suggestions function which takes a rating -// map and a movie_name as arguments. It calculates all the recommended -// movies sorted according to the most frequently suggested movie(s) first. -// needed in Scala 2.13. - -def mapValues[S, T, R](m: Map[S, T], f: T => R) = - m.map { case (x, y) => (x, f(y)) } +// (5) Implement a suggestions function which takes a rating +// map and a movie_name as arguments. It calculates all the recommended +// movies sorted according to the most frequently suggested movie(s) first. + def suggestions(recs: Map[String, List[String]], - mov_name: String) : List[String] = { - val favs = favourites(recs, mov_name).flatten - val favs_counted = mapValues(favs.groupBy(identity), (v:List[String]) => v.size).toList - val favs_sorted = favs_counted.sortBy(_._2).reverse - favs_sorted.map(_._1) + mov_name: String) : List[String] = { + val favs = favourites(recs, mov_name).flatten + favs.map(x => (x, favs.count(_==x))) + .sortBy(_._1) + .reverse + .sortBy(_._2) + .reverse + .distinct + .map(_._1) } -// check -// groupMap is equivalent to groupBy(key).mapValues(_.map(f)) -// test cases +// testcases +//----------- //suggestions(ratings_map, "912") //suggestions(ratings_map, "912").length // => 4110 suggestions with List(858, 260, 318, 593, ...) // being the most frequently suggested movies -// (6) Implement recommendations functions which generates at most -// *two* of the most frequently suggested movies. It Returns the -// actual movie names, not the movieIDs. + + +// (6) Implement a recommendations function which generates at most +// *two* of the most frequently suggested movies. It ReTurns the +// actual movie names, not the movieIDs. + def recommendations(recs: Map[String, List[String]], - movs: Map[String, String], - mov_name: String) : List[String] = - suggestions(recs, mov_name).take(2).map(movs.get(_).get) + movs: Map[String, String], + mov_name: String) : List[String] = { + val sug = suggestions(recs, mov_name) + val toptwo = sug.take(2) + if (toptwo.length == 0) Nil + else toptwo.map(movs(_)) +} + // testcases - +//----------- // recommendations(ratings_map, movies_map, "912") // => List(Godfather, Star Wars: Episode IV - A NewHope (1977)) @@ -177,11 +189,11 @@ // => List(Shawshank Redemption, Forrest Gump (1994)) // recommendations(ratings_map, movies_map, "4") -// => Nil (there are three ratings fro this movie in ratings.csv but they are not positive) +// => Nil (there are three ratings for this movie in ratings.csv but they are not positive) -// If you want to calculate the recomendations for all movies. -// Will take a few seconds calculation time. +// If you want to calculate the recommendations for all movies, +// then use this code (it will take a few seconds calculation time). //val all = for (name <- movie_names.map(_._1)) yield { // recommendations(ratings_map, movies_map, name) @@ -193,4 +205,32 @@ //List(1,2).take(2) //List(1,2,3).take(2) + + } + +// val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv""" +// val movies_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv""" + +// val ratings = CW7b.get_csv_url(ratings_url) +// val movies = CW7b.get_csv_url(movies_url) + +// println(movies.length) +// val good_ratings = CW7b.process_ratings(ratings) +// val movie_names = CW7b.process_movies(movies) + +// val ratings_map = CW7b.groupById(good_ratings, Map()) +// val movies_map = movie_names.toMap + + + +//println(CW7b.recommendations(ratings_map, movies_map, "912")) +/* +val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv""" + +val ratings = CW7b.get_csv_url(ratings_url) + +val good_ratings = CW7b.process_ratings(ratings) +val ratings_map = CW7b.groupById(good_ratings, Map()) + +println(CW7b.suggestions(ratings_map, "912").length)*/ diff -r ca9c1cf929fa -r e5453add7df6 testing3/knight1.scala --- a/testing3/knight1.scala Tue Nov 26 01:22:36 2019 +0000 +++ b/testing3/knight1.scala Tue Dec 03 01:22:16 2019 +0000 @@ -1,13 +1,119 @@ -// Preliminary Part 1 finding and counting Knight's tours -//======================================================== +// Preliminary Part about finding Knight's tours +//=============================================== + + +object CW8a { -object CW8a { +// If you need any auxiliary function, feel free to +// implement it, but do not make any changes to the +// templates below. Also have a look whether the functions +// at the end are of any help. + + type Pos = (Int, Int) // a position on a chessboard type Path = List[Pos] // a path...a list of positions +//(1) Complete the function that tests whether the position x +// is inside the board and not yet element in the path. -// for measuring time in the JAR +def is_legal(dim: Int, path: Path, x: Pos) : Boolean = { + if ((!(path.contains(x))) && (x._1 >= 0) && (x._2 >= 0) && (x._1 < dim) && (x._2 < dim)) + true + else false +} + +//(2) Complete the function that calculates for a position x +// all legal onward moves that are not already in the path. +// The moves should be ordered in a "clockwise" manner. + + +def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {//List[Pos] + val changes = List((1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)) + val returnList = (for ((y,z) <- changes) yield( + //println(y,z)-2,-1 + if ((is_legal(dim,path,((x._1 + y) , (x._2 + z)))) == true) + Some(x._1 + y , x._2 + z) + else + None + )) + returnList.flatten +} + + +//some testcases +// +//assert(legal_moves(8, Nil, (2,2)) == + //List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) +//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == +// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) + + +//(3) Complete the two recursive functions below. +// They exhaustively search for knight's tours starting from the +// given path. The first function counts all possible tours, +// and the second collects all tours in a list of paths. + +def count_tours(dim: Int, path: Path) : Int = (dim,path) match {//Int + case (_, Nil) => 0 + case (0, path) => 0 + case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) + if(path.size < dim*dim) + 0 + else + 1 + else (for (j <- legal_moves(dim,path, path.head)) yield count_tours(dim,j::path)).sum + } +} + +def enum_tours(dim: Int, path: Path) : List[Path] = (dim,path) match { + case (_, Nil) => Nil + case (0, path) => Nil + case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) + if(path.size < dim*dim) + Nil + else + List(path) + else (for (j <- legal_moves(dim,path, path.head)) yield enum_tours(dim,j::path)).flatten + } + +} + + +//(4) Implement a first-function that finds the first +// element, say x, in the list xs where f is not None. +// In that case Return f(x), otherwise None. If possible, +// calculate f(x) only once. + +//def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ... + + +// testcases +// +//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None +// +//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0))) +//first(List((1, 0),(2, 0),(3, 0)), foo) // None + + +//(5) Implement a function that uses the first-function from (5) for +// trying out onward moves, and searches recursively for a +// knight tour on a dim * dim-board. + + +//def first_tour(dim: Int, path: Path) : Option[Path] = ... + + + + + + +/* Helper functions + + +// for measuring time def time_needed[T](code: => T) : T = { val start = System.nanoTime() val result = code @@ -16,6 +122,14 @@ result } +// can be called for example with +// time_needed(count_tours(dim, List((0, 0)))) +// in order to print out the time that is needed for +// running count_tours + + + + // for printing a board def print_board(dim: Int, path: Path): Unit = { println @@ -27,144 +141,7 @@ } } -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) -// testcases -//assert(is_legal(8, Nil, (3, 4)) == true) -//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false) -//assert(is_legal(2, Nil, (0, 0)) == true) - - -def add_pair(x: Pos, y: Pos): Pos = - (x._1 + y._1, x._2 + y._2) - -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, _)) - -// 1 mark - -def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = - moves(x).filter(is_legal(dim, path, _)) - -// testcases -//assert(legal_moves(8, Nil, (2,2)) == -// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) -//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) -//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == -// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) -//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) -//assert(legal_moves(1, Nil, (0,0)) == List()) -//assert(legal_moves(2, Nil, (0,0)) == List()) -//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))) - -// 2 marks - -def tcount_tours(dim: Int, path: Path): Int = { - if (path.length == dim * dim) 1 - else - (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum -} - -def count_tours(dim: Int, path: Path) = - time_needed(tcount_tours(dim: Int, path: Path)) - - -def tenum_tours(dim: Int, path: Path): List[Path] = { - if (path.length == dim * dim) List(path) - else - (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten -} - -def enum_tours(dim: Int, path: Path) = - time_needed(tenum_tours(dim: Int, path: Path)) - -// test cases - -/* -def count_all_tours(dim: Int) = { - for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) -} - -def enum_all_tours(dim: Int): List[Path] = { - (for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten -} - - -println("Number of tours starting from (0, 0)") - -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0))))) -} - -println("Number of tours starting from all fields") - -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim))) -} - -for (dim <- 1 to 5) { - val ts = enum_tours(dim, List((0, 0))) - println(s"${dim} x ${dim} ") - if (ts != Nil) { - print_board(dim, ts.head) - println(ts.head) - } -} */ -// 1 mark - -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) - } } - -// test cases -//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None -// -//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) -//first(List((1, 0),(2, 0),(3, 0)), foo) - - -// 1 mark - -def tfirst_tour(dim: Int, path: Path): Option[Path] = { - if (path.length == dim * dim) Some(path) - else - first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path)) -} - -def first_tour(dim: Int, path: Path) = - time_needed(tfirst_tour(dim: Int, path: Path)) - - -/* -for (dim <- 1 to 8) { - val t = first_tour(dim, List((0, 0))) - println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) -} -*/ - -// 15 secs for 8 x 8 -//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get) - -// no result for 4 x 4 -//val ts2 = time_needed(0, first_tour(4, List((0, 0)))) - -// 0.3 secs for 6 x 6 -//val ts3 = time_needed(0, first_tour(6, List((0, 0)))) - -// 15 secs for 8 x 8 -//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get)) - - -} - -