// 2 x 2 x 2 Rubik's Cube

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

//

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

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)

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)

abstract class Action

case object Up extends Action

case object Right extends Action

case object Clock extends Action

type Actions = List[Action]

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

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

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