# HG changeset patch
# User Christian Urban <christian.urban@kcl.ac.uk>
# Date 1636335540 0
# Node ID ffce7b61b44693ccc8484be77cf129cc577005bd
# Parent  de59aa20a1dc4b1c91a594b6bd0d376fa020eeba
updated

diff -r de59aa20a1dc -r ffce7b61b446 main_testing2/danube.scala
--- a/main_testing2/danube.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing2/danube.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,8 +1,9 @@
-// Core Part about Movie Recommendations
+// Core Part about Movie Recommendations 
 // at Danube.co.uk
-//===========================================
+//========================================
 
-object CW7b {
+
+object M2 { // for purposes of generating a jar
 
 import io.Source
 import scala.util._
@@ -12,65 +13,44 @@
 //     as argument and requests the corresponding file. The two urls
 //     of interest are ratings_url and movies_url, which correspond 
 //     to CSV-files.
-//
-//     The function should ReTurn the CSV-file appropriately broken
+//     The function should return the CSV file appropriately broken
 //     up into lines, and the first line should be dropped (that is without
-//     the header of the CSV-file). The result is a list of strings (lines
+//     the header of the CSV file). The result is a list of strings (lines
 //     in the file).
 
 def get_csv_url(url: String) : List[String] = {
-  val site = Source.fromURL(url, "ISO-8859-1")
-  val site_string = site.mkString
-  val output = (site_string.split("\n")).toList
-  output.tail
+  val csv = Source.fromURL(url)("ISO-8859-1")
+  csv.mkString.split("\n").toList.drop(1)
 }
 
-  // get_csv_url("https://nms.kcl.ac.uk/christian.urban/ratings.csv")
-
-//val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv"""
-//val movies_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv"""
+val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv"""
+val movies_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv"""
 
-// testcases
-//-----------
-//:
+// test cases
+
+//val ratings = get_csv_url(ratings_url)
 //val movies = get_csv_url(movies_url)
-  // val ratings = get_csv_url(ratings_url)
 
 //ratings.length  // 87313
 //movies.length   // 9742
 
-
-// (2) Implement two functions that process the CSV-files from (1). The ratings
-//     function filters out all ratings below 4 and ReTurns a list of 
-//     (userID, movieID) pairs. The movies function just ReTurns a list 
-//     of (movieID, title) pairs. Note the input to these functions, that is
-//     the argument lines, will be the output of the function get_csv_url.
+// (2) Implement two functions that process the CSV files. The ratings
+//     function filters out all ratings below 4 and returns a list of 
+//     (userID, movieID) pairs. The movies function just returns a list 
+//     of (movieId, title) pairs.
 
 
 def process_ratings(lines: List[String]) : List[(String, String)] = {
-  val filter = lines.filter(_.last.asDigit >=4)
-  val output = (for(i <- 0 until filter.length) yield ((filter(i).split(",").toList)(0), (filter(i).split(",").toList)(1))).toList
-  output
+  for (cols <- lines.map(_.split(",").toList); 
+       if (cols(2).toInt >= 4)) yield (cols(0), cols(1))  
 }
 
 def process_movies(lines: List[String]) : List[(String, String)] = {
-  val output = (for(i <- 0 until lines.length) yield ((lines(i).split(",").toList)(0), (lines(i).split(",").toList)(1))).toList
-  output
-}
-
-
-
-def process_ratings2(lines: List[String]) : List[(String, String)] = {
-  for (cols <- lines.map(_.split(",").toList); 
-       if (cols(2).toFloat >= 4)) yield (cols(0), cols(1))  
-}
-
-def process_movies2(lines: List[String]) : List[(String, String)] = {
   for (cols <- lines.map(_.split(",").toList)) yield (cols(0), cols(1))  
 }
 
-// testcases
-//-----------
+// test cases
+
 //val good_ratings = process_ratings(ratings)
 //val movie_names = process_movies(movies)
 
@@ -78,116 +58,45 @@
 //movie_names.length    // 9742
 
 
-
-
-// (3) Implement a grouping function that calculates a Map
-//     containing the userIDs and all the corresponding recommendations 
-//     (list of movieIDs). This  should be implemented in a tail
-//     recursive fashion, using a Map m as accumulator. This Map m
-//     is set to Map() at the beginning of the calculation.
-
-val ratings_url = """https://nms.kcl.ac.uk/christian.urban/ratings.csv"""
-val ratings = get_csv_url(ratings_url)
-val good_ratings = process_ratings(ratings)
-val v515 = good_ratings.filter(_._1 == "515")
-val v515_2 = v515.map(_._2)
+// (3) Implement a grouping function that calulates a map
+//     containing the userIds and all the corresponding recommendations 
+//     (list of movieIds). This  should be implemented in a tail
+//     recursive fashion, using a map m as accumulator. This map
+//     is set to Map() at the beginning of the claculation.
 
 def groupById(ratings: List[(String, String)], 
-              m: Map[String, List[String]]) : Map[String, List[String]] = {
-val users = (for((k,v) <- ratings) yield k).distinct
-val movie_ids = (for(i <- 1 to users.length) yield
-  (for ((k,v) <- ratings if(i.toString == k)) yield v).toList).toList
-  val out_map = (users zip movie_ids).toMap
-out_map
-}
-
-def groupById2(ratings: List[(String, String)], 
               m: Map[String, List[String]]) : Map[String, List[String]] = ratings match {
   case Nil => m
   case (id, mov) :: rest => {
     val old_ratings = m.getOrElse (id, Nil)
     val new_ratings = m + (id -> (mov :: old_ratings))
-    groupById2(rest, new_ratings)
+    groupById(rest, new_ratings)
   }
 }
 
-val ls0_urban = 
-  List(("1", "a"), ("1", "c"), ("1", "c"))
-
-groupById(ls0_urban, Map())
-groupById2(ls0_urban, Map())
-
-val ls00_urban = 
-  List(("3", "a"), ("3", "c"), ("3", "c"))
-
-groupById(ls00_urban, Map())
-groupById2(ls00_urban, Map())
-
-groupById(good_ratings, Map()).getOrElse("515", Nil)
-groupById2(good_ratings, Map()).getOrElse("515", Nil)
-
-val ls1_urban = 
-  List(("1", "a"), ("2", "a"), 
-       ("1", "c"), ("2", "a"), ("1", "c"))
-
-groupById(ls1_urban, Map())
-groupById2(ls1_urban, Map())
-
-val ls2_urban = 
-  List(("1", "a"), ("1", "b"), ("2", "x"), 
-       ("3", "a"), ("2", "y"), ("3", "c"))
-
-groupById(ls2_urban, Map())
-groupById2(ls2_urban, Map())
-
-val ls3_urban = (1 to 1000 by 10).map(_.toString).toList
-val ls4_urban = ls3_urban zip ls3_urban.tail
-val ls5_urban = ls4_urban ::: ls4_urban.reverse
-
-groupById(ls5_urban, Map()) == groupById2(ls5_urban, Map())
-
-groupById(ls5_urban, Map())
-groupById2(ls5_urban, Map())
-
-groupById(v515, Map())
-groupById2(v515, Map())
-
-groupById(v515.take(1), Map())
-groupById2(v515.take(2), Map())
-
-// testcases
-//-----------
+// test cases
 //val ratings_map = groupById(good_ratings, Map())
 //val movies_map = movie_names.toMap
 
-//ratings_map.get("414").get.map(movies_map.get(_)).length
-//    => most prolific recommender with 1227 positive ratings
+//ratings_map.get("414").get.map(movies_map.get(_)) // most prolific recommender with 1227 positive ratings
+//ratings_map.get("474").get.map(movies_map.get(_)) // second-most prolific recommender with 787 positive ratings
+//ratings_map.get("214").get.map(movies_map.get(_)) // least prolific recommender with only 1 positive rating
 
-//ratings_map.get("475").get.map(movies_map.get(_)).length
-//    => second-most prolific recommender with 787 positive ratings
-
-//ratings_map.get("214").get.map(movies_map.get(_)).length 
-//    => least prolific recommender with only 1 positive rating
 
 
-// (4) Implement a function that takes a ratings map and a movie_name as argument.
-//     The function calculates all suggestions containing
-//     the movie in its recommendations. It ReTurns a list of all these
-//     recommendations (each of them is a list and needs to have the movie deleted, 
-//     otherwise it might happen we recommend the same movie).
+//(4) Implement a function that takes a ratings map and a movie_name as argument.
+// The function calculates all suggestions containing
+// the movie mov in its recommendations. It returns a list of all these
+// recommendations (each of them is a list and needs to have mov deleted, 
+// otherwise it might happen we recommend the same movie).
 
-
-def favourites(m: Map[String, List[String]], mov: String) : List[List[String]] = {
- (for((k,v) <- m if (v.contains(mov))) yield v.filter(_!=mov).toList).toList
-}
-
-def favourites2(m: Map[String, List[String]], mov: String) : List[List[String]] = 
+def favourites(m: Map[String, List[String]], mov: String) : List[List[String]] = 
   (for (id <- m.keys.toList;
         if m(id).contains(mov)) yield m(id).filter(_ != mov))
 
 
-// testcases
-//-----------
+
+// test cases
 // movie ID "912" -> Casablanca (1942)
 //          "858" -> Godfather
 //          "260" -> Star Wars: Episode IV - A New Hope (1977)
@@ -199,57 +108,36 @@
 // 52 a good rating to movies 260, 318, 593.
 
 
-
 // (5) Implement a suggestions function which takes a rating
-//     map and a movie_name as arguments. It calculates all the recommended
-//     movies sorted according to the most frequently suggested movie(s) first.
-
+// map and a movie_name as arguments. It calculates all the recommended
+// movies sorted according to the most frequently suggested movie(s) first.
 def suggestions(recs: Map[String, List[String]], 
-                mov_name: String) : List[String] = {
-  val flat = favourites(recs, mov_name).flatten.groupMapReduce(identity)(_ => 1)(_ + _)
-  val sorted = flat.toList.sortWith(_._2 > _._2).map(_._1)
-  sorted
-}
-
-
-def mapValues[S, T, R](m: Map[S, T], f: T => R) =
-  m.map { case (x, y) => (x, f(y)) }
-
-def suggestions2(recs: Map[String, List[String]], 
                     mov_name: String) : List[String] = {
   val favs = favourites(recs, mov_name).flatten
-  val favs_counted = mapValues(favs.groupBy(identity), (v:List[String]) => v.size).toList
+  val favs_counted = favs.groupBy(identity).view.mapValues(_.size).toList
   val favs_sorted = favs_counted.sortBy(_._2).reverse
   favs_sorted.map(_._1)
 }
 
-// testcases
-//-----------
+// test cases
 
 //suggestions(ratings_map, "912")
 //suggestions(ratings_map, "912").length  
 // => 4110 suggestions with List(858, 260, 318, 593, ...)
 //    being the most frequently suggested movies
 
-
-
-// (6) Implement a recommendations function which generates at most
-//     *two* of the most frequently suggested movies. It ReTurns the 
-//     actual movie names, not the movieIDs.
-
+// (6) Implement recommendations functions which generates at most
+// *two* of the most frequently suggested movies. It Returns the 
+// actual movie names, not the movieIDs.
 
 def recommendations(recs: Map[String, List[String]],
-                    movs: Map[String, String],
-                    mov_name: String) : List[String] = {
-  val sugg = suggestions(recs, mov_name)
-  val movies = (for (i <- 0 until 2 if (i < sugg.length)) yield movs(sugg(i))).toList
-  movies
-}
-
+                   movs: Map[String, String],
+                   mov_name: String) : List[String] =
+  suggestions(recs, mov_name).take(2).map(movs.get(_).get)                 
 
 
 // testcases
-//-----------
+
 // recommendations(ratings_map, movies_map, "912")
 //   => List(Godfather, Star Wars: Episode IV - A NewHope (1977))
 
@@ -270,33 +158,4 @@
 //   => Nil  (there are three ratings for this movie in ratings.csv but they are not positive)     
 
 
-
-// (7) Calculate the recommendations for all movies according to
-// what the recommendations function in (6) produces (this
-// can take a few seconds). Put all recommendations into a list 
-// (of strings) and count how often the strings occur in
-// this list. This produces a list of string-int pairs,
-// where the first component is the movie name and the second
-// is the number of how many times the movie was recommended. 
-// Sort all the pairs according to the number
-// of times they were recommended (most recommended movie name 
-// first).
-
-def most_recommended(recs: Map[String, List[String]],
-                     movs: Map[String, String]) : List[(String, Int)] = {
-  val movies = (((for((k,v) <- movs) yield recommendations(recs, movs, k)).toList).flatten).groupMapReduce(identity)(_ => 1)(_ + _)
-  val sorted = movies.toList.sortWith(_._2 > _._2)
-  sorted
 }
-
-// testcase
-//
-//most_recommended(ratings_map, movies_map).take(3)
-// =>
-// List((Matrix,698), 
-//      (Star Wars: Episode IV - A New Hope (1977),402), 
-//      (Jerry Maguire (1996),382))
-
-
-
-}
diff -r de59aa20a1dc -r ffce7b61b446 main_testing2/danube_test.sh
--- a/main_testing2/danube_test.sh	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing2/danube_test.sh	Mon Nov 08 01:39:00 2021 +0000
@@ -113,9 +113,9 @@
 
   if (scala_assert "danube.scala" "danube_test3.scala")
   then
-      echo -e  -e "  --> success" >> $out
+      echo -e "  --> success" >> $out
   else
-      echo -e  -e "  --> ONE OF THE TESTS FAILED\n" >> $out
+      echo -e "  --> ONE OF THE TESTS FAILED\n" >> $out
   fi
 fi
 
@@ -173,23 +173,5 @@
   fi
 fi
 
-### danube most_recommended 1 
 
-if [ $tsts -eq 0 ]
-then
-    echo -e  "  val rmap =  Map(\"1\" -> List(\"b\", \"a\"), " >> $out
-    echo -e  "                  \"2\" -> List(\"y\", \"x\"), " >> $out
-    echo -e  "                  \"3\" -> List(\"c\", \"a\")) " >> $out
-    echo -e  "  val nmap = Map(\"a\" -> \"A\", \"b\" -> \"B\", \"c\" -> \"C\",  " >> $out
-    echo -e  "                 \"x\" -> \"X\", \"y\" -> \"Y\") " >> $out
-    echo -e  "  most_recommended(rmap, nmap).toSet == " >> $out
-    echo -e  "      Set((\"A\",2), (\"B\",1), (\"C\",1), (\"X\",1), (\"Y\",1)) " >> $out
 
-  if (scala_assert "danube.scala" "danube_test7.scala") 
-  then
-    echo -e  "  --> success" >> $out
-  else
-    echo -e  "  --> ONE OF THE TESTS FAILED\n" >>  $out
-  fi
-fi
-
diff -r de59aa20a1dc -r ffce7b61b446 main_testing2/danube_test1.scala
--- a/main_testing2/danube_test1.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing2/danube_test1.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,5 +1,5 @@
 
-import CW7b._
+import M2._
 
 val urban_mov_url = """https://nms.kcl.ac.uk/christian.urban/movies.csv"""
 //val urban_mov_url = """http://localhost:8000/movies.csv"""
diff -r de59aa20a1dc -r ffce7b61b446 main_testing2/danube_test2.scala
--- a/main_testing2/danube_test2.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing2/danube_test2.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -2,7 +2,7 @@
 import io.Source
 import scala.util._
 
-import CW7b._
+import M2._
 
 def urban_get_csv_file(name: String) : List[String] = {
   val csv = Source.fromFile(name)("ISO-8859-1")
diff -r de59aa20a1dc -r ffce7b61b446 main_testing2/danube_test3.scala
--- a/main_testing2/danube_test3.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing2/danube_test3.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW7b._
+import M2._
 
 
 // first test 
diff -r de59aa20a1dc -r ffce7b61b446 main_testing2/danube_test4.scala
--- a/main_testing2/danube_test4.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing2/danube_test4.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,7 +1,7 @@
 
 // first test 
 
-import CW7b._
+import M2._
 
 def urban_groupById(ratings: List[(String, String)]) = 
   ratings.groupBy(_._1).view.mapValues(_.map(_._2)).toMap 
diff -r de59aa20a1dc -r ffce7b61b446 main_testing2/danube_test5.scala
--- a/main_testing2/danube_test5.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing2/danube_test5.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,7 +1,7 @@
 
 // first test 
 
-import CW7b._
+import M2._
 
 def urban_groupById(ratings: List[(String, String)], 
               m: Map[String, List[String]]) : Map[String, List[String]] = ratings match {
diff -r de59aa20a1dc -r ffce7b61b446 main_testing2/danube_test6.scala
--- a/main_testing2/danube_test6.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing2/danube_test6.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,5 +1,5 @@
 
-import CW7b._
+import M2._
 
 // first test 
 
diff -r de59aa20a1dc -r ffce7b61b446 main_testing2/danube_test7.scala
--- a/main_testing2/danube_test7.scala	Mon Nov 08 01:16:13 2021 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,13 +0,0 @@
-
-import CW7b._
-
-val urban_recs = 
-  Map("1" -> List("b", "a"), 
-      "2" -> List("y", "x"), 
-      "3" -> List("a", "c"))
-
-val urban_names = Map("a" -> "A", "b" -> "B", "c" -> "C", "x" -> "X", "y" -> "Y")
-
-assert(most_recommended(urban_recs, urban_names).toSet ==
-        Set(("A",2), ("B",1), ("C",1), ("X",1), ("Y",1)))
-
diff -r de59aa20a1dc -r ffce7b61b446 main_testing3/re.scala
--- a/main_testing3/re.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing3/re.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,19 +1,24 @@
 // Core Part about Regular Expression Matching
 //=============================================
 
-object CW8c {
+object M3 {
 
 // Regular Expressions
 abstract class Rexp
 case object ZERO extends Rexp
 case object ONE extends Rexp
 case class CHAR(c: Char) extends Rexp
-case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
-case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
-case class STAR(r: Rexp) extends Rexp 
+case class ALTs(rs: List[Rexp]) extends Rexp      // alternatives 
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp   // sequence
+case class STAR(r: Rexp) extends Rexp             // star
 
 // some convenience for typing in regular expressions
 
+
+//the usual binary choice can be defined in terms of ALTs
+def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2))
+
+
 import scala.language.implicitConversions    
 import scala.language.reflectiveCalls 
 
@@ -49,7 +54,7 @@
   case ZERO => false
   case ONE => true
   case CHAR(_) => false
-  case ALT(r1, r2) => nullable(r1) || nullable(r2)
+  case ALTs(rs) => rs.exists(nullable)
   case SEQ(r1, r2) => nullable(r1) && nullable(r2)
   case STAR(_) => true
 }
@@ -63,13 +68,22 @@
   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 ALTs(rs) => ALTs(rs.map(der(c, _)))
   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))
 }
 
+
+
+def flts(rs: List[Rexp]) : List[Rexp] = rs match {
+  case Nil => Nil
+  case ZERO::tl => flts(tl)
+  case ALTs(rs1)::rs2 => rs1 ::: flts(rs2)  
+  case r::rs => r :: flts(rs) 
+}
+
 // (3) Complete the simp function according to
 // the specification given in the coursework; this
 // function simplifies a regular expression from
@@ -77,11 +91,12 @@
 // expressions; however it does not simplify inside 
 // STAR-regular expressions.
 
+
 def simp(r: Rexp) : Rexp = r match {
-  case ALT(r1, r2) => (simp(r1), simp(r2)) match {
-    case (ZERO, r2s) => r2s
-    case (r1s, ZERO) => r1s
-    case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
+  case ALTs(rs) => (flts(rs.map(simp)).distinct) match {
+    case Nil => ZERO
+    case r::Nil => r  
+    case rs => ALTs(rs)
   }
   case SEQ(r1, r2) =>  (simp(r1), simp(r2)) match {
     case (ZERO, _) => ZERO
@@ -117,7 +132,7 @@
   case ZERO => 1
   case ONE => 1
   case CHAR(_) => 1
-  case ALT(r1, r2) => 1 + size(r1) + size (r2)
+  case ALTs(rs) => 1 + rs.map(size).sum
   case SEQ(r1, r2) => 1 + size(r1) + size (r2)
   case STAR(r1) => 1 + size(r1)
 }
@@ -132,16 +147,19 @@
 // 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
+//println(matcher(EVIL, "a" * 1000 ++ "b"))   // => true
+//println(matcher(EVIL, "a" * 1000))          // => false
 
 // size without simplifications
-//size(der('a', der('a', EVIL)))             // => 28
-//size(der('a', der('a', der('a', EVIL))))   // => 58
+//println(size(der('a', der('a', EVIL))))             // => 28
+//println(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
+//println(simp(der('a', der('a', EVIL))))          
+//println(simp(der('a', der('a', der('a', EVIL)))))
+
+//println(size(simp(der('a', der('a', EVIL)))))           // => 8
+//println(size(simp(der('a', der('a', der('a', EVIL)))))) // => 8
 
 // Python needs around 30 seconds for matching 28 a's with EVIL. 
 // Java 9 and later increase this to an "astonishing" 40000 a's in
@@ -155,11 +173,11 @@
   val start = System.nanoTime()
   for (j <- 1 to i) code
   val end = System.nanoTime()
-  (end - start)/(i * 1.0e9)
+  "%.5f".format((end - start)/(i * 1.0e9))
 }
 
 //for (i <- 0 to 5000000 by 500000) {
-//  println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + " secs.") 
+//  println(s"$i ${time_needed(2, matcher(EVIL, "a" * i))} secs.") 
 //}
 
 // another "power" test case 
@@ -169,7 +187,7 @@
 //
 //      SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)
 //
-//    where SEQ is nested 100 times.
+//    where SEQ is nested 50 times.
  
 
 
diff -r de59aa20a1dc -r ffce7b61b446 main_testing3/re_test.sh
--- a/main_testing3/re_test.sh	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing3/re_test.sh	Mon Nov 08 01:39:00 2021 +0000
@@ -120,7 +120,7 @@
   echo -e " simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO" >> $out
   echo -e " simp(ALT(ONE | ONE, ONE | ONE)) == ONE" >> $out
   echo -e " simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')" >> $out
-  echo -e " simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE | CHAR('a'), CHAR('a') | ONE)" >> $out
+  echo -e " simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a'))" >> $out
   if (scala_assert "re.scala" "re_test3.scala")
   then
     echo -e "  --> success" >> $out
diff -r de59aa20a1dc -r ffce7b61b446 main_testing3/re_test1.scala
--- a/main_testing3/re_test1.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing3/re_test1.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW8c._
+import M3._
 
 assert(nullable(ZERO) == false)
 assert(nullable(ONE) == true)
diff -r de59aa20a1dc -r ffce7b61b446 main_testing3/re_test2.scala
--- a/main_testing3/re_test2.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing3/re_test2.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW8c._
+import M3._
 
 assert(der('a', ZERO | ONE) == (ZERO | ZERO))
 assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE))
diff -r de59aa20a1dc -r ffce7b61b446 main_testing3/re_test3.scala
--- a/main_testing3/re_test3.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing3/re_test3.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW8c._
+import M3._
 
 
 assert(simp(ZERO | ONE) == ONE)
@@ -16,6 +16,6 @@
 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(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE | CHAR('a'), CHAR('a') | ONE))
+assert(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a')))
 
 
diff -r de59aa20a1dc -r ffce7b61b446 main_testing3/re_test4.scala
--- a/main_testing3/re_test4.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing3/re_test4.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW8c._
+import M3._
 
 val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
 
diff -r de59aa20a1dc -r ffce7b61b446 main_testing3/re_test5.scala
--- a/main_testing3/re_test5.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing3/re_test5.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW8c._ 
+import M3._ 
 val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
 
 assert(size(der('a', der('a', EVIL_urban))) == 28)
diff -r de59aa20a1dc -r ffce7b61b446 main_testing3/re_test6.scala
--- a/main_testing3/re_test6.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing3/re_test6.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW8c._
+import M3._
 
 val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
 
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight1.scala
--- a/main_testing4/knight1.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight1.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,7 +1,7 @@
 // Part 1 about finding and counting Knight's tours
 //==================================================
 
-object CW9a {   // for preparing the jar
+object M4a {   // for preparing the jar
 
 type Pos = (Int, Int)    // a position on a chessboard 
 type Path = List[Pos]    // a path...a list of positions
@@ -43,8 +43,6 @@
   List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),
        (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair(x, _))
 
-// 1 mark
-
 def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = 
   moves(x).filter(is_legal(dim, path, _))
 
@@ -62,7 +60,6 @@
 //assert(legal_moves(2, Nil, (0,0)) == List())
 //assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
 
-// 2 marks
 
 def tcount_tours(dim: Int, path: Path): Int = {
   if (path.length == dim * dim) 1
@@ -119,7 +116,6 @@
 }
 */
 
-// 1 mark
 
 def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
   case Nil => None
@@ -136,8 +132,6 @@
 //first(List((1, 0),(2, 0),(3, 0)), foo)
 
 
-// 1 mark
-
 def tfirst_tour(dim: Int, path: Path): Option[Path] = {
   if (path.length == dim * dim) Some(path)
   else
@@ -157,7 +151,7 @@
 
 // 15 secs for 8 x 8
 //val ts1 = time_needed(0,first_tour(8, List((0, 0))).get)
-//val ts1 = time_needed(0,first_tour(8, List((1, 1))).get)
+//??val ts1 = time_needed(0,first_tour(8, List((1, 1))).get)
 
 // no result for 4 x 4
 //val ts2 = time_needed(0, first_tour(4, List((0, 0))))
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight2.scala
--- a/main_testing4/knight2.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight2.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,7 +1,7 @@
-// Part 3 about finding a single tour using the Warnsdorf Rule
+// Part 2 about finding a single tour using the Warnsdorf Rule
 //=============================================================
 
-object CW9b {
+object M4b { // for preparing the jar
 
 type Pos = (Int, Int)
 type Path = List[Pos]
@@ -67,7 +67,6 @@
 def first_closed_tour_heuristic(dim: Int, path: Path) =
  time_needed(tfirst_closed_tour_heuristics(dim: Int, path: Path))
 
-
 // heuristic cannot be used to search for closed tours on 7 x 7 an beyond
 //for (dim <- 1 to 6) {
 //  val t = time_needed(0, first_closed_tour_heuristics(dim, List((dim / 2, dim / 2))))
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight3.scala
--- a/main_testing4/knight3.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight3.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,7 +1,7 @@
 // Part 3 about finding a single tour using the Warnsdorf Rule
 //=============================================================
 
-object CW9c { 
+object M4c { // for preparing the jar
 
 type Pos = (Int, Int)
 type Path = List[Pos]
@@ -60,4 +60,8 @@
 def tour_on_mega_board(dim: Int, path: Path) =
   time_needed(ttour_on_mega_board(dim: Int, path: Path))
 
+
+// testcases
+//print_board(70, tour_on_mega_board(70, List((0, 0))).get)
+
 }
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight_test1.scala
--- a/main_testing4/knight_test1.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight_test1.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW9a._
+import M4a._
 
 assert(is_legal(8, Nil, (3, 4)) == true)
 assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight_test2.scala
--- a/main_testing4/knight_test2.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight_test2.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,5 +1,5 @@
 
-import CW9a._
+import M4a._
 
 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)))
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight_test3.scala
--- a/main_testing4/knight_test3.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight_test3.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW9a._
+import M4a._
 
 //type Pos = (Int, Int)    // a position on a chessboard 
 //type Path = List[Pos]    // a path...a list of positions
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight_test4.scala
--- a/main_testing4/knight_test4.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight_test4.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW9a._
+import M4a._
 
 val f_urban = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None
 
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight_test5.scala
--- a/main_testing4/knight_test5.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight_test5.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW9a._
+import M4a._
 
 
 //type Pos = (Int, Int)    // a position on a chessboard 
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight_test6.scala
--- a/main_testing4/knight_test6.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight_test6.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW9b._
+import M4b._
 
 assert(ordered_moves(8, List((3,4), (3,2)), (1, 3)) == List((0,1), (0,5), (2,1), (2,5)))
 assert(ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2)))
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight_test7.scala
--- a/main_testing4/knight_test7.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight_test7.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW9b._
+import M4b._
 
 //type Pos = (Int, Int)
 //type Path = List[Pos]
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight_test8.scala
--- a/main_testing4/knight_test8.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight_test8.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW9b._
+import M4b._
 
 
 //type Pos = (Int, Int)
diff -r de59aa20a1dc -r ffce7b61b446 main_testing4/knight_test9.scala
--- a/main_testing4/knight_test9.scala	Mon Nov 08 01:16:13 2021 +0000
+++ b/main_testing4/knight_test9.scala	Mon Nov 08 01:39:00 2021 +0000
@@ -1,4 +1,4 @@
-import CW9c._
+import M4c._
 
 //type Pos = (Int, Int)
 //type Path = List[Pos]