--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/cube.scala	Tue Dec 07 01:35:00 2021 +0000
@@ -0,0 +1,199 @@
+// 2 x 2 x 2 Rubik's Cube
+//========================
+
+// more memory for the JVM
+//
+// JAVA_OPTS="-Xmx2g" scala
+
+
+// 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
+
+// Faces
+//    -------
+//   |c11 c12|
+//   |c21 c22|
+//    -------  
+case class Face(c11: Colour, c12: Colour,
+                c21: Colour, c22: Colour)
+
+
+// Cubes
+//     +--+
+//     |f2|
+//  +--+  +--+
+//  |f5 f1 f6|
+//  +--+  +--+
+//     |f3|
+//     |f4|
+//     +--+ 
+case class Cube(f1: Face, f2: Face, f3: Face,
+                f4: Face, f5: Face, f6: Face)
+
+
+// starting 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))
+
+// solved cube
+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))  
+
+
+
+// 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))         
+
+
+// simple bf-search without solution, just true
+
+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)
+}  
+
+search(List(init), 0)
+
+// Set version
+def actions_set(c: Cube) : Set[Cube] =
+  Set(up(c), clock(c), right(c))
+
+def search_set(cs: Set[Cube], d: Int) : Boolean = {
+  println(s"Depth: $d candidates: ${cs.size}")
+  //memory()
+  if (cs.contains(solved)) true
+  else search_set(cs.flatMap(actions_set), d + 1)
+}  
+
+search_set(Set(init), 0)
+
+
+// For generating 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]
+
+// List version generating a list of actions
+def actions_list(c: Cube, act: Actions) : List[(Cube, Actions)] = 
+  List((up(c), Up::act), 
+       (clock(c), Clock::act), 
+       (right(c), Right::act)) 
+
+
+def search_list(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = { 
+  println(s"Depth: $d    Cands: ${cs.length}")  
+  val res = cs.find(_._1 == solved)
+  if (res.isDefined) res.get
+  else search_list(cs.flatMap{case (c, as) => actions_list(c, as) }, d + 1)
+}  
+
+search_list(List((init, Nil)), 0)._2.reverse.mkString("\n") 
+
+
+// Map version generating a list of actions
+def actions_map(c: Cube, as: Actions) : Map[Cube, Actions] = 
+  Map(up(c) -> (Up::as), 
+      clock(c) -> (Clock::as), 
+      right(c) -> (Right::as)) 
+
+
+def search_map(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 search_map(cs.flatMap{case (c, as) => actions_list(c, as) }, d + 1)
+}  
+
+
+search_map(Map(init -> Nil), 0).reverse.mkString("\n")
+
+
+
+// Bidirectional breadth-first search
+def bsearch(cs: Map[Cube, Actions], 
+            bs: Map[Cube, Actions], d: Int) : 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).reverse ::: bs(res.head))
+  else bsearch(cs.flatMap{case (c, as) => actions_map(c, as) }, 
+               bs.flatMap{case (c, as) => actions_map(c, as) }, d + 1)
+}  
+
+bsearch(Map(init ->  Nil), Map(solved -> Nil), 0).mkString("\n")
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+