# HG changeset patch # User Christian Urban # Date 1667867267 0 # Node ID 6af86ba1208fc1b8c701948a960f980d8406178d # Parent de701b64a4e0235b59ffbcd67f44ae788a6bbf42 updated diff -r de701b64a4e0 -r 6af86ba1208f core_testing1/collatz.scala --- 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. diff -r de701b64a4e0 -r 6af86ba1208f cws/core_cw01.pdf Binary file cws/core_cw01.pdf has changed diff -r de701b64a4e0 -r 6af86ba1208f cws/core_cw02.pdf Binary file cws/core_cw02.pdf has changed diff -r de701b64a4e0 -r 6af86ba1208f cws/core_cw03.pdf Binary file cws/core_cw03.pdf has changed diff -r de701b64a4e0 -r 6af86ba1208f cws/main_cw01.pdf Binary file cws/main_cw01.pdf has changed diff -r de701b64a4e0 -r 6af86ba1208f cws/main_cw02.pdf Binary file cws/main_cw02.pdf has changed diff -r de701b64a4e0 -r 6af86ba1208f cws/main_cw03.pdf Binary file cws/main_cw03.pdf has changed diff -r de701b64a4e0 -r 6af86ba1208f cws/main_cw04.pdf Binary file cws/main_cw04.pdf has changed diff -r de701b64a4e0 -r 6af86ba1208f cws/main_cw05.pdf Binary file cws/main_cw05.pdf has changed diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re.scala --- 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. +*/ } + diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test.sh --- 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 diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test1.scala --- 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) diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test2.scala --- 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)) +*/ diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test3.scala --- 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')) - diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test4.scala --- 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)) diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test5.scala --- 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) diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test6.scala --- 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))) diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test7.scala --- /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) diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test8.scala --- /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) diff -r de701b64a4e0 -r 6af86ba1208f main_testing3/re_test9.scala --- /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) diff -r de701b64a4e0 -r 6af86ba1208f main_testing4/knight1.scala --- 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)) + + + + + +} + + diff -r de701b64a4e0 -r 6af86ba1208f main_testing4/knight3.scala --- 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) diff -r de701b64a4e0 -r 6af86ba1208f main_testing4/knight_test.sh --- 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 diff -r de701b64a4e0 -r 6af86ba1208f main_testing4/knight_test10.scala --- /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) +