59 s"${pp_col(f.c11)} ${pp_col(f.c12)}\n${pp_col(f.c21)} ${pp_col(f.c22)}" |
59 s"${pp_col(f.c11)} ${pp_col(f.c12)}\n${pp_col(f.c21)} ${pp_col(f.c22)}" |
60 |
60 |
61 def pp_cube(c: Cube) : String = |
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)}" |
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 |
63 |
64 // specific cube |
64 |
65 val init = |
65 val init = |
66 Cube(Face(White, Green, White, White), |
66 Cube(Face(White, Green, White, White), |
67 Face(Blue, Yellow, Orange, Red), |
67 Face(Blue, Yellow, Orange, Red), |
68 Face(Red, Blue, Red, Blue), |
68 Face(Red, Blue, Red, Blue), |
69 Face(White, Yellow, Red, Orange), |
69 Face(White, Yellow, Red, Orange), |
135 def actionsS(c: Cube) : Set[Cube] = |
135 def actionsS(c: Cube) : Set[Cube] = |
136 Set(up(c), clock(c), right(c)) |
136 Set(up(c), clock(c), right(c)) |
137 |
137 |
138 def searchS(cs: Set[Cube], d: Int) : Boolean = { |
138 def searchS(cs: Set[Cube], d: Int) : Boolean = { |
139 println(s"Depth: $d Cands: ${cs.size}") |
139 println(s"Depth: $d Cands: ${cs.size}") |
140 //memory() |
140 memory() |
141 if (cs.exists(solved == _)) true |
141 if (cs.exists(solved == _)) true |
142 else searchS(cs.flatMap(actionsS), d + 1) |
142 else searchS(cs.flatMap(actionsS), d + 1) |
143 } |
143 } |
144 |
144 |
145 //println("Set Version") |
145 //println("Set Version") |
161 (right(c), Right::act)) |
161 (right(c), Right::act)) |
162 |
162 |
163 |
163 |
164 def search2(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = { |
164 def search2(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = { |
165 println(s"Depth: $d Cands: ${cs.length}") |
165 println(s"Depth: $d Cands: ${cs.length}") |
166 val res = cs.find(solved == _._1) |
166 val res = cs.find(init == _._1) |
167 if (res.isDefined) res.get |
167 if (res.isDefined) res.get |
168 else search2(cs.flatMap((actions2 _).tupled), d + 1) |
168 else search2(cs.flatMap((actions2 _).tupled), d + 1) |
169 } |
169 } |
170 |
170 |
171 //println("List Version with Actions") |
171 //println("List Version with Actions") |
172 //println(search2(List((init, Nil)), 0)._2.mkString("\n")) |
172 //println(search2(List((solved, Nil)), 0)._2.mkString("\n")) |
173 //println(s"${time_needed(1, search2(List((init, Nil)), 0))} secs") |
173 //println(s"${time_needed(1, search2(List((init, Nil)), 0))} secs") |
174 |
174 |
175 // using Maps for recording the moves |
175 // using Maps for recording the moves |
176 def actionsM(c: Cube, act: Actions) : Map[Cube, Actions] = |
176 def actionsM(c: Cube, act: Actions) : Map[Cube, Actions] = |
177 Map(up(c) -> (Up::act), |
177 Map(up(c) -> (Up::act), |
179 right(c) -> (Right::act)) |
179 right(c) -> (Right::act)) |
180 |
180 |
181 |
181 |
182 def searchM(cs: Map[Cube, Actions], d: Int) : Actions = { |
182 def searchM(cs: Map[Cube, Actions], d: Int) : Actions = { |
183 println(s"Depth: $d Cands: ${cs.keySet.size}") |
183 println(s"Depth: $d Cands: ${cs.keySet.size}") |
184 val res = cs.keySet.find(solved == _) |
184 val res = cs.keySet.find(init == _) |
185 if (res.isDefined) cs(res.get) |
185 if (res.isDefined) cs(res.get) |
186 else searchM(cs.flatMap((actionsM _).tupled), d + 1) |
186 else searchM(cs.flatMap((actionsM _).tupled), d + 1) |
187 } |
187 } |
188 |
188 |
189 println("Map Version with actions") |
189 println("Map Version with actions") |
190 println(searchM(Map(init -> Nil), 0).mkString("\n")) |
190 println(searchM(Map(solved -> Nil), 0).mkString("\n")) |
191 println(s"${time_needed(1, searchM(Map(init -> Nil), 0))} secs") |
191 println(s"${time_needed(1, searchM(Map(init -> Nil), 0))} secs") |
192 |
192 |
193 |
193 |
194 |
194 |
195 // bi-directional search |
195 // bi-directional search |
203 } |
203 } |
204 |
204 |
205 println("Bidirectional Version with actions") |
205 println("Bidirectional Version with actions") |
206 println(bsearch(Map(init -> Nil), Map(solved -> Nil), 0)) |
206 println(bsearch(Map(init -> Nil), Map(solved -> Nil), 0)) |
207 println(s"${time_needed(1, 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" |