--- a/progs/cube.sc Sat Mar 11 23:12:49 2023 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,215 +0,0 @@
-
-// 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"
\ No newline at end of file