--- a/core_testing1/collatz.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/core_testing1/collatz.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -1,51 +1,53 @@
 // Core Part 1 about the 3n+1 conjecture
-//==================================
+//============================================
+
+object C1 {
+
+// ADD YOUR CODE BELOW
+//======================
 
-// generate jar with
-//   > scala -d collatz.jar  collatz.scala
+// test1 7 Nov
+// test2
+// test3
+// test4
 
-object C1 { // for purposes of generating a jar
 
-def collatz(n: Long): Long =
+//(1) 
+def collatz(n: Long) : Long = 
   if (n == 1) 0 else
     if (n % 2 == 0) 1 + collatz(n / 2) else 
       1 + collatz(3 * n + 1)
 
 
+//(2) 
+//def collatz_max(bnd: Long) : (Long, Long) = {
+//  val all = for (i <- (1L to bnd)) yield (collatz(i), i)
+//  all.maxBy(_._1)
+//}
+
 def collatz_max(bnd: Long): (Long, Long) = {
   val all = for (i <- (1L to bnd)) yield (collatz(i), i)
   all.maxBy(_._1)
 }
 
-//collatz_max(1000000)
-
-
-/* some test cases
-val bnds = List(10, 100, 1000, 10000, 100000, 1000000)
-
-for (bnd <- bnds) {
-  val (steps, max) = collatz_max(bnd)
-  println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}")
-}
-
-*/
 
 
-def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0
+//(3)
+
+def is_pow_of_two(n: Long) : Boolean = (n & (n - 1)) == 0
 
-def is_hard(n: Long) : Boolean = is_pow(3 * n + 1)
+def is_hard(n: Long) : Boolean = is_pow_of_two(3 * n + 1)
 
-def last_odd(n: Long) : Long = 
-  if (is_hard(n)) n else
+def last_odd(n: Long) : Long = if (is_hard(n)) n else
     if (n % 2 == 0) last_odd(n / 2) else 
       last_odd(3 * n + 1)
 
-
-
-//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}")
-//for (i <- 1 to 100) println(s"$i: ${collatz(i)}")
-
 }
 
 
 
+// This template code is subject to copyright 
+// by King's College London, 2022. Do not 
+// make the template code public in any shape 
+// or form, and do not exchange it with other 
+// students under any circumstance.

Binary file cws/core_cw01.pdf has changed

Binary file cws/core_cw02.pdf has changed

Binary file cws/core_cw03.pdf has changed

Binary file cws/main_cw01.pdf has changed

Binary file cws/main_cw02.pdf has changed

Binary file cws/main_cw03.pdf has changed

Binary file cws/main_cw04.pdf has changed

Binary file cws/main_cw05.pdf has changed

--- a/main_testing3/re.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing3/re.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -1,5 +1,5 @@
 // Main Part 3 about Regular Expression Matching
-//=============================================
+//==============================================
 
 object M3 {
 
@@ -8,13 +8,15 @@
 case object ZERO extends Rexp
 case object ONE extends Rexp
 case class CHAR(c: Char) 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
+case class ALTs(rs: List[Rexp]) extends Rexp  // alternatives 
+case class SEQs(rs: List[Rexp]) extends Rexp  // sequences
+case class STAR(r: Rexp) extends Rexp         // star
 
 
-//the usual binary choice can be defined in terms of ALTs
+//the usual binary choice and binary sequence can be defined 
+//in terms of ALTs and SEQs
 def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2))
+def SEQ(r1: Rexp, r2: Rexp) = SEQs(List(r1, r2))
 
 // some convenience for typing in regular expressions
 import scala.language.implicitConversions    
@@ -41,83 +43,78 @@
   def ~ (r: String) = SEQ(s, r)
 }
 
-// (1) Complete the function nullable according to
-// the definition given in the coursework; this 
-// function checks whether a regular expression
-// can match the empty string and Returns a boolean
-// accordingly.
-
+// (1) 
 def nullable (r: Rexp) : Boolean = r match {
   case ZERO => false
   case ONE => true
   case CHAR(_) => false
   case ALTs(rs) => rs.exists(nullable)
-  case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+  case SEQs(rs) => rs.forall(nullable)
   case STAR(_) => true
 }
 
-// (2) Complete the function der according to
-// the definition given in the coursework; this
-// function calculates the derivative of a 
-// regular expression w.r.t. a character.
-
-def der (c: Char, r: Rexp) : Rexp = r match {
+// (2) 
+def der(c: Char, r: Rexp) : Rexp = r match {
   case ZERO => ZERO
   case ONE => ZERO
   case CHAR(d) => if (c == d) ONE else ZERO
   case 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 SEQs(Nil) => ZERO
+  case SEQs(r1::rs) => 
+    if (nullable(r1)) ALT(SEQs(der(c, r1)::rs), der(c, SEQs(rs)))
+    else SEQs(der(c, r1):: rs)
   case STAR(r1) => SEQ(der(c, r1), STAR(r1))
 }
 
 
-// (3) Implement the flatten function flts. It
-// deletes 0s from a list of regular expressions
-// and also 'spills out', or flattens, nested 
-// ALTernativeS.
+// (3) 
+def denest(rs: List[Rexp]) : List[Rexp] = rs match {
+  case Nil => Nil
+  case ZERO::tl => denest(tl)
+  case ALTs(rs1)::rs2 => rs1 ::: denest(rs2)  
+  case r::rs => r :: denest(rs) 
+}
 
-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) 
+// (4)
+def flts(rs: List[Rexp], acc: List[Rexp] = Nil) : List[Rexp] = rs match {
+  case Nil => acc
+  case ZERO::rs => ZERO::Nil
+  case ONE::rs => flts(rs, acc)
+  case SEQs(rs1)::rs => flts(rs, acc ::: rs1)
+  case r::rs => flts(rs, acc :+ r) 
 }
 
-
+// (5)
+def ALTs_smart(rs: List[Rexp]) : Rexp = rs match {
+  case Nil => ZERO
+  case r::Nil => r  
+  case rs => ALTs(rs)
+}
 
-// (4) Complete the simp function according to
-// the specification given in the coursework; this
-// function simplifies a regular expression from
-// the inside out, like you would simplify arithmetic 
-// expressions; however it does not simplify inside 
-// STAR-regular expressions.
+def SEQs_smart(rs: List[Rexp]) : Rexp = rs match {
+  case Nil => ONE
+  case ZERO::nil => ZERO
+  case r::Nil => r
+  case rs => SEQs(rs) 
+}
 
+// (6) 
 
 def simp(r: Rexp) : Rexp = r match {
-  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
-    case (_, ZERO) => ZERO
-    case (ONE, r2s) => r2s
-    case (r1s, ONE) => r1s
-    case (r1s, r2s) => SEQ(r1s, r2s)
-  }
+  case ALTs(rs) => 
+    ALTs_smart(denest(rs.map(simp)).distinct)
+  case SEQs(rs) => 
+    SEQs_smart(flts(rs.map(simp)))
   case r => r
 }
 
-simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE))
+//println("Simp tests")
+//println(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)))
+//println(simp(((CHAR('a') | ZERO) ~ ONE) | 
+//              (((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))))
 
-// (5) Complete the two functions below; the first 
-// calculates the derivative w.r.t. a string; the second
-// is the regular expression matcher taking a regular
-// expression and a string and checks whether the
-// string matches the regular expression.
+
+// (7) 
 
 def ders (s: List[Char], r: Rexp) : Rexp = s match {
   case Nil => r
@@ -127,43 +124,40 @@
 // main matcher function
 def matcher(r: Rexp, s: String) = nullable(ders(s.toList, r))
 
-// (6) Complete the size function for regular
-// expressions according to the specification 
-// given in the coursework.
-
+// (8) 
 
 def size(r: Rexp): Int = r match {
   case ZERO => 1
   case ONE => 1
   case CHAR(_) => 1
   case ALTs(rs) => 1 + rs.map(size).sum
-  case SEQ(r1, r2) => 1 + size(r1) + size (r2)
+  case SEQs(rs) => 1 + rs.map(size).sum
   case STAR(r1) => 1 + size(r1)
 }
 
 
 
 // some testing data
-
-//matcher(("a" ~ "b") ~ "c", "abc")  // => true
-//matcher(("a" ~ "b") ~ "c", "ab")   // => false
+/*
+println(matcher(("a" ~ "b") ~ "c", "abc"))  // => true
+println(matcher(("a" ~ "b") ~ "c", "ab"))   // => false
 
 // the supposedly 'evil' regular expression (a*)* b
-// val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
 
-//println(matcher(EVIL, "a" * 1000 ++ "b"))   // => true
-//println(matcher(EVIL, "a" * 1000))          // => false
+println(matcher(EVIL, "a" * 1000 ++ "b"))   // => true
+println(matcher(EVIL, "a" * 1000))          // => false
 
 // size without simplifications
-//println(size(der('a', der('a', EVIL))))             // => 28
-//println(size(der('a', der('a', der('a', EVIL)))))   // => 58
+println(size(der('a', der('a', EVIL))))             // => 36
+println(size(der('a', der('a', der('a', EVIL)))))   // => 83
 
 // size with simplification
-//println(simp(der('a', der('a', EVIL))))          
-//println(simp(der('a', der('a', der('a', EVIL)))))
+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
+println(size(simp(der('a', der('a', EVIL)))))           // => 7
+println(size(simp(der('a', der('a', der('a', EVIL)))))) // => 7
 
 // 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
@@ -171,7 +165,7 @@
 //
 // Lets see how long it takes to match strings with 
 // 5 Million a's...it should be in the range of a 
-// couple of seconds.
+// few seconds.
 
 def time_needed[T](i: Int, code: => T) = {
   val start = System.nanoTime()
@@ -180,19 +174,20 @@
   "%.5f".format((end - start)/(i * 1.0e9))
 }
 
-//for (i <- 0 to 5000000 by 500000) {
-//  println(s"$i ${time_needed(2, matcher(EVIL, "a" * i))} secs.") 
-//}
+for (i <- 0 to 5000000 by 500000) {
+  println(s"$i ${time_needed(2, matcher(EVIL, "a" * i))} secs.") 
+}
 
 // another "power" test case 
-//simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(100).next) == ONE
+println(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(100).next()) == ONE)
 
 // the Iterator produces the rexp
 //
 //      SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)
 //
-//    where SEQ is nested 50 times.
- 
+//    where SEQ is nested 100 times.
+*/ 
 
 
 }
+

--- a/main_testing3/re_test.sh	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing3/re_test.sh	Tue Nov 08 00:27:47 2022 +0000
@@ -53,7 +53,7 @@
 
     if (scala_vars re.scala)
     then
-	echo -e "   --> FAIL (make triple-sure your program conforms to the required format)" >> $out 
+	echo -e "  --> FAIL (make triple-sure your program conforms to the required format)" >> $out 
 	tsts=$(( 1 ))
     else
 	echo -e "  --> passed" >> $out
@@ -89,6 +89,8 @@
   echo -e " nullable(ONE ~  ONE) == true" >> $out
   echo -e " nullable(ONE ~ CHAR('a')) == false" >> $out
   echo -e " nullable(STAR(ZERO)) == true" >> $out
+  echo -e " nullable(ALTs(List(ONE, CHAR('a'), ZERO))) == true" >> $out
+  echo -e " nullable(SEQs(List(ONE, ALTs(List(ONE, CHAR('a'), ZERO)), STAR(ZERO)))) == true" >> $out
   
   if (scala_assert "re.scala" "re_test1.scala")
   then
@@ -99,12 +101,12 @@
 fi
 
 
-
 if [ $tsts -eq 0 ]
 then
   echo -e " der('a', ZERO | ONE) == (ZERO | ZERO)" >> $out
   echo -e " der('a', (CHAR('a') | ONE) ~ CHAR('a')) ==" >> $out
   echo -e "                 ALT((ONE | ZERO) ~ CHAR('a'), ONE)" >> $out
+  echo -e " der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a')" >> $out
   echo -e " der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))" >> $out
   echo -e " der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))" >> $out
   
@@ -117,7 +119,6 @@
 fi
 
 
-
 if [ $tsts -eq 0 ]
 then
   echo -e " simp(ZERO | ONE) == ONE" >> $out
@@ -136,6 +137,8 @@
   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'))" >> $out
+  echo -e " simp(ALTs(Nil)) == ZERO" >> $out
+  echo -e " simp(SEQs(CHAR('a'))) == CHAR('a')" >> $out
   if (scala_assert "re.scala" "re_test3.scala")
   then
     echo -e "  --> success" >> $out
@@ -147,6 +150,55 @@
 
 if [ $tsts -eq 0 ]
 then
+    echo -e " denest(List(ONE, ZERO, ALTs(List(ONE, CHAR('a'))))) == List(ONE, ONE, CHAR('a'))" >> $out
+    echo -e " denest(List(ONE ~ ONE, ZERO, ZERO | ONE)) == List(ONE ~ ONE, ZERO, ONE)" >> $out
+  
+  if (scala_assert "re.scala" "re_test4.scala")
+  then
+    echo -e "  --> success" >> $out
+  else
+    echo -e "  --> \n ONE TEST FAILED\n" >> $out   
+  fi
+fi
+
+
+if [ $tsts -eq 0 ]
+then
+    echo -e " flts(List(CHAR('a'), ZERO, ONE), Nil) == List(ZERO)" >> $out
+    echo -e " flts(List(CHAR('a'), ONE, ONE, CHAR('b')), Nil) == List(CHAR('a'), CHAR('b'))" >> $out
+    echo -e " flts(List(ONE ~ CHAR('a'), CHAR('b') ~ ONE), Nil) == List(ONE, CHAR('a'), CHAR('b'), ONE)" >> $out
+  
+  if (scala_assert "re.scala" "re_test5.scala")
+  then
+    echo -e "  --> success" >> $out
+  else
+    echo -e "  --> \n ONE TEST FAILED\n" >> $out   
+  fi
+fi
+
+
+if [ $tsts -eq 0 ]
+then
+    echo -e " SEQs_smart(Nil) == ONE" >> $out
+    echo -e " SEQs_smart(List(ZERO)) == ZERO" >> $out
+    echo -e " SEQs_smart(List(CHAR('a'))) == CHAR('a')" >> $out
+    echo -e " SEQs_smart(List(ONE ~ ONE)) == ONE ~ ONE" >> $out
+    echo -e " SEQs_smart(List(ONE, ONE)) == SEQs(List(ONE, ONE))" >> $out
+    echo -e " ALTs_smart(Nil) == ZERO" >> $out
+    echo -e " ALTs_smart(List(ONE ~ ONE)) == ONE ~ ONE)" >> $out
+    echo -e " ALTs_smart(List(ZERO, ZERO)) == ALTs(List(ZERO, ZERO))" >> $out
+  
+  if (scala_assert "re.scala" "re_test6.scala")
+  then
+    echo -e "  --> success" >> $out
+  else
+    echo -e "  --> \n ONE TEST FAILED\n" >> $out   
+  fi
+fi
+
+
+if [ $tsts -eq 0 ]
+then
   echo -e " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" >> $out
   echo -e " ders(\"aaaaa\".toList, EVIL) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))" >> $out
   echo -e " ders(List('b'), EVIL) == ONE" >> $out
@@ -161,7 +213,7 @@
   echo -e " matcher(ONE | CHAR('a'), \"\") == true" >> $out
   echo -e " matcher(ONE | CHAR('a'), \"a\") == true" >> $out
   
-  if (scala_assert "re.scala" "re_test4.scala")
+  if (scala_assert "re.scala" "re_test7.scala")
   then
     echo -e "  --> success" >> $out
   else
@@ -173,11 +225,12 @@
 if [ $tsts -eq 0 ]
 then
   echo -e " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" >> $out  
-  echo -e " size(der('a', der('a', EVIL))) == 28" >> $out
-  echo -e " size(der('a', der('a', der('a', EVIL)))) == 58" >> $out
-  echo -e " size(ders(\"aaaaaa\".toList, EVIL)) == 8" >> $out
+  echo -e " size(der('a', der('a', EVIL))) == 36" >> $out
+  echo -e " size(der('a', der('a', der('a', EVIL)))) == 83" >> $out
+  echo -e " size(ders(\"aaaaaa\".toList, EVIL)) == 7" >> $out
+  echo -e " size(ders((\"a\" * 50).toList, EVIL)) == 7" >> $out
   
-  if (scala_assert "re.scala" "re_test5.scala")
+  if (scala_assert "re.scala" "re_test8.scala")
   then
     echo -e "  --> success" >> $out
   else

--- a/main_testing3/re_test1.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing3/re_test1.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -8,4 +8,6 @@
 assert(nullable(ONE ~  ONE) == true)
 assert(nullable(ONE ~ CHAR('a')) == false)
 assert(nullable(STAR(ZERO)) == true)
+assert(nullable(ALTs(List(ONE, CHAR('a'), ZERO))) == true)
+assert(nullable(SEQs(List(ONE, ALTs(List(ONE, CHAR('a'), ZERO)), STAR(ZERO)))) == true)
 

--- a/main_testing3/re_test2.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing3/re_test2.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -1,12 +1,12 @@
 import M3._
 
-assert(der('a', ZERO | ONE) == (ZERO | ZERO))
-assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE))
+assert(der('a', ZERO | ONE) == ALT(ZERO, ZERO))
+assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALTs(List(SEQ(ALT(ONE, ZERO), CHAR('a')), SEQs(List(ONE)))))
 assert(der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a'))
 assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a'))))
 assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a'))))
 
-
+/*
 val r0_urban = "a" ~ "b" ~ "c"
 assert(der('a', r0_urban) == (ONE ~ "b") ~ "c")
 assert(der('b', r0_urban) == (ZERO ~ "b") ~ "c")
@@ -23,3 +23,4 @@
 assert(der('a', r2_urban) == ((((ZERO ~ "b") | ZERO) ~ "c") | ZERO))
 assert(der('b', r2_urban) == ((((ZERO ~ "b") | ZERO) ~ "c") | ZERO))
 assert(der('c', r2_urban) == ((((ZERO ~ "b") | ZERO) ~ "c") | ONE))
+*/

--- a/main_testing3/re_test3.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing3/re_test3.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -17,5 +17,6 @@
 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')))
+assert(simp(ALTs(Nil)) == ZERO)
+assert(simp(SEQs(List(CHAR('a')))) == CHAR('a'))
 
-

--- a/main_testing3/re_test4.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing3/re_test4.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -1,19 +1,5 @@
 import M3._
 
-val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-
-assert(ders(("a" * 5).toList, EVIL_urban) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b')))
-assert(ders(List('b'), EVIL_urban) == ONE)
-assert(ders(List('b','b'), EVIL_urban) == ZERO)
-assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true)
-assert(matcher(EVIL_urban, "a" * 50 ++ "b") == true)
-assert(matcher(EVIL_urban, "a" * 50) == false)
-assert(matcher(EVIL_urban, "b") == true)
-assert(matcher(EVIL_urban, "bb") == false)
-assert(matcher("abc", "abc") == true)
-assert(matcher("abc", "ab") == false)
-assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true)
-assert(matcher(ONE, "") == true)
-assert(matcher(ZERO, "") == false)
-assert(matcher(ONE | CHAR('a'), "") == true)
-assert(matcher(ONE | CHAR('a'), "a") == true)
+assert(denest(List(ONE, ZERO, ALTs(List(ONE, CHAR('a'))))) 
+   == List(ONE, ONE, CHAR('a')))
+assert(denest(List(ONE ~ ONE, ZERO, ZERO | ONE)) == List(ONE ~ ONE, ZERO, ONE))

--- a/main_testing3/re_test5.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing3/re_test5.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -1,8 +1,6 @@
-import M3._ 
-val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+import M3._
 
-assert(size(der('a', der('a', EVIL_urban))) == 28)
-assert(size(der('a', der('a', der('a', EVIL_urban)))) == 58)
+assert(flts(List(CHAR('a'), ZERO, ONE), Nil) == List(ZERO))
+assert(flts(List(CHAR('a'), ONE, ONE, CHAR('b')), Nil) == List(CHAR('a'), CHAR('b')))
+assert(flts(List(ONE ~ CHAR('a'), CHAR('b') ~ ONE), Nil) == List(ONE, CHAR('a'), CHAR('b'), ONE))
 
-assert(size(ders("aaaaaa".toList, EVIL_urban)) == 8)
-assert(size(ders(("a" * 50).toList, EVIL_urban)) == 8)

--- a/main_testing3/re_test6.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing3/re_test6.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -1,9 +1,10 @@
 import M3._
 
-val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-
-
-assert(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE)
-assert(simp(Iterator.iterate(ONE:Rexp)(r => ALT(r, r)).drop(20).next) == ONE)
-assert(matcher(EVIL_urban, "a" * 1000000) == false)
-assert(matcher(EVIL_urban, "a" * 1000000 ++ "b") == true)
+assert(SEQs_smart(Nil) == ONE)
+assert(SEQs_smart(List(ZERO)) == ZERO)
+assert(SEQs_smart(List(CHAR('a'))) == CHAR('a'))
+assert(SEQs_smart(List(ONE ~ ONE)) == ONE ~ ONE)
+assert(SEQs_smart(List(ONE, ONE)) == SEQs(List(ONE, ONE)))
+assert(ALTs_smart(Nil) == ZERO)
+assert(ALTs_smart(List(ONE ~ ONE)) == ONE ~ ONE)
+assert(ALTs_smart(List(ZERO, ZERO)) == ALTs(List(ZERO, ZERO)))

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing3/re_test7.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -0,0 +1,19 @@
+import M3._
+
+val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+assert(ders(("a" * 5).toList, EVIL_urban) == SEQs(List(STAR(CHAR('a')), STAR(STAR(CHAR('a'))), CHAR('b'))))
+assert(ders(List('b'), EVIL_urban) == ONE)
+assert(ders(List('b','b'), EVIL_urban) == ZERO)
+assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true)
+assert(matcher(EVIL_urban, "a" * 50 ++ "b") == true)
+assert(matcher(EVIL_urban, "a" * 50) == false)
+assert(matcher(EVIL_urban, "b") == true)
+assert(matcher(EVIL_urban, "bb") == false)
+assert(matcher("abc", "abc") == true)
+assert(matcher("abc", "ab") == false)
+assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true)
+assert(matcher(ONE, "") == true)
+assert(matcher(ZERO, "") == false)
+assert(matcher(ONE | CHAR('a'), "") == true)
+assert(matcher(ONE | CHAR('a'), "a") == true)

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing3/re_test8.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -0,0 +1,8 @@
+import M3._ 
+val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+assert(size(der('a', der('a', EVIL_urban))) == 36)
+assert(size(der('a', der('a', der('a', EVIL_urban)))) == 83)
+
+assert(size(ders("aaaaaa".toList, EVIL_urban)) == 7)
+assert(size(ders(("a" * 50).toList, EVIL_urban)) == 7)

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing3/re_test9.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -0,0 +1,9 @@
+import M3._
+
+val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+
+assert(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE)
+assert(simp(Iterator.iterate(ONE:Rexp)(r => ALT(r, r)).drop(20).next) == ONE)
+assert(matcher(EVIL_urban, "a" * 1000000) == false)
+assert(matcher(EVIL_urban, "a" * 1000000 ++ "b") == true)

--- a/main_testing4/knight1.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing4/knight1.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -1,119 +1,13 @@
-// Main Part 4 about finding Knight's tours
-//==========================================
-import scala.annotation.tailrec
-
-
-object M4a {
+// Part 1 about finding and counting Knight's tours
+//==================================================
 
-// If you need any auxiliary functions, feel free to 
-// implement them, but do not make any changes to the
-// templates below. Also have a look whether the functions
-// at the end of the file are of any help.
-
-
+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
 
-//(1) Complete the function that tests whether the position x
-//    is inside the board and not yet element in the path.
 
-def is_legal(dim: Int, path: Path, x: Pos) : Boolean = {
-  (x._1 < dim) && (x._2 < dim) && (!path.contains(x))
-}
-
-
-
-//(2) Complete the function that calculates for a position x
-//    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] = {
-    val movesets = 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)
-  )
-  movesets.filter(is_legal(dim, path, _))
-}
-
-
-//some testcases
-//
-//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)))
-
-
-//(3) 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 = {
-  if (dim <= 4) 0 else {
-    if (path.length >= (dim * dim)) 1 else {
-      val movesets = legal_moves(dim, path, path.head)
-      (for (move <- movesets) yield count_tours(dim, move :: path)).sum
-    }
-  }
-}
-
-def enum_tours(dim: Int, path: Path) : List[Path] = {
-  if (dim <= 4) Nil else {
-    if (path.length >= (dim * dim)) List(path) else {
-      val movesets = legal_moves(dim, path, path.head)
-      (for (move <- movesets) yield enum_tours(dim, move :: path)).flatten
-    }
-  }
-}
-
-
-//(4) Implement a first-function that finds the first 
-//    element, say x, in the list xs where f is not None. 
-//    In that case Return f(x), otherwise None. If possible,
-//    calculate f(x) only once.
-
-@tailrec
-def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = {
-  xs match {
-    case Nil => None
-    case head :: rest => {
-      val result = f(head)
-      if (result.isEmpty) first(rest, f) else result
-    }
-  }
-}
-
-
-// testcases
-//
-//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
-//
-//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)   // Some(List((4,0)))
-//first(List((1, 0),(2, 0),(3, 0)), foo)          // None
-
-
-//(5) Implement a function that uses the first-function from (4) for
-//    trying out onward moves, and searches recursively for a
-//    knight tour on a dim * dim-board.
-
-def first_tour(dim: Int, path: Path) : Option[Path] = ???
- 
-
-
-/* Helper functions
-
-
-// for measuring time
+// for measuring time in the JAR
 def time_needed[T](code: => T) : T = {
   val start = System.nanoTime()
   val result = code
@@ -122,14 +16,6 @@
   result
 }
 
-// can be called for example with
-//
-//     time_needed(count_tours(dim, List((0, 0))))
-//
-// in order to print out the time that is needed for 
-// running count_tours
-
-
 // for printing a board
 def print_board(dim: Int, path: Path): Unit = {
   println()
@@ -141,7 +27,145 @@
   } 
 }
 
+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)
 
+// testcases
+//assert(is_legal(8, Nil, (3, 4)) == true)
+//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false)
+//assert(is_legal(2, Nil, (0, 0)) == true)
+
+
+def add_pair(x: Pos, y: Pos): Pos = 
+  (x._1 + y._1, x._2 + y._2)
+
+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, _))
+
+
+
+// testcases
+//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)))
+//assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0)))
+//assert(legal_moves(1, Nil, (0,0)) == List())
+//assert(legal_moves(2, Nil, (0,0)) == List())
+//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))
+
+
+def tcount_tours(dim: Int, path: Path): Int = {
+  if (path.length == dim * dim) 1
+  else 
+    (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum
+}
+
+def count_tours(dim: Int, path: Path) =
+  time_needed(tcount_tours(dim: Int, path: Path))
+
+
+def tenum_tours(dim: Int, path: Path): List[Path] = {
+  if (path.length == dim * dim) List(path)
+  else 
+    (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten
+}
+
+def enum_tours(dim: Int, path: Path) =
+  time_needed(tenum_tours(dim: Int, path: Path))
+
+// test cases
+
+/*
+def count_all_tours(dim: Int) = {
+  for (i <- (0 until dim).toList; 
+       j <- (0 until dim).toList) yield count_tours(dim, List((i, j)))
+}
+
+def enum_all_tours(dim: Int): List[Path] = {
+  (for (i <- (0 until dim).toList; 
+        j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten
+}
+
+
+println("Number of tours starting from (0, 0)")
+
+for (dim <- 1 to 5) {
+  println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0)))))
+}
+
+println("Number of tours starting from all fields")
+
+for (dim <- 1 to 5) {
+  println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim)))
+}
+
+for (dim <- 1 to 5) {
+  val ts = enum_tours(dim, List((0, 0)))
+  println(s"${dim} x ${dim} ")   
+  if (ts != Nil) {
+    print_board(dim, ts.head)
+    println(ts.head)
+  }
+}
 */
 
+
+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)
+  }
 }
+
+// test cases
+//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
+//
+//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo)
+//first(List((1, 0),(2, 0),(3, 0)), foo)
+
+
+def tfirst_tour(dim: Int, path: Path): Option[Path] = {
+  if (path.length == dim * dim) Some(path)
+  else
+    first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path))
+}
+
+def first_tour(dim: Int, path: Path) = 
+  time_needed(tfirst_tour(dim: Int, path: Path))
+
+
+/*
+for (dim <- 1 to 8) {
+  val t = first_tour(dim, List((0, 0)))
+  println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" }))
+}
+*/
+
+// 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)
+
+// no result for 4 x 4
+//val ts2 = time_needed(0, first_tour(4, List((0, 0))))
+
+// 0.3 secs for 6 x 6
+//val ts3 = time_needed(0, first_tour(6, List((0, 0))))
+
+// 15 secs for 8 x 8
+//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get))
+
+
+
+
+
+}
+
+

--- a/main_testing4/knight3.scala	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing4/knight3.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -64,4 +64,10 @@
 // testcases
 //print_board(70, tour_on_mega_board(70, List((0, 0))).get)
 
+
+
 }
+
+
+//val dim = 30 //75
+//M4c.print_board(dim, M4c.tour_on_mega_board(dim, List((0, 0))).get)

--- a/main_testing4/knight_test.sh	Thu Nov 03 11:30:09 2022 +0000
+++ b/main_testing4/knight_test.sh	Tue Nov 08 00:27:47 2022 +0000
@@ -72,65 +72,65 @@
 
 ### knight1 test
 
-#if [ $tsts1 -eq 0 ]
-#then
-#    #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
-#    echo -e " is_legal(8, Nil, (3, 4)) == true " >> $out
-#    echo -e " is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false " >> $out
-#    echo -e " is_legal(2, Nil, (0, 0)) == true" >> $out                          
-#
-#    if (scala_assert "knight1.scala" "knight_test1.scala")
-#    then
-#        echo -e "  --> success" >> $out
-#    else
-#        echo -e "  --> \n ONE TEST FAILED\n" >> $out
-#    fi
-#fi
+if [ $tsts1 -eq 0 ]
+then
+    #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
+    echo -e " is_legal(8, Nil, (3, 4)) == true " >> $out
+    echo -e " is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false " >> $out
+    echo -e " is_legal(2, Nil, (0, 0)) == true" >> $out                          
+
+    if (scala_assert "knight1.scala" "knight_test1.scala")
+    then
+        echo -e "  --> success" >> $out
+    else
+        echo -e "  --> \n ONE TEST FAILED\n" >> $out
+    fi
+fi
 
 ### knight2 test
 
-#if [ $tsts1 -eq 0 ]
-#then
-#  #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
-#  echo -e " 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 -e " legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))" >> $out
-#  echo -e " 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 -e " legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))" >> $out
-#  echo -e " legal_moves(1, Nil, (0,0)) == Nil" >> $out
-#  echo -e " legal_moves(2, Nil, (0,0)) == Nil" >> $out
-#  echo -e " legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))" >> $out
-#  
-#  if (scala_assert "knight1.scala" "knight_test2.scala")
-#  then
-#    echo -e "  --> success" >> $out
-#  else
-#    echo -e "  --> \n ONE TEST FAILED\n" >> $out
-#  fi
-#fi
+if [ $tsts1 -eq 0 ]
+then
+  #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
+  echo -e " 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 -e " legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))" >> $out
+  echo -e " 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 -e " legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))" >> $out
+  echo -e " legal_moves(1, Nil, (0,0)) == Nil" >> $out
+  echo -e " legal_moves(2, Nil, (0,0)) == Nil" >> $out
+  echo -e " legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))" >> $out
+  
+  if (scala_assert "knight1.scala" "knight_test2.scala")
+  then
+    echo -e "  --> success" >> $out
+  else
+    echo -e "  --> \n ONE TEST FAILED\n" >> $out
+  fi
+fi
 
 
 ### knight3 test
 
-#if [ $tsts1 -eq 0 ]
-#then
-#  #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
-#  echo -e " count_tours from every position on the board" >> $out
-#  echo -e " dim = 1: 1" >> $out
-#  echo -e "       2: 0,0,0,0" >>  $out
-#  echo -e "       3: 0,0,0,0,0,0,0,0,0" >>  $out
-#  echo -e "       4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" >> $out
-#  #echo -e "       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 -e " enum_tours(5, List((0,0)) ) == 304 and all correct?" >> $out
-#  echo -e " enum_tours(5, List((0,1)) ) == 0" >> $out
-#  echo -e " enum_tours(5, List((0,2)) ) == 56 and all correct?" >> $out
-#  
-#  if (scala_assert "knight1.scala" "knight_test3.scala") 
-#  then
-#    echo -e "  --> success" >> $out
-#  else
-#    echo -e "  --> \n ONE TEST FAILED\n" >> $out
-#  fi
-#fi
+if [ $tsts1 -eq 0 ]
+then
+  #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out
+  echo -e " count_tours from every position on the board" >> $out
+  echo -e " dim = 1: 1" >> $out
+  echo -e "       2: 0,0,0,0" >>  $out
+  echo -e "       3: 0,0,0,0,0,0,0,0,0" >>  $out
+  echo -e "       4: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0" >> $out
+  #echo -e "       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 -e " enum_tours(5, List((0,0)) ) == 304 and all correct?" >> $out
+  echo -e " enum_tours(5, List((0,1)) ) == 0" >> $out
+  echo -e " enum_tours(5, List((0,2)) ) == 56 and all correct?" >> $out
+  
+  if (scala_assert "knight1.scala" "knight_test3.scala")
+  then
+    echo -e "  --> success" >> $out
+  else
+    echo -e "  --> \n ONE TEST FAILED\n" >> $out
+  fi
+fi
 
 ### knight4 test
 
@@ -278,7 +278,7 @@
 
     if (scala_vars knight3.scala)
     then
-	echo "  --> Fail (make triple-sure your program conforms to the required format)xsxs" >> $out
+	echo "  --> Fail (make triple-sure your program conforms to the required format)" >> $out
 	tsts3=$(( 1 ))
     else
 	echo "  --> passed" >> $out
@@ -300,3 +300,50 @@
   fi
 fi
 
+
+echo -e "" >> $out
+echo -e "" >> $out
+
+
+
+# compilation test
+   
+echo "knight4.scala runs?" >> $out
+
+if (scala_compile knight4.scala)
+then
+    echo "  --> passed" >> $out
+    tsts4=$(( 0 ))
+else
+    echo -e "  --> SCALA DID NOT RUN KNIGHT4.SCALA\n" >> $out  
+    tsts4=$(( 1 )) 
+fi
+
+# knights4: purity test
+#
+if  [ $tsts4 -eq 0 ]
+then 
+    echo -e "knight4.scala does not contain vars, returns, Arrays, ListBuffers etc?" >> $out
+
+    if (scala_vars knight4.scala)
+    then
+	echo "  --> Fail (make triple-sure your program conforms to the required format)" >> $out
+	tsts4=$(( 1 ))
+    else
+	echo "  --> passed" >> $out
+	tsts4=$(( 0 )) 
+    fi
+fi
+
+if [ $tsts4 -eq 0 ]
+then
+  #echo -e "For testing needs to take 10 seconds or less to execute: " >> $out  
+  echo -e " " >> $out
+  
+  if (scala_assert "knight4.scala" "knight_test10.scala")
+  then
+      echo -e "  --> success" >> $out
+  else
+      echo -e "  --> \n ONE TEST FAILED\n" >> $out 
+  fi
+fi

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main_testing4/knight_test10.scala	Tue Nov 08 00:27:47 2022 +0000
@@ -0,0 +1,29 @@
+import M4d._
+
+//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
+}
+
+
+val ts70 = tour_on_mega_board(70, List((0,0))).get
+assert(correct_urban(70)(ts70) == true)
+