// 2 x 2 x 2 Rubik's Cube

//========================

// !! UPDATE for Scala 3

// !! 

// !! Scala 3 allocates much more memory to 

// !! the JVM such that the memory issues from

// !! Scala 2 and the video do not arise. 

// for more memory for the JVM, call

//

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

}

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

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{ (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{ (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{ (c, as) => actions_map(c, as) }, 

               bs.flatMap{ (c, as) => actions_map(c, as) }, d + 1)

}  

bsearch(Map(init ->  Nil), Map(solved -> Nil), 0).mkString("\n")