progs/cube.sc
changeset 468 0587ef444547
parent 467 9b5165b8a762
child 469 48de09728447
equal deleted inserted replaced
467:9b5165b8a762 468:0587ef444547
     1 
       
     2 // for measuring time
       
     3 def time_needed[T](i: Int, code: => T) = {
       
     4   val start = System.nanoTime()
       
     5   for (j <- 1 to i) code
       
     6   val end = System.nanoTime()
       
     7   (end - start) / (i * 1.0e9)
       
     8 }
       
     9 
       
    10 // for measuring memory usage
       
    11 val mb = 1024*1024
       
    12 val runtime = Runtime.getRuntime
       
    13 
       
    14 def memory() = {
       
    15     println(s"  ** Used Memory:  ${(runtime.totalMemory - runtime.freeMemory) / mb}")
       
    16     println(s"  ** Free Memory:  ${runtime.freeMemory / mb}")
       
    17     println(s"  ** Total Memory: ${runtime.totalMemory / mb}")
       
    18     println(s"  ** Max Memory:   ${runtime.maxMemory / mb}")
       
    19 }
       
    20 
       
    21 
       
    22 abstract class Colour
       
    23 case object White extends Colour
       
    24 case object Yellow extends Colour
       
    25 case object Orange extends Colour
       
    26 case object Red extends Colour
       
    27 case object Green extends Colour
       
    28 case object Blue extends Colour
       
    29 
       
    30 //    -------
       
    31 //   |c11 c12|
       
    32 //   |c21 c22|
       
    33 //    -------  
       
    34 case class Face(c11: Colour, c12: Colour,
       
    35                 c21: Colour, c22: Colour)
       
    36 
       
    37 //     +--+
       
    38 //     |f2|
       
    39 //  +--+  +--+
       
    40 //  |f5 f1 f6|
       
    41 //  +--+  +--+
       
    42 //     |f3|
       
    43 //     |f4|
       
    44 //     +--+ 
       
    45 case class Cube(f1: Face, f2: Face, f3: Face,
       
    46                 f4: Face, f5: Face, f6: Face)                
       
    47 
       
    48 // pretty printing
       
    49 def pp_col(c: Colour) : String = c match {
       
    50     case White => "W"
       
    51     case Yellow => "Y"
       
    52     case Orange => "O"
       
    53     case Red => "R"
       
    54     case Green => "G"
       
    55     case Blue => "B"
       
    56 }
       
    57 
       
    58 def pp_face(f: Face) : String = 
       
    59   s"${pp_col(f.c11)} ${pp_col(f.c12)}\n${pp_col(f.c21)} ${pp_col(f.c22)}"
       
    60 
       
    61 def pp_cube(c: Cube) : String = 
       
    62   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)}"  
       
    63 
       
    64 
       
    65 val init = 
       
    66     Cube(Face(White, Green, White, White), 
       
    67          Face(Blue, Yellow, Orange, Red), 
       
    68          Face(Red, Blue, Red, Blue),
       
    69          Face(White, Yellow, Red, Orange),
       
    70          Face(Yellow, Green, Blue, Green),
       
    71          Face(Yellow, Green, Orange, Orange))  
       
    72 
       
    73 val solved = 
       
    74     Cube(Face(Yellow, Yellow, Yellow, Yellow), 
       
    75          Face(Orange, Orange, Orange, Orange), 
       
    76          Face(Red, Red, Red, Red),
       
    77          Face(White, White, White, White),
       
    78          Face(Blue, Blue, Blue, Blue),
       
    79          Face(Green, Green, Green, Green))  
       
    80 
       
    81 //println(pp_cube(init))                
       
    82 
       
    83 // actions
       
    84 
       
    85 
       
    86 def up(c: Cube) : Cube =
       
    87     Cube(Face(c.f1.c11, c.f3.c12, c.f1.c21, c.f3.c22),
       
    88          Face(c.f2.c11, c.f1.c12, c.f2.c21, c.f1.c22),
       
    89          Face(c.f3.c11, c.f4.c12, c.f3.c21, c.f4.c22),
       
    90          Face(c.f4.c11, c.f2.c12, c.f4.c21, c.f2.c22),
       
    91          Face(c.f5.c11, c.f5.c12, c.f5.c21, c.f5.c22),
       
    92          Face(c.f6.c21, c.f6.c11, c.f6.c22, c.f6.c12))
       
    93 
       
    94 def clock(c: Cube) : Cube =
       
    95     Cube(Face(c.f1.c21, c.f1.c11, c.f1.c22, c.f1.c12),
       
    96          Face(c.f2.c11, c.f2.c12, c.f5.c22, c.f5.c12),
       
    97          Face(c.f6.c21, c.f6.c11, c.f3.c21, c.f3.c22),
       
    98          Face(c.f4.c11, c.f4.c12, c.f4.c21, c.f4.c22),
       
    99          Face(c.f5.c11, c.f3.c11, c.f5.c21, c.f3.c12),
       
   100          Face(c.f2.c21, c.f6.c12, c.f2.c22, c.f6.c22))
       
   101 
       
   102 def right(c: Cube) : Cube =
       
   103     Cube(Face(c.f5.c11, c.f5.c12, c.f1.c21, c.f1.c22),
       
   104          Face(c.f2.c12, c.f2.c22, c.f2.c11, c.f2.c21),
       
   105          Face(c.f3.c11, c.f3.c12, c.f3.c21, c.f3.c22),
       
   106          Face(c.f4.c11, c.f4.c12, c.f6.c12, c.f6.c11),
       
   107          Face(c.f4.c22, c.f4.c21, c.f5.c21, c.f5.c22),
       
   108          Face(c.f1.c11, c.f1.c12, c.f6.c21, c.f6.c22))         
       
   109 
       
   110 
       
   111 //println("\n" ++ pp_cube(up(init)))           
       
   112 //println("\n" ++ pp_cube(clock(init)))   
       
   113 //println("\n" ++ pp_cube(right(init))) 
       
   114 
       
   115 //println(List(init, up(init), clock(init), right(init)).map(solved))
       
   116 
       
   117 
       
   118 // simple bf-search without solution
       
   119 
       
   120 def actions(c: Cube) : List[Cube] = 
       
   121   List(up(c), clock(c), right(c)) 
       
   122 
       
   123 def search(cs: List[Cube], d: Int) : Boolean = { 
       
   124   println(s"Depth: $d    Cands: ${cs.length}")  
       
   125   //memory()
       
   126   if (cs.exists(solved == _)) true
       
   127   else search(cs.flatMap(actions), d + 1)
       
   128 }  
       
   129 
       
   130 //println("List Version")
       
   131 //println(search(List(init), 0))
       
   132 //println(s"${time_needed(1, search(List(init), 0))} secs")  
       
   133 
       
   134 
       
   135 def actionsS(c: Cube) : Set[Cube] = 
       
   136   Set(up(c), clock(c), right(c)) 
       
   137 
       
   138 def searchS(cs: Set[Cube], d: Int) : Boolean = { 
       
   139   println(s"Depth: $d    Cands: ${cs.size}")  
       
   140   memory()
       
   141   if (cs.exists(solved == _)) true
       
   142   else searchS(cs.flatMap(actionsS), d + 1)
       
   143 }  
       
   144 
       
   145 //println("Set Version")
       
   146 //println(searchS(Set(init), 0))
       
   147 //println(s"${time_needed(1, searchS(Set(init), 0))} secs")  
       
   148 
       
   149 // bf-search generating a list of "actions""
       
   150 
       
   151 abstract class Action
       
   152 case object Up extends Action
       
   153 case object Right extends Action
       
   154 case object Clock extends Action
       
   155 
       
   156 type Actions = List[Action]
       
   157 
       
   158 def actions2(c: Cube, act: Actions) : List[(Cube, Actions)] = 
       
   159   List((up(c), Up::act), 
       
   160        (clock(c), Clock::act), 
       
   161        (right(c), Right::act)) 
       
   162 
       
   163 
       
   164 def search2(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = { 
       
   165   println(s"Depth: $d    Cands: ${cs.length}")  
       
   166   val res = cs.find(init == _._1)
       
   167   if (res.isDefined) res.get
       
   168   else search2(cs.flatMap((actions2 _).tupled), d + 1)
       
   169 }  
       
   170 
       
   171 //println("List Version with Actions")
       
   172 //println(search2(List((solved, Nil)), 0)._2.mkString("\n"))  
       
   173 //println(s"${time_needed(1, search2(List((init, Nil)), 0))} secs") 
       
   174 
       
   175 // using Maps for recording the moves
       
   176 def actionsM(c: Cube, act: Actions) : Map[Cube, Actions] = 
       
   177   Map(up(c) -> (Up::act), 
       
   178       clock(c) -> (Clock::act), 
       
   179       right(c) -> (Right::act)) 
       
   180 
       
   181 
       
   182 def searchM(cs: Map[Cube, Actions], d: Int) : Actions = { 
       
   183   println(s"Depth: $d    Cands: ${cs.keySet.size}")  
       
   184   val res = cs.keySet.find(init == _)
       
   185   if (res.isDefined) cs(res.get)
       
   186   else searchM(cs.flatMap((actionsM _).tupled), d + 1)
       
   187 }  
       
   188 
       
   189 println("Map Version with actions")
       
   190 println(searchM(Map(solved -> Nil), 0).mkString("\n"))  
       
   191 println(s"${time_needed(1, searchM(Map(init -> Nil), 0))} secs")
       
   192 
       
   193 
       
   194 
       
   195 // bi-directional search
       
   196 def bsearch(cs: Map[Cube, Actions], 
       
   197             bs: Map[Cube, Actions], d: Int) : (Actions, Actions) = { 
       
   198   println(s"Depth: $d    Cands: ${cs.keySet.size}/${bs.keySet.size}") 
       
   199   val res = cs.keySet intersect bs.keySet
       
   200   if (!res.isEmpty) (cs(res.head), bs(res.head))
       
   201   else bsearch(cs.flatMap((actions2 _).tupled), 
       
   202                bs.flatMap((actions2 _).tupled), d + 1)
       
   203 } 
       
   204 
       
   205 println("Bidirectional Version with actions")
       
   206 println(bsearch(Map(init -> Nil), Map(solved -> Nil), 0))  
       
   207 println(s"${time_needed(1, bsearch(Map(init -> Nil), Map(solved -> Nil), 0))}")
       
   208 
       
   209 
       
   210 
       
   211 
       
   212 
       
   213 
       
   214 // more memory 
       
   215 // JAVA_OPTS="-Xmx2g"