--- /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))}")