# HG changeset patch # User Christian Urban # Date 1543676977 0 # Node ID 33c2655be47d93b7ff3a653a332f266c9af3c16f # Parent b5f3e814a7105a340ec5066ee55a519bc1b88f72 updated diff -r b5f3e814a710 -r 33c2655be47d README --- a/README Fri Nov 30 14:13:11 2018 +0000 +++ b/README Sat Dec 01 15:09:37 2018 +0000 @@ -1,5 +1,6 @@ scalac -Ydelambdafy:inline -d docdiff.jar docdiff.scala +gerp -h // gerp without filename given two lists, is one a sublist of the other except one diff -r b5f3e814a710 -r 33c2655be47d TAs --- a/TAs Fri Nov 30 14:13:11 2018 +0000 +++ b/TAs Sat Dec 01 15:09:37 2018 +0000 @@ -10,6 +10,10 @@ robert.greener@kcl.ac.uk tania.copocean@kcl.ac.uk + +2018 RESULTS +============ + CW6, Part 1 + 2 late 163 => 6 163 @@ -23,11 +27,20 @@ 234 submissions +CW7, Part 1 + 2 + late +192 => 6 163 +14 => 5 28 +12 => 4 4 +0 => 3 12 +6 => 2 4 +21 => 1 0 +12 => 0 23 +-------- +260 submissions -scala -Dscala.color - 2017 RESULTS ============ diff -r b5f3e814a710 -r 33c2655be47d marking2/danube.scala --- a/marking2/danube.scala Fri Nov 30 14:13:11 2018 +0000 +++ b/marking2/danube.scala Sat Dec 01 15:09:37 2018 +0000 @@ -26,6 +26,7 @@ // test cases + //val ratings = get_csv_url(ratings_url) //val movies = get_csv_url(movies_url) diff -r b5f3e814a710 -r 33c2655be47d marking2/danube_test.sh --- a/marking2/danube_test.sh Fri Nov 30 14:13:11 2018 +0000 +++ b/marking2/danube_test.sh Sat Dec 01 15:09:37 2018 +0000 @@ -20,13 +20,13 @@ # compilation tests function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc "$1" 2>> $out 1>> $out) } # functional tests function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) } # purity test diff -r b5f3e814a710 -r 33c2655be47d marking2/danube_test1.scala --- a/marking2/danube_test1.scala Fri Nov 30 14:13:11 2018 +0000 +++ b/marking2/danube_test1.scala Sat Dec 01 15:09:37 2018 +0000 @@ -1,5 +1,6 @@ -val urban_mov_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv""" +//val urban_mov_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv""" +val urban_mov_url = """http://localhost:8000/movies.csv""" assert(get_csv_url(urban_mov_url).length == 9742) diff -r b5f3e814a710 -r 33c2655be47d marking2/docdiff_test.sh --- a/marking2/docdiff_test.sh Fri Nov 30 14:13:11 2018 +0000 +++ b/marking2/docdiff_test.sh Sat Dec 01 15:09:37 2018 +0000 @@ -24,13 +24,13 @@ # compilation tests function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc "$1" 2>> $out 1>> $out) } # functional tests function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) } # purity test diff -r b5f3e814a710 -r 33c2655be47d marking2/mk --- a/marking2/mk Fri Nov 30 14:13:11 2018 +0000 +++ b/marking2/mk Sat Dec 01 15:09:37 2018 +0000 @@ -16,6 +16,8 @@ cp ../../../marking2/docdiff_test2.scala . cp ../../../marking2/docdiff_test3.scala . cp ../../../marking2/docdiff_test4.scala . + cp ../../../marking2/movies.csv . + cp ../../../marking2/ratings.csv . ./docdiff_test.sh output ./danube_test.sh output rm *.sh @@ -25,6 +27,8 @@ rm docdiff_test2.scala rm docdiff_test3.scala rm docdiff_test4.scala + rm ratings.csv + rm movies.csv cd .. done diff -r b5f3e814a710 -r 33c2655be47d testing4/re.scala --- a/testing4/re.scala Fri Nov 30 14:13:11 2018 +0000 +++ b/testing4/re.scala Sat Dec 01 15:09:37 2018 +0000 @@ -1,22 +1,20 @@ // Part 1 about Regular Expression Matching //========================================== -//object CW9a { - // Regular Expressions abstract class Rexp case object ZERO extends Rexp case object ONE extends Rexp case class CHAR(c: Char) extends Rexp -case class ALT(r1: Rexp, r2: Rexp) extends Rexp -case class SEQ(r1: Rexp, r2: Rexp) extends Rexp -case class STAR(r: Rexp) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative +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 -import scala.language.implicitConversions -import scala.language.reflectiveCalls - +import scala.language.implicitConversions +import scala.language.reflectiveCalls def charlist2rexp(s: List[Char]): Rexp = s match { case Nil => ONE @@ -40,116 +38,190 @@ } // (1) Complete the function nullable according to -// the definition given in the coursework; this +// the definition given in the coursework; this // function checks whether a regular expression // can match the empty string and Returns a boolean // accordingly. -def nullable (r: Rexp) : Boolean = r match { +def nullable (r: Rexp) : Boolean = r match{ case ZERO => false case ONE => true case CHAR(_) => false - case ALT(r1, r2) => nullable(r1) || nullable(r2) - case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case ALT(a,b)=>nullable(a)||nullable(b) + case SEQ(a,b) => nullable(a) && nullable(b) case STAR(_) => true } + +/*val rex = "1~0.%|11" + +assert(der('1',rex) == SEQ(ONE,SEQ(CHAR(~),SEQ(CHAR(0),SEQ(CHAR(.),SEQ(CHAR(%),SEQ(CHAR(|),SEQ(CHAR(1),CHAR(1))))))))) + +assert(der('1',der('1',rex)) == + ALT(SEQ(ZERO,SEQ(CHAR(~),SEQ(CHAR(0),SEQ(CHAR(.),SEQ(CHAR(%),SEQ(CHAR(|), + SEQ(CHAR(1),CHAR(1)))))))),SEQ(ZERO,SEQ(CHAR(0),SEQ(CHAR(.),SEQ(CHAR(%), + SEQ(CHAR(|),SEQ(CHAR(1),CHAR(1))))))))*/ + // (2) Complete the function der according to // the definition given in the coursework; this -// function calculates the derivative of a +// function calculates the derivative of a // regular expression w.r.t. a character. -def der (c: Char, r: Rexp) : Rexp = r match { +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 ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) - 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(d) => if (c==d) ONE else ZERO + case ALT(a,b) => der(c,a)|der(c,b) + case SEQ(a,b) => if(nullable(a)) {(der(c,a)~b)|der(c,b)} + else der(c,a)~b + case STAR(a) => der(c,a)~STAR(a) } +println(der('a', ZERO | ONE))// == (ZERO | ZERO) +println(der('a', (CHAR('a') | ONE) ~ CHAR('a')))// ==ALT((ONE | ZERO) ~ CHAR('a'), ONE) +println(der('a', STAR(CHAR('a'))))// == (ONE ~ STAR(CHAR('a'))) +println(der('b', STAR(CHAR('a'))))// == (ZERO ~ STAR(CHAR('a')))) + + +//ALT(SEQ(ZERO,ZERO),ZERO) +//ALT(ALT(ZERO,ZERO),ALT(ZERO,ZERO)) + +// * == | +// + == ~ // (3) Complete the simp function according to // the specification given in the coursework; this // function simplifies a regular expression from -// the inside out, like you would simplify arithmetic -// expressions; however it does not simplify inside +// the inside out, like you would simplify arithmetic +// expressions; however it does not simplify inside // STAR-regular expressions. -def simp(r: Rexp) : Rexp = r match { - case ALT(r1, r2) => (simp(r1), simp(r2)) match { - case (ZERO, r2s) => r2s - case (r1s, ZERO) => r1s - case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) - } - 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 +/* +def simp(r: Rexp) : Rexp = r match{ + case SEQ(ZERO,_) => ZERO + case SEQ(_,ZERO) => ZERO + case SEQ(ONE,a) => simp(a) + case SEQ(a,ONE) => simp(a) + case ALT(ZERO,a) => simp(a) + case ALT(a,ZERO) => simp(a) + case ALT(a,b) => if(a == b) simp(a) else r + case _ => r +}*/ + +def simp(r: Rexp) : Rexp = r match{ + case SEQ(a,b) =>{ val sa = simp(a) + val sb = simp(b) + if(sa == ZERO || sb == ZERO) ZERO + else if(sa == ONE) sb + else if(sb == ONE) sa + else SEQ(sa,sb) + } + case ALT(a,b) =>{ val sa = simp(a) + val sb = simp(b) + if(sa == ONE || sb == ONE) ONE + else if(sa == ZERO) sb + else if(sb == ZERO) sa + else if(sa == sb) sa + else ALT(sa,sb) + } + //case STAR(STAR(a)) => simp(STAR(a)) + //case STAR(a) => STAR(simp(a)) + case _ => r + /* + case SEQ(ZERO,_) => ZERO + case SEQ(_,ZERO) => ZERO + case SEQ(ONE,a) => simp(a) + case SEQ(a,ONE) => simp(a) + case SEQ(a,b) => SEQ(simp(a),simp(b)) + //case ALT(ZERO,a) => simp(a) + case ALT(a,ZERO) => simp(a) + case ALT(ONE,_) => ONE + case ALT(_,ONE) => ONE + case ALT(a,b) => {val sa = simp(a) + if(sa == simp(b)) sa else r + } + case STAR(STAR(a)) => simp(STAR(a)) + case STAR(a) => STAR(simp(a)) + case _ => r*/ } -// (4) Complete the two functions below; the first +/*val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) +println("TEST: " + simp(der('a', der('a', EVIL)))) +println(simp(ONE)) +val r1 = ALT(ZERO,ONE) +val r2 = SEQ(ONE,ZERO) +val r3 = SEQ(r1,SEQ(r2,r1)) +println("R1 = " + simp(r1)) +println(simp(r2)) +println(simp(r3)) +*/ + +// (4) 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 { +def ders (s: List[Char], r: Rexp ="") : Rexp = s match{ case Nil => r - case c::s => ders(s, simp(der(c, r))) + case a::z => ders(z,simp(der(a,r))) } -// main matcher function -def matcher(r: Rexp, s: String) = nullable(ders(s.toList, r)) +def matcher(r: Rexp, s: String): Boolean = { + val derivatives = simp(ders(s.toList,r)) + nullable(derivatives) +} // (5) Complete the size function for regular -// expressions according to the specification +// expressions according to the specification // given in the coursework. - -def size(r: Rexp): Int = r match { +def size(r: Rexp): Int = r match{ case ZERO => 1 case ONE => 1 case CHAR(_) => 1 - case ALT(r1, r2) => 1 + size(r1) + size (r2) - case SEQ(r1, r2) => 1 + size(r1) + size (r2) - case STAR(r1) => 1 + size(r1) + case SEQ(a,b) => 1 + size(a) + size(b) + case ALT(a,b) => 1 + size(a) + size(b) + case STAR(a) => 1 + size(a) } - - +println(der('a', ZERO | ONE))// == (ZERO | ZERO) +println(der('a', (CHAR('a') | ONE) ~ CHAR('a')))// ==ALT((ONE | ZERO) ~ CHAR('a'), ONE) +println(der('a', STAR(CHAR('a'))))// == (ONE ~ STAR(CHAR('a'))) +println(der('b', STAR(CHAR('a'))))// == (ZERO ~ STAR(CHAR('a')))) // some testing data /* -matcher(("a" ~ "b") ~ "c", "abc") // => true -matcher(("a" ~ "b") ~ "c", "ab") // => false + +assert(matcher(("a" ~ "b") ~ "c", "abc") == true) // => true +assert(matcher(("a" ~ "b") ~ "c", "ab") == false) // => 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')) + -matcher(EVIL, "a" * 1000 ++ "b") // => true -matcher(EVIL, "a" * 1000) // => false +assert(matcher(EVIL, "a" * 1000 ++ "b") == true) // => true +assert(matcher(EVIL, "a" * 1000) == false) // => false // size without simplifications -size(der('a', der('a', EVIL))) // => 28 -size(der('a', der('a', der('a', EVIL)))) // => 58 +assert("28 " + size(der('a', der('a', EVIL))) ==28)// => 28 +assert("58 " + size(der('a', der('a', der('a', EVIL)))) ==58)// => 58 // size with simplification -size(simp(der('a', der('a', EVIL)))) // => 8 -size(simp(der('a', der('a', der('a', EVIL))))) // => 8 +assert("8 " + size(simp(der('a', der('a', EVIL)))) ==8)// => 8 +assert("8 " + size(simp(der('a', der('a', der('a', EVIL))))) ==8) // => 8 -// Python needs around 30 seconds for matching 28 a's with EVIL. +*/ + + +/* +// 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() @@ -162,15 +234,13 @@ println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i)))) } -// another "power" test case -simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(100).next) == ONE +// another "power" test case +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 100 times. - +// where SEQ is nested 50 times. + */ - -//} diff -r b5f3e814a710 -r 33c2655be47d testing4/re_test.sh --- a/testing4/re_test.sh Fri Nov 30 14:13:11 2018 +0000 +++ b/testing4/re_test.sh Sat Dec 01 15:09:37 2018 +0000 @@ -19,7 +19,7 @@ # functional tests 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 -nc -i "$1" "$2" -e "") #2> /dev/null 1> /dev/null) }