diff -r 9b5165b8a762 -r 0587ef444547 progs/cube.sc --- a/progs/cube.sc Sat Mar 11 23:12:49 2023 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,215 +0,0 @@ - -// 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)}" - - -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(init == _._1) - if (res.isDefined) res.get - else search2(cs.flatMap((actions2 _).tupled), d + 1) -} - -//println("List Version with Actions") -//println(search2(List((solved, 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(init == _) - if (res.isDefined) cs(res.get) - else searchM(cs.flatMap((actionsM _).tupled), d + 1) -} - -println("Map Version with actions") -println(searchM(Map(solved -> 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))}") - - - - - - -// more memory -// JAVA_OPTS="-Xmx2g" \ No newline at end of file