# HG changeset patch # User Christian Urban # Date 1626474859 -3600 # Node ID 839ad118e4677af3897273eb0a77b81ee7c80be2 # Parent 7a9cc14d09120a58c762dde27f5400cdfcd92b43 updated diff -r 7a9cc14d0912 -r 839ad118e467 cws/pre_cw01.pdf Binary file cws/pre_cw01.pdf has changed diff -r 7a9cc14d0912 -r 839ad118e467 main_marking5/bf_test.sh --- a/main_marking5/bf_test.sh Sun Jan 31 03:28:20 2021 +0000 +++ b/main_marking5/bf_test.sh Fri Jul 16 23:34:19 2021 +0100 @@ -262,7 +262,7 @@ if [ $tsts -eq 0 ] then echo -e " optimise(load_bff(\"benchmark.bf\")).length == 181" | tee -a $out - echo -e " optimise(load_bff(\"mandelbrot.bf\")).length == 11203" | tee -a $out + echo -e " optimise(load_bff(\"mandelbrot.bf\")).length == 11205" | tee -a $out echo -e " run3(\"[-]\", Map(0 -> 100)) == Map(0 -> 0)" | tee -a $out echo -e " run3(\"[->+<]\", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)" | tee -a $out echo -e " run3(\"[>>+>>+<<<<-]\", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)" | tee -a $out @@ -287,7 +287,7 @@ if [ $tsts -eq 0 ] then echo -e " combine(optimise(load_bff(\"benchmark.bf\"))).length == 134" | tee -a $out - echo -e " combine(optimise(load_bff(\"mandelbrot.bf\"))).length == 6509" | tee -a $out + echo -e " combine(optimise(load_bff(\"mandelbrot.bf\"))).length == 6511" | tee -a $out echo -e " run4(\"[-]\", Map(0 -> 100)) == Map(0 -> 0)" | tee -a $out echo -e " run4(\"[->+<]\", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)" | tee -a $out echo -e " run4(\"[>>+>>+<<<<-]\", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)" | tee -a $out diff -r 7a9cc14d0912 -r 839ad118e467 main_marking5/bf_test6.scala --- a/main_marking5/bf_test6.scala Sun Jan 31 03:28:20 2021 +0000 +++ b/main_marking5/bf_test6.scala Fri Jul 16 23:34:19 2021 +0100 @@ -1,7 +1,7 @@ import CW10b._ assert(optimise(load_bff("benchmark.bf")).length == 181) -assert(optimise(load_bff("mandelbrot.bf")).length == 11203) +assert(optimise(load_bff("mandelbrot.bf")).length == 11205) diff -r 7a9cc14d0912 -r 839ad118e467 main_marking5/bf_test7.scala --- a/main_marking5/bf_test7.scala Sun Jan 31 03:28:20 2021 +0000 +++ b/main_marking5/bf_test7.scala Fri Jul 16 23:34:19 2021 +0100 @@ -1,7 +1,7 @@ import CW10b._ assert(combine(optimise(load_bff("benchmark.bf"))).length == 134) -assert(combine(optimise(load_bff("mandelbrot.bf"))).length == 6509) +assert(combine(optimise(load_bff("mandelbrot.bf"))).length == 6511) diff -r 7a9cc14d0912 -r 839ad118e467 pre_marking3/postfix_test.sh --- a/pre_marking3/postfix_test.sh Sun Jan 31 03:28:20 2021 +0000 +++ b/pre_marking3/postfix_test.sh Fri Jul 16 23:34:19 2021 +0100 @@ -30,7 +30,7 @@ # functional tests function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "") # 2> /dev/null 1> /dev/null) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) } # purity test diff -r 7a9cc14d0912 -r 839ad118e467 progs/cube.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/cube.sc Fri Jul 16 23:34:19 2021 +0100 @@ -0,0 +1,207 @@ + +// for measuring time +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 measuring memory usage +val mb = 1024*1024 +val runtime = Runtime.getRuntime + +def memory() = { + println(s" ** Used Memory: ${(runtime.totalMemory - runtime.freeMemory) / mb}") + println(s" ** Free Memory: ${runtime.freeMemory / mb}") + println(s" ** Total Memory: ${runtime.totalMemory / mb}") + println(s" ** Max Memory: ${runtime.maxMemory / mb}") +} + + +abstract class Colour +case object White extends Colour +case object Yellow extends Colour +case object Orange extends Colour +case object Red extends Colour +case object Green extends Colour +case object Blue extends Colour + +// ------- +// |c11 c12| +// |c21 c22| +// ------- +case class Face(c11: Colour, c12: Colour, + c21: Colour, c22: Colour) + +// +--+ +// |f2| +// +--+ +--+ +// |f5 f1 f6| +// +--+ +--+ +// |f3| +// |f4| +// +--+ +case class Cube(f1: Face, f2: Face, f3: Face, + f4: Face, f5: Face, f6: Face) + +// pretty printing +def pp_col(c: Colour) : String = c match { + case White => "W" + case Yellow => "Y" + case Orange => "O" + case Red => "R" + case Green => "G" + case Blue => "B" +} + +def pp_face(f: Face) : String = + s"${pp_col(f.c11)} ${pp_col(f.c12)}\n${pp_col(f.c21)} ${pp_col(f.c22)}" + +def pp_cube(c: Cube) : String = + s"${pp_face(c.f1)}\n${pp_face(c.f2)}\n${pp_face(c.f3)}\n${pp_face(c.f4)}\n${pp_face(c.f5)}\n${pp_face(c.f6)}" + +// specific cube +val init = + Cube(Face(White, Green, White, White), + Face(Blue, Yellow, Orange, Red), + Face(Red, Blue, Red, Blue), + Face(White, Yellow, Red, Orange), + Face(Yellow, Green, Blue, Green), + Face(Yellow, Green, Orange, Orange)) + +val solved = + Cube(Face(Yellow, Yellow, Yellow, Yellow), + Face(Orange, Orange, Orange, Orange), + Face(Red, Red, Red, Red), + Face(White, White, White, White), + Face(Blue, Blue, Blue, Blue), + Face(Green, Green, Green, Green)) + +//println(pp_cube(init)) + +// actions + + +def up(c: Cube) : Cube = + Cube(Face(c.f1.c11, c.f3.c12, c.f1.c21, c.f3.c22), + Face(c.f2.c11, c.f1.c12, c.f2.c21, c.f1.c22), + Face(c.f3.c11, c.f4.c12, c.f3.c21, c.f4.c22), + Face(c.f4.c11, c.f2.c12, c.f4.c21, c.f2.c22), + Face(c.f5.c11, c.f5.c12, c.f5.c21, c.f5.c22), + Face(c.f6.c21, c.f6.c11, c.f6.c22, c.f6.c12)) + +def clock(c: Cube) : Cube = + Cube(Face(c.f1.c21, c.f1.c11, c.f1.c22, c.f1.c12), + Face(c.f2.c11, c.f2.c12, c.f5.c22, c.f5.c12), + Face(c.f6.c21, c.f6.c11, c.f3.c21, c.f3.c22), + Face(c.f4.c11, c.f4.c12, c.f4.c21, c.f4.c22), + Face(c.f5.c11, c.f3.c11, c.f5.c21, c.f3.c12), + Face(c.f2.c21, c.f6.c12, c.f2.c22, c.f6.c22)) + +def right(c: Cube) : Cube = + Cube(Face(c.f5.c11, c.f5.c12, c.f1.c21, c.f1.c22), + Face(c.f2.c12, c.f2.c22, c.f2.c11, c.f2.c21), + Face(c.f3.c11, c.f3.c12, c.f3.c21, c.f3.c22), + Face(c.f4.c11, c.f4.c12, c.f6.c12, c.f6.c11), + Face(c.f4.c22, c.f4.c21, c.f5.c21, c.f5.c22), + Face(c.f1.c11, c.f1.c12, c.f6.c21, c.f6.c22)) + + +//println("\n" ++ pp_cube(up(init))) +//println("\n" ++ pp_cube(clock(init))) +//println("\n" ++ pp_cube(right(init))) + +//println(List(init, up(init), clock(init), right(init)).map(solved)) + + +// simple bf-search without solution + +def actions(c: Cube) : List[Cube] = + List(up(c), clock(c), right(c)) + +def search(cs: List[Cube], d: Int) : Boolean = { + println(s"Depth: $d Cands: ${cs.length}") + //memory() + if (cs.exists(solved == _)) true + else search(cs.flatMap(actions), d + 1) +} + +//println("List Version") +//println(search(List(init), 0)) +//println(s"${time_needed(1, search(List(init), 0))} secs") + + +def actionsS(c: Cube) : Set[Cube] = + Set(up(c), clock(c), right(c)) + +def searchS(cs: Set[Cube], d: Int) : Boolean = { + println(s"Depth: $d Cands: ${cs.size}") + //memory() + if (cs.exists(solved == _)) true + else searchS(cs.flatMap(actionsS), d + 1) +} + +//println("Set Version") +//println(searchS(Set(init), 0)) +//println(s"${time_needed(1, searchS(Set(init), 0))} secs") + +// bf-search generating a list of "actions"" + +abstract class Action +case object Up extends Action +case object Right extends Action +case object Clock extends Action + +type Actions = List[Action] + +def actions2(c: Cube, act: Actions) : List[(Cube, Actions)] = + List((up(c), Up::act), + (clock(c), Clock::act), + (right(c), Right::act)) + + +def search2(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = { + println(s"Depth: $d Cands: ${cs.length}") + val res = cs.find(solved == _._1) + if (res.isDefined) res.get + else search2(cs.flatMap((actions2 _).tupled), d + 1) +} + +//println("List Version with Actions") +//println(search2(List((init, Nil)), 0)._2.mkString("\n")) +//println(s"${time_needed(1, search2(List((init, Nil)), 0))} secs") + +// using Maps for recording the moves +def actionsM(c: Cube, act: Actions) : Map[Cube, Actions] = + Map(up(c) -> (Up::act), + clock(c) -> (Clock::act), + right(c) -> (Right::act)) + + +def searchM(cs: Map[Cube, Actions], d: Int) : Actions = { + println(s"Depth: $d Cands: ${cs.keySet.size}") + val res = cs.keySet.find(solved == _) + if (res.isDefined) cs(res.get) + else searchM(cs.flatMap((actionsM _).tupled), d + 1) +} + +println("Map Version with actions") +println(searchM(Map(init -> Nil), 0).mkString("\n")) +println(s"${time_needed(1, searchM(Map(init -> Nil), 0))} secs") + + + +// bi-directional search +def bsearch(cs: Map[Cube, Actions], + bs: Map[Cube, Actions], d: Int) : (Actions, Actions) = { + println(s"Depth: $d Cands: ${cs.keySet.size}/${bs.keySet.size}") + val res = cs.keySet intersect bs.keySet + if (!res.isEmpty) (cs(res.head), bs(res.head)) + else bsearch(cs.flatMap((actions2 _).tupled), + bs.flatMap((actions2 _).tupled), d + 1) +} + +println("Bidirectional Version with actions") +println(bsearch(Map(init -> Nil), Map(solved -> Nil), 0)) +println(s"${time_needed(1, bsearch(Map(init -> Nil), Map(solved -> Nil), 0))}") diff -r 7a9cc14d0912 -r 839ad118e467 progs/mandelbrot.scala --- a/progs/mandelbrot.scala Sun Jan 31 03:28:20 2021 +0000 +++ b/progs/mandelbrot.scala Fri Jul 16 23:34:19 2021 +0100 @@ -158,10 +158,10 @@ val delta = (exc2 - exc1) * 0.0333 -println(s"${time_needed( - for (n <- (0 to 12)) - mandelbrot(exc1 + delta * n, - exc2 - delta * n, 100))} secs") +//println(s"${time_needed( +// for (n <- (0 to 12)) +// mandelbrot(exc1 + delta * n, +// exc2 - delta * n, 100))} secs") @@ -177,3 +177,10 @@ val exj2 = 0.11084 - 0.64075 * i //time_needed(mandelbrot(exj1, exj2, 1000)) + + +// another example +val exA = 0.3439274 + 0.6516478 * i +val exB = 0.3654477 + 0.6301795 * i + +//time_needed(mandelbrot(exA, exB, 1000))