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