// 2 x 2 x 2 Rubik's Cube
//========================

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


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



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