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


enum Colour {
  case White 
  case Yellow
  case Orange
  case Red 
  case Green
  case Blue
}
import 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 generating a 
// solution, just true in case there is a 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)
}  

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