// for measuring time

def time_needed[T](i: Int, code: => T) = {

  val start = System.nanoTime()

  for (j <- 1 to i) code

  val end = System.nanoTime()

  (end - start) / (i * 1.0e9)

}

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

//    -------

//   |c11 c12|

//   |c21 c22|

//    -------  

case class Face(c11: Colour, c12: Colour,

                c21: Colour, c22: Colour)

//     +--+

//     |f2|

//  +--+  +--+

//  |f5 f1 f6|

//  +--+  +--+

//     |f3|

//     |f4|

//     +--+ 

case class Cube(f1: Face, f2: Face, f3: Face,

                f4: Face, f5: Face, f6: Face)                

// pretty printing

def pp_col(c: Colour) : String = c match {

    case White => "W"

    case Yellow => "Y"

    case Orange => "O"

    case Red => "R"

    case Green => "G"

    case Blue => "B"

}

def pp_face(f: Face) : String = 

  s"${pp_col(f.c11)} ${pp_col(f.c12)}\n${pp_col(f.c21)} ${pp_col(f.c22)}"

def pp_cube(c: Cube) : String = 

  s"${pp_face(c.f1)}\n${pp_face(c.f2)}\n${pp_face(c.f3)}\n${pp_face(c.f4)}\n${pp_face(c.f5)}\n${pp_face(c.f6)}"  

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

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

//println(pp_cube(init))                

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

//println("\n" ++ pp_cube(up(init)))           

//println("\n" ++ pp_cube(clock(init)))   

//println("\n" ++ pp_cube(right(init))) 

//println(List(init, up(init), clock(init), right(init)).map(solved))

// simple bf-search without 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)

}  

//println("List Version")

//println(search(List(init), 0))

//println(s"${time_needed(1, search(List(init), 0))} secs")  

def actionsS(c: Cube) : Set[Cube] = 

  Set(up(c), clock(c), right(c)) 

def searchS(cs: Set[Cube], d: Int) : Boolean = { 

  println(s"Depth: $d    Cands: ${cs.size}")  

  memory()

  if (cs.exists(solved == _)) true

  else searchS(cs.flatMap(actionsS), d + 1)

}  

//println("Set Version")

//println(searchS(Set(init), 0))

//println(s"${time_needed(1, searchS(Set(init), 0))} secs")  

// bf-search generating a 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]

def actions2(c: Cube, act: Actions) : List[(Cube, Actions)] = 

  List((up(c), Up::act), 

       (clock(c), Clock::act), 

       (right(c), Right::act)) 

def search2(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = { 

  println(s"Depth: $d    Cands: ${cs.length}")  

  val res = cs.find(init == _._1)

  if (res.isDefined) res.get

  else search2(cs.flatMap((actions2 _).tupled), d + 1)

}  

//println("List Version with Actions")

//println(search2(List((solved, Nil)), 0)._2.mkString("\n"))  

//println(s"${time_needed(1, search2(List((init, Nil)), 0))} secs") 

// using Maps for recording the moves

def actionsM(c: Cube, act: Actions) : Map[Cube, Actions] = 

  Map(up(c) -> (Up::act), 

      clock(c) -> (Clock::act), 

      right(c) -> (Right::act)) 

def searchM(cs: Map[Cube, Actions], d: Int) : Actions = { 

  println(s"Depth: $d    Cands: ${cs.keySet.size}")  

  val res = cs.keySet.find(init == _)

  if (res.isDefined) cs(res.get)

  else searchM(cs.flatMap((actionsM _).tupled), d + 1)

}  

println("Map Version with actions")

println(searchM(Map(solved -> Nil), 0).mkString("\n"))  

println(s"${time_needed(1, searchM(Map(init -> Nil), 0))} secs")

// bi-directional search

def bsearch(cs: Map[Cube, Actions], 

            bs: Map[Cube, Actions], d: Int) : (Actions, 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), bs(res.head))

  else bsearch(cs.flatMap((actions2 _).tupled), 

               bs.flatMap((actions2 _).tupled), d + 1)

} 

println("Bidirectional Version with actions")

println(bsearch(Map(init -> Nil), Map(solved -> Nil), 0))  

println(s"${time_needed(1, bsearch(Map(init -> Nil), Map(solved -> Nil), 0))}")

// more memory 

// JAVA_OPTS="-Xmx2g"