--- a/template3/bf.scala Thu Dec 07 12:04:31 2017 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,151 +0,0 @@
-// Part 2 about an Interpreter for the Brainf*** language
-//========================================================
-
-object CW8b {
-
-type Mem = Map[Int, Int]
-
-// (2a) Complete the functions for safely reading
-// and writing brainf*** memory. Safely read should
-// Return the value stored in the Map for a given memory
-// pointer, if it exists; otherwise it Returns 0. The
-// writing function generates a new Map with the
-// same data, except at the given memory pointer the
-// value v is stored.
-
-
-//def sread(mem: Mem, mp: Int) : Int = ...
-
-//def write(mem: Mem, mp: Int, v: Int) : Mem = ...
-
-
-// (2b) Implement the two jumping instructions in the
-// brainf*** language. In jumpRight, given a program and
-// a program counter move the counter to the right
-// until the command after the *matching* ]-command. Similarly,
-// jumpLeft implements the move to the left to just after
-// the *matching* [-command. The levels are used to find the
-// *matching* bracket.
-
-//def jumpRight(prog: String, pc: Int, level: Int) : Int = ...
-
-//def jumpLeft(prog: String, pc: Int, level: Int) : Int = ...
-
-
-
-// (2c) Complete the run function that interprets (runs) a brainf***
-// program: the arguments are a program, a program counter,
-// a memory counter and a brainf*** memory. It Returns the
-// memory at the stage when the execution of the brainf*** program
-// finishes. The interpretation finishes once the program counter
-// pc is pointing to something outside the program string.
-// If the pc points to a character inside the program, the pc,
-// memory pointer and memory need to be updated according to
-// rules of the brainf*** language. Then, recursively, the run
-// function continues with the command at the new program
-// counter.
-//
-// Implement the start function that calls run with the program
-// counter and memory counter set to 0.
-
-//def run(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ...
-
-//def start(prog: String, mem: Mem) = ...
-
-
-
-
-
-
-// some sample bf programs collected from the Internet
-//==================================================
-
-
-/*
-// first some contrived (small) programs
-
-// clears the 0-cell
-start("[-]", Map(0 -> 100))
-
-// copies content of the 0-cell to 1-cell
-start("[->+<]", Map(0 -> 10))
-
-// copies content of the 0-cell to 2-cell and 4-cell
-start("[>>+>>+<<<<-]", Map(0 -> 42))
-
-start("+++[>+++++<-]", Map(0 -> 10))
-
-
-// prints out numbers 0 to 9
-start("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""", Map())
-
-
-// some more "useful" programs
-
-// hello world program 1
-start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
- ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map())
-
-// hello world program 2
-start("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+
- +.<<+++++++++++++++.>.+++.------.--------.>+.>.""", Map())
-
-
-// draws the Sierpinski triangle
-start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
- ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
- ]>.>+[>>]>+]""", Map())
-
-//Fibonacci numbers below 100
-start("""+++++++++++
- >+>>>>++++++++++++++++++++++++++++++++++++++++++++
- >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
- +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
- <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
- -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
- >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
- +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
- ++++++++++++++++++++++++++++++++++++++++++++.[-]<<
- <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
- [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", Map())
-
-
-//outputs the square numbers up to 10000
-start("""++++[>+++++<-]>[<+++++>-]+<+[
- >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
- >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
- <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""", Map())
-
-
-//Collatz numbers (need to be typed in)
-start(""">,[[----------[
- >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]
- ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[
- <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]
- >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]
- >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>
- ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""", Map())
-
-
-// infinite Collatz (never stops)
-start(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[<
- <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++
- +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+<
- [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>->
- [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[
- <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+
- ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<
- +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<-
- ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<-
- >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>
- -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++
- +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[<
- <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++
- +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-<
- <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>-
- [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""", Map())
-
-
-*/
-
-}
--- a/template3/re.scala Thu Dec 07 12:04:31 2017 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,127 +0,0 @@
-// Part 1 about Regular Expression Matching
-//==========================================
-
-
-object CW8a {
-
-abstract class Rexp
-case object ZERO extends Rexp
-case object ONE extends Rexp
-case class CHAR(c: Char) extends Rexp
-case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
-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
-
-import scala.language.implicitConversions
-import scala.language.reflectiveCalls
-
-def charlist2rexp(s: List[Char]): Rexp = s match {
- case Nil => ONE
- case c::Nil => CHAR(c)
- case c::s => SEQ(CHAR(c), charlist2rexp(s))
-}
-implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
-
-implicit def RexpOps (r: Rexp) = new {
- def | (s: Rexp) = ALT(r, s)
- def % = STAR(r)
- def ~ (s: Rexp) = SEQ(r, s)
-}
-
-implicit def stringOps (s: String) = new {
- def | (r: Rexp) = ALT(s, r)
- def | (r: String) = ALT(s, r)
- def % = STAR(s)
- def ~ (r: Rexp) = SEQ(s, r)
- def ~ (r: String) = SEQ(s, r)
-}
-
-// (1a) Complete the function nullable according to
-// the definition given in the coursework; this
-// function checks whether a regular expression
-// can match the empty string and Returns a boolean
-// accordingly.
-
-//def nullable (r: Rexp) : Boolean = ...
-
-
-// (1b) Complete the function der according to
-// the definition given in the coursework; this
-// function calculates the derivative of a
-// regular expression w.r.t. a character.
-
-//def der (c: Char, r: Rexp) : Rexp = ...
-
-
-// (1c) 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 simp(r: Rexp) : Rexp = ...
-
-
-// (1d) Complete the two functions below; the first
-// calculates the derivative w.r.t. a string; the second
-// is the regular expression matcher taking a regular
-// expression and a string and checks whether the
-// string matches the regular expression
-
-//def ders (s: List[Char], r: Rexp) : Rexp = ...
-
-//def matcher(r: Rexp, s: String): Boolean = ...
-
-
-// (1e) Complete the size function for regular
-// expressions according to the specification
-// given in the coursework.
-
-//def size(r: Rexp): Int = ...
-
-
-// some testing data
-
-/*
-matcher(("a" ~ "b") ~ "c", "abc") // => true
-matcher(("a" ~ "b") ~ "c", "ab") // => false
-
-// the supposedly 'evil' regular expression (a*)* b
-val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-
-matcher(EVIL, "a" * 1000 ++ "b") // => true
-matcher(EVIL, "a" * 1000) // => false
-
-// size without simplifications
-size(der('a', der('a', EVIL))) // => 28
-size(der('a', der('a', der('a', EVIL)))) // => 58
-
-// size with simplification
-size(simp(der('a', der('a', EVIL)))) // => 8
-size(simp(der('a', der('a', der('a', EVIL))))) // => 8
-
-// Java needs around 30 seconds for matching 28 a's with EVIL.
-//
-// Lets see how long it takes to match strings with
-// 0.5 Million a's...it should be in the range of some
-// seconds.
-
-def time_needed[T](i: Int, code: => T) = {
- val start = System.nanoTime()
- for (j <- 1 to i) code
- val end = System.nanoTime()
- (end - start)/(i * 1.0e9)
-}
-
-for (i <- 0 to 5000000 by 500000) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))))
-}
-
-*/
-
-
-}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates3/template3/bf.scala Thu Dec 07 12:05:10 2017 +0000
@@ -0,0 +1,151 @@
+// Part 2 about an Interpreter for the Brainf*** language
+//========================================================
+
+object CW8b {
+
+type Mem = Map[Int, Int]
+
+// (2a) Complete the functions for safely reading
+// and writing brainf*** memory. Safely read should
+// Return the value stored in the Map for a given memory
+// pointer, if it exists; otherwise it Returns 0. The
+// writing function generates a new Map with the
+// same data, except at the given memory pointer the
+// value v is stored.
+
+
+//def sread(mem: Mem, mp: Int) : Int = ...
+
+//def write(mem: Mem, mp: Int, v: Int) : Mem = ...
+
+
+// (2b) Implement the two jumping instructions in the
+// brainf*** language. In jumpRight, given a program and
+// a program counter move the counter to the right
+// until the command after the *matching* ]-command. Similarly,
+// jumpLeft implements the move to the left to just after
+// the *matching* [-command. The levels are used to find the
+// *matching* bracket.
+
+//def jumpRight(prog: String, pc: Int, level: Int) : Int = ...
+
+//def jumpLeft(prog: String, pc: Int, level: Int) : Int = ...
+
+
+
+// (2c) Complete the run function that interprets (runs) a brainf***
+// program: the arguments are a program, a program counter,
+// a memory counter and a brainf*** memory. It Returns the
+// memory at the stage when the execution of the brainf*** program
+// finishes. The interpretation finishes once the program counter
+// pc is pointing to something outside the program string.
+// If the pc points to a character inside the program, the pc,
+// memory pointer and memory need to be updated according to
+// rules of the brainf*** language. Then, recursively, the run
+// function continues with the command at the new program
+// counter.
+//
+// Implement the start function that calls run with the program
+// counter and memory counter set to 0.
+
+//def run(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ...
+
+//def start(prog: String, mem: Mem) = ...
+
+
+
+
+
+
+// some sample bf programs collected from the Internet
+//==================================================
+
+
+/*
+// first some contrived (small) programs
+
+// clears the 0-cell
+start("[-]", Map(0 -> 100))
+
+// copies content of the 0-cell to 1-cell
+start("[->+<]", Map(0 -> 10))
+
+// copies content of the 0-cell to 2-cell and 4-cell
+start("[>>+>>+<<<<-]", Map(0 -> 42))
+
+start("+++[>+++++<-]", Map(0 -> 10))
+
+
+// prints out numbers 0 to 9
+start("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""", Map())
+
+
+// some more "useful" programs
+
+// hello world program 1
+start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+ ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map())
+
+// hello world program 2
+start("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+
+ +.<<+++++++++++++++.>.+++.------.--------.>+.>.""", Map())
+
+
+// draws the Sierpinski triangle
+start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+ ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+ ]>.>+[>>]>+]""", Map())
+
+//Fibonacci numbers below 100
+start("""+++++++++++
+ >+>>>>++++++++++++++++++++++++++++++++++++++++++++
+ >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
+ +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
+ <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
+ -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
+ >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
+ +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
+ ++++++++++++++++++++++++++++++++++++++++++++.[-]<<
+ <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
+ [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", Map())
+
+
+//outputs the square numbers up to 10000
+start("""++++[>+++++<-]>[<+++++>-]+<+[
+ >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
+ >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
+ <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""", Map())
+
+
+//Collatz numbers (need to be typed in)
+start(""">,[[----------[
+ >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]
+ ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[
+ <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]
+ >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]
+ >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>
+ ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""", Map())
+
+
+// infinite Collatz (never stops)
+start(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[<
+ <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++
+ +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+<
+ [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>->
+ [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[
+ <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+
+ ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<
+ +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<-
+ ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<-
+ >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>
+ -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++
+ +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[<
+ <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++
+ +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-<
+ <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>-
+ [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""", Map())
+
+
+*/
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates3/template3/re.scala Thu Dec 07 12:05:10 2017 +0000
@@ -0,0 +1,127 @@
+// Part 1 about Regular Expression Matching
+//==========================================
+
+
+object CW8a {
+
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
+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
+
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+
+def charlist2rexp(s: List[Char]): Rexp = s match {
+ case Nil => ONE
+ case c::Nil => CHAR(c)
+ case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+
+implicit def RexpOps (r: Rexp) = new {
+ def | (s: Rexp) = ALT(r, s)
+ def % = STAR(r)
+ def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps (s: String) = new {
+ def | (r: Rexp) = ALT(s, r)
+ def | (r: String) = ALT(s, r)
+ def % = STAR(s)
+ def ~ (r: Rexp) = SEQ(s, r)
+ def ~ (r: String) = SEQ(s, r)
+}
+
+// (1a) Complete the function nullable according to
+// the definition given in the coursework; this
+// function checks whether a regular expression
+// can match the empty string and Returns a boolean
+// accordingly.
+
+//def nullable (r: Rexp) : Boolean = ...
+
+
+// (1b) Complete the function der according to
+// the definition given in the coursework; this
+// function calculates the derivative of a
+// regular expression w.r.t. a character.
+
+//def der (c: Char, r: Rexp) : Rexp = ...
+
+
+// (1c) 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 simp(r: Rexp) : Rexp = ...
+
+
+// (1d) Complete the two functions below; the first
+// calculates the derivative w.r.t. a string; the second
+// is the regular expression matcher taking a regular
+// expression and a string and checks whether the
+// string matches the regular expression
+
+//def ders (s: List[Char], r: Rexp) : Rexp = ...
+
+//def matcher(r: Rexp, s: String): Boolean = ...
+
+
+// (1e) Complete the size function for regular
+// expressions according to the specification
+// given in the coursework.
+
+//def size(r: Rexp): Int = ...
+
+
+// some testing data
+
+/*
+matcher(("a" ~ "b") ~ "c", "abc") // => true
+matcher(("a" ~ "b") ~ "c", "ab") // => false
+
+// the supposedly 'evil' regular expression (a*)* b
+val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+matcher(EVIL, "a" * 1000 ++ "b") // => true
+matcher(EVIL, "a" * 1000) // => false
+
+// size without simplifications
+size(der('a', der('a', EVIL))) // => 28
+size(der('a', der('a', der('a', EVIL)))) // => 58
+
+// size with simplification
+size(simp(der('a', der('a', EVIL)))) // => 8
+size(simp(der('a', der('a', der('a', EVIL))))) // => 8
+
+// Java needs around 30 seconds for matching 28 a's with EVIL.
+//
+// Lets see how long it takes to match strings with
+// 0.5 Million a's...it should be in the range of some
+// seconds.
+
+def time_needed[T](i: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (j <- 1 to i) code
+ val end = System.nanoTime()
+ (end - start)/(i * 1.0e9)
+}
+
+for (i <- 0 to 5000000 by 500000) {
+ println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))))
+}
+
+*/
+
+
+}