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