--- /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
--- 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
Binary file cws/cw03.pdf has changed
--- 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
--- /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)
--- /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
--- /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
--- 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 ..
--- /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)
--- /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)
--- /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)
--- /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)
--- /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)
--- /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)
--- /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)
--- /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)
--- /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
+
--- 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))