]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // The Computer Language Benchmarks Game |
2 | // http://benchmarksgame.alioth.debian.org/ | |
3 | // | |
4 | // contributed by the Rust Project Developers | |
5 | ||
6 | // Copyright (c) 2013-2014 The Rust Project Developers | |
7 | // | |
8 | // All rights reserved. | |
9 | // | |
10 | // Redistribution and use in source and binary forms, with or without | |
11 | // modification, are permitted provided that the following conditions | |
12 | // are met: | |
13 | // | |
14 | // - Redistributions of source code must retain the above copyright | |
15 | // notice, this list of conditions and the following disclaimer. | |
16 | // | |
17 | // - Redistributions in binary form must reproduce the above copyright | |
18 | // notice, this list of conditions and the following disclaimer in | |
19 | // the documentation and/or other materials provided with the | |
20 | // distribution. | |
21 | // | |
22 | // - Neither the name of "The Computer Language Benchmarks Game" nor | |
23 | // the name of "The Computer Language Shootout Benchmarks" nor the | |
24 | // names of its contributors may be used to endorse or promote | |
25 | // products derived from this software without specific prior | |
26 | // written permission. | |
27 | // | |
28 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
29 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
30 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | |
31 | // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | |
32 | // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, | |
33 | // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
34 | // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |
35 | // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
36 | // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
37 | // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
38 | // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
39 | // OF THE POSSIBILITY OF SUCH DAMAGE. | |
40 | ||
41 | // no-pretty-expanded FIXME #15189 | |
42 | ||
62682a34 | 43 | #![feature(iter_cmp)] |
c34b1796 | 44 | |
1a4d82fc JJ |
45 | use std::sync::Arc; |
46 | use std::sync::mpsc::channel; | |
85aaf69f | 47 | use std::thread; |
1a4d82fc JJ |
48 | |
49 | // | |
50 | // Utilities. | |
51 | // | |
52 | ||
53 | // returns an infinite iterator of repeated applications of f to x, | |
54 | // i.e. [x, f(x), f(f(x)), ...], as haskell iterate function. | |
55 | fn iterate<T, F>(x: T, f: F) -> Iterate<T, F> where F: FnMut(&T) -> T { | |
56 | Iterate {f: f, next: x} | |
57 | } | |
58 | struct Iterate<T, F> where F: FnMut(&T) -> T { | |
59 | f: F, | |
60 | next: T | |
61 | } | |
62 | impl<T, F> Iterator for Iterate<T, F> where F: FnMut(&T) -> T { | |
63 | type Item = T; | |
64 | ||
65 | fn next(&mut self) -> Option<T> { | |
66 | let mut res = (self.f)(&self.next); | |
67 | std::mem::swap(&mut res, &mut self.next); | |
68 | Some(res) | |
69 | } | |
70 | } | |
71 | ||
72 | // a linked list using borrowed next. | |
73 | enum List<'a, T:'a> { | |
74 | Nil, | |
75 | Cons(T, &'a List<'a, T>) | |
76 | } | |
77 | struct ListIterator<'a, T:'a> { | |
78 | cur: &'a List<'a, T> | |
79 | } | |
80 | impl<'a, T> List<'a, T> { | |
81 | fn iter(&'a self) -> ListIterator<'a, T> { | |
82 | ListIterator{cur: self} | |
83 | } | |
84 | } | |
85 | impl<'a, T> Iterator for ListIterator<'a, T> { | |
86 | type Item = &'a T; | |
87 | ||
88 | fn next(&mut self) -> Option<&'a T> { | |
89 | match *self.cur { | |
90 | List::Nil => None, | |
91 | List::Cons(ref elt, next) => { | |
92 | self.cur = next; | |
93 | Some(elt) | |
94 | } | |
95 | } | |
96 | } | |
97 | } | |
98 | ||
99 | // | |
100 | // preprocess | |
101 | // | |
102 | ||
103 | // Takes a pieces p on the form [(y1, x1), (y2, x2), ...] and returns | |
104 | // every possible transformations (the 6 rotations with their | |
105 | // corresponding mirrored piece), with, as minimum coordinates, (0, | |
106 | // 0). If all is false, only generate half of the possibilities (used | |
107 | // to break the symmetry of the board). | |
85aaf69f SL |
108 | fn transform(piece: Vec<(i32, i32)> , all: bool) -> Vec<Vec<(i32, i32)>> { |
109 | let mut res: Vec<Vec<(i32, i32)>> = | |
1a4d82fc JJ |
110 | // rotations |
111 | iterate(piece, |rot| rot.iter().map(|&(y, x)| (x + y, -y)).collect()) | |
112 | .take(if all {6} else {3}) | |
113 | // mirror | |
114 | .flat_map(|cur_piece| { | |
115 | iterate(cur_piece, |mir| mir.iter().map(|&(y, x)| (x, y)).collect()) | |
116 | .take(2) | |
117 | }).collect(); | |
118 | ||
119 | // translating to (0, 0) as minimum coordinates. | |
85aaf69f | 120 | for cur_piece in &mut res { |
1a4d82fc | 121 | let (dy, dx) = *cur_piece.iter().min_by(|e| *e).unwrap(); |
85aaf69f | 122 | for &mut (ref mut y, ref mut x) in cur_piece { |
1a4d82fc JJ |
123 | *y -= dy; *x -= dx; |
124 | } | |
125 | } | |
126 | ||
127 | res | |
128 | } | |
129 | ||
130 | // A mask is a piece somewhere on the board. It is represented as a | |
131 | // u64: for i in the first 50 bits, m[i] = 1 if the cell at (i/5, i%5) | |
132 | // is occupied. m[50 + id] = 1 if the identifier of the piece is id. | |
133 | ||
134 | // Takes a piece with minimum coordinate (0, 0) (as generated by | |
135 | // transform). Returns the corresponding mask if p translated by (dy, | |
136 | // dx) is on the board. | |
85aaf69f | 137 | fn mask(dy: i32, dx: i32, id: usize, p: &Vec<(i32, i32)>) -> Option<u64> { |
1a4d82fc | 138 | let mut m = 1 << (50 + id); |
85aaf69f | 139 | for &(y, x) in p { |
1a4d82fc JJ |
140 | let x = x + dx + (y + (dy % 2)) / 2; |
141 | if x < 0 || x > 4 {return None;} | |
142 | let y = y + dy; | |
143 | if y < 0 || y > 9 {return None;} | |
85aaf69f | 144 | m |= 1 << (y * 5 + x) as usize; |
1a4d82fc JJ |
145 | } |
146 | Some(m) | |
147 | } | |
148 | ||
149 | // Makes every possible masks. masks[i][id] correspond to every | |
150 | // possible masks for piece with identifier id with minimum coordinate | |
151 | // (i/5, i%5). | |
152 | fn make_masks() -> Vec<Vec<Vec<u64> > > { | |
153 | let pieces = vec!( | |
85aaf69f SL |
154 | vec!((0,0),(0,1),(0,2),(0,3),(1,3)), |
155 | vec!((0,0),(0,2),(0,3),(1,0),(1,1)), | |
156 | vec!((0,0),(0,1),(0,2),(1,2),(2,1)), | |
157 | vec!((0,0),(0,1),(0,2),(1,1),(2,1)), | |
158 | vec!((0,0),(0,2),(1,0),(1,1),(2,1)), | |
159 | vec!((0,0),(0,1),(0,2),(1,1),(1,2)), | |
160 | vec!((0,0),(0,1),(1,1),(1,2),(2,1)), | |
161 | vec!((0,0),(0,1),(0,2),(1,0),(1,2)), | |
162 | vec!((0,0),(0,1),(0,2),(1,2),(1,3)), | |
163 | vec!((0,0),(0,1),(0,2),(0,3),(1,2))); | |
1a4d82fc JJ |
164 | |
165 | // To break the central symmetry of the problem, every | |
166 | // transformation must be taken except for one piece (piece 3 | |
167 | // here). | |
85aaf69f | 168 | let transforms: Vec<Vec<Vec<(i32, i32)>>> = |
1a4d82fc JJ |
169 | pieces.into_iter().enumerate() |
170 | .map(|(id, p)| transform(p, id != 3)) | |
171 | .collect(); | |
172 | ||
c34b1796 | 173 | (0..50).map(|yx| { |
1a4d82fc JJ |
174 | transforms.iter().enumerate().map(|(id, t)| { |
175 | t.iter().filter_map(|p| mask(yx / 5, yx % 5, id, p)).collect() | |
176 | }).collect() | |
177 | }).collect() | |
178 | } | |
179 | ||
180 | // Check if all coordinates can be covered by an unused piece and that | |
181 | // all unused piece can be placed on the board. | |
182 | fn is_board_unfeasible(board: u64, masks: &Vec<Vec<Vec<u64>>>) -> bool { | |
183 | let mut coverable = board; | |
184 | for (i, masks_at) in masks.iter().enumerate() { | |
185 | if board & 1 << i != 0 { continue; } | |
186 | for (cur_id, pos_masks) in masks_at.iter().enumerate() { | |
187 | if board & 1 << (50 + cur_id) != 0 { continue; } | |
85aaf69f | 188 | for &cur_m in pos_masks { |
1a4d82fc JJ |
189 | if cur_m & board != 0 { continue; } |
190 | coverable |= cur_m; | |
191 | // if every coordinates can be covered and every | |
192 | // piece can be used. | |
193 | if coverable == (1 << 60) - 1 { return false; } | |
194 | } | |
195 | } | |
196 | if coverable & 1 << i == 0 { return true; } | |
197 | } | |
198 | true | |
199 | } | |
200 | ||
201 | // Filter the masks that we can prove to result to unfeasible board. | |
202 | fn filter_masks(masks: &mut Vec<Vec<Vec<u64>>>) { | |
85aaf69f SL |
203 | for i in 0..masks.len() { |
204 | for j in 0..(*masks)[i].len() { | |
1a4d82fc | 205 | masks[i][j] = |
85aaf69f | 206 | (*masks)[i][j].iter().cloned() |
1a4d82fc JJ |
207 | .filter(|&m| !is_board_unfeasible(m, masks)) |
208 | .collect(); | |
209 | } | |
210 | } | |
211 | } | |
212 | ||
213 | // Gets the identifier of a mask. | |
214 | fn get_id(m: u64) -> u8 { | |
c34b1796 | 215 | for id in 0..10 { |
85aaf69f | 216 | if m & (1 << (id + 50) as usize) != 0 {return id;} |
1a4d82fc JJ |
217 | } |
218 | panic!("{:016x} does not have a valid identifier", m); | |
219 | } | |
220 | ||
221 | // Converts a list of mask to a Vec<u8>. | |
222 | fn to_vec(raw_sol: &List<u64>) -> Vec<u8> { | |
c1a9b12d | 223 | let mut sol = vec![b'.'; 50]; |
1a4d82fc JJ |
224 | for &m in raw_sol.iter() { |
225 | let id = '0' as u8 + get_id(m); | |
85aaf69f | 226 | for i in 0..50 { |
1a4d82fc JJ |
227 | if m & 1 << i != 0 { |
228 | sol[i] = id; | |
229 | } | |
230 | } | |
231 | } | |
232 | sol | |
233 | } | |
234 | ||
235 | // Prints a solution in Vec<u8> form. | |
236 | fn print_sol(sol: &Vec<u8>) { | |
237 | for (i, c) in sol.iter().enumerate() { | |
238 | if (i) % 5 == 0 { println!(""); } | |
239 | if (i + 5) % 10 == 0 { print!(" "); } | |
240 | print!("{} ", *c as char); | |
241 | } | |
242 | println!(""); | |
243 | } | |
244 | ||
245 | // The data managed during the search | |
246 | struct Data { | |
247 | // Number of solution found. | |
85aaf69f | 248 | nb: isize, |
1a4d82fc JJ |
249 | // Lexicographically minimal solution found. |
250 | min: Vec<u8>, | |
251 | // Lexicographically maximal solution found. | |
252 | max: Vec<u8> | |
253 | } | |
254 | impl Data { | |
255 | fn new() -> Data { | |
256 | Data {nb: 0, min: vec!(), max: vec!()} | |
257 | } | |
258 | fn reduce_from(&mut self, other: Data) { | |
259 | self.nb += other.nb; | |
260 | let Data { min: min, max: max, ..} = other; | |
261 | if min < self.min { self.min = min; } | |
262 | if max > self.max { self.max = max; } | |
263 | } | |
264 | } | |
265 | ||
266 | // Records a new found solution. Returns false if the search must be | |
267 | // stopped. | |
268 | fn handle_sol(raw_sol: &List<u64>, data: &mut Data) { | |
269 | // because we break the symmetry, 2 solutions correspond to a call | |
270 | // to this method: the normal solution, and the same solution in | |
271 | // reverse order, i.e. the board rotated by half a turn. | |
272 | data.nb += 2; | |
273 | let sol1 = to_vec(raw_sol); | |
85aaf69f | 274 | let sol2: Vec<u8> = sol1.iter().rev().cloned().collect(); |
1a4d82fc JJ |
275 | |
276 | if data.nb == 2 { | |
277 | data.min = sol1.clone(); | |
278 | data.max = sol1.clone(); | |
279 | } | |
280 | ||
281 | if sol1 < data.min {data.min = sol1;} | |
282 | else if sol1 > data.max {data.max = sol1;} | |
283 | if sol2 < data.min {data.min = sol2;} | |
284 | else if sol2 > data.max {data.max = sol2;} | |
285 | } | |
286 | ||
287 | fn search( | |
288 | masks: &Vec<Vec<Vec<u64>>>, | |
289 | board: u64, | |
85aaf69f | 290 | mut i: usize, |
1a4d82fc JJ |
291 | cur: List<u64>, |
292 | data: &mut Data) | |
293 | { | |
294 | // Search for the lesser empty coordinate. | |
295 | while board & (1 << i) != 0 && i < 50 {i += 1;} | |
296 | // the board is full: a solution is found. | |
297 | if i >= 50 {return handle_sol(&cur, data);} | |
298 | let masks_at = &masks[i]; | |
299 | ||
300 | // for every unused piece | |
85aaf69f | 301 | for id in (0..10).filter(|&id| board & (1 << (id + 50)) == 0) { |
1a4d82fc JJ |
302 | // for each mask that fits on the board |
303 | for m in masks_at[id].iter().filter(|&m| board & *m == 0) { | |
304 | // This check is too costly. | |
305 | //if is_board_unfeasible(board | m, masks) {continue;} | |
306 | search(masks, board | *m, i + 1, List::Cons(*m, &cur), data); | |
307 | } | |
308 | } | |
309 | } | |
310 | ||
311 | fn par_search(masks: Vec<Vec<Vec<u64>>>) -> Data { | |
312 | let masks = Arc::new(masks); | |
313 | let (tx, rx) = channel(); | |
314 | ||
315 | // launching the search in parallel on every masks at minimum | |
316 | // coordinate (0,0) | |
62682a34 | 317 | for m in (*masks)[0].iter().flat_map(|masks_pos| masks_pos) { |
1a4d82fc JJ |
318 | let masks = masks.clone(); |
319 | let tx = tx.clone(); | |
320 | let m = *m; | |
85aaf69f | 321 | thread::spawn(move|| { |
1a4d82fc JJ |
322 | let mut data = Data::new(); |
323 | search(&*masks, m, 1, List::Cons(m, &List::Nil), &mut data); | |
324 | tx.send(data).unwrap(); | |
325 | }); | |
326 | } | |
327 | ||
328 | // collecting the results | |
329 | drop(tx); | |
330 | let mut data = rx.recv().unwrap(); | |
331 | for d in rx.iter() { data.reduce_from(d); } | |
332 | data | |
333 | } | |
334 | ||
335 | fn main () { | |
336 | let mut masks = make_masks(); | |
337 | filter_masks(&mut masks); | |
338 | let data = par_search(masks); | |
339 | println!("{} solutions found", data.nb); | |
340 | print_sol(&data.min); | |
341 | print_sol(&data.max); | |
342 | println!(""); | |
343 | } |