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