1 // 2 x 2 x 2 Rubik's Cube |
1 // 2 x 2 x 2 Rubik's Cube |
2 //======================== |
2 //======================== |
3 |
3 |
4 // more memory for the JVM |
4 // for more memory for the JVM, call |
5 // |
5 // |
6 // JAVA_OPTS="-Xmx2g" scala |
6 // JAVA_OPTS="-Xmx2g" scala |
7 |
7 |
8 |
8 |
9 // for measuring memory usage |
9 // for measuring memory usage |
92 Face(c.f4.c11, c.f4.c12, c.f6.c12, c.f6.c11), |
92 Face(c.f4.c11, c.f4.c12, c.f6.c12, c.f6.c11), |
93 Face(c.f4.c22, c.f4.c21, c.f5.c21, c.f5.c22), |
93 Face(c.f4.c22, c.f4.c21, c.f5.c21, c.f5.c22), |
94 Face(c.f1.c11, c.f1.c12, c.f6.c21, c.f6.c22)) |
94 Face(c.f1.c11, c.f1.c12, c.f6.c21, c.f6.c22)) |
95 |
95 |
96 |
96 |
97 // simple bf-search without solution, just true |
97 // simple bf-search without generating a solution, just true |
98 |
98 |
99 def actions(c: Cube) : List[Cube] = |
99 def actions(c: Cube) : List[Cube] = |
100 List(up(c), clock(c), right(c)) |
100 List(up(c), clock(c), right(c)) |
101 |
101 |
102 def search(cs: List[Cube], d: Int) : Boolean = { |
102 def search(cs: List[Cube], d: Int) : Boolean = { |
106 else search(cs.flatMap(actions), d + 1) |
106 else search(cs.flatMap(actions), d + 1) |
107 } |
107 } |
108 |
108 |
109 search(List(init), 0) |
109 search(List(init), 0) |
110 |
110 |
111 // Set version |
111 |
|
112 // set version |
112 def actions_set(c: Cube) : Set[Cube] = |
113 def actions_set(c: Cube) : Set[Cube] = |
113 Set(up(c), clock(c), right(c)) |
114 Set(up(c), clock(c), right(c)) |
114 |
115 |
115 def search_set(cs: Set[Cube], d: Int) : Boolean = { |
116 def search_set(cs: Set[Cube], d: Int) : Boolean = { |
116 println(s"Depth: $d candidates: ${cs.size}") |
117 println(s"Depth: $d candidates: ${cs.size}") |
120 } |
121 } |
121 |
122 |
122 search_set(Set(init), 0) |
123 search_set(Set(init), 0) |
123 |
124 |
124 |
125 |
125 // For generating list of actions |
126 // for generating list of actions |
126 abstract class Action |
127 abstract class Action |
127 case object Up extends Action |
128 case object Up extends Action |
128 case object Right extends Action |
129 case object Right extends Action |
129 case object Clock extends Action |
130 case object Clock extends Action |
130 |
131 |
131 type Actions = List[Action] |
132 type Actions = List[Action] |
132 |
133 |
133 // List version generating a list of actions |
134 // list version generating a list of actions |
134 def actions_list(c: Cube, act: Actions) : List[(Cube, Actions)] = |
135 def actions_list(c: Cube, act: Actions) : List[(Cube, Actions)] = |
135 List((up(c), Up::act), |
136 List((up(c), Up::act), |
136 (clock(c), Clock::act), |
137 (clock(c), Clock::act), |
137 (right(c), Right::act)) |
138 (right(c), Right::act)) |
138 |
139 |
145 } |
146 } |
146 |
147 |
147 search_list(List((init, Nil)), 0)._2.reverse.mkString("\n") |
148 search_list(List((init, Nil)), 0)._2.reverse.mkString("\n") |
148 |
149 |
149 |
150 |
150 // Map version generating a list of actions |
151 // map version generating a list of actions |
151 def actions_map(c: Cube, as: Actions) : Map[Cube, Actions] = |
152 def actions_map(c: Cube, as: Actions) : Map[Cube, Actions] = |
152 Map(up(c) -> (Up::as), |
153 Map(up(c) -> (Up::as), |
153 clock(c) -> (Clock::as), |
154 clock(c) -> (Clock::as), |
154 right(c) -> (Right::as)) |
155 right(c) -> (Right::as)) |
155 |
156 |
164 |
165 |
165 search_map(Map(init -> Nil), 0).reverse.mkString("\n") |
166 search_map(Map(init -> Nil), 0).reverse.mkString("\n") |
166 |
167 |
167 |
168 |
168 |
169 |
169 // Bidirectional breadth-first search |
170 // bidirectional breadth-first search |
170 def bsearch(cs: Map[Cube, Actions], |
171 def bsearch(cs: Map[Cube, Actions], |
171 bs: Map[Cube, Actions], d: Int) : Actions = { |
172 bs: Map[Cube, Actions], d: Int) : Actions = { |
172 println(s"Depth: $d Cands: ${cs.keySet.size}/${bs.keySet.size}") |
173 println(s"Depth: $d Cands: ${cs.keySet.size}/${bs.keySet.size}") |
173 val res = cs.keySet intersect bs.keySet |
174 val res = cs.keySet intersect bs.keySet |
174 if (!res.isEmpty) (cs(res.head).reverse ::: bs(res.head)) |
175 if (!res.isEmpty) (cs(res.head).reverse ::: bs(res.head)) |
178 |
179 |
179 bsearch(Map(init -> Nil), Map(solved -> Nil), 0).mkString("\n") |
180 bsearch(Map(init -> Nil), Map(solved -> Nil), 0).mkString("\n") |
180 |
181 |
181 |
182 |
182 |
183 |
183 |
184 // bidirectional breadth-first search |
184 |
185 def bsearch(cs: Map[Cube, Actions], |
185 |
186 bs: Map[Cube, Actions], d: Int) : Actions = { |
186 |
187 println(s"Depth: $d Cands: ${cs.keySet.size}/${bs.keySet.size}") |
187 |
188 val res = cs.keySet intersect bs.keySet |
188 |
189 if (!res.isEmpty) (cs(res.head).reverse ::: bs(res.head)) |
189 |
190 else bsearch(cs.flatMap{ (c, as) => actions_map(c, as) }, |
190 |
191 bs.flatMap{ (c, as) => actions_map(c, as) }, d + 1) |
191 |
192 } |
192 |
193 |
193 |
194 bsearch(Map(init -> Nil), Map(solved -> Nil), 0).mkString("\n") |
194 |
195 |
195 |
196 |
196 |
197 |
197 |
198 |
198 |
199 |
199 |
200 |
|
201 |
|
202 |
|
203 |
|
204 |
|
205 |
|
206 |
|
207 |
|
208 |
|
209 |
|
210 |
|
211 |
|
212 |
|
213 |
|
214 |