# HG changeset patch # User Christian Urban # Date 1641690390 0 # Node ID 4edc1a3086520c0aaf049fa02507630bc6707c43 # Parent d8dbf91c149b8b2dae374a953bf7e1223e543bdc updated diff -r d8dbf91c149b -r 4edc1a308652 cws/core_cw01.pdf Binary file cws/core_cw01.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/core_cw02.pdf Binary file cws/core_cw02.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/core_cw03.pdf Binary file cws/core_cw03.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/cw04.pdf Binary file cws/cw04.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/cw05.pdf Binary file cws/cw05.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/cw06.pdf Binary file cws/cw06.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/main_cw01.pdf Binary file cws/main_cw01.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/main_cw02.pdf Binary file cws/main_cw02.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/main_cw02.tex --- a/cws/main_cw02.tex Mon Jan 03 00:59:32 2022 +0000 +++ b/cws/main_cw02.tex Sun Jan 09 01:06:30 2022 +0000 @@ -1,3 +1,4 @@ + % !TEX program = xelatex \documentclass{article} \usepackage{../style} @@ -11,6 +12,12 @@ \section*{Main Part 2 (Scala, 6 Marks)} +\mbox{}\hfill\textit{``C makes it easy to shoot yourself in the foot; C++ makes it harder,}\\ +\mbox{}\hfill\textit{ but when you do, it blows your whole leg off.''}\smallskip\\ +\mbox{}\hfill\textit{ --- Bjarne Stroustrup (creator of the C++ language)}\bigskip\bigskip + + + \noindent You are asked to implement a Scala program for recommending movies diff -r d8dbf91c149b -r 4edc1a308652 cws/main_cw03.pdf Binary file cws/main_cw03.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/main_cw04.pdf Binary file cws/main_cw04.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/main_cw05.pdf Binary file cws/main_cw05.pdf has changed diff -r d8dbf91c149b -r 4edc1a308652 cws/main_cw05.tex --- a/cws/main_cw05.tex Mon Jan 03 00:59:32 2022 +0000 +++ b/cws/main_cw05.tex Sun Jan 09 01:06:30 2022 +0000 @@ -470,7 +470,7 @@ implement this command by writing 0 to \pcode{mem(mp)}, that is use \pcode{write(mem, mp, 0)} as the rule for the command \texttt{0}. The easiest way to modify a string in this way is to use the regular - expression \pcode{"""[^<>+-.\\[\\]]"""}, which recognises everything that is + expression \pcode{"""[^<>+\\-.\\[\\]]"""}, which recognises everything that is not a bf-command. Similarly, the regular expression \pcode{"""\\[-\\]"""} finds all occurrences of \pcode{[-]}. By using the Scala method \pcode{.replaceAll} you can replace substrings with new strings.\\ diff -r d8dbf91c149b -r 4edc1a308652 main_solution5/bf.scala --- a/main_solution5/bf.scala Mon Jan 03 00:59:32 2022 +0000 +++ b/main_solution5/bf.scala Sun Jan 09 01:06:30 2022 +0000 @@ -209,3 +209,6 @@ //run(load_bff("collatz.bf")) } + + +M5a.run(M5a.load_bff("mandelbrot.bf")) diff -r d8dbf91c149b -r 4edc1a308652 main_solution5/bfc.scala --- a/main_solution5/bfc.scala Mon Jan 03 00:59:32 2022 +0000 +++ b/main_solution5/bfc.scala Sun Jan 09 01:06:30 2022 +0000 @@ -212,9 +212,10 @@ //println(optimise(load_bff("collatz.bf"))) //optimise(load_bff("benchmark.bf")) // should have inserted 0's -//optimise(load_bff("mandelbrot.bf")).length // => 11203 +//optimise(load_bff("mandelbrot.bf")).length // => 11205 //time_needed(1, run3(load_bff("benchmark.bf"))) +//time_needed(1, run3(load_bff("mandelbrot.bf"))) diff -r d8dbf91c149b -r 4edc1a308652 main_templates5/bfc.scala --- a/main_templates5/bfc.scala Mon Jan 03 00:59:32 2022 +0000 +++ b/main_templates5/bfc.scala Sun Jan 09 01:06:30 2022 +0000 @@ -95,7 +95,7 @@ // that is write(mem, mp, 0). // // The easiest way to modify a string in this way is to use the regular -// expression """[^<>+-,\[\]]""", which recognises everything that is +// expression """[^<>+\-.\[\]]""", which recognises everything that is // not a bf-command and replace it by the empty string. Similarly the // regular expression """\[-\]""" finds all occurrences of [-] and // by using the Scala method .replaceAll you can replace it with the diff -r d8dbf91c149b -r 4edc1a308652 main_testing1/drumb_test.sh --- a/main_testing1/drumb_test.sh Mon Jan 03 00:59:32 2022 +0000 +++ b/main_testing1/drumb_test.sh Sun Jan 09 01:06:30 2022 +0000 @@ -1,7 +1,9 @@ #!/bin/bash set -euo pipefail -out=${1:-output} +scalafile=${1:-drumb.scala} +out=${2:-output} + echo -e "" > $out @@ -33,7 +35,7 @@ # compilation test echo -e "drumb.scala runs?" >> $out -if (scala_compile drumb.scala) +if (scala_compile $scalafile) then echo -e " --> passed" >> $out tsts=$(( 0 )) @@ -51,7 +53,7 @@ then echo -e "drumb.scala does not contain vars, returns etc?" >> $out - if (scala_vars drumb.scala) + if (scala_vars $scalafile) then echo -e " --> FAIL (make triple-sure your program conforms to the required format)" >> $out tsts=$(( 1 )) @@ -69,7 +71,7 @@ echo -e " get_january_data(\"GOOG\", 1980) == List()" >> $out echo -e " get_january_data(\"GOOG\", 2010).head == \"2010-01-04,312.204773\"" >> $out - if (scala_assert "drumb.scala" "drumb_test1.scala") + if (scala_assert $scalafile "drumb_test1.scala") then echo -e " --> success" >> $out else @@ -84,7 +86,7 @@ echo -e " get_first_price(\"GOOG\", 1980) == None" >> $out echo -e " get_first_price(\"GOOG\", 2010) == Some(312.204773)" >> $out - if (scala_assert "drumb.scala" "drumb_test2.scala") + if (scala_assert $scalafile "drumb_test2.scala") then echo -e " --> success" >> $out else @@ -101,7 +103,7 @@ echo " List(Some(301.0466), Some(41.244694))," >> $out echo " List(Some(331.462585), Some(51.464207)))" >> $out - if (scala_assert "drumb.scala" "drumb_test3.scala") + if (scala_assert $scalafile "drumb_test3.scala") then echo -e " --> success" >> $out else @@ -118,7 +120,7 @@ echo -e " get_delta(None, Some(100.0)) == None" >> $out echo -e " get_delta(Some(50.0), Some(100.0)) == Some(1.0)" >> $out - if (scala_assert "drumb.scala" "drumb_test4.scala") + if (scala_assert $scalafile "drumb_test4.scala") then echo -e " --> success" >> $out else @@ -139,7 +141,7 @@ echo -e " List(List(None), List(None), " >> $out echo -e " List(Some(0.9277165354330709)), List(Some(2.119679764725104))) " >> $out - if (scala_assert "drumb.scala" "drumb_test5.scala") + if (scala_assert $scalafile "drumb_test5.scala") then echo -e " --> success" >> $out else @@ -156,7 +158,7 @@ echo -e " yearly_yield(ds, 100, 0) == 125" >> $out echo -e " yearly_yield(ds, 100, 1) == 117" >> $out - if (scala_assert "drumb.scala" "drumb_test6.scala") + if (scala_assert $scalafile "drumb_test6.scala") then echo -e " --> success" >> $out else @@ -181,7 +183,7 @@ echo -e " investment(List(\"GOOG\", \"AAPL\", \"BIDU\"), 1990 to 2017, 100) == 11504" >> $out - if (scala_assert "drumb.scala" "drumb_test7.scala") + if (scala_assert $scalafile "drumb_test7.scala") then echo -e " --> success" >> $out else diff -r d8dbf91c149b -r 4edc1a308652 main_testing3/re.scala --- a/main_testing3/re.scala Mon Jan 03 00:59:32 2022 +0000 +++ b/main_testing3/re.scala Sun Jan 09 01:06:30 2022 +0000 @@ -1,4 +1,4 @@ -// Core Part about Regular Expression Matching +// Main Part 3 about Regular Expression Matching //============================================= object M3 { @@ -12,8 +12,8 @@ case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence case class STAR(r: Rexp) extends Rexp // star -// some convenience for typing in regular expressions +// some convenience for typing regular expressions //the usual binary choice can be defined in terms of ALTs def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2)) @@ -22,7 +22,6 @@ import scala.language.implicitConversions import scala.language.reflectiveCalls - def charlist2rexp(s: List[Char]): Rexp = s match { case Nil => ONE case c::Nil => CHAR(c) @@ -53,12 +52,18 @@ def nullable (r: Rexp) : Boolean = r match { case ZERO => false case ONE => true - case CHAR(_) => false - case ALTs(rs) => rs.exists(nullable) - case SEQ(r1, r2) => nullable(r1) && nullable(r2) - case STAR(_) => true + case CHAR(c) => false + case ALTs(rs) => { + if (rs.size == 0) false + else if (nullable(rs.head)) true + else nullable(ALTs(rs.tail)) + } + case SEQ(c, s) => nullable(c) && nullable(s) + case STAR(r) => true + case _ => false } + // (2) Complete the function der according to // the definition given in the coursework; this // function calculates the derivative of a @@ -67,128 +72,138 @@ def der (c: Char, r: Rexp) : Rexp = r match { case ZERO => ZERO case ONE => ZERO - case CHAR(d) => if (c == d) ONE else ZERO - case ALTs(rs) => ALTs(rs.map(der(c, _))) - case SEQ(r1, r2) => - if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) - else SEQ(der(c, r1), r2) - case STAR(r1) => SEQ(der(c, r1), STAR(r1)) + case CHAR(x) => { + if (x==c) ONE + else ZERO + } + case ALTs(rs) => ALTs(for (i <- rs) yield der(c, i)) + case SEQ(x, y) => { + if (nullable(x)) ALTs(List(SEQ(der(c, x), y), der(c, y))) + else SEQ(der(c, x), y) + } + case STAR(x) => SEQ(der(c, x), STAR(x)) +} + + +// (3) Implement the flatten function flts. It +// deletes 0s from a list of regular expressions +// and also 'spills out', or flattens, nested +// ALTernativeS. + +def flts(rs: List[Rexp]) : List[Rexp] = rs match { + case Nil => Nil + case ZERO::rest => flts(rest) + case ALTs(rs_other)::rest => rs_other ::: flts(rest) + case r::rest => r::flts(rest) } -def flts(rs: List[Rexp]) : List[Rexp] = rs match { - case Nil => Nil - case ZERO::tl => flts(tl) - case ALTs(rs1)::rs2 => rs1 ::: flts(rs2) - case r::rs => r :: flts(rs) -} - -// (3) Complete the simp function according to -// the specification given in the coursework; this -// function simplifies a regular expression from +// (4) Complete the simp function according to +// the specification given in the coursework description; +// this function simplifies a regular expression from // the inside out, like you would simplify arithmetic // expressions; however it does not simplify inside -// STAR-regular expressions. - +// STAR-regular expressions. Use the _.distinct and +// flts functions. def simp(r: Rexp) : Rexp = r match { - case ALTs(rs) => (flts(rs.map(simp)).distinct) match { - case Nil => ZERO - case r::Nil => r - case rs => ALTs(rs) + case SEQ(x, ZERO) => ZERO + case SEQ(ZERO, x) => ZERO + case SEQ(x, ONE) => x + case SEQ(ONE, x) => x + case SEQ(x, y) => SEQ(simp(x), simp(y)) + case ALTs(rs) => { + val list = flts(for (x <- rs) yield simp(x)).distinct + if (list.size == 0) ZERO + else if (list.size == 1) list.head + else ALTs(list) } - case SEQ(r1, r2) => (simp(r1), simp(r2)) match { - case (ZERO, _) => ZERO - case (_, ZERO) => ZERO - case (ONE, r2s) => r2s - case (r1s, ONE) => r1s - case (r1s, r2s) => SEQ(r1s, r2s) - } - case r => r + case x => x } -// (4) Complete the two functions below; the first +// (5) Complete the two functions below; the first // calculates the derivative w.r.t. a string; the second // is the regular expression matcher taking a regular // expression and a string and checks whether the -// string matches the regular expression. +// string matches the regular expression def ders (s: List[Char], r: Rexp) : Rexp = s match { case Nil => r - case c::s => ders(s, simp(der(c, r))) + case c::rest => { + val deriv = simp(der(c,r)) + ders(rest, deriv) + } } -// main matcher function -def matcher(r: Rexp, s: String) = nullable(ders(s.toList, r)) +def matcher(r: Rexp, s: String): Boolean = nullable(ders(s.toList, r)) -// (5) Complete the size function for regular + +// (6) Complete the size function for regular // expressions according to the specification // given in the coursework. - def size(r: Rexp): Int = r match { + case Nil => 0 case ZERO => 1 case ONE => 1 - case CHAR(_) => 1 - case ALTs(rs) => 1 + rs.map(size).sum - case SEQ(r1, r2) => 1 + size(r1) + size (r2) - case STAR(r1) => 1 + size(r1) + case CHAR(x) => 1 + case ALTs(rs) => 1 + (for (x <- rs) yield size(x)).sum + case SEQ(x, y) => 1 + size(x) + size(y) + case STAR(x) => 1 + size(x) } - // some testing data -//matcher(("a" ~ "b") ~ "c", "abc") // => true -//matcher(("a" ~ "b") ~ "c", "ab") // => false + +// matcher(("a" ~ "b") ~ "c", "abc") // => true +// matcher(("a" ~ "b") ~ "c", "ab") // => false // the supposedly 'evil' regular expression (a*)* b -val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) +// val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) -//println(matcher(EVIL, "a" * 1000 ++ "b")) // => true -//println(matcher(EVIL, "a" * 1000)) // => false +// matcher(EVIL, "a" * 1000 ++ "b") // => true +// matcher(EVIL, "a" * 1000) // => false // size without simplifications -//println(size(der('a', der('a', EVIL)))) // => 28 -//println(size(der('a', der('a', der('a', EVIL))))) // => 58 +// size(der('a', der('a', EVIL))) // => 28 +// size(der('a', der('a', der('a', EVIL)))) // => 58 // size with simplification -//println(simp(der('a', der('a', EVIL)))) -//println(simp(der('a', der('a', der('a', EVIL))))) - -//println(size(simp(der('a', der('a', EVIL))))) // => 8 -//println(size(simp(der('a', der('a', der('a', EVIL)))))) // => 8 +// size(simp(der('a', der('a', EVIL)))) // => 8 +// size(simp(der('a', der('a', der('a', EVIL))))) // => 8 // Python needs around 30 seconds for matching 28 a's with EVIL. // Java 9 and later increase this to an "astonishing" 40000 a's in -// around 30 seconds. +// 30 seconds. // -// Lets see how long it takes to match strings with -// 5 Million a's...it should be in the range of a -// couple of seconds. +// Lets see how long it really takes to match strings with +// 5 Million a's...it should be in the range of a couple +// of seconds. -def time_needed[T](i: Int, code: => T) = { - val start = System.nanoTime() - for (j <- 1 to i) code - val end = System.nanoTime() - "%.5f".format((end - start)/(i * 1.0e9)) -} +// def time_needed[T](i: Int, code: => T) = { +// val start = System.nanoTime() +// for (j <- 1 to i) code +// val end = System.nanoTime() +// "%.5f".format((end - start)/(i * 1.0e9)) +// } -//for (i <- 0 to 5000000 by 500000) { -// println(s"$i ${time_needed(2, matcher(EVIL, "a" * i))} secs.") -//} +// for (i <- 0 to 5000000 by 500000) { +// println(s"$i ${time_needed(2, matcher(EVIL, "a" * i))} secs.") +// } // another "power" test case -//simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(100).next) == ONE +// simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next()) == ONE // the Iterator produces the rexp // // SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE) // // where SEQ is nested 50 times. - +// This a dummy comment. Hopefully it works! } +