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
43 use std
::iter
::repeat
;
45 use std
::sync
::mpsc
::channel
;
46 use std
::thread
::Thread
;
52 // returns an infinite iterator of repeated applications of f to x,
53 // i.e. [x, f(x), f(f(x)), ...], as haskell iterate function.
54 fn iterate
<T
, F
>(x
: T
, f
: F
) -> Iterate
<T
, F
> where F
: FnMut(&T
) -> T
{
55 Iterate {f: f, next: x}
57 struct Iterate
<T
, F
> where F
: FnMut(&T
) -> T
{
61 impl<T
, F
> Iterator
for Iterate
<T
, F
> where F
: FnMut(&T
) -> T
{
64 fn next(&mut self) -> Option
<T
> {
65 let mut res
= (self.f
)(&self.next
);
66 std
::mem
::swap(&mut res
, &mut self.next
);
71 // a linked list using borrowed next.
74 Cons(T
, &'a List
<'a
, T
>)
76 struct ListIterator
<'a
, T
:'a
> {
79 impl<'a
, T
> List
<'a
, T
> {
80 fn iter(&'a
self) -> ListIterator
<'a
, T
> {
81 ListIterator{cur: self}
84 impl<'a
, T
> Iterator
for ListIterator
<'a
, T
> {
87 fn next(&mut self) -> Option
<&'a T
> {
90 List
::Cons(ref elt
, next
) => {
102 // Takes a pieces p on the form [(y1, x1), (y2, x2), ...] and returns
103 // every possible transformations (the 6 rotations with their
104 // corresponding mirrored piece), with, as minimum coordinates, (0,
105 // 0). If all is false, only generate half of the possibilities (used
106 // to break the symmetry of the board).
107 fn transform(piece
: Vec
<(int
, int
)> , all
: bool
) -> Vec
<Vec
<(int
, int
)>> {
108 let mut res
: Vec
<Vec
<(int
, int
)>> =
110 iterate(piece
, |rot
| rot
.iter().map(|&(y
, x
)| (x
+ y
, -y
)).collect())
111 .take(if all {6}
else {3}
)
113 .flat_map(|cur_piece
| {
114 iterate(cur_piece
, |mir
| mir
.iter().map(|&(y
, x
)| (x
, y
)).collect())
118 // translating to (0, 0) as minimum coordinates.
119 for cur_piece
in res
.iter_mut() {
120 let (dy
, dx
) = *cur_piece
.iter().min_by(|e
| *e
).unwrap();
121 for &mut (ref mut y
, ref mut x
) in cur_piece
.iter_mut() {
129 // A mask is a piece somewhere on the board. It is represented as a
130 // u64: for i in the first 50 bits, m[i] = 1 if the cell at (i/5, i%5)
131 // is occupied. m[50 + id] = 1 if the identifier of the piece is id.
133 // Takes a piece with minimum coordinate (0, 0) (as generated by
134 // transform). Returns the corresponding mask if p translated by (dy,
135 // dx) is on the board.
136 fn mask(dy
: int
, dx
: int
, id
: uint
, p
: &Vec
<(int
, int
)>) -> Option
<u64> {
137 let mut m
= 1 << (50 + id
);
138 for &(y
, x
) in p
.iter() {
139 let x
= x
+ dx
+ (y
+ (dy
% 2)) / 2;
140 if x
< 0 || x
> 4 {return None;}
142 if y
< 0 || y
> 9 {return None;}
143 m
|= 1 << (y
* 5 + x
) as uint
;
148 // Makes every possible masks. masks[i][id] correspond to every
149 // possible masks for piece with identifier id with minimum coordinate
151 fn make_masks() -> Vec
<Vec
<Vec
<u64> > > {
153 vec
!((0i,0i),(0,1),(0,2),(0,3),(1,3)),
154 vec
!((0i,0i),(0,2),(0,3),(1,0),(1,1)),
155 vec
!((0i,0i),(0,1),(0,2),(1,2),(2,1)),
156 vec
!((0i,0i),(0,1),(0,2),(1,1),(2,1)),
157 vec
!((0i,0i),(0,2),(1,0),(1,1),(2,1)),
158 vec
!((0i,0i),(0,1),(0,2),(1,1),(1,2)),
159 vec
!((0i,0i),(0,1),(1,1),(1,2),(2,1)),
160 vec
!((0i,0i),(0,1),(0,2),(1,0),(1,2)),
161 vec
!((0i,0i),(0,1),(0,2),(1,2),(1,3)),
162 vec
!((0i,0i),(0,1),(0,2),(0,3),(1,2)));
164 // To break the central symmetry of the problem, every
165 // transformation must be taken except for one piece (piece 3
167 let transforms
: Vec
<Vec
<Vec
<(int
, int
)>>> =
168 pieces
.into_iter().enumerate()
169 .map(|(id
, p
)| transform(p
, id
!= 3))
172 range(0i, 50).map(|yx
| {
173 transforms
.iter().enumerate().map(|(id
, t
)| {
174 t
.iter().filter_map(|p
| mask(yx
/ 5, yx
% 5, id
, p
)).collect()
179 // Check if all coordinates can be covered by an unused piece and that
180 // all unused piece can be placed on the board.
181 fn is_board_unfeasible(board
: u64, masks
: &Vec
<Vec
<Vec
<u64>>>) -> bool
{
182 let mut coverable
= board
;
183 for (i
, masks_at
) in masks
.iter().enumerate() {
184 if board
& 1 << i
!= 0 { continue; }
185 for (cur_id
, pos_masks
) in masks_at
.iter().enumerate() {
186 if board
& 1 << (50 + cur_id
) != 0 { continue; }
187 for &cur_m
in pos_masks
.iter() {
188 if cur_m
& board
!= 0 { continue; }
190 // if every coordinates can be covered and every
191 // piece can be used.
192 if coverable
== (1 << 60) - 1 { return false; }
195 if coverable
& 1 << i
== 0 { return true; }
200 // Filter the masks that we can prove to result to unfeasible board.
201 fn filter_masks(masks
: &mut Vec
<Vec
<Vec
<u64>>>) {
202 for i
in range(0, masks
.len()) {
203 for j
in range(0, (*masks
)[i
].len()) {
205 (*masks
)[i
][j
].iter().map(|&m
| m
)
206 .filter(|&m
| !is_board_unfeasible(m
, masks
))
212 // Gets the identifier of a mask.
213 fn get_id(m
: u64) -> u8 {
214 for id
in range(0u8, 10) {
215 if m
& (1 << (id
+ 50) as uint
) != 0 {return id;}
217 panic
!("{:016x} does not have a valid identifier", m
);
220 // Converts a list of mask to a Vec<u8>.
221 fn to_vec(raw_sol
: &List
<u64>) -> Vec
<u8> {
222 let mut sol
= repeat('
.'
as u8).take(50).collect
::<Vec
<_
>>();
223 for &m
in raw_sol
.iter() {
224 let id
= '
0'
as u8 + get_id(m
);
225 for i
in range(0u, 50) {
234 // Prints a solution in Vec<u8> form.
235 fn print_sol(sol
: &Vec
<u8>) {
236 for (i
, c
) in sol
.iter().enumerate() {
237 if (i
) % 5 == 0 { println!(""); }
238 if (i
+ 5) % 10 == 0 { print!(" "); }
239 print
!("{} ", *c
as char);
244 // The data managed during the search
246 // Number of solution found.
248 // Lexicographically minimal solution found.
250 // Lexicographically maximal solution found.
255 Data {nb: 0, min: vec!(), max: vec!()}
257 fn reduce_from(&mut self, other
: Data
) {
259 let Data { min: min, max: max, ..}
= other
;
260 if min
< self.min { self.min = min; }
261 if max
> self.max { self.max = max; }
265 // Records a new found solution. Returns false if the search must be
267 fn handle_sol(raw_sol
: &List
<u64>, data
: &mut Data
) {
268 // because we break the symmetry, 2 solutions correspond to a call
269 // to this method: the normal solution, and the same solution in
270 // reverse order, i.e. the board rotated by half a turn.
272 let sol1
= to_vec(raw_sol
);
273 let sol2
: Vec
<u8> = sol1
.iter().rev().map(|x
| *x
).collect();
276 data
.min
= sol1
.clone();
277 data
.max
= sol1
.clone();
280 if sol1
< data
.min {data.min = sol1;}
281 else if sol1
> data
.max {data.max = sol1;}
282 if sol2
< data
.min {data.min = sol2;}
283 else if sol2
> data
.max {data.max = sol2;}
287 masks
: &Vec
<Vec
<Vec
<u64>>>,
293 // Search for the lesser empty coordinate.
294 while board
& (1 << i
) != 0 && i
< 50 {i += 1;}
295 // the board is full: a solution is found.
296 if i
>= 50 {return handle_sol(&cur, data);}
297 let masks_at
= &masks
[i
];
299 // for every unused piece
300 for id
in range(0u, 10).filter(|&id
| board
& (1 << (id
+ 50)) == 0) {
301 // for each mask that fits on the board
302 for m
in masks_at
[id
].iter().filter(|&m
| board
& *m
== 0) {
303 // This check is too costly.
304 //if is_board_unfeasible(board | m, masks) {continue;}
305 search(masks
, board
| *m
, i
+ 1, List
::Cons(*m
, &cur
), data
);
310 fn par_search(masks
: Vec
<Vec
<Vec
<u64>>>) -> Data
{
311 let masks
= Arc
::new(masks
);
312 let (tx
, rx
) = channel();
314 // launching the search in parallel on every masks at minimum
316 for m
in (*masks
)[0].iter().flat_map(|masks_pos
| masks_pos
.iter()) {
317 let masks
= masks
.clone();
320 Thread
::spawn(move|| {
321 let mut data
= Data
::new();
322 search(&*masks
, m
, 1, List
::Cons(m
, &List
::Nil
), &mut data
);
323 tx
.send(data
).unwrap();
327 // collecting the results
329 let mut data
= rx
.recv().unwrap();
330 for d
in rx
.iter() { data.reduce_from(d); }
335 let mut masks
= make_masks();
336 filter_masks(&mut masks
);
337 let data
= par_search(masks
);
338 println
!("{} solutions found", data
.nb
);
339 print_sol(&data
.min
);
340 print_sol(&data
.max
);