1 // 2 x 2 x 2 Rubik's Cube |
1 // 2 x 2 x 2 Rubik's Cube |
2 //======================== |
2 //======================== |
|
3 |
|
4 // !! UPDATE for Scala 3 |
|
5 // !! |
|
6 // !! Scala 3 allocates much more memory to |
|
7 // !! the JVM such that the memory issues from |
|
8 // !! Scala 2 and the video do not arise. |
|
9 |
|
10 |
3 |
11 |
4 // for more memory for the JVM, call |
12 // for more memory for the JVM, call |
5 // |
13 // |
6 // JAVA_OPTS="-Xmx2g" scala |
14 // JAVA_OPTS="-Xmx2g" scala |
7 |
15 |
140 |
148 |
141 def search_list(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = { |
149 def search_list(cs: List[(Cube, Actions)], d: Int) : (Cube, Actions) = { |
142 println(s"Depth: $d Cands: ${cs.length}") |
150 println(s"Depth: $d Cands: ${cs.length}") |
143 val res = cs.find(_._1 == solved) |
151 val res = cs.find(_._1 == solved) |
144 if (res.isDefined) res.get |
152 if (res.isDefined) res.get |
145 else search_list(cs.flatMap{case (c, as) => actions_list(c, as) }, d + 1) |
153 else search_list(cs.flatMap{ (c, as) => actions_list(c, as) }, d + 1) |
146 } |
154 } |
147 |
155 |
148 search_list(List((init, Nil)), 0)._2.reverse.mkString("\n") |
156 search_list(List((init, Nil)), 0)._2.reverse.mkString("\n") |
149 |
157 |
150 |
158 |
157 |
165 |
158 def search_map(cs: Map[Cube, Actions], d: Int) : Actions = { |
166 def search_map(cs: Map[Cube, Actions], d: Int) : Actions = { |
159 println(s"Depth: $d Cands: ${cs.keySet.size}") |
167 println(s"Depth: $d Cands: ${cs.keySet.size}") |
160 val res = cs.keySet.find(_ == solved) |
168 val res = cs.keySet.find(_ == solved) |
161 if (res.isDefined) cs(res.get) |
169 if (res.isDefined) cs(res.get) |
162 else search_map(cs.flatMap{case (c, as) => actions_list(c, as) }, d + 1) |
170 else search_map(cs.flatMap{ (c, as) => actions_list(c, as) }, d + 1) |
163 } |
171 } |
164 |
172 |
165 |
173 |
166 search_map(Map(init -> Nil), 0).reverse.mkString("\n") |
174 search_map(Map(init -> Nil), 0).reverse.mkString("\n") |
167 |
|
168 |
|
169 |
|
170 // bidirectional breadth-first search |
|
171 def bsearch(cs: Map[Cube, Actions], |
|
172 bs: Map[Cube, Actions], d: Int) : Actions = { |
|
173 println(s"Depth: $d Cands: ${cs.keySet.size}/${bs.keySet.size}") |
|
174 val res = cs.keySet intersect bs.keySet |
|
175 if (!res.isEmpty) (cs(res.head).reverse ::: bs(res.head)) |
|
176 else bsearch(cs.flatMap{case (c, as) => actions_map(c, as) }, |
|
177 bs.flatMap{case (c, as) => actions_map(c, as) }, d + 1) |
|
178 } |
|
179 |
|
180 bsearch(Map(init -> Nil), Map(solved -> Nil), 0).mkString("\n") |
|
181 |
175 |
182 |
176 |
183 |
177 |
184 // bidirectional breadth-first search |
178 // bidirectional breadth-first search |
185 def bsearch(cs: Map[Cube, Actions], |
179 def bsearch(cs: Map[Cube, Actions], |