1 // The Computer Language Benchmarks Game
2 // http://benchmarksgame.alioth.debian.org/
4 // contributed by the Rust Project Developers
6 // Copyright (c) 2013-2014 The Rust Project Developers
8 // All rights reserved.
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions
14 // - Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
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
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.
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.
41 // no-pretty-expanded FIXME #15189
46 use std
::sync
::mpsc
::channel
;
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}
58 struct Iterate
<T
, F
> where F
: FnMut(&T
) -> T
{
62 impl<T
, F
> Iterator
for Iterate
<T
, F
> where F
: FnMut(&T
) -> T
{
65 fn next(&mut self) -> Option
<T
> {
66 let mut res
= (self.f
)(&self.next
);
67 std
::mem
::swap(&mut res
, &mut self.next
);
72 // a linked list using borrowed next.
75 Cons(T
, &'a List
<'a
, T
>)
77 struct ListIterator
<'a
, T
:'a
> {
80 impl<'a
, T
> List
<'a
, T
> {
81 fn iter(&'a
self) -> ListIterator
<'a
, T
> {
82 ListIterator{cur: self}
85 impl<'a
, T
> Iterator
for ListIterator
<'a
, T
> {
88 fn next(&mut self) -> Option
<&'a T
> {
91 List
::Cons(ref elt
, next
) => {
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).
108 fn transform(piece
: Vec
<(i32, i32)> , all
: bool
) -> Vec
<Vec
<(i32, i32)>> {
109 let mut res
: Vec
<Vec
<(i32, i32)>> =
111 iterate(piece
, |rot
| rot
.iter().map(|&(y
, x
)| (x
+ y
, -y
)).collect())
112 .take(if all {6}
else {3}
)
114 .flat_map(|cur_piece
| {
115 iterate(cur_piece
, |mir
| mir
.iter().map(|&(y
, x
)| (x
, y
)).collect())
119 // translating to (0, 0) as minimum coordinates.
120 for cur_piece
in &mut res
{
121 let (dy
, dx
) = *cur_piece
.iter().min_by(|e
| *e
).unwrap();
122 for &mut (ref mut y
, ref mut x
) in cur_piece
{
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.
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.
137 fn mask(dy
: i32, dx
: i32, id
: usize, p
: &Vec
<(i32, i32)>) -> Option
<u64> {
138 let mut m
= 1 << (50 + id
);
140 let x
= x
+ dx
+ (y
+ (dy
% 2)) / 2;
141 if x
< 0 || x
> 4 {return None;}
143 if y
< 0 || y
> 9 {return None;}
144 m
|= 1 << (y
* 5 + x
) as usize;
149 // Makes every possible masks. masks[i][id] correspond to every
150 // possible masks for piece with identifier id with minimum coordinate
152 fn make_masks() -> Vec
<Vec
<Vec
<u64> > > {
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)));
165 // To break the central symmetry of the problem, every
166 // transformation must be taken except for one piece (piece 3
168 let transforms
: Vec
<Vec
<Vec
<(i32, i32)>>> =
169 pieces
.into_iter().enumerate()
170 .map(|(id
, p
)| transform(p
, id
!= 3))
174 transforms
.iter().enumerate().map(|(id
, t
)| {
175 t
.iter().filter_map(|p
| mask(yx
/ 5, yx
% 5, id
, p
)).collect()
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; }
188 for &cur_m
in pos_masks
{
189 if cur_m
& board
!= 0 { continue; }
191 // if every coordinates can be covered and every
192 // piece can be used.
193 if coverable
== (1 << 60) - 1 { return false; }
196 if coverable
& 1 << i
== 0 { return true; }
201 // Filter the masks that we can prove to result to unfeasible board.
202 fn filter_masks(masks
: &mut Vec
<Vec
<Vec
<u64>>>) {
203 for i
in 0..masks
.len() {
204 for j
in 0..(*masks
)[i
].len() {
206 (*masks
)[i
][j
].iter().cloned()
207 .filter(|&m
| !is_board_unfeasible(m
, masks
))
213 // Gets the identifier of a mask.
214 fn get_id(m
: u64) -> u8 {
216 if m
& (1 << (id
+ 50) as usize) != 0 {return id;}
218 panic
!("{:016x} does not have a valid identifier", m
);
221 // Converts a list of mask to a Vec<u8>.
222 fn to_vec(raw_sol
: &List
<u64>) -> Vec
<u8> {
223 let mut sol
= vec
![b'
.'
; 50];
224 for &m
in raw_sol
.iter() {
225 let id
= '
0'
as u8 + get_id(m
);
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);
245 // The data managed during the search
247 // Number of solution found.
249 // Lexicographically minimal solution found.
251 // Lexicographically maximal solution found.
256 Data {nb: 0, min: vec!(), max: vec!()}
258 fn reduce_from(&mut self, other
: Data
) {
260 let Data { min: min, max: max, ..}
= other
;
261 if min
< self.min { self.min = min; }
262 if max
> self.max { self.max = max; }
266 // Records a new found solution. Returns false if the search must be
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.
273 let sol1
= to_vec(raw_sol
);
274 let sol2
: Vec
<u8> = sol1
.iter().rev().cloned().collect();
277 data
.min
= sol1
.clone();
278 data
.max
= sol1
.clone();
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;}
288 masks
: &Vec
<Vec
<Vec
<u64>>>,
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
];
300 // for every unused piece
301 for id
in (0..10).filter(|&id
| board
& (1 << (id
+ 50)) == 0) {
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
);
311 fn par_search(masks
: Vec
<Vec
<Vec
<u64>>>) -> Data
{
312 let masks
= Arc
::new(masks
);
313 let (tx
, rx
) = channel();
315 // launching the search in parallel on every masks at minimum
317 for m
in (*masks
)[0].iter().flat_map(|masks_pos
| masks_pos
) {
318 let masks
= masks
.clone();
321 thread
::spawn(move|| {
322 let mut data
= Data
::new();
323 search(&*masks
, m
, 1, List
::Cons(m
, &List
::Nil
), &mut data
);
324 tx
.send(data
).unwrap();
328 // collecting the results
330 let mut data
= rx
.recv().unwrap();
331 for d
in rx
.iter() { data.reduce_from(d); }
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
);