board_game/util/
mask.rs

1use crate::util::bitboard::BitBoard8;
2use crate::util::coord::Coord8;
3use std::fmt::{Display, Formatter};
4
5#[derive(Debug, Default, Copy, Clone)]
6pub struct Mask {
7    one: u64,
8    zero: u64,
9}
10
11/// Find a set of masks that covers the given requirements.
12/// This basically solves the [Set cover problem](https://en.wikipedia.org/wiki/Set_cover_problem).
13pub fn cover_masks(requirements: &[Mask]) -> Vec<(Mask, Vec<usize>)> {
14    // TODO this is a greedy implementation, write a better one
15    //   doesn't really need to be fast, just optimal
16    let mut result: Vec<(Mask, Vec<usize>)> = vec![];
17    'outer: for (req_index, &req) in requirements.iter().enumerate() {
18        for (cand, map) in &mut result {
19            if let Some(new) = cand.merge(req) {
20                *cand = new;
21                map.push(req_index);
22                continue 'outer;
23            }
24        }
25        result.push((req, vec![req_index]));
26    }
27    result
28}
29
30impl Mask {
31    fn new(one: u64, zero: u64) -> Option<Self> {
32        if one & zero == 0 {
33            Some(Mask { one, zero })
34        } else {
35            None
36        }
37    }
38
39    fn merge(self, other: Mask) -> Option<Mask> {
40        Mask::new(self.one | other.one, self.zero | other.zero)
41    }
42
43    pub fn one(&self) -> u64 {
44        self.one
45    }
46
47    pub fn zero(&self) -> u64 {
48        self.zero
49    }
50}
51
52pub type Operation = fn(BitBoard8) -> BitBoard8;
53
54pub fn find_requirements(ops: &[(i32, Operation)], result_mask: u64) -> Vec<Mask> {
55    let mut requirements = vec![];
56
57    for &(shift, op) in ops {
58        let mut mask_one = 0;
59        let mut mask_zero = 0;
60
61        for coord in Coord8::all() {
62            let before = BitBoard8::coord(coord).0 & result_mask;
63            let after_correct = op(BitBoard8(before)).0 & result_mask;
64            let after_shift = apply_shift(before, shift) & result_mask;
65
66            assert_eq!(after_correct & !after_shift, 0, "Shift must cover correct");
67            mask_one |= after_correct;
68            mask_zero |= after_shift & !after_correct;
69        }
70
71        requirements.push(Mask::new(mask_one, mask_zero).unwrap());
72    }
73
74    requirements
75}
76
77impl Display for Mask {
78    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
79        for y in (0..8).rev() {
80            for x in 0..8 {
81                let coord = Coord8::from_xy(x, y);
82
83                let c = match (BitBoard8(self.one).has(coord), BitBoard8(self.zero).has(coord)) {
84                    (true, false) => '1',
85                    (false, true) => '0',
86                    (false, false) => '.',
87                    (true, true) => 'x',
88                };
89
90                write!(f, "{}", c)?;
91            }
92            writeln!(f)?;
93        }
94        Ok(())
95    }
96}
97
98fn apply_shift(x: u64, delta: i32) -> u64 {
99    if delta >= 0 {
100        x << delta as u32
101    } else {
102        x >> (-delta) as u32
103    }
104}
board_game/util/mask.rs

board_game/util/
mask.rs
