# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1542333963 0
# Node ID 9b45dd24271b6199e44a73e72fb42758432e6c4f
# Parent  eb188f9ac0382a766fb4e6d220d81c905cc0a17c
updated

diff -r eb188f9ac038 -r 9b45dd24271b progs/lecture2.scala
--- a/progs/lecture2.scala	Thu Nov 15 14:23:55 2018 +0000
+++ b/progs/lecture2.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -1,11 +1,216 @@
 // Scala Lecture 2
 //=================
 
+// UNFINISHED BUSINESS from Lecture 1
+//====================================
+
+
+// for measuring time
+def time_needed[T](n: Int, code: => T) = {
+  val start = System.nanoTime()
+  for (i <- (0 to n)) code
+  val end = System.nanoTime()
+  (end - start) / 1.0e9
+}
+
+
+val list = (1 to 1000000).toList
+time_needed(10, for (n <- list) yield n + 42)
+time_needed(10, for (n <- list.par) yield n + 42)
+
+
+// Just for "Fun": Mutable vs Immutable
+//=======================================
+//
+// - no vars, no ++i, no +=
+// - no mutable data-structures (no Arrays, no ListBuffers)
+
+
+// Q: Count how many elements are in the intersections of two sets?
+
+def count_intersection(A: Set[Int], B: Set[Int]) : Int = {
+  var count = 0
+  for (x <- A; if B contains x) count += 1 
+  count
+}
+
+val A = (1 to 1000).toSet
+val B = (1 to 1000 by 4).toSet
+
+count_intersection(A, B)
+
+// but do not try to add .par to the for-loop above
+
+
+//propper parallel version
+def count_intersection2(A: Set[Int], B: Set[Int]) : Int = 
+  A.par.count(x => B contains x)
+
+count_intersection2(A, B)
+
+
+val A = (1 to 1000000).toSet
+val B = (1 to 1000000 by 4).toSet
+
+time_needed(100, count_intersection(A, B))
+time_needed(100, count_intersection2(A, B))
+
+
+
+// For-Comprehensions Again
+//==========================
+
+// the first produces a result, while the second does not
+for (n <- List(1, 2, 3, 4, 5)) yield n * n
+
+
+for (n <- List(1, 2, 3, 4, 5)) println(n)
+
+
+
+// Higher-Order Functions
+//========================
+
+// functions can take functions as arguments
+
+def even(x: Int) : Boolean = x % 2 == 0
+def odd(x: Int) : Boolean = x % 2 == 1
+
+val lst = (1 to 10).toList
+
+lst.filter(x => even(x))
+lst.filter(even(_))
+lst.filter(even)
+
+lst.count(even)
+
+lst.find(_ > 8)
+
+
+val ps = List((3, 0), (3, 2), (4, 2), (2, 0), (1, 1), (1, 0))
+
+ps.sortBy(_._1)
+ps.sortBy(_._2)
+
+ps.maxBy(_._1)
+ps.maxBy(_._2)
+
+
+
+// maps
+//=====
+
+def square(x: Int): Int = x * x
+
+val lst = (1 to 10).toList
+
+lst.map(square)
+
+// this is actually what for is defined at in Scala
+
+lst.map(n => square(n))
+for (n <- lst) yield square(n)
+
+// this can be iterated
+
+lst.map(square).filter(_ > 4)
+
+lst.map(square).filter(_ > 4).map(square)
+
+
+// lets define our own functions
+// type of functions, for example f: Int => Int
+
+def my_map_int(lst: List[Int], f: Int => Int) : List[Int] = {
+  if (lst == Nil) Nil
+  else f(lst.head) :: my_map_int(lst.tail, f)
+}
+
+my_map_int(lst, square)
+
+
+// same function using pattern matching: a kind
+// of switch statement on steroids (see more later on)
+
+def my_map_int(lst: List[Int], f: Int => Int) : List[Int] = lst match {
+  case Nil => Nil
+  case x::xs => f(x)::my_map_int(xs, f)
+}
+
+
+// other function types
+//
+// f1: (Int, Int) => Int
+// f2: List[String] => Option[Int]
+// ... 
+
+
+def sumOf(f: Int => Int, lst: List[Int]): Int = lst match {
+  case Nil => 0
+  case x::xs => f(x) + sumOf(f, xs)
+}
+
+def sum_squares(lst: List[Int]) = sumOf(square, lst)
+def sum_cubes(lst: List[Int])   = sumOf(x => x * x * x, lst)
+
+sum_squares(lst)
+sum_cubes(lst)
+
+// lets try it factorial
+def fact(n: Int) : Int = ...
+
+def sum_fact(lst: List[Int]) = sumOf(fact, lst)
+sum_fact(lst)
+
+
+
+
+
+// Map type
+//==========
+
+// Note the difference between map and Map
+
+def factors(n: Int) : List[Int] =
+  ((1 until n).filter { divisor =>
+      n % divisor == 0
+    }).toList
+
+
+var ls = (1 to 10).toList
+
+val facs = ls.map(n => (n, factors(n)))
+
+facs.find(_._1 == 4)
+
+// works for lists of pairs
+facs.toMap
+
+
+facs.toMap.get(4)
+facs.toMap.getOrElse(4, Nil)
+
+val facsMap = facs.toMap
+
+val facsMap0 = facsMap + (0 -> List(1,2,3,4,5))
+facsMap0.get(0)
+
+val facsMap4 = facsMap + (1 -> List(1,2,3,4,5))
+facsMap.get(1)
+facsMap4.get(1)
+
+val ls = List("one", "two", "three", "four", "five")
+ls.groupBy(_.length)
+
+ls.groupBy(_.length).get(3)
+
+
 
 // Option type
 //=============
 
 //in Java if something unusually happens, you return null;
+//
 //in Scala you use Option
 //   - if the value is present, you use Some(value)
 //   - if no value is present, you use None
@@ -14,16 +219,7 @@
 List(7,2,3,4,5,6).find(_ < 4)
 List(5,6,7,8,9).find(_ < 4)
 
-
-// Values in types
-//
-// Boolean: 
-// Int: 
-// String: 
-//
-// Option[String]:
-//   
-
+// operations on options
 
 val lst = List(None, Some(1), Some(2), None, Some(3))
 
@@ -43,6 +239,7 @@
 // getOrElse is for setting a default value
 
 val lst = List(None, Some(1), Some(2), None, Some(3))
+
 for (x <- lst) yield x.getOrElse(0)
 
 
@@ -61,17 +258,24 @@
 
 Try(Some(Source.fromURL("""http://www.inf.kcl.ac.uk/staff/urbanc/""").mkString)).getOrElse(None)
 
-// a function that turns strings into numbers
-Integer.parseInt("12u34")
 
-def get_me_an_int(s: String): Option[Int] = 
+// a function that turns strings into numbers (similar to .toInt)
+Integer.parseInt("1234")
+
+
+def get_me_an_int(s: String) : Option[Int] = 
  Try(Some(Integer.parseInt(s))).getOrElse(None)
 
-val lst = List("12345", "foo", "5432", "bar", "x21")
+val lst = List("12345", "foo", "5432", "bar", "x21", "456")
 for (x <- lst) yield get_me_an_int(x)
 
 // summing all the numbers
-val sum = lst.flatMap(get_me_an_int(_)).sum
+
+lst.map(get_me_an_int)
+lst.map(get_me_an_int).flatten.sum
+
+
+val sum = lst.flatMap(get_me_an_int).sum
 
 
 // This may not look any better than working with null in Java, but to
@@ -89,64 +293,8 @@
 // even Scala is not immune to problems like this:
 
 List(5,6,7,8,9).indexOf(7)
-
-
-
-
-
-// Type abbreviations
-//====================
-
-// some syntactic convenience
-type Pos = (int, Int)
-
-type Board = List[List[Int]]
-
-
-
-// Implicits
-//===========
-//
-// for example adding your own methods to Strings:
-// imagine you want to increment strings, like
-//
-//     "HAL".increment
-//
-// you can avoid ugly fudges, like a MyString, by
-// using implicit conversions
-
+List(5,6,7,8,9).indexOf(10)
 
-implicit class MyString(s: String) {
-  def increment = for (c <- s) yield (c + 1).toChar 
-}
-
-"HAL".increment
-
-
-// No return in Scala
-//====================
-
-//You should not use "return" in Scala:
-//
-// A return expression, when evaluated, abandons the 
-// current computation and returns to the caller of the 
-// function in which return appears."
-
-def sq1(x: Int): Int = x * x
-def sq2(x: Int): Int = return x * x
-
-def sumq(ls: List[Int]): Int = {
-  (for (x <- ls) yield (return x * x)).sum[Int]
-}
-
-sumq(List(1,2,3,4))
-
-
-// last expression in a function is the return statement
-def square(x: Int): Int = {
-  println(s"The argument is ${x}.")
-  x * x
-}
 
 
 
@@ -169,7 +317,7 @@
 
 
 
-// remember
+// remember?
 val lst = List(None, Some(1), Some(2), None, Some(3)).flatten
 
 
@@ -178,6 +326,7 @@
 }
 
 
+
 def my_flatten(lst: List[Option[Int]]): List[Int] = lst match {
   case Nil => Nil
   case None::xs => my_flatten(xs)
@@ -200,7 +349,8 @@
   case "March" | "April" | "May" => "It's spring"
   case "June" | "July" | "August" => "It's summer"
   case "September" | "October" | "November" => "It's autumn"
-  case "December" | "January" | "February" => "It's winter"
+  case "December" => "It's winter"
+  case "January" | "February" => "It's unfortunately winter"
 }
  
 println(season("November"))
@@ -209,7 +359,7 @@
 
 println(season("foobar"))
 
-// fizz buzz
+// Silly: fizz buzz
 def fizz_buzz(n: Int) : String = (n % 3, n % 5) match {
   case (0, 0) => "fizz buzz"
   case (0, _) => "fizz"
@@ -224,162 +374,177 @@
 // User-defined Datatypes
 //========================
 
-abstract class Tree
-case class Node(elem: Int, left: Tree, right: Tree) extends Tree
-case class Leaf() extends Tree
 
+abstract class Colour
+case object Red extends Colour 
+case object Green extends Colour 
+case object Blue extends Colour
 
-def insert(tr: Tree, n: Int): Tree = tr match {
-  case Leaf() => Node(n, Leaf(), Leaf())
-  case Node(m, left, right) => 
-    if (n == m) Node(m, left, right) 
-    else if (n < m) Node(m, insert(left, n), right)
-    else Node(m, left, insert(right, n))
+def fav_colour(c: Colour) : Boolean = c match {
+  case Red   => false
+  case Green => true
+  case Blue  => false 
 }
 
+fav_colour(Green)
+
 
-val t1 = Node(4, Node(2, Leaf(), Leaf()), Node(7, Leaf(), Leaf()))
-insert(t1, 3)
+// ... a bit more useful: Roman Numerals
+
+abstract class RomanDigit 
+case object I extends RomanDigit 
+case object V extends RomanDigit 
+case object X extends RomanDigit 
+case object L extends RomanDigit 
+case object C extends RomanDigit 
+case object D extends RomanDigit 
+case object M extends RomanDigit 
+
+type RomanNumeral = List[RomanDigit] 
 
-def depth(tr: Tree): Int = tr match {
-  case Leaf() => 0
-  case Node(_, left, right) => 1 + List(depth(left), depth(right)).max
+def RomanNumeral2Int(rs: RomanNumeral): Int = rs match { 
+  case Nil => 0
+  case M::r    => 1000 + RomanNumeral2Int(r)  
+  case C::M::r => 900 + RomanNumeral2Int(r)
+  case D::r    => 500 + RomanNumeral2Int(r)
+  case C::D::r => 400 + RomanNumeral2Int(r)
+  case C::r    => 100 + RomanNumeral2Int(r)
+  case X::C::r => 90 + RomanNumeral2Int(r)
+  case L::r    => 50 + RomanNumeral2Int(r)
+  case X::L::r => 40 + RomanNumeral2Int(r)
+  case X::r    => 10 + RomanNumeral2Int(r)
+  case I::X::r => 9 + RomanNumeral2Int(r)
+  case V::r    => 5 + RomanNumeral2Int(r)
+  case I::V::r => 4 + RomanNumeral2Int(r)
+  case I::r    => 1 + RomanNumeral2Int(r)
 }
 
+RomanNumeral2Int(List(I,V))             // 4
+RomanNumeral2Int(List(I,I,I,I))         // 4 (invalid Roman number)
+RomanNumeral2Int(List(V,I))             // 6
+RomanNumeral2Int(List(I,X))             // 9
+RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979
+RomanNumeral2Int(List(M,M,X,V,I,I))     // 2017
+
 
-def balance(tr: Tree): Int = tr match {
-  case Leaf() => 0
-  case Node(_, left, right) => depth(left) - depth(right)
-}
+// another example
+//=================
 
-balance(insert(t1, 3))
+// Once upon a time, in a complete fictional country there were Persons...
 
-// another example
 
 abstract class Person
-case class King() extends Person
+case object King extends Person
 case class Peer(deg: String, terr: String, succ: Int) extends Person
 case class Knight(name: String) extends Person
 case class Peasant(name: String) extends Person
-case class Clown() extends Person
+case object Clown extends Person
 
 def title(p: Person): String = p match {
-  case King() => "His Majesty the King"
+  case King => "His Majesty the King"
   case Peer(deg, terr, _) => s"The ${deg} of ${terr}"
   case Knight(name) => s"Sir ${name}"
   case Peasant(name) => name
 }
 
 def superior(p1: Person, p2: Person): Boolean = (p1, p2) match {
-  case (King(), _) => true
+  case (King, _) => true
   case (Peer(_,_,_), Knight(_)) => true
   case (Peer(_,_,_), Peasant(_)) => true
-  case (Peer(_,_,_), Clown()) => true
+  case (Peer(_,_,_), Clown) => true
   case (Knight(_), Peasant(_)) => true
-  case (Knight(_), Clown()) => true
-  case (Clown(), Peasant(_)) => true
+  case (Knight(_), Clown) => true
+  case (Clown, Peasant(_)) => true
   case _ => false
 }
 
 val people = List(Knight("David"), 
                   Peer("Duke", "Norfolk", 84), 
                   Peasant("Christian"), 
-                  King(), 
-                  Clown())
+                  King, 
+                  Clown)
 
 println(people.sortWith(superior(_, _)).mkString(", "))
 
 
-
-// Higher-Order Functions
-//========================
-
-// functions can take functions as arguments
-
-val lst = (1 to 10).toList
-
-def even(x: Int): Boolean = x % 2 == 0
-def odd(x: Int): Boolean = x % 2 == 1
-
-lst.filter(x => even(x))
-lst.filter(even(_))
-lst.filter(even)
-
-lst.find(_ > 8)
-
-def square(x: Int): Int = x * x
-
-lst.map(square)
-
-lst.map(square).filter(_ > 4)
-
-lst.map(square).filter(_ > 4).map(square)
-
-// in my collatz.scala
-//(1 to bnd).map(i => (collatz(i), i)).maxBy(_._1)
+// Tail recursion
+//================
 
 
-// type of functions, for example f: Int => Int
-
-def my_map_int(lst: List[Int], f: Int => Int): List[Int] = lst match {
-  case Nil => Nil
-  case x::xs => f(x)::my_map_int(xs, f)
-}
+def fact(n: Long): Long = 
+  if (n == 0) 1 else n * fact(n - 1)
 
-my_map_int(lst, square)
+fact(10)              //ok
+fact(10000)           // produces a stackoverflow
 
-// other function types
-//
-// f1: (Int, Int) => Int
-// f2: List[String] => Option[Int]
-// ... 
-
+def factT(n: BigInt, acc: BigInt): BigInt =
+  if (n == 0) acc else factT(n - 1, n * acc)
 
-def sumOf(f: Int => Int, lst: List[Int]): Int = lst match {
-  case Nil => 0
-  case x::xs => f(x) + sumOf(f, xs)
-}
-
-def sum_squares(lst: List[Int]) = sumOf(square, lst)
-def sum_cubes(lst: List[Int])   = sumOf(x => x * x * x, lst)
-
-sum_squares(lst)
-sum_cubes(lst)
+factT(10, 1)
+factT(100000, 1)
 
-// lets try it factorial
-def fact(n: Int): Int = ...
-
-def sum_fact(lst: List[Int]) = sumOf(fact, lst)
-sum_fact(lst)
+// there is a flag for ensuring a function is tail recursive
+import scala.annotation.tailrec
 
-// Avoid being mutable
-//=====================
-
-// a student showed me...
-import scala.collection.mutable.ListBuffer
+@tailrec
+def factT(n: BigInt, acc: BigInt): BigInt =
+  if (n == 0) acc else factT(n - 1, n * acc)
 
 
 
-def collatz_max(bnd: Long): (Long, Long) = {
-  val colNos = ListBuffer[(Long, Long)]()
-  for (i <- (1L to bnd).toList) colNos += ((collatz(i), i))
-  colNos.max
-}
+// for tail-recursive functions the Scala compiler
+// generates loop-like code, which does not need
+// to allocate stack-space in each recursive
+// call; Scala can do this only for tail-recursive
+// functions
+
 
-def collatz_max(bnd: Long): (Long, Long) = {
-  (1L to bnd).map((i) => (collatz(i), i)).maxBy(_._1)
+// A Web Crawler 
+//===============
+//
+// the idea is to look for dead links using the
+// regular expression "https?://[^"]*"
+
+import io.Source
+import scala.util._
+
+// gets the first 10K of a web-page
+def get_page(url: String) : String = {
+  Try(Source.fromURL(url)("ISO-8859-1").take(10000).mkString).
+    getOrElse { println(s"  Problem with: $url"); ""}
 }
 
-//views -> lazy collection
-def collatz_max(bnd: Long): (Long, Long) = {
-  (1L to bnd).view.map((i) => (collatz(i), i)).maxBy(_._1)
+// regex for URLs and emails
+val http_pattern = """"https?://[^"]*"""".r
+val email_pattern = """([a-z0-9_\.-]+)@([\da-z\.-]+)\.([a-z\.]{2,6})""".r
+
+
+// drops the first and last character from a string
+def unquote(s: String) = s.drop(1).dropRight(1)
+
+def get_all_URLs(page: String): Set[String] = 
+  http_pattern.findAllIn(page).map(unquote).toSet
+
+// naive version of crawl - searches until a given depth,
+// visits pages potentially more than once
+def crawl(url: String, n: Int) : Set[String] = {
+  if (n == 0) Set()
+  else {
+    println(s"  Visiting: $n $url")
+    val page = get_page(url)
+    val new_emails = email_pattern.findAllIn(page).toSet
+    new_emails ++ (for (u <- get_all_URLs(page).par) yield crawl(u, n - 1)).flatten
+  }
 }
 
-// raises a GC exception
-(1 to 1000000000).filter(_ % 2 == 0).take(10).toList
-// ==> java.lang.OutOfMemoryError: GC overhead limit exceeded
+// some starting URLs for the crawler
+val startURL = """https://nms.kcl.ac.uk/christian.urban/"""
 
-(1 to 1000000000).view.filter(_ % 2 == 0).take(10).toList
+crawl(startURL, 2)
+
+
+
+
 
 
 
diff -r eb188f9ac038 -r 9b45dd24271b slides/slides02.pdf
Binary file slides/slides02.pdf has changed
diff -r eb188f9ac038 -r 9b45dd24271b slides/slides02.tex
--- a/slides/slides02.tex	Thu Nov 15 14:23:55 2018 +0000
+++ b/slides/slides02.tex	Fri Nov 16 02:06:03 2018 +0000
@@ -69,22 +69,98 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 \begin{frame}[c]
-\frametitle{Scala on Lab Computers}
+\frametitle{Assignments}
 
-Avoid at all costs, even in comments
+Don't change anything with the templates!\bigskip
+
+Avoid at all costs:
 
 \begin{itemize}
-\item \texttt{var} \only<2>{$\quad\Rightarrow\;$\texttt{Var}}
-\item \texttt{return} \only<2>{$\quad\Rightarrow\;$\texttt{Return}}
-\item \texttt{.par}
+\item \texttt{var} 
+\item \texttt{return} 
 \item \texttt{ListBuffer}
-\item \texttt{mutable}  
-\end{itemize}
+\item \texttt{mutable}
+\item \texttt{.par}  
+\end{itemize}\pause\bigskip
+
+
+\mbox{}\hfill\textit{``Scala --- \underline{S}lowly \underline{c}ompiled 
+\underline{a}cademic \underline{la}nguage''}\smallskip\\
+\mbox{}\hfill\textit{ --- a joke(?) found on Twitter}\bigskip
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Email: Hate 'val'}
+
+\mbox{}\\[-25mm]\mbox{}
+
+\begin{center}
+  \begin{bubble}[10.5cm]
+  Subject: \textbf{Hate '\textbf{\texttt{val}}'}\hfill 01:00 AM\medskip\\
+
+  Hello Mr Urban,\medskip\\
+
+  I just wanted to ask, how are we suppose to work
+  with the completely useless \textbf{\texttt{val}}, that can’t be changed ever? Why is
+  this rule active at all? I’ve spent 4 hours not thinking on the
+  coursework, but how to bypass this annoying rule. What’s the whole
+  point of all these coursework, when we can’t use everything Scala
+  gives us?!?\medskip\\
+
+  Regards.\\
+  \mbox{}\hspace{5mm}\textcolor{black!50}{<<deleted>>}\\
+  \end{bubble}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\def\firstcircle{(0,0) circle (1.4cm)}
+\def\secondcircle{(0:2cm) circle (1.4cm)}
+\colorlet{circle edge}{blue!50}
+\colorlet{circle area}{blue!20}
+
+\tikzset{filled/.style={fill=circle area, draw=circle edge, thick},
+    outline/.style={draw=circle edge, thick}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Par: Intersections}
+
+\begin{textblock}{6}(1,2)
+\begin{tikzpicture}
+  \draw[outline] \firstcircle node {$A$};
+  \node[anchor=south] at (current bounding box.north)
+    {$A = \{1,2,3,\ldots,1000\}$};
+\end{tikzpicture}
+\end{textblock}
+
+\begin{textblock}{6}(8,2)
+\begin{tikzpicture}
+  \draw[outline] \secondcircle node {$B$};
+  \node[anchor=south] at (current bounding box.north)
+    {$B = \{1,5,9,13,\ldots,997\}$};
+\end{tikzpicture}
+\end{textblock}
+
+\begin{textblock}{6}(3.3,9)
+\begin{tikzpicture}
+    \begin{scope}
+        \clip \firstcircle;
+        \fill[filled] \secondcircle;
+    \end{scope}
+    \draw[outline] \firstcircle node {$A$};
+    \draw[outline] \secondcircle node {$B$};
+    \node[anchor=north] at (current bounding box.south)
+    {How many elements are in $A \cap B$?};
+\end{tikzpicture}
+\end{textblock}  
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 \begin{frame}[t]
 \frametitle{For-Comprehensions Again}
@@ -219,7 +295,7 @@
 \end{center}
             
 \begin{center}
-My Scala Office Hours: Thursdays 11 -- 13
+My Office Hours: Mondays 12 -- 14
 \end{center}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight1.scala
--- a/testing2/knight1.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,133 +0,0 @@
-
-// Part 1 about finding and counting Knight's tours
-//==================================================
-
-object CW7a extends App{
-
-type Pos = (Int, Int)    // a position on a chessboard 
-type Path = List[Pos]    // a path...a list of positions
-
-//(1a) Complete the function that tests whether the position 
-//     is inside the board and not yet element in the path.
-
-//def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = ...
-
-def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = {
-  
-// if ((x._1<dim && x._2<dim) && (x._1>0 || x._2>0)) false else !path.contains(x)
- 
-  if (x._1 < 0 || x._2 < 0) false 
-  else if (x._1 < dim && x._2 < dim && !path.contains(x)) true 
-  else false
- 
-  
-}
-
-
-
-def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {
-  
-  val allPossibleMoves = List((x._1+1, x._2+2), (x._1+2, x._2+1), (x._1+2, x._2-1), (x._1+1, x._2-2), (x._1-1, x._2-2), (x._1-2, x._2-1), (x._1-2, x._2+1), (x._1-1, x._2+2));
- 
-  //val finalList = allPossibleMoves.filter((a=>a._1<dim && a._2<dim && x._1 >= 0 && a._2 >= 0));
-  
-  val finalList = for(pos<-allPossibleMoves if(is_legal(dim,path)(pos))) yield pos;
-  
-  // println("Space in board: " + dim*dim + " for dim: " + dim)
-   
-  
-  finalList.toList;
-    
-  
-}
-
-println(legal_moves(8, Nil, (2,2)))
-println(legal_moves(8, Nil, (7,7)))
-println(legal_moves(8, List((4,1), (1,0)), (2,2)))
-println(legal_moves(8, List((6,6)), (7,7)))
-println(legal_moves(1, Nil, (0,0)))
-println(legal_moves(2, Nil, (0,0)))
-println(legal_moves(3, Nil, (0,0)))
-
-println("=================================================================================")
-println("================================Comparision output===============================")
-println("=================================================================================")
-
-println(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-println(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-println(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-println(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-println(legal_moves(1, Nil, (0,0)) == Nil)
-println(legal_moves(2, Nil, (0,0)) == Nil)
-println(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
-
-
-def count_tours(dim: Int, path: Path) : Int = {
-     
-  val allMovesFromCurrentPosition = legal_moves(dim, path, path.head);
-  
-  if (path.length == dim*dim) 1 else  {
-    
-    if (allMovesFromCurrentPosition.size == 0 ) 0  else {
-      
-      allMovesFromCurrentPosition.map( element => count_tours(dim, element::path)).sum
-      
-      
-    }
-    
-  }
-  
-}
-    
-  
-
-println ( count_tours(5, List((0,0))) )
-
-def enum_tours(dim: Int, path: Path) : List[Path] = {
-  
-     val allMovesFromCurrentPosition = legal_moves(dim, path, path.head);
-  
-  if (path.length == dim*dim) List(path) else  {
-    
-  allMovesFromCurrentPosition.map( element => enum_tours(dim, element::path)).flatten ;
-      
-      
-      }
-    }
-  println ( enum_tours(6, List((0,2))).size)
-}
-
-
-
-
-
- 
- 
-//(1b) Complete the function that calculates for a position 
-//     all legal onward moves that are not already in the path. 
-//     The moves should be ordered in a "clockwise" manner.
- 
-//def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ...
-
-
-
-
-//some test cases
-//
-//assert(legal_moves(8, Nil, (2,2)) == 
-//  List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == 
-//  List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-
-
-//(1c) Complete the two recursive functions below. 
-//     They exhaustively search for knight's tours starting from the 
-//     given path. The first function counts all possible tours, 
-//     and the second collects all tours in a list of paths.
-
-//def count_tours(dim: Int, path: Path) : Int = ...
-
-
-//def enum_tours(dim: Int, path: Path) : List[Path] = ...
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight1_test.sh
--- a/testing2/knight1_test.sh	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,195 +0,0 @@
-#!/bin/bash
-set -e
-
-out=${1:-output}
-
-echo "" > $out
-
-echo "Below is the feedback for your submission of CW 7, Part 1 and 2." >> $out
-echo "" >> $out
-
-
-# compilation tests
-
-function scala_compile {
-  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) 
-}
-
-# functional tests
-
-function scala_assert_slow {
-  (ulimit -t 120; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
-}
-
-function scala_assert_thirty {
-  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
-}
-
-function scala_assert_quick {
-  (ulimit -t 10; 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)
-}
-
-
-# knights1: purity test
-
-echo "knight1.scala does not contain vars, returns etc?" >> $out
-
-if (scala_vars knight1.scala)
-then
-  echo "  --> fail: if you do not fix this, you will receive a mark of zero" >> $out
-  tsts0=$(( 1 ))
-else
-  echo "  --> success" >> $out
-  tsts0=$(( 0 )) 
-fi
-
-
-# compilation test
-
-if [ $tsts0 -eq 0 ]
-then    
-  echo "knight1.scala runs?" >> $out
-
-  if (scala_compile knight1.scala)
-  then
-    echo "  --> success " >> $out
-    tsts1=$(( 0 ))
-  else
-    echo "  --> scala did not run knight1.scala" >> $out
-    tsts1=$(( 1 )) 
-  fi
-else
-  tsts1=$(( 1 ))   
-fi
-
-### knight1a test
-
-if [ $tsts1 -eq 0 ]
-then
-    echo "Takes 10 seconds or less to execute: " >> $out
-    echo " is_legal(8, Nil)(3, 4) == true " >> $out
-    echo " is_legal(8, List((4, 1), (1, 0)))(4, 1) == false " >> $out
-    echo " is_legal(2, Nil)(0, 0) == true" >> $out                          
-
-    if (scala_assert_quick "knight1.scala" "knight1a_test.scala")
-    then
-        echo "  --> success" >> $out
-    else
-        echo "  --> test failed" >> $out
-    fi
-fi
-
-### knight1b test
-
-if [ $tsts1 -eq 0 ]
-then
-  echo "Takes 10 seconds or less to execute: " >> $out
-  echo " legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))" >> $out
-  echo " legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))" >> $out
-  echo " legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))" >> $out
-  echo " legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))" >> $out
-  echo " legal_moves(1, Nil, (0,0)) == Nil" >> $out
-  echo " legal_moves(2, Nil, (0,0)) == Nil" >> $out
-  echo " legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))" >> $out
-  
-  if (scala_assert_quick "knight1.scala" "knight1b_test.scala")
-  then
-    echo "  --> success" >> $out
-  else
-    echo "  --> test failed" >> $out
-  fi
-fi
-
-
-### knight1c test
-
-if [ $tsts1 -eq 0 ]
-then
-  echo " all_tours from every position on the board, in 2 minutes or less" >> $out
-  echo " dim = 1: 1" >> $out
-  echo "       2: 0,0,0,0" >>  $out
-  echo "       3: 0,0,0,0,0,0,0,0,0" >>  $out
-  echo "       4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" >> $out
-  echo "       5: 304,0,56,0,304,0,56,0,56,0,56,0,64,0,56,0,56,0,56,0,304,0,56,0,304" >> $out
-  echo " enum_tours(5, List((0,2)) ) == 56 and all correct?" >> $out
-  
-  if (scala_assert_slow "knight1.scala" "knight1c_test.scala") 
-  then
-    echo "  --> success" >> $out
-  else
-    echo "  --> test failed" >> $out
-  fi
-fi
-
-
-# knights2: var test
-
-echo "knight2.scala does not contain vars, returns etc?" >> $out
-
-if (scala_vars knight2.scala)
-then
-  echo "  --> fail" >> $out
-  tsts0=$(( 1 ))
-else
-  echo "  --> success" >> $out
-  tsts0=$(( 0 )) 
-fi
-
-
-# compilation test
-if  [ $tsts0 -eq 0 ]
-then    
-  echo "knight2.scala runs?" >> $out
-
-  if (scala_compile knight2.scala)
-  then
-    echo "  --> success" >> $out
-    tsts1=$(( 0 ))
-  else
-    echo "  --> scala did not run knight2.scala" >> $out
-    tsts1=$(( 1 )) 
-  fi
-else
-  tsts1=$(( 1 ))     
-fi
-
-### knight2a test
-
-if [ $tsts1 -eq 0 ]
-then
-  echo "Takes 10 seconds or less to execute: " >> $out
-  echo " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " >> $out
-  echo "   first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0)))" >> $out
-  echo "   first(List((1,0),(2,0),(3,0)), f) == None" >> $out
-
-  if (scala_assert_quick "knight2.scala" "knight2a_test.scala") 
-  then
-    echo "  --> success" >> $out
-  else
-    echo "  --> test failed" >> $out
-  fi
-fi
-
-
-### knight2b test
-
-if [ $tsts1 -eq 0 ]
-then
-  echo "Takes 30 seconds or less to execute: " >> $out
-  echo " is first_tour(8, List((0, 0))) ok? " >> $out
-  echo " is first_tour(4, List((0, 0))) == None " >> $out
-
-  if (scala_assert_thirty "knight2.scala" "knight2b_test.scala") 
-  then
-    echo "  --> success" >> $out
-  else
-    echo "  --> test failed" >> $out
-  fi
-fi
-
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight1a_test.scala
--- a/testing2/knight1a_test.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,5 +0,0 @@
-
-assert(CW7a.is_legal(8, Nil)(3, 4) == true)
-assert(CW7a.is_legal(8, List((4, 1), (1, 0)))(4, 1) == false)
-assert(CW7a.is_legal(2, Nil)(0, 0) == true)
-
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight1b_test.scala
--- a/testing2/knight1b_test.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,11 +0,0 @@
-
-assert(CW7a.legal_moves(8, Nil, (2,2)) == 
-             List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
-assert(CW7a.legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-assert(CW7a.legal_moves(8, List((4,1), (1,0)), (2,2)) == 
-       List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
-assert(CW7a.legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
-assert(CW7a.legal_moves(1, Nil, (0,0)) == List())
-assert(CW7a.legal_moves(2, Nil, (0,0)) == List())
-assert(CW7a.legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
-
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight1c_test.scala
--- a/testing2/knight1c_test.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,47 +0,0 @@
-
-import scala.concurrent._
-import scala.concurrent.duration._
-import ExecutionContext.Implicits.global
-import scala.language.postfixOps 
-
-type Pos = (Int, Int)    // a position on a chessboard 
-type Path = List[Pos]    // a path...a list of positions
-
-def count_all_tours_urban(dim: Int) = {
-  for (i <- (0 until dim).toList; 
-       j <- (0 until dim).toList) yield CW7a.count_tours(dim, List((i, j)))
-}
-
-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 f = Future {
-  assert(count_all_tours_urban(1) == List(1))
-  assert(count_all_tours_urban(2) == List(0, 0, 0, 0))
-  assert(count_all_tours_urban(3) == List(0, 0, 0, 0, 0, 0, 0, 0, 0))
-  assert(count_all_tours_urban(4) == List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
-  assert(count_all_tours_urban(5) == List(304, 0, 56, 0, 304, 0, 56, 0, 56, 0, 56, 0, 64, 0, 56, 0, 56, 0, 56, 0, 304, 0, 56, 0, 304))
-
-  val ts = CW7a.enum_tours(5, List((0, 2)))
-  assert(ts.map(correct_urban(5)).forall(_ == true) == true)
-  assert(ts.length == 56)  
-}
-
-Await.result(f, 360 second)
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight2.scala
--- a/testing2/knight2.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,61 +0,0 @@
-// 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)
-*/
-
-}
-
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight2a_test.scala
--- a/testing2/knight2a_test.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,5 +0,0 @@
-
-val f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None
-
-assert(CW7b.first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0))))
-assert(CW7b.first(List((1,0),(2,0),(3,0)), f) == None)
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight2b_test.scala
--- a/testing2/knight2b_test.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,40 +0,0 @@
-
-import scala.concurrent._
-import scala.concurrent.duration._
-import ExecutionContext.Implicits.global
-import scala.language.postfixOps 
-
-type Pos = (Int, Int)    // a position on a chessboard 
-type Path = List[Pos]    // a path...a list of positions
-
-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 f = Future {
-
-  val ts1 = CW7b.first_tour(8, List((0, 0))).get
-  assert(correct_urban(8)(ts1) == true)
-
-  val ts2 = CW7b.first_tour(4, List((0, 0)))
-  assert(ts2 == None)  
-}
-
-Await.result(f, 300 second)
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight3.scala
--- a/testing2/knight3.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,96 +0,0 @@
-// 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
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight3_test.sh
--- a/testing2/knight3_test.sh	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,118 +0,0 @@
-#!/bin/bash
-set -e
-
-out=${1:-output}
-
-echo "" > $out
-
-echo "Below is the feedback for your submission of CW 7, Part 3." >> $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 {
-  (ulimit -t 30 ; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) 
-}
-
-# functional tests
-
-# not sure yet what the right kind of stack should be
-
-function scala_assert {
-    (ulimit -t 20 ; JAVA_OPTS="-Xmx1g -Xss200m" 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)
-}
-
-
-# knights3: purity test
-#
-echo "knight3.scala does not contain vars, returns etc?" >> $out
-
-if (scala_vars knight3.scala)
-then
-  echo "  --> fail: if you do not fix this, you will receive a mark of zero" >> $out
-  tsts0=$(( 1 ))
-else
-  echo "  --> success" >> $out
-  tsts0=$(( 0 )) 
-fi
-
-
-# compilation test
-if  [ $tsts0 -eq 0 ]
-then    
-  echo "knight3.scala runs?" >> $out
-
-  if (scala_compile knight3.scala)
-  then
-    echo "  --> success" >> $out
-    tsts1=$(( 0 ))
-  else
-    echo "  --> scala knight3.scala did not run successfully" >> $out
-    tsts1=$(( 1 )) 
-  fi
-else
-  tsts1=$(( 1 ))     
-fi
-
-# ordered move test
-
-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
-  
-  if (scala_assert "knight3.scala" "knight3a_test.scala")
-  then
-    echo "  --> success" >> $out
-  else
-    echo "  --> test failed" >> $out
-  fi
-fi
-
-
-# first-closed-tour test
-
-if [ $tsts1 -eq 0 ]
-then
-  echo " first_closed_tour_heuristic(6, List((3, 3))) found and ok?" >> $out
-  
-  if (scala_assert "knight3.scala" "knight3b_test.scala")
-  then
-    echo "  --> success" >> $out
-  else
-    echo "  --> test failed" >> $out
-  fi
-fi
-
-
-
-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
-  
-  if (scala_assert "knight3.scala" "knight3c_test.scala")
-  then
-    echo "  --> success" >> $out
-  else
-    echo "  --> test failed" >> $out
-  fi
-fi
-
-
-## final marks
-##echo "Overall mark for CW 7, Part 2" | tee -a $out
-##echo "$marks" | tee -a $out
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight3a_test.scala
--- a/testing2/knight3a_test.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,15 +0,0 @@
-
-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((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)
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight3b_test.scala
--- a/testing2/knight3b_test.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,40 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps 
-
-type Pos = (Int, Int)
-type Path = List[Pos]
-
-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
-}
-
-def correct_closed_urban(dim: Int)(p: Path) =
-  correct_urban(6)(p) &&  moves_urban(p.head).contains(p.last)
-
-//lazy val f = Future {
-
-  val tsc = CW7c.first_closed_tour_heuristic(6, List((3, 3))).get
-  assert(correct_closed_urban(6)(tsc) == true)
-
-//}
-
-//Await.result(f, 300 second)
diff -r eb188f9ac038 -r 9b45dd24271b testing2/knight3c_test.scala
--- a/testing2/knight3c_test.scala	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,49 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps 
-
-type Pos = (Int, Int)
-type Path = List[Pos]
-
-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
-}
-
-
-// !!!!!!! the futures need to be removed...otherwise funny results
-//lazy val f1 = Future {
-
-  val ts8 = CW7c.first_tour_heuristic(8, List((0,0))).get
-  assert(correct_urban(8)(ts8) == true)
-
-//}
-
-//Await.result(f1, 360 second)
-
-
-//lazy val f2 = Future {
-
-  val ts40 = CW7c.first_tour_heuristic(40, List((0,0))).get
-  assert(correct_urban(40)(ts40) == true)
-
-//}
-
-//Await.result(f2, 360 second)
diff -r eb188f9ac038 -r 9b45dd24271b testing2/mark
--- a/testing2/mark	Thu Nov 15 14:23:55 2018 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,8 +0,0 @@
-#!/bin/sh
-###set -e
-
-trap "exit" INT
-
-./knight1_test.sh output1
-./knight3_test.sh output3
-
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight1.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight1.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,133 @@
+
+// Part 1 about finding and counting Knight's tours
+//==================================================
+
+object CW7a extends App{
+
+type Pos = (Int, Int)    // a position on a chessboard 
+type Path = List[Pos]    // a path...a list of positions
+
+//(1a) Complete the function that tests whether the position 
+//     is inside the board and not yet element in the path.
+
+//def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = ...
+
+def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = {
+  
+// if ((x._1<dim && x._2<dim) && (x._1>0 || x._2>0)) false else !path.contains(x)
+ 
+  if (x._1 < 0 || x._2 < 0) false 
+  else if (x._1 < dim && x._2 < dim && !path.contains(x)) true 
+  else false
+ 
+  
+}
+
+
+
+def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {
+  
+  val allPossibleMoves = List((x._1+1, x._2+2), (x._1+2, x._2+1), (x._1+2, x._2-1), (x._1+1, x._2-2), (x._1-1, x._2-2), (x._1-2, x._2-1), (x._1-2, x._2+1), (x._1-1, x._2+2));
+ 
+  //val finalList = allPossibleMoves.filter((a=>a._1<dim && a._2<dim && x._1 >= 0 && a._2 >= 0));
+  
+  val finalList = for(pos<-allPossibleMoves if(is_legal(dim,path)(pos))) yield pos;
+  
+  // println("Space in board: " + dim*dim + " for dim: " + dim)
+   
+  
+  finalList.toList;
+    
+  
+}
+
+println(legal_moves(8, Nil, (2,2)))
+println(legal_moves(8, Nil, (7,7)))
+println(legal_moves(8, List((4,1), (1,0)), (2,2)))
+println(legal_moves(8, List((6,6)), (7,7)))
+println(legal_moves(1, Nil, (0,0)))
+println(legal_moves(2, Nil, (0,0)))
+println(legal_moves(3, Nil, (0,0)))
+
+println("=================================================================================")
+println("================================Comparision output===============================")
+println("=================================================================================")
+
+println(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+println(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+println(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+println(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+println(legal_moves(1, Nil, (0,0)) == Nil)
+println(legal_moves(2, Nil, (0,0)) == Nil)
+println(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
+
+def count_tours(dim: Int, path: Path) : Int = {
+     
+  val allMovesFromCurrentPosition = legal_moves(dim, path, path.head);
+  
+  if (path.length == dim*dim) 1 else  {
+    
+    if (allMovesFromCurrentPosition.size == 0 ) 0  else {
+      
+      allMovesFromCurrentPosition.map( element => count_tours(dim, element::path)).sum
+      
+      
+    }
+    
+  }
+  
+}
+    
+  
+
+println ( count_tours(5, List((0,0))) )
+
+def enum_tours(dim: Int, path: Path) : List[Path] = {
+  
+     val allMovesFromCurrentPosition = legal_moves(dim, path, path.head);
+  
+  if (path.length == dim*dim) List(path) else  {
+    
+  allMovesFromCurrentPosition.map( element => enum_tours(dim, element::path)).flatten ;
+      
+      
+      }
+    }
+  println ( enum_tours(6, List((0,2))).size)
+}
+
+
+
+
+
+ 
+ 
+//(1b) Complete the function that calculates for a position 
+//     all legal onward moves that are not already in the path. 
+//     The moves should be ordered in a "clockwise" manner.
+ 
+//def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ...
+
+
+
+
+//some test cases
+//
+//assert(legal_moves(8, Nil, (2,2)) == 
+//  List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == 
+//  List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+
+
+//(1c) Complete the two recursive functions below. 
+//     They exhaustively search for knight's tours starting from the 
+//     given path. The first function counts all possible tours, 
+//     and the second collects all tours in a list of paths.
+
+//def count_tours(dim: Int, path: Path) : Int = ...
+
+
+//def enum_tours(dim: Int, path: Path) : List[Path] = ...
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight1_test.sh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight1_test.sh	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,195 @@
+#!/bin/bash
+set -e
+
+out=${1:-output}
+
+echo "" > $out
+
+echo "Below is the feedback for your submission of CW 7, Part 1 and 2." >> $out
+echo "" >> $out
+
+
+# compilation tests
+
+function scala_compile {
+  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) 
+}
+
+# functional tests
+
+function scala_assert_slow {
+  (ulimit -t 120; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
+}
+
+function scala_assert_thirty {
+  (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
+}
+
+function scala_assert_quick {
+  (ulimit -t 10; 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)
+}
+
+
+# knights1: purity test
+
+echo "knight1.scala does not contain vars, returns etc?" >> $out
+
+if (scala_vars knight1.scala)
+then
+  echo "  --> fail: if you do not fix this, you will receive a mark of zero" >> $out
+  tsts0=$(( 1 ))
+else
+  echo "  --> success" >> $out
+  tsts0=$(( 0 )) 
+fi
+
+
+# compilation test
+
+if [ $tsts0 -eq 0 ]
+then    
+  echo "knight1.scala runs?" >> $out
+
+  if (scala_compile knight1.scala)
+  then
+    echo "  --> success " >> $out
+    tsts1=$(( 0 ))
+  else
+    echo "  --> scala did not run knight1.scala" >> $out
+    tsts1=$(( 1 )) 
+  fi
+else
+  tsts1=$(( 1 ))   
+fi
+
+### knight1a test
+
+if [ $tsts1 -eq 0 ]
+then
+    echo "Takes 10 seconds or less to execute: " >> $out
+    echo " is_legal(8, Nil)(3, 4) == true " >> $out
+    echo " is_legal(8, List((4, 1), (1, 0)))(4, 1) == false " >> $out
+    echo " is_legal(2, Nil)(0, 0) == true" >> $out                          
+
+    if (scala_assert_quick "knight1.scala" "knight1a_test.scala")
+    then
+        echo "  --> success" >> $out
+    else
+        echo "  --> test failed" >> $out
+    fi
+fi
+
+### knight1b test
+
+if [ $tsts1 -eq 0 ]
+then
+  echo "Takes 10 seconds or less to execute: " >> $out
+  echo " legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))" >> $out
+  echo " legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))" >> $out
+  echo " legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))" >> $out
+  echo " legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))" >> $out
+  echo " legal_moves(1, Nil, (0,0)) == Nil" >> $out
+  echo " legal_moves(2, Nil, (0,0)) == Nil" >> $out
+  echo " legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))" >> $out
+  
+  if (scala_assert_quick "knight1.scala" "knight1b_test.scala")
+  then
+    echo "  --> success" >> $out
+  else
+    echo "  --> test failed" >> $out
+  fi
+fi
+
+
+### knight1c test
+
+if [ $tsts1 -eq 0 ]
+then
+  echo " all_tours from every position on the board, in 2 minutes or less" >> $out
+  echo " dim = 1: 1" >> $out
+  echo "       2: 0,0,0,0" >>  $out
+  echo "       3: 0,0,0,0,0,0,0,0,0" >>  $out
+  echo "       4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" >> $out
+  echo "       5: 304,0,56,0,304,0,56,0,56,0,56,0,64,0,56,0,56,0,56,0,304,0,56,0,304" >> $out
+  echo " enum_tours(5, List((0,2)) ) == 56 and all correct?" >> $out
+  
+  if (scala_assert_slow "knight1.scala" "knight1c_test.scala") 
+  then
+    echo "  --> success" >> $out
+  else
+    echo "  --> test failed" >> $out
+  fi
+fi
+
+
+# knights2: var test
+
+echo "knight2.scala does not contain vars, returns etc?" >> $out
+
+if (scala_vars knight2.scala)
+then
+  echo "  --> fail" >> $out
+  tsts0=$(( 1 ))
+else
+  echo "  --> success" >> $out
+  tsts0=$(( 0 )) 
+fi
+
+
+# compilation test
+if  [ $tsts0 -eq 0 ]
+then    
+  echo "knight2.scala runs?" >> $out
+
+  if (scala_compile knight2.scala)
+  then
+    echo "  --> success" >> $out
+    tsts1=$(( 0 ))
+  else
+    echo "  --> scala did not run knight2.scala" >> $out
+    tsts1=$(( 1 )) 
+  fi
+else
+  tsts1=$(( 1 ))     
+fi
+
+### knight2a test
+
+if [ $tsts1 -eq 0 ]
+then
+  echo "Takes 10 seconds or less to execute: " >> $out
+  echo " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " >> $out
+  echo "   first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0)))" >> $out
+  echo "   first(List((1,0),(2,0),(3,0)), f) == None" >> $out
+
+  if (scala_assert_quick "knight2.scala" "knight2a_test.scala") 
+  then
+    echo "  --> success" >> $out
+  else
+    echo "  --> test failed" >> $out
+  fi
+fi
+
+
+### knight2b test
+
+if [ $tsts1 -eq 0 ]
+then
+  echo "Takes 30 seconds or less to execute: " >> $out
+  echo " is first_tour(8, List((0, 0))) ok? " >> $out
+  echo " is first_tour(4, List((0, 0))) == None " >> $out
+
+  if (scala_assert_thirty "knight2.scala" "knight2b_test.scala") 
+  then
+    echo "  --> success" >> $out
+  else
+    echo "  --> test failed" >> $out
+  fi
+fi
+
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight1a_test.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight1a_test.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,5 @@
+
+assert(CW7a.is_legal(8, Nil)(3, 4) == true)
+assert(CW7a.is_legal(8, List((4, 1), (1, 0)))(4, 1) == false)
+assert(CW7a.is_legal(2, Nil)(0, 0) == true)
+
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight1b_test.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight1b_test.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,11 @@
+
+assert(CW7a.legal_moves(8, Nil, (2,2)) == 
+             List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+assert(CW7a.legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
+assert(CW7a.legal_moves(8, List((4,1), (1,0)), (2,2)) == 
+       List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+assert(CW7a.legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
+assert(CW7a.legal_moves(1, Nil, (0,0)) == List())
+assert(CW7a.legal_moves(2, Nil, (0,0)) == List())
+assert(CW7a.legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight1c_test.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight1c_test.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,47 @@
+
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps 
+
+type Pos = (Int, Int)    // a position on a chessboard 
+type Path = List[Pos]    // a path...a list of positions
+
+def count_all_tours_urban(dim: Int) = {
+  for (i <- (0 until dim).toList; 
+       j <- (0 until dim).toList) yield CW7a.count_tours(dim, List((i, j)))
+}
+
+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 f = Future {
+  assert(count_all_tours_urban(1) == List(1))
+  assert(count_all_tours_urban(2) == List(0, 0, 0, 0))
+  assert(count_all_tours_urban(3) == List(0, 0, 0, 0, 0, 0, 0, 0, 0))
+  assert(count_all_tours_urban(4) == List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
+  assert(count_all_tours_urban(5) == List(304, 0, 56, 0, 304, 0, 56, 0, 56, 0, 56, 0, 64, 0, 56, 0, 56, 0, 56, 0, 304, 0, 56, 0, 304))
+
+  val ts = CW7a.enum_tours(5, List((0, 2)))
+  assert(ts.map(correct_urban(5)).forall(_ == true) == true)
+  assert(ts.length == 56)  
+}
+
+Await.result(f, 360 second)
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight2.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight2.scala	Fri Nov 16 02:06:03 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)
+*/
+
+}
+
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight2a_test.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight2a_test.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,5 @@
+
+val f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None
+
+assert(CW7b.first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0))))
+assert(CW7b.first(List((1,0),(2,0),(3,0)), f) == None)
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight2b_test.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight2b_test.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,40 @@
+
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps 
+
+type Pos = (Int, Int)    // a position on a chessboard 
+type Path = List[Pos]    // a path...a list of positions
+
+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 f = Future {
+
+  val ts1 = CW7b.first_tour(8, List((0, 0))).get
+  assert(correct_urban(8)(ts1) == true)
+
+  val ts2 = CW7b.first_tour(4, List((0, 0)))
+  assert(ts2 == None)  
+}
+
+Await.result(f, 300 second)
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight3.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight3.scala	Fri Nov 16 02:06:03 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
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight3_test.sh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight3_test.sh	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,118 @@
+#!/bin/bash
+set -e
+
+out=${1:-output}
+
+echo "" > $out
+
+echo "Below is the feedback for your submission of CW 7, Part 3." >> $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 {
+  (ulimit -t 30 ; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) 
+}
+
+# functional tests
+
+# not sure yet what the right kind of stack should be
+
+function scala_assert {
+    (ulimit -t 20 ; JAVA_OPTS="-Xmx1g -Xss200m" 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)
+}
+
+
+# knights3: purity test
+#
+echo "knight3.scala does not contain vars, returns etc?" >> $out
+
+if (scala_vars knight3.scala)
+then
+  echo "  --> fail: if you do not fix this, you will receive a mark of zero" >> $out
+  tsts0=$(( 1 ))
+else
+  echo "  --> success" >> $out
+  tsts0=$(( 0 )) 
+fi
+
+
+# compilation test
+if  [ $tsts0 -eq 0 ]
+then    
+  echo "knight3.scala runs?" >> $out
+
+  if (scala_compile knight3.scala)
+  then
+    echo "  --> success" >> $out
+    tsts1=$(( 0 ))
+  else
+    echo "  --> scala knight3.scala did not run successfully" >> $out
+    tsts1=$(( 1 )) 
+  fi
+else
+  tsts1=$(( 1 ))     
+fi
+
+# ordered move test
+
+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
+  
+  if (scala_assert "knight3.scala" "knight3a_test.scala")
+  then
+    echo "  --> success" >> $out
+  else
+    echo "  --> test failed" >> $out
+  fi
+fi
+
+
+# first-closed-tour test
+
+if [ $tsts1 -eq 0 ]
+then
+  echo " first_closed_tour_heuristic(6, List((3, 3))) found and ok?" >> $out
+  
+  if (scala_assert "knight3.scala" "knight3b_test.scala")
+  then
+    echo "  --> success" >> $out
+  else
+    echo "  --> test failed" >> $out
+  fi
+fi
+
+
+
+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
+  
+  if (scala_assert "knight3.scala" "knight3c_test.scala")
+  then
+    echo "  --> success" >> $out
+  else
+    echo "  --> test failed" >> $out
+  fi
+fi
+
+
+## final marks
+##echo "Overall mark for CW 7, Part 2" | tee -a $out
+##echo "$marks" | tee -a $out
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight3a_test.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight3a_test.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,15 @@
+
+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((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)
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight3b_test.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight3b_test.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,40 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps 
+
+type Pos = (Int, Int)
+type Path = List[Pos]
+
+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
+}
+
+def correct_closed_urban(dim: Int)(p: Path) =
+  correct_urban(6)(p) &&  moves_urban(p.head).contains(p.last)
+
+//lazy val f = Future {
+
+  val tsc = CW7c.first_closed_tour_heuristic(6, List((3, 3))).get
+  assert(correct_closed_urban(6)(tsc) == true)
+
+//}
+
+//Await.result(f, 300 second)
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/knight3c_test.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/knight3c_test.scala	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,49 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps 
+
+type Pos = (Int, Int)
+type Path = List[Pos]
+
+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
+}
+
+
+// !!!!!!! the futures need to be removed...otherwise funny results
+//lazy val f1 = Future {
+
+  val ts8 = CW7c.first_tour_heuristic(8, List((0,0))).get
+  assert(correct_urban(8)(ts8) == true)
+
+//}
+
+//Await.result(f1, 360 second)
+
+
+//lazy val f2 = Future {
+
+  val ts40 = CW7c.first_tour_heuristic(40, List((0,0))).get
+  assert(correct_urban(40)(ts40) == true)
+
+//}
+
+//Await.result(f2, 360 second)
diff -r eb188f9ac038 -r 9b45dd24271b testing3-bak/mark
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3-bak/mark	Fri Nov 16 02:06:03 2018 +0000
@@ -0,0 +1,8 @@
+#!/bin/sh
+###set -e
+
+trap "exit" INT
+
+./knight1_test.sh output1
+./knight3_test.sh output3
+