--- a/main_templates3/re.scala	Sat Oct 08 00:30:51 2022 +0100
+++ b/main_templates3/re.scala	Tue Nov 01 15:03:48 2022 +0000
@@ -1,23 +1,24 @@
 // Main Part 3 about Regular Expression Matching
-//=============================================
+//==============================================
 
 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 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 regular expressions
-
 import scala.language.implicitConversions    
 import scala.language.reflectiveCalls 
 
@@ -42,92 +43,77 @@
   def ~ (r: String) = SEQ(s, r)
 }
 
-
+// examples for the implicits:
 // ALT(CHAR('a'), CHAR('b'))
-// val reg : Rexp = "a" | "b" 
-
+// val areg : Rexp = "a" | "b"
 
-// (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.
-
-def nullable (r: Rexp) : Boolean = ???
-
-
-// (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 = ???
+// SEQ(CHAR('a'), CHAR('b')) 
+// val sreg : Rexp = "a" ~ "b"
 
 
-// (3) Implement the flatten function flts. It
-// deletes 0s from a list of regular expressions
-// and also 'spills out', or flattens, nested 
-// ALTernativeS.
+// ADD YOUR CODE BELOW
+//======================
 
-def flts(rs: List[Rexp]) : List[Rexp] = ???
+// (1)
+def nullable (r: Rexp) : Boolean = ???
 
-
+// (2) 
+def der (c: Char, r: Rexp) : Rexp = ???
 
-// (4) Complete the simp function according to
-// the specification given in the coursework description; 
-// 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. Use the _.distinct and 
-// flts functions.
+// (3) 
+def denest(rs: List[Rexp]) : List[Rexp] = ???
+
+// (4)
+def flts(rs: List[Rexp], acc: List[Rexp] = Nil) : List[Rexp] = ???
 
+// (5)
+def ALTs_smart(rs: List[Rexp]) : Rexp = ???
+def SEQs_smart(rs: List[Rexp]) : Rexp = ???
+
+// (6)
 def simp(r: Rexp) : Rexp = ???
 
-
-// (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 = ???
-
 def matcher(r: Rexp, s: String): Boolean = ???
 
-
-// (6) Complete the size function for regular
-// expressions according to the specification 
-// given in the coursework.
-
+// (8) 
 def size(r: Rexp): Int = ???
 
 
-// some testing data
-
+// Some testing data
+//===================
 /*
+
+simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE))   // => ALTs(List(ONE, CHAR(a)))
+simp(((CHAR('a') | ZERO) ~ ONE) | 
+     (((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO)))   // => CHAR(a)
+
+matcher(("a" ~ "b") ~ "c", "ab")   // => false
 matcher(("a" ~ "b") ~ "c", "abc")  // => true
-matcher(("a" ~ "b") ~ "c", "ab")   // => false
+
 
 // the supposedly 'evil' regular expression (a*)* b
 val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
 
+matcher(EVIL, "a" * 1000)          // => false
 matcher(EVIL, "a" * 1000 ++ "b")   // => true
-matcher(EVIL, "a" * 1000)          // => false
+
 
 // size without simplifications
-size(der('a', der('a', EVIL)))             // => 28
-size(der('a', der('a', der('a', EVIL))))   // => 58
+size(der('a', der('a', EVIL)))             // => 36
+size(der('a', der('a', der('a', EVIL))))   // => 83
 
 // size with simplification
-size(simp(der('a', der('a', EVIL))))           // => 8
-size(simp(der('a', der('a', der('a', EVIL))))) // => 8
+size(simp(der('a', der('a', EVIL))))           // => 7
+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
 // 30 seconds.
 //
 // Lets see how long it really takes to match strings with 
-// 5 Million a's...it should be in the range of a couple
+// 5 Million a's...it should be in the range of a few
 // of seconds.
 
 def time_needed[T](i: Int, code: => T) = {