--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking2/knight1.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,79 @@
+// Part 1 about finding and counting Knight's tours
+//==================================================
+
+object CW7a {
+
+type Pos = (Int, Int)    // a position on a chessboard 
+type Path = List[Pos]    // a path...a list of positions
+
+def print_board(dim: Int, path: Path): Unit = {
+  println
+  for (i <- 0 until dim) {
+    for (j <- 0 until dim) {
+      print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ")
+    }
+    println
+  } 
+}
+
+def add_pair(x: Pos)(y: Pos): Pos = 
+  (x._1 + y._1, x._2 + y._2)
+
+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)
+
+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 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))
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = 
+  moves(x).filter(is_legal(dim, path))
+
+def count_tours(dim: Int, path: Path): Int = {
+  if (path.length == dim * dim) 1
+  else 
+    (for (x <- legal_moves(dim, path, path.head)) yield count_tours(dim, x::path)).sum
+}
+
+def enum_tours(dim: Int, path: Path): List[Path] = {
+  if (path.length == dim * dim) List(path)
+  else 
+    (for (x <- legal_moves(dim, path, path.head)) yield enum_tours(dim, x::path)).flatten
+}
+
+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
+}
+
+/*
+for (dim <- 1 to 5) {
+  println(s"${dim} x ${dim} " + count_tours(dim, List((0, 0))))
+}
+
+for (dim <- 1 to 5) {
+  println(s"${dim} x ${dim} " + 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)
+  }
+}
+*/ 
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking2/knight2.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,61 @@
+// Part 2 about finding a single tour for a board
+//================================================
+
+object CW7b {
+
+type Pos = (Int, Int)    // a position on a chessboard 
+type Path = List[Pos]    // a path...a list of positions
+
+def print_board(dim: Int, path: Path) : Unit = {
+  println
+  for (i <- 0 until dim) {
+    for (j <- 0 until dim) {
+      print(f"${path.reverse.indexOf((i, j))}%3.0f ")
+    }
+    println
+  } 
+}
+
+def add_pair(x: Pos)(y: Pos) : Pos = 
+  (x._1 + y._1, x._2 + y._2)
+
+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)
+
+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))
+
+def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = 
+  moves(x).filter(is_legal(dim, path))
+
+
+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)
+  }
+}
+
+//first(List((1, 0),(2, 0),(3, 0),(4, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
+//first(List((1, 0),(2, 0),(3, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
+
+def first_tour(dim: Int, path: Path) : Option[Path] = {
+  if (path.length == dim * dim) Some(path)
+  else
+    first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))
+}
+
+/* 
+val ts1 = first_tour(8, List((0, 0))).get
+  assert(correct_urban(8)(ts1) == true)
+
+val ts2 = first_tour(4, List((0, 0)))
+assert(ts2 == None)  
+
+print_board(8, first_tour(8, List((0, 0))).get)
+*/
+
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking2/knight3.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,96 @@
+// Part 3 about finding a single tour using the Warnsdorf Rule
+//=============================================================
+
+object CW7c {
+
+type Pos = (Int, Int)
+type Path = List[Pos]
+
+def print_board(dim: Int, path: Path): Unit = {
+  println
+  for (i <- 0 until dim) {
+    for (j <- 0 until dim) {
+      print(f"${path.reverse.indexOf((i, j))}%3.0f ")
+    }
+    println
+  } 
+}
+
+def add_pair(x: Pos)(y: Pos): Pos = 
+  (x._1 + y._1, x._2 + y._2)
+
+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)
+
+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))
+
+def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = 
+  moves(x).filter(is_legal(dim, path))
+
+def ordered_moves(dim: Int, path: Path, x: Pos): List[Pos] = 
+  legal_moves(dim, path, x).sortBy((x) => legal_moves(dim, path, x).length)
+
+
+import scala.annotation.tailrec
+
+@tailrec
+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)
+  }
+}
+
+
+def first_closed_tour_heuristic(dim: Int, path: Path): Option[Path] = {
+  if (path.length == dim * dim && moves(path.head).contains(path.last)) Some(path)
+  else
+    first(ordered_moves(dim, path, path.head), (x: Pos) => first_closed_tour_heuristic(dim, x::path))
+}
+
+/*
+for (dim <- 1 to 6) {
+  val t = first_closed_tour_heuristic(dim, List((dim / 2, dim / 2)))
+  println(s"${dim} x ${dim} closed: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}*/
+
+
+def first_tour_heuristic(dim: Int, path: Path): Option[Path] = {
+
+  @tailrec
+  def aux(dim: Int, path: Path, moves: List[Pos]): Option[Path] =  
+  if (path.length == dim * dim) Some(path)
+  else
+    moves match {
+      case Nil => None
+      case x::xs => {
+        val r = first_tour_heuristic(dim, x::path)
+        if (r.isDefined) r else aux(dim, path, xs)
+    }
+  }    
+ 
+  aux(dim, path, ordered_moves(dim, path, path.head)) 
+}
+
+/*
+def first_tour_heuristic(dim: Int, path: Path): Option[Path] = {
+  if (path.length == dim * dim) Some(path)
+  else
+    first(ordered_moves(dim, path, path.head), (x: Pos) => first_tour_heuristic(dim, x::path))
+}
+*/
+
+/*
+for (dim <- 1 to 50) {
+  val t = first_tour_heuristic(dim, List((dim / 2, dim / 2)))
+  println(s"${dim} x ${dim}: " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+}
+
+
+//CW7c.first_tour_heuristic(50, List((0,0))).get

--- a/marking2/knight3_test.sh	Mon Jan 15 23:15:34 2018 +0000
+++ b/marking2/knight3_test.sh	Tue Jan 16 10:47:29 2018 +0000
@@ -1,29 +1,35 @@
 #!/bin/bash
-set -e
+
+# to make the script fail safely
+set -euo pipefail
+
 
 out=${1:-output}
 
 echo "" > $out
 
-echo "Below is the feedback for your submission of CW 7, Part 3." >> $out
+echo "Below is the feedback and provisional marks for your submission" >> $out
+echo "for assignment 7 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)
-}
+# marks for CW7 part 2
+marks=$(( 0 ))
 
 # compilation tests
 
 function scala_compile {
-  (ulimit -t 30 ; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) 
+    (ulimit -t 360; JAVA_OPTS="-Xmx1g" scala "$1" 2> /dev/null 1> /dev/null)
 }
 
 # functional tests
 
 function scala_assert {
-    (ulimit -t 20 ; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
+    (ulimit -t 360; JAVA_OPTS="-Xmx4g -Xss200m" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
 }
 
+
 # purity test
 
 function scala_vars {
@@ -33,14 +39,15 @@
 
 # knights3: purity test
 #
-echo "knight3.scala does not contain vars, returns etc?" >> $out
+echo "knight3.scala does not contain vars, returns, Arrays, ListBuffers etc?" | tee -a $out
+
 
 if (scala_vars knight3.scala)
 then
-  echo "  --> fail: if you do not fix this, you will receive a mark of zero" >> $out
+  echo "  --> test failed" | tee -a $out
   tsts0=$(( 1 ))
 else
-  echo "  --> success" >> $out
+  echo "  --> success" | tee -a $out
   tsts0=$(( 0 )) 
 fi
 
@@ -48,14 +55,14 @@
 # compilation test
 if  [ $tsts0 -eq 0 ]
 then    
-  echo "knight3.scala runs?" >> $out
+  echo "knight3.scala runs?" | tee -a $out
 
   if (scala_compile knight3.scala)
   then
-    echo "  --> success" >> $out
+    echo "  --> success" | tee -a $out
     tsts1=$(( 0 ))
   else
-    echo "  --> scala knight3.scala did not run successfully" >> $out
+    echo "  --> scala knight3.scala did not run successfully" | tee -a $out
     tsts1=$(( 1 )) 
   fi
 else
@@ -66,16 +73,16 @@
 
 if [ $tsts1 -eq 0 ]
 then
-  echo "Takes 20 seconds or less to execute: " >> $out
-  echo " ordered_moves(8, List((3,4), (3,2)), (1, 3)) == List((0,1), (0,5), (2,1), (2,5))" >> $out
-  echo " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" >> $out
-  echo " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" >> $out
+  echo " ordered_moves(8, List((3,4), (3,2)), (1,3)) == List((0,1), (0,5), (2,1), (2,5))" | tee -a $out
+  echo " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" | tee -a $out
+  echo " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" | tee -a $out
   
   if (scala_assert "knight3.scala" "knight3a_test.scala")
   then
-    echo "  --> success" >> $out
+      echo "  --> success" | tee -a $out
+      marks=$(( marks + 1 ))
   else
-    echo "  --> test failed" >> $out
+    echo "  --> test failed" | tee -a $out
   fi
 fi
 
@@ -84,13 +91,14 @@
 
 if [ $tsts1 -eq 0 ]
 then
-  echo " first_closed_tour_heuristic(6, List((3, 3))) found and ok?" >> $out
+  echo " first_closed_tour_heuristic(6, List((3,3))) found and correct?" | tee -a $out
   
   if (scala_assert "knight3.scala" "knight3b_test.scala")
   then
-    echo "  --> success" >> $out
+      echo "  --> success" | tee -a $out
+      marks=$(( marks + 1 ))
   else
-    echo "  --> test failed" >> $out
+      echo "  --> test failed" | tee -a $out
   fi
 fi
 
@@ -98,19 +106,19 @@
 
 if [ $tsts1 -eq 0 ]
 then
-  echo "Takes 20 seconds or less to execute: " >> $out
-  echo " first_tour_heuristic(8, List((0,0))) found and ok?" >> $out
-  echo " first_tour_heuristic(40, List((0,0))) found and ok?" >> $out
+  echo " first_tour_heuristic(8, List((0,0))) found and correct?" | tee -a $out
+  echo " first_tour_heuristic(40, List((0,0))) found and correct?" | tee -a $out
   
   if (scala_assert "knight3.scala" "knight3c_test.scala")
   then
-    echo "  --> success" >> $out
+      echo "  --> success" | tee -a $out
+      marks=$(( marks + 1 ))
   else
-    echo "  --> test failed" >> $out
+    echo "  --> test failed" | tee -a $out
   fi
 fi
 
 
 ## final marks
-##echo "Overall mark for CW 7, Part 2" | tee -a $out
-##echo "$marks" | tee -a $out
+echo "Overall mark for CW 7, Part 2" | tee -a $out
+echo "$marks" | tee -a $out

--- a/marking2/knight3a_test.scala	Mon Jan 15 23:15:34 2018 +0000
+++ b/marking2/knight3a_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -1,15 +1,5 @@
 
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps 
-
-//lazy val f = Future {
-
-assert(CW7c.ordered_moves(8, List((3,4), (3,2)), (1, 3)) == List((0,1), (0,5), (2,1), (2,5)))
+assert(CW7c.ordered_moves(8, List((3,4), (3,2)), (1,3)) == List((0,1), (0,5), (2,1), (2,5)))
 assert(CW7c.ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2)))
 assert(CW7c.ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1)))
 
-//}
-
-//Await.result(f, 120 second)

--- a/marking2/knight3c_test.scala	Mon Jan 15 23:15:34 2018 +0000
+++ b/marking2/knight3c_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -4,6 +4,8 @@
 //import ExecutionContext.Implicits.global
 //import scala.language.postfixOps 
 
+println(Runtime.getRuntime.maxMemory)
+
 type Pos = (Int, Int)
 type Path = List[Pos]
 
@@ -27,6 +29,7 @@
     if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
 }
 
+// !!!!!!! the futures need to be removed
 //lazy val f1 = Future {
 
   val ts8 = CW7c.first_tour_heuristic(8, List((0,0))).get

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking2/mk-advanced	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,24 @@
+#!/bin/sh
+###set -e
+
+trap "exit" INT
+
+files=${1:-assignment20177-*}
+
+for sd in $files; do
+  cd $sd
+  echo $sd
+  touch .
+  cp ../../../marking2/knight3_test.sh .
+  cp ../../../marking2/knight3a_test.scala .
+  cp ../../../marking2/knight3b_test.scala .
+  cp ../../../marking2/knight3c_test.scala .
+  ./knight3_test.sh output
+  rm knight3_test.sh
+  rm knight3a_test.scala
+  rm knight3b_test.scala
+  rm knight3c_test.scala
+  cd ..
+done
+
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/-	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,1 @@
+               +++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."""

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/bf.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,462 @@
+// Part 2 about an Interpreter for the Brainf*** language
+//========================================================
+
+object CW8b {
+
+type Mem = Map[Int, Int]
+
+// (2a) Complete the functions for safely reading  
+// and writing brainf*** memory. Safely read should
+// Return the value stored in the Map for a given memory
+// pointer, if it exists; otherwise it Returns 0. The
+// writing function generates a new Map with the
+// same data, except at the given memory pointer the
+// value v is stored.
+
+
+def sread(mem: Mem, mp: Int) : Int = 
+  mem.getOrElse(mp, 0)
+
+def write(mem: Mem, mp: Int, v: Int) : Mem =
+  mem.updated(mp, v)
+
+
+// (2b) Implement the two jumping instructions in the 
+// brainf*** language. In jumpRight, given a program and 
+// a program counter move the program counter to the right 
+// until after the *matching* ]-command. Similarly, 
+// jumpLeft implements the move to the left to just after
+// the *matching* [--command.
+
+def jumpRight(prog: String, pc: Int, level: Int) : Int = {
+  if (prog.length <= pc) pc 
+  else (prog(pc), level) match {
+    case (']', 0) => pc + 1
+    case (']', l) => jumpRight(prog, pc + 1, l - 1)
+    case ('[', l) => jumpRight(prog, pc + 1, l + 1)
+    case (_, l) => jumpRight(prog, pc + 1, l)
+  }
+}
+
+def jumpLeft(prog: String, p: Int, level: Int) : Int = {
+  if (p < 0) p 
+  else (prog(p), level) match {
+    case ('[', 0) => p + 1
+    case ('[', l) => jumpLeft(prog, p - 1, l - 1)
+    case (']', l) => jumpLeft(prog, p - 1, l + 1)
+    case (_, l) => jumpLeft(prog, p - 1, l)
+  }
+}
+
+//jumpLeft("[******]***", 7, 0)
+
+// (2c) Complete the run function that interpretes (runs) a brainf***
+// program: the arguments are a program, a program counter,
+// a memory counter and a brainf*** memory. It Returns the
+// memory at the stage when the excution of the brainf*** program
+// finishes. The interpretation finishes once the program counter
+// pc is pointing to something outside the program string.
+// If the pc points to a character inside the program, the pc, 
+// memory pointer and memory need to be updated according to 
+// rules of the brainf*** language. Then, recursively, run 
+// function continues with the command at the new program
+// counter. 
+// Implement the start function that calls run with the program
+// counter and memory counter set to 0.
+
+def run(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = {
+  if (0 <= pc && pc < prog.length) { 
+    val (new_pc, new_mp, new_mem) = prog(pc) match {
+      case '>' => (pc + 1, mp + 1, mem)
+      case '<' => (pc + 1, mp - 1, mem)
+      case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+      case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+      case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+      case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+      case '['  => 
+	if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) 
+      case ']'  => 
+	if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) 
+      case _ => (pc + 1, mp, mem)
+    }		     
+    run(prog, new_pc, new_mp, new_mem)	
+  }
+  else mem
+}
+
+def start(prog: String, m: Mem) = run(prog, 0, 0, m)
+
+// some sample programs collected from the Internet
+//==================================================
+
+
+/*
+// first some contrived (small) programs
+
+// clears the 0-cell
+start("[-]", Map(0 -> 100)) 
+
+// copies content of the 0-cell to 1-cell
+start("[->+<]", Map(0 -> 10))
+
+// copies content of the 0-cell to 2-cell and 4-cell
+start("[>>+>>+<<<<-]", Map(0 -> 42))
+
+
+// prints out numbers 0 to 9
+start("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""", Map())
+
+
+// some more "useful" programs
+
+// hello world program 1
+start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+       ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map())
+
+// hello world program 2
+start("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+
+      +.<<+++++++++++++++.>.+++.------.--------.>+.>.""", Map())
+
+
+// draws the Sierpinski triangle
+start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+      ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+      ]>.>+[>>]>+]""", Map())
+
+println(start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+      ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+      ]>.>+[>>]>+]""", Map())) 
+
+//fibonacci numbers below 100
+start("""+++++++++++
+      >+>>>>++++++++++++++++++++++++++++++++++++++++++++
+      >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
+      +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
+      <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
+      -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
+      >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
+      +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
+      ++++++++++++++++++++++++++++++++++++++++++++.[-]<<
+      <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
+      [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", Map())
+
+
+//outputs the square numbers up to 10000
+start("""++++[>+++++<-]>[<+++++>-]+<+[
+    >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
+    >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
+    <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""", Map())
+
+//collatz numbers (need to be typed in)
+start(""">,[[----------[
+      >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]
+      ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[
+      <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]
+      >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]
+      >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>
+      ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""", Map())
+
+
+// infinite collatz (never stops)
+start(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[<
+      <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++
+      +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+<
+      [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>->
+      [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[
+      <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+
+      ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<
+      +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<-
+      ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<-
+      >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>
+      -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++
+      +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[<
+      <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++
+      +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-<
+      <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>-
+      [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""", Map())
+
+
+start("""+++++[>+++++++++<-],[[>--.++>+<<-]>+.->[<.>-]<<,]""", Map())
+
+*/ 
+
+/*
+def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match {
+  case (Nil, acc) => acc
+  case (c :: cs, Nil) => splice(cs, List((c, 1)))
+  case (c :: cs, (d, n) :: acc) => 
+    if (c == d) splice(cs, (c, n + 1) :: acc)
+    else splice(cs, (c, 1) :: (d, n) :: acc)
+}
+
+def spl(s: String) = splice(s.toList, Nil).reverse
+
+
+// simple instructions
+def instr(c: Char) : String = c match {
+  case '>' => "ptr++;"
+  case '<' => "ptr--;"
+  case '+' => "(*ptr)++;"
+  case '-' => "(*ptr)--;"
+  case '.' => "putchar(*ptr);"
+  case ',' => "*ptr = getchar();\n"
+  case '['  => "while(*ptr){"
+  case ']'  => "}"
+  case _ => ""
+}
+
+def instrs(prog: String) : String =
+  prog.toList.map(instr(_)).mkString
+
+
+//optimised instructions
+
+def instr2(c: Char, n: Int) : String = c match {
+  case '>' => "ptr += " + n.toString + ";"
+  case '<' => "ptr -= " + n.toString + ";"
+  case '+' => "(*ptr) += " + n.toString + ";"
+  case '-' => "(*ptr) -= " + n.toString + ";"
+  case '.' => "putchar(*ptr);" * n
+  case ',' => "*ptr = getchar();\n" * n
+  case '['  => "while(*ptr){" * n
+  case ']'  => "}" * n
+  case _ => ""
+}
+
+def instrs2(prog: String) : String =
+  spl(prog).map{ case (c, n) => instr2(c, n) }.mkString
+
+
+// peephole optimisers are at
+// https://github.com/Wilfred/bfc#peephole-optimisations
+// http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html
+
+def compile_str(prog: String) : String = {
+  "#include <string.h>\n" ++
+  "#include <stdio.h>\n" ++
+  "char field[30000];\n" ++
+  "char *ptr = &field[15000];" ++
+  "int main()\n{\n" ++
+  "memset(field, '\\0', 30000);\n" ++
+  instrs2(prog) ++
+  "\n re turn 0;\n}"
+}
+
+def compile(name: String, prog: String) = {
+  val fw = new java.io.FileWriter(name + ".c") 
+  fw.write(compile_str(prog)) 
+  fw.close()
+}
+
+import sys.process._
+
+def compile_run(prog: String) = {
+  compile("tmp", prog)
+  "gcc -O3 -o tmp tmp.c".!
+  "./tmp".!
+  ()
+}
+
+
+compile_run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+       ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
+
+compile_run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+      ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+      ]>.>+[>>]>+]""")
+
+compile_run("""      A mandelbrot set fractal viewer in brainf*** written by Erik Bosman
++++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+
+<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>>
+>+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>>
+>>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>>
+>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>>
+>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>
+[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<
+<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[
+>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[
+-<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<
+<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<
+[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>
+>>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+
+<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>
+>>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<
++>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<
+<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<
+<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->
+>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<
+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++
++++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>-
+<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>>
+[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<<
+<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[-
+]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<<
+<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]<
+<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>>
+>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>>
+[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-<
+<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>>
+]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++
++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+
+>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[
+-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-<
+<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<<
+[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]
++>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<
+[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<
+<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<
+<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<<
+<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<<
+<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<<
+]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<<
+[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<<
++>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<<
+<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<
+<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[
+[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>
+[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<
+<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[
+>[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[
+>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>
+>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<
+<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<
+<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-
+<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>
+>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>>
+[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<<
++>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]>
+[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>
+>>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>>
+>>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<<
+]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<<
+<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>
+>]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<<
+<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<
+<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]<
+<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<
+<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+
+<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<<
+]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+>
+>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[
+->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>>
+>>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<
+<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+
+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>>
+]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>
+>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<
+<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>>
+>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+
+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>
+>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<]
+>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<<
+]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+<
+<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>
+>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<<
+->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[
+>[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<<
+[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<<
+<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<<
+<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<<
+<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>>
+>+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<
+<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]<
++<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>>
+>>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<
+<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<<
+<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<<
+<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-<
+<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<<
+<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<
+<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<<
+<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>>
+>+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<<
+<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>>
+>]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<<
+<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>>
+>>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<-
+>>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<
+<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>>
+>>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<
+<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>
++>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+<
+<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<<
+<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>
+-<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>
+>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++
++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<<
+<<<<<]]>>>]""")
+
+compile_run("""
+>+>+>+>+>++<[>[<+++>-
+
+  >>>>>
+  >+>+>+>+>++<[>[<+++>-
+
+    >>>>>
+    >+>+>+>+>++<[>[<+++>-
+
+      >>>>>
+      >+>+>+>+>++<[>[<+++>-
+
+        >>>>>
+        +++[->+++++<]>[-]<
+        <<<<<
+
+      ]<<]>[-]
+      <<<<<
+
+    ]<<]>[-]
+    <<<<<
+
+  ]<<]>[-]
+  <<<<<
+
+]<<]>.""")
+
+// benchmarks
+compile_run(""">++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
+[>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
+++++++++[>++++++++++[>++++++++++[>++++++++++[>+
++++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""")
+
+//
+compile_run("""++++[>++++<-]>[>+>++>[+++++++>]+++[<]>-]>>>>>>>>-.
+<<<<.<..+++.<.>>>>.<<<.+++.------.>-.<<+.<------.""")
+
+compile_run("""++++++++[->-[->-[->-[-]<]<]<]
+>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>""")
+
+
+
+
+// register to BF compiler
+// https://gergo.erdi.hu/blog/2010-09-06-from_register_machines_to_brainfuck,_part_1/
+
+*/
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/bf1a_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,17 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps 
+//import scala.language.reflectiveCalls
+
+//lazy val f = Future {
+  import CW8b._
+
+  assert(sread(Map(), 2) == 0)
+  assert(sread(Map(2 -> 1), 2) == 1)
+  assert(write(Map(), 1, 2) == Map(1 -> 2))
+  assert(write(Map(1 -> 0), 1, 2) == Map(1 -> 2))
+//}
+
+//Await.result(f, 120 second)

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/bf1b_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,21 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps 
+//import scala.language.reflectiveCalls
+
+//lazy val f = Future {
+  import CW8b._
+
+  assert(jumpRight("[******]***", 1, 0) == 8)
+  assert(jumpRight("[**[*]*]***", 1, 0) == 8)
+  assert(jumpRight("[**[*]*]***", 1, 0) == 8)  
+  assert(jumpRight("[**[***]***", 1, 0) == 11)
+  assert(jumpRight("[*[][]*]***", 1, 0) == 8)
+  assert(jumpLeft("[******]***", 6, 0) == 1)
+  assert(jumpLeft("[******]***", 7, 0) == -1)
+  assert(jumpLeft("[*[][]*]***", 6, 0) == 1)
+//}
+
+//Await.result(f, 120 second)

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/bf1c_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,9 @@
+
+import CW8b._
+
+assert(start("[-]", Map(0 -> 100)) == Map(0 -> 0))
+assert(start("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10))
+assert(start("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42))
+assert(start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]
+	     <-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map()) == Map(0 -> 0, 5 -> 33, 1 -> 0, 6 -> 10, 2 -> 72, 3 -> 100, 4 -> 87))
+assert(start("+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]", Map()) == Map(0 -> 0, 1 -> 58, 2 -> 32))

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/bf_test.sh	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,140 @@
+#!/bin/bash
+
+# to make the script fail safely
+set -euo pipefail
+
+
+out=${1:-output}
+
+echo "" > $out
+
+
+echo "Below is the feedback and provisional marks for your submission" >> $out
+echo "for assignment 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
+
+# marks for CW8 part 2
+marks=$(( 0 ))
+
+# compilation tests
+
+function scala_compile {
+    (ulimit -t 360; JAVA_OPTS="-Xmx1g" scala "$1" 2> /dev/null 1> /dev/null)
+}
+
+# functional tests
+
+function scala_assert {
+    (ulimit -t 360; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
+}
+
+
+# purity test
+
+function scala_vars {
+   (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null)
+}
+
+
+
+# var, return, ListBuffer test
+#
+echo "bf.scala does not contain vars, returns, Arrays, ListBuffers etc?" | tee -a $out
+
+if (scala_vars bf.scala)
+then
+  echo "  --> test failed" | tee -a $out
+  tsts0=$(( 1 ))
+else
+  echo "  --> success" | tee -a $out
+  tsts0=$(( 0 )) 
+fi
+
+
+# compilation test
+if  [ $tsts0 -eq 0 ]
+then    
+  echo "bf.scala runs?" | tee -a $out
+
+  if (scala_compile bf.scala)
+  then
+    echo "  --> success" | tee -a $out
+    tsts1=$(( 0 ))
+  else
+    echo "  --> scala bf.scala did not run successfully" | tee -a $out
+    tsts1=$(( 1 )) 
+  fi
+else
+  tsts1=$(( 1 ))     
+fi
+
+
+
+if [ $tsts1 -eq 0 ]
+then
+  echo " sread(Map(), 2) == 0" | tee -a $out
+  echo " sread(Map(2 -> 1), 2) == 1" | tee -a $out  
+  echo " write(Map(), 1, 2) == Map(1 -> 2)" | tee -a $out
+  echo " write(Map(1 -> 0), 1, 2) == Map(1 -> 2)" | tee -a $out
+  
+  if (scala_assert "bf.scala" "bf1a_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 " jumpRight(\"[******]***\", 1, 0) == 8" | tee -a $out
+    echo " jumpRight(\"[**[*]*]***\", 1, 0) == 8" | tee -a $out
+    echo " jumpRight(\"[**[*]*]***\", 1, 0) == 8" | tee -a $out
+    echo " jumpRight(\"[**[***]***\", 1, 0) == 11" | tee -a $out
+    echo " jumpRight(\"[*[][]*]***\", 1, 0) == 8" | tee -a $out
+    echo " jumpLeft(\"[******]***\", 6, 0) == 1" | tee -a $out
+    echo " jumpLeft(\"[******]***\", 7, 0) == -1" | tee -a $out
+    echo " jumpLeft(\"[*[][]*]***\", 6, 0) == 1" | tee -a $out
+  
+  if (scala_assert "bf.scala" "bf1b_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 " start(\"[-]\", Map(0 -> 100)) == Map(0 -> 0)" | tee -a $out
+  echo " start(\"[->+<]\", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)" | tee -a $out
+  echo " start(\"[>>+>>+<<<<-]\", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)" | tee -a $out
+  echo " val hello = \"\"\"++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---." | tee -a $out
+  echo "               +++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.\"\"\"" | tee -a $out
+  echo " start(hello, Map()) == " | tee -a $out
+  echo "       Map(0 -> 0, 5 -> 33, 1 -> 0, 6 -> 10, 2 -> 72, 3 -> 100, 4 -> 87)" | tee -a $out
+  echo " start(\"+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]\", Map()) == " | tee -a $out
+  echo "       Map(0 -> 0, 1 -> 58, 2 -> 32)" | tee -a $out
+  
+  if (scala_assert "bf.scala" "bf1c_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 2" | tee -a $out
+echo "$marks" | tee -a $out
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/mk	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,28 @@
+#!/bin/sh
+###set -e
+
+trap "exit" INT
+
+files=${1:-assignment20178-*}
+
+for sd in $files; do
+  cd $sd
+  echo $sd
+  touch .
+  cp ../../../marking3/re_test.sh .
+  cp ../../../marking3/re1a_test.scala .
+  cp ../../../marking3/re1b_test.scala .
+  cp ../../../marking3/re1c_test.scala .
+  cp ../../../marking3/re1d_test.scala .
+  cp ../../../marking3/re1e_test.scala .
+  ./re_test.sh output
+  rm re_test.sh
+  rm re1a_test.scala
+  rm re1b_test.scala
+  rm re1c_test.scala
+  rm re1d_test.scala
+  rm re1e_test.scala
+  cd ..
+done
+
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/mk-advanced	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,24 @@
+#!/bin/sh
+###set -e
+
+trap "exit" INT
+
+files=${1:-assignment20178-*}
+
+for sd in $files; do
+  cd $sd
+  echo $sd
+  touch .
+  cp ../../../marking3/bf_test.sh .
+  cp ../../../marking3/bf1a_test.scala .
+  cp ../../../marking3/bf1b_test.scala .
+  cp ../../../marking3/bf1c_test.scala .
+  ./bf_test.sh output
+  rm bf_test.sh
+  rm bf1a_test.scala
+  rm bf1b_test.scala
+  rm bf1c_test.scala
+  cd ..
+done
+
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/re.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,159 @@
+// Part 1 about Regular Expression Matching
+//==========================================
+
+object CW8a {
+
+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 
+
+// some convenience for typing in regular expressions
+
+import scala.language.implicitConversions    
+import scala.language.reflectiveCalls 
+
+
+def charlist2rexp(s: List[Char]): Rexp = s match {
+  case Nil => ONE
+  case c::Nil => CHAR(c)
+  case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+
+implicit def RexpOps (r: Rexp) = new {
+  def | (s: Rexp) = ALT(r, s)
+  def % = STAR(r)
+  def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps (s: String) = new {
+  def | (r: Rexp) = ALT(s, r)
+  def | (r: String) = ALT(s, r)
+  def % = STAR(s)
+  def ~ (r: Rexp) = SEQ(s, r)
+  def ~ (r: String) = SEQ(s, r)
+}
+
+// (1a) Complete the function nullable according to
+// the definition given in the coursework; this 
+// function checks whether a regular expression
+// can match the empty string
+
+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 STAR(_) => true
+}
+
+// (1b) Complete the function der according to
+// the definition given in the coursework; this
+// function calculates the derivative of a 
+// regular expression w.r.t. a character
+
+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))
+}
+
+// (1c) Complete the function der according to
+// the specification given in the coursework; this
+// function simplifies a regular expression;
+// 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
+}
+
+// (1d) 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
+
+def ders (s: List[Char], r: Rexp) : Rexp = s match {
+  case Nil => r
+  case c::s => ders(s, simp(der(c, r)))
+}
+
+// main matcher function
+def matcher(r: Rexp, s: String): Boolean = nullable(ders(s.toList, r))
+
+// (1e) Complete the size function for regular
+// expressions  according to the specification 
+// given in the coursework.
+
+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)
+}
+
+
+
+// some testing data
+/*
+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'))
+
+matcher(EVIL, "a" * 1000 ++ "b")   // => true
+matcher(EVIL, "a" * 1000)          // => false
+
+// size without simplifications
+size(der('a', der('a', EVIL)))             // => 28
+size(der('a', der('a', der('a', EVIL))))   // => 58
+
+// size with simplification
+size(simp(der('a', der('a', EVIL))))           // => 8
+size(simp(der('a', der('a', der('a', EVIL))))) // => 8
+
+// Java needs around 30 seconds for matching 28 a's with EVIL. 
+//
+// Lets see how long it takes to match strings with 
+// 0.5 Million a's...it should be in the range of some
+// seconds.
+
+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)
+}
+
+for (i <- 0 to 5000000 by 500000) {
+  println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))))
+}
+*/
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/re1a_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,11 @@
+import CW8a._
+
+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)
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/re1b_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,8 @@
+
+import CW8a._
+
+assert(der('a', ZERO | ONE) == (ZERO | ZERO))
+assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE))
+assert(der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a'))
+assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a'))))
+assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a'))))

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/re1c_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,19 @@
+
+import CW8a._
+
+
+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(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a'))
+assert(simp(ONE | CHAR('a')) == (ONE | CHAR('a')))
+assert(simp(ALT((CHAR('a') | ZERO) ~ ONE,
+                  ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a'))
+assert(simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO)
+assert(simp(ALT(ONE | ONE, ONE | ONE)) == ONE)
+assert(simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a'))
+assert(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE)
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/re1d_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,19 @@
+
+import CW8a._
+
+val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+assert(ders(("a" * 5).toList, EVIL_urban) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b')))
+assert(ders(List('b'), EVIL_urban) == ONE)
+assert(ders(List('b','b'), EVIL_urban) == ZERO)
+assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true)
+assert(matcher(EVIL_urban, "a" * 500 ++ "b") == true)
+assert(matcher(EVIL_urban, "a" * 500) == false)
+assert(matcher(EVIL_urban, "b") == true)
+assert(matcher(EVIL_urban, "bb") == false)
+assert(matcher("abc", "abc") == true)
+assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true)
+assert(matcher(ONE, "") == true)
+assert(matcher(ZERO, "") == false)
+assert(matcher(ONE | CHAR('a'), "") == true)
+assert(matcher(ONE | CHAR('a'), "a") == true)

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/re1e_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,10 @@
+
+import CW8a._
+
+val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+assert(size(der('a', der('a', EVIL_urban))) == 28)
+assert(size(der('a', der('a', der('a', EVIL_urban)))) == 58)
+
+assert(size(ders("aaaaaa".toList, EVIL_urban)) == 8)
+assert(size(ders(("a" * 50).toList, EVIL_urban)) == 8)

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking3/re_test.sh	Tue Jan 16 10:47:29 2018 +0000
@@ -0,0 +1,194 @@
+#!/bin/bash
+
+# to make the script fail safely
+set -euo pipefail
+
+out=${1:-output}
+
+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 "ratified by the assessment board -- this is not an official" >> $out
+echo "results transcript." >> $out
+echo "" >> $out
+
+# marks for CW8 part 1
+marks=$(( 0 ))
+
+# compilation tests
+
+function scala_compile {
+    (ulimit -t 360; JAVA_OPTS="-Xmx1g" scala "$1" 2> /dev/null 1> /dev/null)
+}
+
+# functional tests
+
+function scala_assert {
+    (ulimit -t 360; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
+}
+
+# purity test
+
+function scala_vars {
+   (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null)
+}
+
+
+# var, return, ListBuffer test
+#
+echo "re.scala does not contain vars, returns, Arrays, ListBuffers etc?" | tee -a $out
+
+if (scala_vars re.scala)
+then
+  echo "  --> test failed" | tee -a $out
+  tsts0=$(( 1 ))
+else
+  echo "  --> success" | 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)
+  then
+    echo "  --> success" | 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" "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', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a')" | 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" "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(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a')" | tee -a $out
+  echo " simp(ONE | CHAR('a')) == (ONE | CHAR('a'))" | tee -a $out
+  echo " simp(ALT((CHAR('a') | ZERO) ~ ONE," | tee -a $out
+  echo "          ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a')" | tee -a $out
+  echo " simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO" | tee -a $out
+  echo " simp(ALT(ONE | ONE, ONE | ONE)) == ONE" | tee -a $out
+  echo " simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')" | tee -a $out
+  echo " simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE" | tee -a $out
+  echo "    the Iterator produces the rexp" | tee -a $out
+  echo "" | tee -a $out
+  echo "      SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)" | tee -a $out
+  echo "" | tee -a $out
+  echo "    where SEQ is nested 50 times." | tee -a $out
+  if (scala_assert "re.scala" "re1c_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 " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" | tee -a $out
+  echo " ders((\"a\" * 5).toList,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, \"a\" * 50 ++ \"b\") == true" | tee -a $out
+  echo " matcher(EVIL, \"a\" * 50) == false" | 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" "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 " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" | tee -a $out  
+  echo " size(der('a', der('a', EVIL))) == 28" | tee -a $out
+  echo " size(der('a', der('a', der('a', EVIL)))) == 58" | tee -a $out
+  echo " size(ders(\"aaaaaa\".toList, EVIL)) == 8" | tee -a $out
+  echo " size(ders((\"a\" * 50).toList, EVIL)) == 8" | tee -a $out
+  
+  if (scala_assert "re.scala" "re1e_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 1" | tee -a $out
+echo "$marks" | tee -a $out
+
+

--- a/testing2/knight3_test.sh	Mon Jan 15 23:15:34 2018 +0000
+++ b/testing2/knight3_test.sh	Tue Jan 16 10:47:29 2018 +0000
@@ -20,8 +20,10 @@
 
 # functional tests
 
+# not sure yet what the right kind of stack should be
+
 function scala_assert {
-    (ulimit -t 20 ; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
+    (ulimit -t 20 ; JAVA_OPTS="-Xmx1g -Xss200m" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
 }
 
 # purity test

--- a/testing2/knight3c_test.scala	Mon Jan 15 23:15:34 2018 +0000
+++ b/testing2/knight3c_test.scala	Tue Jan 16 10:47:29 2018 +0000
@@ -27,6 +27,8 @@
     if (legal_moves_urban(dim, p, y).contains(x)) correct_urban(dim)(y::p) else false
 }
 
+
+// !!!!!!! the futures need to be removed...otherwise funny results
 //lazy val f1 = Future {
 
   val ts8 = CW7c.first_tour_heuristic(8, List((0,0))).get