--- 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
--- 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)
+
+
--- 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)
--- 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
--- 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)
--- 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
--- 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))
--- 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
Binary file slides/slides04.pdf has changed
--- 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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--- 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)))
--- 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)*/
--- 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))
-
-
-}
-
-