# HG changeset patch # User Christian Urban # Date 1484145766 0 # Node ID 8f03f0dc3065e571208195103625fa929d67dcaf # Parent 3db70bdce7a4c2a0d4d314d1fab97aeee7328f2d# Parent 4fa7231fede7452cf1b77dc5ad990444b5a7ddb0 merged diff -r 3db70bdce7a4 -r 8f03f0dc3065 LINKS --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/LINKS Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,2 @@ +Source of exercises + http://exercism.io \ No newline at end of file diff -r 3db70bdce7a4 -r 8f03f0dc3065 README --- a/README Wed Jan 11 14:41:32 2017 +0000 +++ b/README Wed Jan 11 14:42:46 2017 +0000 @@ -6,4 +6,30 @@ deleting comments from scala files -find . -name '*.scala' -print0 | xargs -0 perl -n -p -0 -i.bak -e 's%/\*([^*].*?)?\*/%%gs;s%^([^\"\n\r]*(\"[^\"\n\r]*\"[^\"\n\r]*?)*?)//([^*\n\r].*)?$%$1%gm' \ No newline at end of file +find . -name '*.scala' -print0 | xargs -0 perl -n -p -0 -i.bak -e 's%/\*([^*].*?)?\*/%%gs;s%^([^\"\n\r]*(\"[^\"\n\r]*\"[^\"\n\r]*?)*?)//([^*\n\r].*)?$%$1%gm' + + +find . -name '*.scala' -print0 | sed -i.2 's|def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = ..|//def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = ..|g' + + +LC_ALL=C sed -i.2 -- 's|def ordered_moves(dim: Int, path: Path, x: Pos): List\[Pos\] = \.\.|//def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = ..|g' k*/knight3.scala.bak + +LC_ALL=C sed -i.2 -- 's|def first_closed_tour_heuristic(dim: Int, path: Path): Option\[Path\] = \.\.\.|//def first_closed_tour_heuristic(dim: Int, path: Path): Option[Path] = ...|g' k*/knight3.scala.bak + +LC_ALL=C sed -i.2 -- 's|def first_tour_heuristic(dim: Int, path: Path): Option\[Path\] = \.\.\.|//def first_tour_heuristic(dim: Int, path: Path): Option[Path] = ...|g' k*/knight3.scala.bak + +LC_ALL=C sed -i.2 -- 's|def nullable (r: Rexp) : Boolean = \.\.\.|//def nullable (r: Rexp) : Boolean = ...|g' k*/re.scala.bak + +LC_ALL=C sed -i.2 -- 's|def der (c: Char, r: Rexp) : Rexp = \.\.\.|//def der (c: Char, r: Rexp) : Rexp = ...|g' k*/re.scala.bak + +LC_ALL=C sed -i.2 -- 's|def simp(r: Rexp) : Rexp = \.\.\.|//def simp(r: Rexp) : Rexp = ...|g' k*/re.scala.bak + +LC_ALL=C sed -i.2 -- 's|def ders (s: List[Char], r: Rexp) : Rexp = \.\.\.|//def ders (s: List[Char], r: Rexp) : Rexp = ...|g' k*/re.scala.bak + +LC_ALL=C sed -i.2 -- 's|def matcher(r: Rexp, s: String): Boolean = \.\.\.|//def matcher(r: Rexp, s: String): Boolean = ...|g' k*/re.scala.bak + +LC_ALL=C sed -i.2 -- 's|def replace(r: Rexp, s1: String, s2: String): String = \.\.\.|//def replace(r: Rexp, s1: String, s2: String): String = ...|g' k*/re.scala.bak + +LC_ALL=C sed -i.2 -- 's|println(matcher(EVIL,|//println(matcher(EVIL,|g' k*/re.scala.bak + +LC_ALL=C sed -i.2 -- 's|for (i <- 1 to 5000001 by 500000)|for (i <- 1 to 11 by 10)|g' k*/re.scala.bak \ No newline at end of file diff -r 3db70bdce7a4 -r 8f03f0dc3065 cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 3db70bdce7a4 -r 8f03f0dc3065 cws/cw03.tex --- a/cws/cw03.tex Wed Jan 11 14:41:32 2017 +0000 +++ b/cws/cw03.tex Wed Jan 11 14:42:46 2017 +0000 @@ -327,18 +327,17 @@ \end{itemize}\bigskip +\subsection*{Background} -\noindent -\textbf{Background} Although easily implementable in Scala, the idea -behind the derivative function might not so easy to be seen. To -understand its purpose better, assume a regular expression $r$ can -match strings of the form $c::cs$ (that means strings which start with -a character $c$ and have some rest, or tail, $cs$). If you now take the -derivative of $r$ with respect to the character $c$, then you obtain a -regular expressions that can match all the strings $cs$. In other -words, the regular expression $\textit{der}\;c\;r$ can match the same -strings $c::cs$ that can be matched by $r$, except that the $c$ is -chopped off. +Although easily implementable in Scala, the idea behind the derivative +function might not so easy to be seen. To understand its purpose +better, assume a regular expression $r$ can match strings of the form +$c::cs$ (that means strings which start with a character $c$ and have +some rest, or tail, $cs$). If you now take the derivative of $r$ with +respect to the character $c$, then you obtain a regular expressions +that can match all the strings $cs$. In other words, the regular +expression $\textit{der}\;c\;r$ can match the same strings $c::cs$ +that can be matched by $r$, except that the $c$ is chopped off. Assume now $r$ can match the string $abc$. If you take the derivative according to $a$ then you obtain a regular expression that can match diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/knight3b_test.scala diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/knight3c_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/knight3c_test.scala Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,45 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + + +def add_pair_urban(x: Pos)(y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +def is_legal_urban(dim: Int, path: Path)(x: Pos): Boolean = + 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) + +def moves_urban(x: Pos): List[Pos] = + List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), + (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair_urban(x)) + +def legal_moves_urban(dim: Int, path: Path, x: Pos): List[Pos] = + moves_urban(x).filter(is_legal_urban(dim, path)) + +def correct_urban(dim: Int)(p: Path): Boolean = p match { + case Nil => true + case x::Nil => true + case x::y::p => + if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false +} + + +lazy val f1 = Future { + + val ts8 = first_tour_heuristic(8, List((0,0))).get + assert(correct_urban(8)(ts8) == true) + +} + +Await.result(f1, 360 second) + +lazy val f2 = Future { + + val ts50 = first_tour_heuristic(50, List((0,0))).get + assert(correct_urban(50)(ts50) == true) + +} + +Await.result(f2, 360 second) diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/mark02b diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/mark03a --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/mark03a Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,165 @@ +#!/bin/bash +set -e + +out=${1:-output} + +echo "" > $out + +echo "Below is the feedback and provisional mark for your submission" >> $out +echo "for CW 8, Part 1. 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 + +function scala_vars { + (egrep '\bvar\b|\breturn\b|ListBuffer|mutable' "$1" 2> /dev/null 1> /dev/null) +} + + +# compilation tests + +function scala_compile { + (scala "$1" 2> /dev/null 1> /dev/null) +} + + +# functional tests + +function scala_assert { + (scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + + +# marks for CW +marks=$(( 0 )) + + +# var, return, ListBuffer test +# +echo "re.scala does not contain vars, returns etc?" | tee -a $out + +if (scala_vars re.scala) +then + echo " --> fail" | tee -a $out + tsts0=$(( 1 )) +else + echo " --> yes" | tee -a $out + tsts0=$(( 0 )) +fi + + +# compilation test +if [ $tsts0 -eq 0 ] +then + echo "re.scala runs?" | tee -a $out + + if (scala_compile re.scala.bak) + then + echo " --> yes" | tee -a $out + tsts1=$(( 0 )) + else + echo " --> scala re.scala did not run successfully" | tee -a $out + tsts1=$(( 1 )) + fi +else + tsts1=$(( 1 )) +fi + +if [ $tsts1 -eq 0 ] +then + echo " nullable(ZERO) == false" | tee -a $out + echo " nullable(ONE) == true" | tee -a $out + echo " nullable(CHAR('a')) == false" | tee -a $out + echo " nullable(ZERO | ONE) == true" | tee -a $out + echo " nullable(ZERO | CHAR('a')) == false" | tee -a $out + echo " nullable(ONE ~ ONE) == true" | tee -a $out + echo " nullable(ONE ~ CHAR('a')) == false" | tee -a $out + echo " nullable(STAR(ZERO)) == true" | tee -a $out + + if (scala_assert "re.scala.bak" "../../../marking/re1a_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo " --> test failed" | tee -a $out + fi +fi + +if [ $tsts1 -eq 0 ] +then + echo " der('a', ZERO | ONE) == (ZERO | ZERO)" | tee -a $out + echo " der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE)" | tee -a $out + echo " der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))" | tee -a $out + echo " der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))" | tee -a $out + + if (scala_assert "re.scala.bak" "../../../marking/re1b_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo " --> test failed" | tee -a $out + fi +fi + +if [ $tsts1 -eq 0 ] +then + echo " simp(ZERO | ONE) == ONE" | tee -a $out + echo " simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)" | tee -a $out + echo " simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')" | tee -a $out + echo " simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO" | tee -a $out + echo " simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')" | tee -a $out + echo " simp(CHAR('a') | CHAR('a')) == CHAR('a')" | tee -a $out + echo " simp(ONE | CHAR('a')) == (ONE | CHAR('a'))" | tee -a $out + + if (scala_assert "re.scala.bak" "../../../marking/re1c_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo " --> test failed" | tee -a $out + fi +fi + +if [ $tsts1 -eq 0 ] +then + echo " EVIL = (a*)* b" | tee -a $out + echo " ders(List.fill(5)('a'),EVIL) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))" | tee -a $out + echo " ders(List('b'),EVIL) == ONE" | tee -a $out + echo " ders(List('b','b'),EVIL) == ZERO" | tee -a $out + echo " matcher(EVIL, \"a\" * 5 ++ \"b\") == true" | tee -a $out + echo " matcher(EVIL, \"b\") == true" | tee -a $out + echo " matcher(EVIL, \"bb\") == false" | tee -a $out + echo " matcher(\"abc\", \"abc\") == true" | tee -a $out + echo " matcher((\"ab\" | \"a\") ~ (ONE | \"bc\"), \"abc\") == true" | tee -a $out + echo " matcher(ONE, \"\") == true" | tee -a $out + echo " matcher(ZERO, \"\") == false" | tee -a $out + echo " matcher(ONE | CHAR('a'), \"\") == true" | tee -a $out + echo " matcher(ONE | CHAR('a'), \"a\") == true" | tee -a $out + + if (scala_assert "re.scala.bak" "../../../marking/re1d_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo " --> test failed" | tee -a $out + fi +fi + +if [ $tsts1 -eq 0 ] +then + echo " replace(\"aa\".% | \"bb\", \"aabbbaaaaaaabaaaaabbaaaabb\" , \"c\") == \"ccbcabcaccc\"" | tee -a $out + echo " replace(\"aa\".% | \"bb\", \"abba\" , \"\") == \"aa\"" | tee -a $out + + if (scala_assert "re.scala.bak" "../../../marking/re1e_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 2 )) + else + echo " --> test failed" | tee -a $out + fi +fi + + +## final marks +echo "Overall mark for CW 8, Part 1" | tee -a $out +echo "$marks" | tee -a $out diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/mark03b --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/mark03b Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,113 @@ +#!/bin/bash +set -e + +out=${1:-output} + +echo "" > $out + +echo "Below is the feedback and provisional mark for your submission" >> $out +echo "for CW 8, Part 2. 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 + +function scala_vars { + (egrep '\bvar\b|\breturn\b|ListBuffer|mutable' "$1" 2> /dev/null 1> /dev/null) +} + + +# compilation tests + +function scala_compile { + (scala "$1" 2> /dev/null 1> /dev/null) +} + + +# functional tests + +function scala_assert { + (scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + + +# marks for CW +marks=$(( 0 )) + + +# var, return, ListBuffer test +# +echo "re2.scala does not contain vars, returns etc?" | tee -a $out + +if (scala_vars re2.scala) +then + echo " --> fail" | tee -a $out + tsts0=$(( 1 )) +else + echo " --> yes" | tee -a $out + tsts0=$(( 0 )) +fi + + +# compilation test +if [ $tsts0 -eq 0 ] +then + echo "re2.scala runs?" | tee -a $out + + if (scala_compile re2.scala) + then + echo " --> yes" | tee -a $out + tsts1=$(( 0 )) + else + echo " --> scala re2.scala did not run successfully" | tee -a $out + tsts1=$(( 1 )) + fi +else + tsts1=$(( 1 )) +fi + +if [ $tsts1 -eq 0 ] +then + echo " iterT(200000, (x: Int) => x + 1, 0) == 200000" | tee -a $out + echo " iterT(100, (x: BigInt) => x * 2, BigInt(2)) == BigInt(\"2535301200456458802993406410752\")" | tee -a $out + echo " iterT(10, (x: String) => x ++ \"a\", \"a\") == \"aaaaaaaaaaa\"" | tee -a $out + + if (scala_assert "re2.scala" "../../../marking/re2a_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 2 )) + else + echo " --> test failed" | tee -a $out + fi +fi + +if [ $tsts1 -eq 0 ] +then + echo " size(iterT(20, (r: Rexp) => der('a', r), EVIL)) == 7340068" | tee -a $out + echo " size(iterT(20, (r: Rexp) => simp(der('a', r)), EVIL)) == 8" | tee -a $out + + if (scala_assert "re2.scala" "../../../marking/re2b_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo " --> test failed" | tee -a $out + fi +fi + +if [ $tsts1 -eq 0 ] +then + echo " fixpT((x:Int) => if (200000 < x) x else x + 1, 0) == 200001" | tee -a $out + echo " fixpT((x:Long) => if (20 < x) x else x + 1, 0L) == 21L" | tee -a $out + + if (scala_assert "re2.scala" "../../../marking/re2c_test.scala") + then + echo " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo " --> test failed" | tee -a $out + fi +fi + +## final marks +echo "Overall mark for CW 8, Part 2" | tee -a $out +echo "$marks" | tee -a $out diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/mk --- a/marking/mk Wed Jan 11 14:41:32 2017 +0000 +++ b/marking/mk Wed Jan 11 14:42:46 2017 +0000 @@ -5,6 +5,7 @@ for sd in k*; do cd $sd echo $sd + touch . #../mark ../mark01b cd .. diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/re1a_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/re1a_test.scala Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,20 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + + + +lazy val f = Future { + assert(nullable(ZERO) == false) + assert(nullable(ONE) == true) + assert(nullable(CHAR('a')) == false) + assert(nullable(ZERO | ONE) == true) + assert(nullable(ZERO | CHAR('a')) == false) + assert(nullable(ONE ~ ONE) == true) + assert(nullable(ONE ~ CHAR('a')) == false) + assert(nullable(STAR(ZERO)) == true) +} + +Await.result(f, 120 second) diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/re1b_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/re1b_test.scala Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,16 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + + + +lazy val f = Future { + assert(der('a', ZERO | ONE) == (ZERO | ZERO)) + assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE)) + assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))) + assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))) +} + +Await.result(f, 120 second) diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/re1c_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/re1c_test.scala Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,19 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + + + +lazy val f = Future { + assert(simp(ZERO | ONE) == ONE) + assert(simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)) + assert(simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')) + assert(simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO) + assert(simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')) + assert(simp(CHAR('a') | CHAR('a')) == CHAR('a')) + assert(simp(ONE | CHAR('a')) == (ONE | CHAR('a'))) +} + +Await.result(f, 30 second) diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/re1d_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/re1d_test.scala Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,37 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + + +val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +lazy val f = Future { + println("1") + assert(ders(List.fill(5)('a'), EVIL_urban) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))) + println("2") + assert(ders(List('b'), EVIL_urban) == ONE) + println("3") + assert(ders(List('b','b'), EVIL_urban) == ZERO) + println("4") + assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true) + println("5") + assert(matcher(EVIL_urban, "b") == true) + println("6") + assert(matcher(EVIL_urban, "bb") == false) + println("7") + assert(matcher("abc", "abc") == true) + println("8") + assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true) + println("9") + assert(matcher(ONE, "") == true) + println("10") + assert(matcher(ZERO, "") == false) + println("11") + assert(matcher(ONE | CHAR('a'), "") == true) + println("12") + assert(matcher(ONE | CHAR('a'), "a") == true) +} + +Await.result(f, 90 second) diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/re1e_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/re1e_test.scala Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,14 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + + + +lazy val f = Future { + assert(replace("aa".% | "bb", "aabbbaaaaaaabaaaaabbaaaabb" , "c") == "ccbcabcaccc") + assert(replace("aa".% | "bb", "abba" , "") == "aa") +} + +Await.result(f, 120 second) diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/re2a_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/re2a_test.scala Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,14 @@ +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + + + +lazy val f = Future { + assert(iterT(200000, (x: Int) => x + 1, 0) == 200000) + assert(iterT(100, (x: BigInt) => x * 2, BigInt(2)) == BigInt("2535301200456458802993406410752")) + assert(iterT(10, (x: String) => x ++ "a", "a") == "aaaaaaaaaaa") +} + +Await.result(f, 90 second) diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/re2b_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/re2b_test.scala Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,56 @@ +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + +val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +def nullable_urban (r: Rexp) : Boolean = r match { + case ZERO => false + case ONE => true + case CHAR(_) => false + case ALT(r1, r2) => nullable_urban(r1) || nullable_urban(r2) + case SEQ(r1, r2) => nullable_urban(r1) && nullable_urban(r2) + case STAR(_) => true +} + +def der_urban (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_urban(c, r1), der_urban(c, r2)) + case SEQ(r1, r2) => + if (nullable_urban(r1)) ALT(SEQ(der_urban(c, r1), r2), der_urban(c, r2)) + else SEQ(der_urban(c, r1), r2) + case STAR(r1) => SEQ(der_urban(c, r1), STAR(r1)) +} + +def simp_urban(r: Rexp) : Rexp = r match { + case ALT(r1, r2) => (simp_urban(r1), simp_urban(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_urban(r1), simp_urban(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 +} + +import scala.annotation.tailrec + +@tailrec +def iterT_urban[A](n: Int, f: A => A, x: A): A = + if (n == 0) x else iterT_urban(n - 1, f, f(x)) + + +lazy val f = Future { + assert(size(iterT_urban(20, (r: Rexp) => der_urban('a', r), EVIL_urban)) == 7340068) + assert(size(iterT_urban(20, (r: Rexp) => simp_urban(der_urban('a', r)), EVIL_urban)) == 8) +} + +Await.result(f, 90 second) diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/re2c_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/re2c_test.scala Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,13 @@ +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps + + + +lazy val f = Future { + assert(fixpT((x:Int) => if (200000 < x) x else x + 1, 0) == 200001) + assert(fixpT((x:Long) => if (20 < x) x else x + 1, 0L) == 21L) +} + +Await.result(f, 90 second) diff -r 3db70bdce7a4 -r 8f03f0dc3065 marking/test --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marking/test Wed Jan 11 14:42:46 2017 +0000 @@ -0,0 +1,92 @@ +#!/bin/bash +set -e + +out=${1:-output-test} + + +function scala_vars { + (egrep '\bvar\b|\breturn\b|ListBuffer|mutable' "$1" 2> /dev/null 1> /dev/null) +} + + +# compilation tests + +function scala_compile { + (scala "$1" 2> /dev/null 1> /dev/null) +} + + +# functional tests + +function scala_assert { + (scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + + + +# var, return, ListBuffer test +# +#echo "re.scala does not contain vars, returns etc?" | tee -a $out + +if (scala_vars re.scala) +then + #echo " --> fail" | tee -a $out + tsts0=$(( 1 )) +else + #echo " --> yes" | tee -a $out + tsts0=$(( 0 )) +fi + + +# compilation test +if [ $tsts0 -eq 0 ] +then + #echo "re.scala runs?" | tee -a $out + + if (scala_compile re.scala.bak) + then + #echo " --> yes" | tee -a $out + tsts1=$(( 0 )) + else + #echo " --> scala re.scala did not run successfully" | tee -a $out + tsts1=$(( 1 )) + fi +else + tsts1=$(( 1 )) +fi + + +if [ $tsts1 -eq 0 ] +then + if (scala_assert "re.scala.bak" "../../../marking/re1d_test.scala") + then + echo " --> success" | tee -a $out + t1=$(( 1 )) + else + echo " --> test failed" | tee -a $out + t1=$(( 0 )) + fi +else + t1=$(( 0 )) +fi + +if [ $tsts1 -eq 0 ] +then + if (scala_assert "re.scala.bak" "../../../marking/re1d_bug_test.scala") + then + echo " bug --> success" | tee -a $out + t2=$(( 1 )) + else + echo " bug --> test failed" | tee -a $out + t2=$(( 0 )) + fi +else + t2=$(( 0 )) +fi + +if [ $t1 -ne $t2 ] +then + echo "disagree" + pwd +fi + diff -r 3db70bdce7a4 -r 8f03f0dc3065 progs/lecture2.scala --- a/progs/lecture2.scala Wed Jan 11 14:41:32 2017 +0000 +++ b/progs/lecture2.scala Wed Jan 11 14:42:46 2017 +0000 @@ -348,6 +348,8 @@ // a student showed me... import scala.collection.mutable.ListBuffer + + def collatz_max(bnd: Long): (Long, Long) = { val colNos = ListBuffer[(Long, Long)]() for (i <- (1L to bnd).toList) colNos += ((collatz(i), i)) diff -r 3db70bdce7a4 -r 8f03f0dc3065 progs/re_sol.scala