Minesweeper combinatorial number system

binomial_coefficient.rs

use malachite::Natural;
use malachite::base::num::arithmetic::traits::BinomialCoefficient as _;
use malachite::base::num::basic::traits::{One, Zero};

use crate::multiply_and_divide::MultiplyAndDivide;

/// Compute binomial coefficients (`n choose k`). Store the last result and parameters and reuse
/// them if it makes the computation of the next result with nearby parameters faster.
#[derive(Debug, Clone)]
pub struct BinomialCoefficient {
    /// The last computed binomial coefficient (`n choose k`).
    value: Natural,
    /// the `n` value in `n choose k` for `value`.
    n: usize,
    /// the `k` value in `n choose k` for `value`.
    k: usize,

    /// An event log for the test suite.
    #[cfg(test)]
    pub(self) _test_event_log: Vec<Event>,
}

/// Events logged by the implementation while running the test suite.
#[cfg(test)]
#[derive(Debug, Clone, Eq, PartialEq)]
pub(self) enum Event {
    OneCase {
        target_n: usize,
        target_k: usize,
    },
    NCase {
        target_n: usize,
        target_k: usize,
    },
    ZeroCase {
        target_n: usize,
        target_k: usize,
    },
    IdenticalCase {
        n: usize,
        k: usize,
        value: Natural,
    },
    FlippingK {
        n: usize,
        k_old: usize,
        k_new: usize,
        target_n: usize,
        target_k: usize,
    },
    ComputingFromScratch {
        n: usize,
        k: usize,
        target_n: usize,
        target_k: usize,
    },
    ShrinkingNK {
        n: usize,
        k: usize,
        target_n: usize,
        target_k: usize,
    },
    ShrinkingN {
        n: usize,
        k: usize,
        target_n: usize,
        target_k: usize,
    },
    ShrinkingK {
        n: usize,
        k: usize,
        target_n: usize,
        target_k: usize,
    },
    GrowingNK {
        n: usize,
        k: usize,
        target_n: usize,
        target_k: usize,
    },
    GrowingK {
        n: usize,
        k: usize,
        target_n: usize,
        target_k: usize,
    },
    GrowingN {
        n: usize,
        k: usize,
        target_n: usize,
        target_k: usize,
    },
    Done {
        n: usize,
        k: usize,
        value: Natural,
    },
}

#[derive(Debug, Copy, Clone, Eq, PartialEq)]
struct Params {
    /// the `n` value in `n choose k`.
    n: usize,
    /// the `k` value in `n choose k`.
    k: usize,
}

macro_rules! bc_debug_assert {
    ($self:expr, $invariant:expr, $message:literal, [ $($value:expr),+ $(,)? ] $(,)?) => {
        #[cfg(debug_assertions)] {
            if !$invariant {
                eprintln!("[{}:{}:{}] Assertion failure", file!(), line!(), column!());

                #[cfg(test)]
                {
                    eprintln!("Events:");
                    for event in &$self._test_event_log {
                        eprintln!("  - {:?}", event);
                    }
                }

                if ($message.len() > 0) {
                    eprintln!("{}", $message);
                } else {
                    eprintln!("Expected: {}", stringify!($invariant));
                }

                eprint!("Values:");
                $(
                    eprint!(" {}={:?}", stringify!($value), &$value);
                )+
                eprintln!();

                panic!("Assertion failure");
            }
        }
    };
}

impl Default for BinomialCoefficient {
    fn default() -> Self {
        Self::new()
    }
}

impl BinomialCoefficient {
    pub fn new() -> Self {
        Self {
            value: Natural::ONE,
            n: 1,
            k: 1,

            #[cfg(test)]
            _test_event_log: vec![],
        }
    }

    /// Compute a binomial coefficient (`n choose k`).
    pub fn choose(&mut self, target_n: usize, target_k: usize) -> Natural {
        #[cfg(test)]
        self._test_event_log.clear();

        let target = Params {
            n: target_n,
            k: target_k,
        };

        if target.k == 0 || target.k == target.n {
            #[cfg(test)]
            self._test_event_log.push(Event::OneCase {
                target_n: target.n,
                target_k: target.k,
            });

            return Natural::ONE;
        } else if target.k == 1 {
            #[cfg(test)]
            self._test_event_log.push(Event::NCase {
                target_n: target.n,
                target_k: target.k,
            });

            return Natural::from(target.n);
        } else if target.k > target.n {
            #[cfg(test)]
            self._test_event_log.push(Event::ZeroCase {
                target_n: target.n,
                target_k: target.k,
            });

            return Natural::ZERO;
        } else if target.n == self.n && target.k == self.k {
            #[cfg(test)]
            self._test_event_log.push(Event::IdenticalCase {
                n: target.n,
                k: target.k,
                value: self.value.clone(),
            });

            return self.value.clone();
        }

        // Flip `k` if that gets us closer to the target.
        if let n_minus_k = self.n - self.k
            && target.k.abs_diff(n_minus_k) < target.k.abs_diff(self.k)
        {
            #[cfg(test)]
            self._test_event_log.push(Event::FlippingK {
                n: self.n,
                k_old: self.k,
                k_new: n_minus_k,
                target_n: target.n,
                target_k: target.k,
            });

            self.k = n_minus_k;
        }

        let num_iterations_predicted = self.num_iterations_incrementally(target);

        if Self::num_iterations_from_scratch(target) <= num_iterations_predicted {
            #[cfg(test)]
            self._test_event_log.push(Event::ComputingFromScratch {
                n: self.n,
                k: self.k,
                target_n: target.n,
                target_k: target.k,
            });

            self.n = target.n;
            self.k = target.k;

            self.value =
                Natural::binomial_coefficient(Natural::from(self.n), Natural::from(self.k));

            return self.value.clone();
        }

        #[cfg(debug_assertions)]
        let mut num_iterations = 0;

        let mut mul_div = MultiplyAndDivide::default();

        while self.n > target.n && self.k > target.k {
            #[cfg(test)]
            self._test_event_log.push(Event::ShrinkingNK {
                n: self.n,
                k: self.k,
                target_n: target.n,
                target_k: target.k,
            });

            self.shrink_n_k(&mut mul_div);

            #[cfg(debug_assertions)]
            {
                num_iterations += 1;
            }
        }

        while self.n > target.n {
            #[cfg(test)]
            self._test_event_log.push(Event::ShrinkingN {
                n: self.n,
                k: self.k,
                target_n: target.n,
                target_k: target.k,
            });

            self.shrink_n(&mut mul_div);

            #[cfg(debug_assertions)]
            {
                num_iterations += 1;
            }
        }

        while self.k > target.k {
            #[cfg(test)]
            self._test_event_log.push(Event::ShrinkingK {
                n: self.n,
                k: self.k,
                target_n: target.n,
                target_k: target.k,
            });

            self.shrink_k(&mut mul_div);

            #[cfg(debug_assertions)]
            {
                num_iterations += 1;
            }
        }

        while self.n < target.n && self.k < target.k {
            #[cfg(test)]
            self._test_event_log.push(Event::GrowingNK {
                n: self.n,
                k: self.k,
                target_n: target.n,
                target_k: target.k,
            });

            self.grow_n_k(&mut mul_div);

            #[cfg(debug_assertions)]
            {
                num_iterations += 1;
            }
        }

        while self.n < target.n {
            #[cfg(test)]
            self._test_event_log.push(Event::GrowingN {
                n: self.n,
                k: self.k,
                target_n: target.n,
                target_k: target.k,
            });

            self.grow_n(&mut mul_div);

            #[cfg(debug_assertions)]
            {
                num_iterations += 1;
            }
        }

        while self.k < target.k {
            #[cfg(test)]
            self._test_event_log.push(Event::GrowingK {
                n: self.n,
                k: self.k,
                target_n: target.n,
                target_k: target.k,
            });

            self.grow_k(&mut mul_div);

            #[cfg(debug_assertions)]
            {
                num_iterations += 1;
            }
        }

        mul_div.apply_mut(&mut self.value);

        bc_debug_assert!(
            self,
            num_iterations == num_iterations_predicted,
            "Expected the number of iterations to match the predicted value",
            [num_iterations, num_iterations_predicted],
        );
        bc_debug_assert!(
            self,
            self.n == target.n,
            "",
            [self.n, self.k, target.n, target.k]
        );
        bc_debug_assert!(
            self,
            self.k == target.k,
            "",
            [self.n, self.k, target.n, target.k],
        );

        #[cfg(test)]
        self._test_event_log.push(Event::Done {
            n: self.n,
            k: self.k,
            value: self.value.clone(),
        });

        self.value.clone()
    }

    /// Determine a very rough estimate of the amount of work to compute the binomial coefficient
    /// with `Natural::binomial_coefficient`.
    #[inline(always)]
    fn num_iterations_from_scratch(target: Params) -> usize {
        target.k.min(target.n - target.k)
    }

    #[inline(always)]
    /// Estimate the amount of work to compute the binomial coefficient incrementally.
    fn num_iterations_incrementally(&self, target: Params) -> usize {
        let delta_n = target.n.abs_diff(self.n);
        let delta_k = target.k.abs_diff(self.k);

        let delta_common = if (self.n < target.n && self.k < target.k)
            || (self.n > target.n && self.k > target.k)
        {
            delta_n.min(delta_k)
        } else {
            0
        };

        delta_n + delta_k - delta_common
    }

    /// Go from `n choose k` to `(n + 1) choose (k + 1)`.
    #[inline(always)]
    fn grow_n_k(&mut self, mul_div: &mut MultiplyAndDivide) {
        // n_new = n_old + 1
        // k_new = k_old + 1
        //
        // (n_new choose k_new) / (n_old choose k)
        // = (n_new choose k_new) / ((n_new - 1) choose (k_new - 1))
        // = n_new / k_new

        let n_old = self.n;
        let k_old = self.k;

        bc_debug_assert!(self, n_old < usize::MAX, "", [n_old, k_old]);
        bc_debug_assert!(self, k_old < usize::MAX, "", [n_old, k_old]);

        let n_new = n_old + 1;
        let k_new = k_old + 1;

        self.n = n_new;
        self.k = k_new;

        mul_div.update(&Natural::from(n_new), &Natural::from(k_new));
    }

    /// Go from `n choose k` to `(n - 1) choose (k - 1)`.
    #[inline(always)]
    fn shrink_n_k(&mut self, mul_div: &mut MultiplyAndDivide) {
        // n_new = n_old - 1
        // k_new = k_old - 1
        //
        // (n_new choose k_new) / (n_old choose k_old)
        // = ((n_old - 1) choose (k_old - 1)) / (n_old choose k_old)
        // = k_old / n_old

        let n_old = self.n;
        let k_old = self.k;

        bc_debug_assert!(self, n_old > 0, "", [n_old, k_old]);
        bc_debug_assert!(self, k_old > 0, "", [n_old, k_old]);

        let n_new = n_old - 1;
        let k_new = k_old - 1;

        self.n = n_new;
        self.k = k_new;

        mul_div.update(&Natural::from(k_old), &Natural::from(n_old));
    }

    /// Go from `n choose k` to `(n + 1) choose k`.
    #[inline(always)]
    fn grow_n(&mut self, mul_div: &mut MultiplyAndDivide) {
        // n_new = n_old + 1
        //
        // (n_new choose k) / (n_old choose k)
        // = (n_new choose k) / ((n_new - 1) choose k)
        // = n_new / (n_new - k)

        let n_old = self.n;
        let k = self.k;

        bc_debug_assert!(self, n_old < usize::MAX, "", [n_old, k]);

        let n_new = n_old + 1;

        self.n = n_new;

        bc_debug_assert!(self, n_new > k, "", [n_old, n_new, k]);

        mul_div.update(&Natural::from(n_new), &Natural::from(n_new - k));
    }

    /// Go from `n choose k` to `(n - 1) choose k`.
    #[inline(always)]
    fn shrink_n(&mut self, mul_div: &mut MultiplyAndDivide) {
        // n_new = n_old - 1
        //
        // (n_new choose k) / (n_old choose k)
        // = ((n_old - 1) choose k) / (n_old choose k)
        // = (n_old - k) / n_old

        let n_old = self.n;
        let k = self.k;

        bc_debug_assert!(self, n_old > 0, "", [n_old, k]);

        let n_new = n_old - 1;

        self.n = n_new;

        bc_debug_assert!(self, n_old > k, "", [n_old, n_new, k]);

        mul_div.update(&Natural::from(n_old - k), &Natural::from(n_old));
    }

    /// Go from `n choose k` to `n choose (k + 1)`.
    #[inline(always)]
    fn grow_k(&mut self, mul_div: &mut MultiplyAndDivide) {
        // k_new = k_old + 1
        //
        // (n choose k_new) / (n choose k_old)
        // = (n choose (k_old + 1)) / (n choose k_old))
        // = (n - k_old) / (k_old + 1)
        // = (n - k_old) / k_new

        let n = self.n;
        let k_old = self.k;

        bc_debug_assert!(self, k_old < usize::MAX, "", [n, k_old]);

        let k_new = k_old + 1;

        self.k = k_new;

        bc_debug_assert!(self, n > k_old, "", [n, k_old, k_new]);

        mul_div.update(&Natural::from(n - k_old), &Natural::from(k_new));
    }

    /// Go from `n choose k` to `n choose (k - 1)`.
    #[inline(always)]
    fn shrink_k(&mut self, mul_div: &mut MultiplyAndDivide) {
        // k_new = k_old - 1
        //
        // (n choose k_new) / (n choose k_old)
        // = (n choose k_new) / (n choose (k_new + 1))
        // = (k_new + 1) / (n - k_new)
        // = k_old / (n - k_new)

        let n = self.n;
        let k_old = self.k;

        bc_debug_assert!(self, k_old > 0, "", [n, k_old]);

        let k_new = k_old - 1;

        self.k = k_new;

        bc_debug_assert!(self, n > k_new, "", [n, k_old, k_new]);

        mul_div.update(&Natural::from(k_old), &Natural::from(n - k_new));
    }
}

#[cfg(test)]
mod tests {
    use proptest::prelude::*;
    use proptest_state_machine::{ReferenceStateMachine, StateMachineTest, prop_state_machine};

    use super::*;

    macro_rules! my_dbg {
        ($($value:expr),+ $(,)?) => {
            eprint!("[{}:{}:{}]", file!(), line!(), column!());
            $(
                eprint!(" {}={:?}", stringify!($value), &$value);
            )+
            eprintln!();
        };
    }

    #[test]
    fn test_binomial_coefficient_one_case() {
        for n in 0..10 {
            my_dbg!(n);

            let mut bc = BinomialCoefficient::new();

            assert_eq!(
                bc.choose(n, 0),
                Natural::binomial_coefficient(Natural::from(n), Natural::ZERO)
            );
            assert_eq!(
                bc._test_event_log,
                vec![Event::OneCase {
                    target_n: n,
                    target_k: 0,
                }]
            );

            let mut bc = BinomialCoefficient::new();

            assert_eq!(
                bc.choose(n, n),
                Natural::binomial_coefficient(Natural::from(n), Natural::ZERO)
            );
            assert_eq!(
                bc._test_event_log,
                vec![Event::OneCase {
                    target_n: n,
                    target_k: n,
                }]
            );
        }
    }

    #[test]
    fn test_binomial_coefficient_n_case() {
        for n in 2..10 {
            my_dbg!(n);

            let mut bc = BinomialCoefficient::new();

            assert_eq!(
                bc.choose(n, 1),
                Natural::binomial_coefficient(Natural::from(n), Natural::ONE)
            );
            assert_eq!(
                bc._test_event_log,
                vec![Event::NCase {
                    target_n: n,
                    target_k: 1,
                }]
            );
        }
    }

    #[test]
    fn test_binomial_coefficient_zero_case() {
        for n in 0..10 {
            for k in (n + 1).max(2)..(n + 5) {
                my_dbg!(n, k);

                let mut bc = BinomialCoefficient::new();

                assert_eq!(
                    bc.choose(n, k),
                    Natural::binomial_coefficient(Natural::from(n), Natural::from(k))
                );
                assert_eq!(
                    bc._test_event_log,
                    vec![Event::ZeroCase {
                        target_n: n,
                        target_k: k,
                    }]
                );
            }
        }
    }

    #[test]
    fn test_binomial_coefficient_identical_case() {
        for n in 0..10 {
            for k in 2..n {
                my_dbg!(n, k);

                let mut bc = BinomialCoefficient::new();

                let expected = Natural::binomial_coefficient(Natural::from(n), Natural::from(k));

                assert_eq!(bc.choose(n, k), expected);

                assert_eq!(bc.choose(n, k), expected);
                assert_eq!(
                    bc._test_event_log,
                    vec![Event::IdenticalCase {
                        n,
                        k,
                        value: expected
                    }]
                );

                assert_eq!(
                    bc.choose(n + 1, k),
                    Natural::binomial_coefficient(Natural::from(n + 1), Natural::from(k))
                );
                assert!(
                    !bc._test_event_log
                        .iter()
                        .any(|event| matches!(event, Event::IdenticalCase { .. }))
                );
            }
        }
    }

    #[test]
    fn test_binomial_coefficient_flipping_k() {
        let mut bc = BinomialCoefficient::new();

        assert_eq!(
            bc.choose(10, 3),
            Natural::binomial_coefficient(Natural::from(10usize), Natural::from(3usize))
        );

        assert_eq!(
            bc.choose(10, 4),
            Natural::binomial_coefficient(Natural::from(10usize), Natural::from(4usize))
        );
        assert!(
            !bc._test_event_log
                .iter()
                .any(|event| matches!(event, Event::FlippingK { .. }))
        );

        assert_eq!(
            bc.choose(10, 8),
            Natural::binomial_coefficient(Natural::from(10usize), Natural::from(8usize))
        );
        assert!(bc._test_event_log.iter().any(|event| matches!(
            event,
            Event::FlippingK {
                n: 10,
                k_old: 4,
                k_new: 6,
                target_n: 10,
                target_k: 8,
            }
        )));
    }

    #[test]
    fn test_binomial_coefficient_computing_from_scratch() {
        let mut bc = BinomialCoefficient::new();

        assert_eq!(
            bc.choose(10, 4),
            Natural::binomial_coefficient(Natural::from(10usize), Natural::from(4usize))
        );

        assert_eq!(
            bc.choose(10, 5),
            Natural::binomial_coefficient(Natural::from(10usize), Natural::from(5usize))
        );
        assert!(
            !bc._test_event_log
                .iter()
                .any(|event| matches!(event, Event::ComputingFromScratch { .. }))
        );

        assert_eq!(
            bc.choose(10, 2),
            Natural::binomial_coefficient(Natural::from(10usize), Natural::from(2usize))
        );
        assert!(bc._test_event_log.iter().any(|event| matches!(
            event,
            Event::ComputingFromScratch {
                n: 10,
                k: 5,
                target_n: 10,
                target_k: 2,
            }
        )));
    }

    #[test]
    fn test_binomial_coefficient_shrinking_n_k() {
        let mut bc = BinomialCoefficient::new();

        let n = 20;
        let k = 8;

        assert_eq!(
            bc.choose(n + 2, k + 2),
            Natural::binomial_coefficient(Natural::from(n + 2), Natural::from(k + 2))
        );

        assert_eq!(
            bc.choose(n, k),
            Natural::binomial_coefficient(Natural::from(n), Natural::from(k))
        );
        assert_eq!(
            bc._test_event_log,
            vec![
                Event::ShrinkingNK {
                    n: n + 2,
                    k: k + 2,
                    target_n: n,
                    target_k: k,
                },
                Event::ShrinkingNK {
                    n: n + 1,
                    k: k + 1,
                    target_n: n,
                    target_k: k,
                },
                Event::Done {
                    n,
                    k,
                    value: Natural::binomial_coefficient(Natural::from(n), Natural::from(k)),
                },
            ]
        );
    }

    #[test]
    fn test_binomial_coefficient_shrinking_n() {
        let mut bc = BinomialCoefficient::new();

        let n = 20;
        let k = 10;

        assert_eq!(
            bc.choose(n + 2, k),
            Natural::binomial_coefficient(Natural::from(n + 2), Natural::from(k))
        );

        assert_eq!(
            bc.choose(n, k),
            Natural::binomial_coefficient(Natural::from(n), Natural::from(k))
        );
        assert_eq!(
            bc._test_event_log,
            vec![
                Event::ShrinkingN {
                    n: n + 2,
                    k: k,
                    target_n: n,
                    target_k: k,
                },
                Event::ShrinkingN {
                    n: n + 1,
                    k: k,
                    target_n: n,
                    target_k: k,
                },
                Event::Done {
                    n,
                    k,
                    value: Natural::binomial_coefficient(Natural::from(n), Natural::from(k)),
                },
            ]
        );
    }

    #[test]
    fn test_binomial_coefficient_shrinking_k() {
        let mut bc = BinomialCoefficient::new();

        let n = 20;
        let k = 7;

        assert_eq!(
            bc.choose(n, k + 2),
            Natural::binomial_coefficient(Natural::from(n), Natural::from(k + 2))
        );

        assert_eq!(
            bc.choose(n, k),
            Natural::binomial_coefficient(Natural::from(n), Natural::from(k))
        );
        assert_eq!(
            bc._test_event_log,
            vec![
                Event::ShrinkingK {
                    n: n,
                    k: k + 2,
                    target_n: n,
                    target_k: k,
                },
                Event::ShrinkingK {
                    n: n,
                    k: k + 1,
                    target_n: n,
                    target_k: k,
                },
                Event::Done {
                    n,
                    k,
                    value: Natural::binomial_coefficient(Natural::from(n), Natural::from(k)),
                },
            ]
        );
    }

    #[test]
    fn test_binomial_coefficient_growing_n_k() {
        let mut bc = BinomialCoefficient::new();

        let n = 20;
        let k = 12;

        assert_eq!(
            bc.choose(n - 2, k - 2),
            Natural::binomial_coefficient(Natural::from(n - 2), Natural::from(k - 2))
        );

        assert_eq!(
            bc.choose(n, k),
            Natural::binomial_coefficient(Natural::from(n), Natural::from(k))
        );
        assert_eq!(
            bc._test_event_log,
            vec![
                Event::GrowingNK {
                    n: n - 2,
                    k: k - 2,
                    target_n: n,
                    target_k: k,
                },
                Event::GrowingNK {
                    n: n - 1,
                    k: k - 1,
                    target_n: n,
                    target_k: k,
                },
                Event::Done {
                    n,
                    k,
                    value: Natural::binomial_coefficient(Natural::from(n), Natural::from(k)),
                },
            ]
        );
    }

    #[test]
    fn test_binomial_coefficient_growing_n() {
        let mut bc = BinomialCoefficient::new();

        let n = 20;
        let k = 10;

        assert_eq!(
            bc.choose(n - 2, k),
            Natural::binomial_coefficient(Natural::from(n - 2), Natural::from(k))
        );

        assert_eq!(
            bc.choose(n, k),
            Natural::binomial_coefficient(Natural::from(n), Natural::from(k))
        );
        assert_eq!(
            bc._test_event_log,
            vec![
                Event::GrowingN {
                    n: n - 2,
                    k: k,
                    target_n: n,
                    target_k: k,
                },
                Event::GrowingN {
                    n: n - 1,
                    k: k,
                    target_n: n,
                    target_k: k,
                },
                Event::Done {
                    n,
                    k,
                    value: Natural::binomial_coefficient(Natural::from(n), Natural::from(k)),
                },
            ]
        );
    }

    #[test]
    fn test_binomial_coefficient_growing_k() {
        let mut bc = BinomialCoefficient::new();

        let n = 20;
        let k = 13;

        assert_eq!(
            bc.choose(n, k - 2),
            Natural::binomial_coefficient(Natural::from(n), Natural::from(k - 2))
        );

        assert_eq!(
            bc.choose(n, k),
            Natural::binomial_coefficient(Natural::from(n), Natural::from(k))
        );
        assert_eq!(
            bc._test_event_log,
            vec![
                Event::GrowingK {
                    n: n,
                    k: k - 2,
                    target_n: n,
                    target_k: k,
                },
                Event::GrowingK {
                    n: n,
                    k: k - 1,
                    target_n: n,
                    target_k: k,
                },
                Event::Done {
                    n,
                    k,
                    value: Natural::binomial_coefficient(Natural::from(n), Natural::from(k)),
                },
            ]
        );
    }

    #[derive(Clone, Debug, Eq, PartialEq)]
    pub struct BCStateMachine;

    #[derive(Clone, Debug, Eq, PartialEq)]
    pub enum BCTransition {
        NewNK { n: usize, k: usize },
        NewN { n: usize },
        NewK { k: usize },
    }

    impl ReferenceStateMachine for BCStateMachine {
        type State = (usize, usize);
        type Transition = BCTransition;

        fn init_state() -> BoxedStrategy<Self::State> {
            Just((0, 0)).boxed()
        }

        fn transitions(&(n, k): &Self::State) -> BoxedStrategy<Self::Transition> {
            let delta_range = 1..=10usize;

            prop_oneof![
                n_k_strategy().prop_map(|(n, k)| BCTransition::NewNK { n, k }),
                n_strategy().prop_map(|n| BCTransition::NewN { n }),
                k_strategy_given_n(n).prop_map(|k| BCTransition::NewK { k }),
                Just(BCTransition::NewK {
                    // Flip k.
                    k: n.saturating_sub(k)
                }),
                (Just(n), Just(k), delta_range.clone(), delta_range.clone()).prop_map(
                    |(n, k, delta_n, delta_k)| BCTransition::NewNK {
                        n: n.saturating_sub(delta_n),
                        k: k.saturating_sub(delta_k)
                    }
                ),
                (Just(n), Just(k), delta_range.clone(), delta_range.clone()).prop_map(
                    |(n, k, delta_n, delta_k)| BCTransition::NewNK {
                        n: n.saturating_sub(delta_n),
                        k: k.saturating_add(delta_k)
                    }
                ),
                (Just(n), Just(k), delta_range.clone(), delta_range.clone()).prop_map(
                    |(n, k, delta_n, delta_k)| BCTransition::NewNK {
                        n: n.saturating_add(delta_n),
                        k: k.saturating_sub(delta_k)
                    }
                ),
                (Just(n), Just(k), delta_range.clone(), delta_range.clone()).prop_map(
                    |(n, k, delta_n, delta_k)| BCTransition::NewNK {
                        n: n.saturating_add(delta_n),
                        k: k.saturating_add(delta_k)
                    }
                ),
                (Just(n), delta_range.clone()).prop_map(|(n, delta_n)| BCTransition::NewN {
                    n: n.saturating_sub(delta_n)
                }),
                (Just(n), delta_range.clone()).prop_map(|(n, delta_n)| BCTransition::NewN {
                    n: n.saturating_add(delta_n)
                }),
                (Just(k), delta_range.clone()).prop_map(|(k, delta_k)| BCTransition::NewK {
                    k: k.saturating_sub(delta_k)
                }),
                (Just(k), delta_range.clone()).prop_map(|(k, delta_k)| BCTransition::NewK {
                    k: k.saturating_add(delta_k)
                }),
            ]
            .boxed()
        }

        fn apply((n, k): Self::State, transition: &Self::Transition) -> Self::State {
            match *transition {
                BCTransition::NewNK { n, k } => (n, k),
                BCTransition::NewN { n } => (n, k),
                BCTransition::NewK { k } => (n, k),
            }
        }
    }

    fn n_strategy() -> BoxedStrategy<usize> {
        (0..=100usize).boxed()
    }

    fn k_strategy_given_n(n: usize) -> BoxedStrategy<usize> {
        prop_oneof![
            // Up to n.
            10 => 0..=n,
            // Above n.
            1 => (n+1)..=(n+10),
            // At the middle point (rounded down).
            1 => Just(n / 2),
            // At the middle point (rounded up).
            1 => Just(n.div_ceil(2)),
        ]
        .boxed()
    }

    fn n_k_strategy() -> BoxedStrategy<(usize, usize)> {
        n_strategy()
            .prop_flat_map(|n| (Just(n), k_strategy_given_n(n)))
            .boxed()
    }

    impl StateMachineTest for BinomialCoefficient {
        type SystemUnderTest = Self;
        type Reference = BCStateMachine;

        fn init_test(
            _ref_state: &<Self::Reference as ReferenceStateMachine>::State,
        ) -> Self::SystemUnderTest {
            Self::new()
        }

        fn apply(
            mut state: Self::SystemUnderTest,
            &(n, k): &<Self::Reference as ReferenceStateMachine>::State,
            transition: <Self::Reference as ReferenceStateMachine>::Transition,
        ) -> Self::SystemUnderTest {
            let (n, k) = match transition {
                BCTransition::NewNK { n, k } => (n, k),
                BCTransition::NewN { n } => (n, k),
                BCTransition::NewK { k } => (n, k),
            };

            assert_eq!(
                state.choose(n, k),
                Natural::binomial_coefficient(Natural::from(n), Natural::from(k))
            );

            state
        }
    }

    prop_state_machine! {
        #![proptest_config(
            proptest::test_runner::Config {
                verbose: 1,
                failure_persistence: None,
                .. proptest::test_runner::Config::default()
            }
        )]

        #[test]
        fn test_binomial_coefficient_prop(sequential 1..=100 => BinomialCoefficient);
    }
}

board.rs

use base64::{Engine as _, engine::general_purpose::URL_SAFE_NO_PAD_INDIFFERENT as Base64URL};
use bitvec::prelude::*;
use malachite::Natural;
use malachite::base::num::basic::traits::Zero as _;
use malachite::base::num::conversion::traits::PowerOf2Digits as _;
use rand::rng;
use rand::seq::index::sample;

use crate::binomial_coefficient::BinomialCoefficient;

const BOARD_SIZE_LIMIT: usize = 100 * 100;

#[derive(Debug, Clone, Eq, PartialEq)]
pub struct Board {
    tiles: BitVec,
    num_mines: usize,
}

impl Board {
    fn validate_board_size(num_tiles: usize) -> Result<(), &'static str> {
        if num_tiles > BOARD_SIZE_LIMIT {
            return Err("num_tiles is too large");
        }

        Ok(())
    }

    pub fn new(tiles: BitVec, num_mines: usize) -> Result<Self, &'static str> {
        Self::validate_board_size(tiles.len())?;

        if !(tiles.count_ones() == num_mines) {
            return Err("Expected tiles.count_ones() to equal num_mines");
        }

        Ok(Self { tiles, num_mines })
    }

    pub fn tiles(self: &Self) -> &BitVec {
        &self.tiles
    }

    pub fn num_tiles(self: &Self) -> usize {
        self.tiles.len()
    }

    pub fn num_mines(self: &Self) -> usize {
        self.num_mines
    }

    /// Generate a random Minesweeper board.
    pub fn generate(num_tiles: usize, num_mines: usize) -> Result<Self, &'static str> {
        Self::validate_board_size(num_tiles)?;

        if num_tiles < num_mines {
            return Err("num_tiles can not be lower than num_mines");
        }

        let tiles = if num_mines <= num_tiles / 2 {
            // Start with no mines and mark random tiles as mines.

            let mut tiles = bitvec![0; num_tiles];

            for ix in sample(&mut rng(), num_tiles, num_mines) {
                tiles.set(ix, true);
            }

            tiles
        } else {
            // Start with all mines and mark random tiles as safe.

            let mut tiles = bitvec![1; num_tiles];

            for ix in sample(&mut rng(), num_tiles, num_tiles - num_mines) {
                tiles.set(ix, false);
            }

            tiles
        };

        debug_assert_eq!(
            tiles.len(),
            num_tiles,
            "Expected tiles.len() to equal num_tiles"
        );

        Self::new(tiles, num_mines)
    }

    /// Encode the board using the combinatorial number system.
    ///
    /// For instance, a 16x30/99 board takes ceil(log2(480 choose 99)) = 348 bits to represent while
    /// a naive encoding of each tile as a bit would take 480 bits.
    ///
    /// A 100x100/2200 board takes 7595 bits while the naive encoding would take 10000 bits.
    pub fn to_number(&self) -> Natural {
        let mut number = Natural::ZERO;
        let mut bc = BinomialCoefficient::new();

        for (counter, position) in self.tiles.iter_ones().enumerate() {
            number += bc.choose(position, counter + 1);
        }

        debug_assert!(
            number < bc.choose(self.num_tiles(), self.num_mines()),
            "Expected the result to be less than (num_tiles choose num_mines)"
        );

        number
    }

    /// Decode a board using the combinatorial number system.
    pub fn from_number(
        num_tiles: usize,
        num_mines: usize,
        number: Natural,
    ) -> Result<Self, &'static str> {
        Self::validate_board_size(num_tiles)?;

        let mut bc = BinomialCoefficient::new();

        let mut n = num_tiles;
        let mut k = num_mines;
        let mut num_combinations = bc.choose(n, k);

        if number >= num_combinations {
            return Err("number is too large for the board parameters");
        }

        let mut tiles = bitvec![0; num_tiles];

        // Go from `n choose k` to `(n - 1) choose k`.
        if !(n > 0) {
            return Self::new(tiles, num_mines);
        }
        n -= 1;
        num_combinations = bc.choose(n, k);

        let mut number = number;

        loop {
            if number >= num_combinations {
                tiles.set(n, true);

                number -= &num_combinations;

                // Go from `n choose k` to `(n - 1) choose (k - 1)`.
                if !(n > 0 && k > 0) {
                    break;
                }
                n -= 1;
                k -= 1;
                num_combinations = bc.choose(n, k);
            } else {
                // Go from `n choose k` to `(n - 1) choose k`.
                if !(n > 0) {
                    break;
                }
                n -= 1;
                num_combinations = bc.choose(n, k);
            }
        }

        debug_assert_eq!(
            number,
            Natural::ZERO,
            "Expected number to be zero after decoding"
        );

        Self::new(tiles, num_mines)
    }

    /// Encode the board using the combinatorial number system and Base64URL.
    ///
    /// For instance, a 16x30/99 board takes ceil(ceil(log2(480 choose 99) / 8) * 8 / 6) = 59
    /// characters to represent while a naive encoding of each tile as a bit would take 80
    /// characters.
    ///
    /// A 100x100/2200 board takes 1267 characters while the naive encoding would take 1667
    /// characters.
    pub fn to_string(&self) -> String {
        let number = self.to_number();

        let digits = number.to_power_of_2_digits_desc(8);

        Base64URL.encode(digits)
    }

    /// Decode a board using the combinatorial number system and Base64URL.
    pub fn from_string(
        num_tiles: usize,
        num_mines: usize,
        string: &str,
    ) -> Result<Self, &'static str> {
        let Ok(digits) = Base64URL.decode(string) else {
            return Err("Failed to decode the string as Base64URL");
        };

        let Some(number) = Natural::from_power_of_2_digits_desc(8, digits.into_iter()) else {
            return Err("Failed to convert the string into a number");
        };

        Self::from_number(num_tiles, num_mines, number)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_board_new() {
        let tiles = bitvec![1, 0, 1, 0, 0, 1];
        let board = Board::new(tiles.clone(), 3).unwrap();

        assert_eq!(board.tiles(), &tiles);
        assert_eq!(board.num_tiles(), 6);
        assert_eq!(board.num_mines(), 3);
    }

    #[test]
    fn test_board_new_too_large() {
        let tiles = bitvec![0; 100*100+1];
        assert!(Board::new(tiles, 0).is_err());
    }

    #[test]
    fn test_board_new_incorrect_num_mines() {
        let tiles = bitvec![1, 0, 1, 0, 0, 1];
        assert!(Board::new(tiles, 2).is_err());
    }

    fn board_examples() -> Vec<(BitVec, usize, usize, &'static str)> {
        return vec![
            // The examples are from <https://en.wikipedia.org/wiki/Combinatorial_number_system>.
            (bitvec![1, 1, 1, 0, 0], 3, 0, ""),
            (bitvec![1, 1, 0, 1, 0], 3, 1, "AQ"),
            (bitvec![1, 0, 1, 1, 0], 3, 2, "Ag"),
            (bitvec![0, 1, 1, 1, 0], 3, 3, "Aw"),
            (bitvec![1, 1, 0, 0, 1], 3, 4, "BA"),
            (bitvec![1, 0, 1, 0, 1], 3, 5, "BQ"),
            (bitvec![0, 1, 1, 0, 1], 3, 6, "Bg"),
            (bitvec![1, 0, 0, 1, 1], 3, 7, "Bw"),
            (bitvec![0, 1, 0, 1, 1], 3, 8, "CA"),
            (bitvec![0, 0, 1, 1, 1], 3, 9, "CQ"),
            (bitvec![0, 0, 0, 0, 0, 0, 0, 1, 1, 1], 3, 119, "dw"),
            (bitvec![1, 0, 0, 1, 1, 0, 1, 0, 0, 1], 5, 148, "lA"),
            (bitvec![1, 1, 0, 1, 0, 0, 0, 1, 0, 1], 5, 162, "og"),
        ];
    }

    #[test]
    fn test_board_to_number_and_string() {
        for (tiles, num_mines, number, string) in board_examples() {
            println!(
                "[{file}:{line}:{col}] tiles={tiles} num_mines={num_mines} number={number} string={string}",
                file = file!(),
                line = line!(),
                col = column!(),
            );

            let board = Board::new(tiles, num_mines).unwrap();
            assert_eq!(board.to_number(), Natural::from(number));
            assert_eq!(board.to_string(), string);
        }
    }

    #[test]
    fn test_board_from_number_and_string() {
        for (tiles, num_mines, number, string) in board_examples() {
            println!(
                "[{file}:{line}:{col}] tiles={tiles} num_mines={num_mines} number={number} string={string}",
                file = file!(),
                line = line!(),
                col = column!(),
            );

            let num_tiles = tiles.len();

            let board = Board::from_number(num_tiles, num_mines, Natural::from(number)).unwrap();
            assert_eq!(board, Board::new(tiles.clone(), num_mines).unwrap());

            let board = Board::from_string(num_tiles, num_mines, string).unwrap();
            assert_eq!(board, Board::new(tiles, num_mines).unwrap());
        }
    }

    #[test]
    fn test_board_from_number_and_string_too_large() {
        assert!(Board::from_number(100 * 100 + 1, 1, Natural::ZERO).is_err());
        assert!(Board::from_string(100 * 100 + 1, 1, "AQ").is_err());
    }

    #[test]
    fn test_board_from_and_to_number_and_string() {
        for (num_tiles, num_mines) in [
            (9 * 9, 10),
            (16 * 16, 40),
            (20 * 30, 130),
            (100 * 100, 100 * 100 / 2),
        ] {
            println!(
                "[{file}:{line}:{col}] num_tiles={num_tiles} num_mines={num_mines}",
                file = file!(),
                line = line!(),
                col = column!(),
            );

            let board = Board::generate(num_tiles, num_mines).unwrap();

            let number = board.to_number();
            assert_eq!(
                Board::from_number(num_tiles, num_mines, number).unwrap(),
                board
            );

            let string = board.to_string();
            assert_eq!(
                Board::from_string(num_tiles, num_mines, string.as_str()).unwrap(),
                board
            );
        }
    }
}

Cargo.toml

[package]
name = "minesweeper-combinatorial-number-system"
version = "0.0.1"
edition = "2024"

[dependencies]
base64 = "0.23.1"
bitvec = "1.1.1"
malachite = "0.10.0"
rand = "0.10.2"

[dev-dependencies]
proptest = "1.11.0"
proptest-state-machine = "0.8.0"

lib.rs

pub mod binomial_coefficient;
pub mod board;
pub mod multiply_and_divide;

main.rs

use std::time::Instant;

use minesweeper_combinatorial_number_system::board::Board;

fn main() {
    // let board = Board::generate(100 * 100, 2200).unwrap();
    // let board = Board::generate(100 * 100, 100 * 100 / 2).unwrap();
    let board = Board::generate(16 * 30, 99).unwrap();

    println!("{board:?}");

    let start = Instant::now();
    let string = board.to_string();
    let to_string_duration = start.elapsed();

    let start = Instant::now();
    _ = Board::from_string(board.num_tiles(), board.num_mines(), string.as_str()).unwrap();
    let from_string_duration = start.elapsed();

    dbg!(string);
    println!(
        "to_string: {:.3} ms",
        to_string_duration.as_secs_f64() * 1000.0
    );
    println!(
        "from_string: {:.3} ms",
        from_string_duration.as_secs_f64() * 1000.0
    );
}

multiply_and_divide.rs

use std::ops::MulAssign;

use malachite::Natural;
use malachite::base::num::arithmetic::traits::DivExactAssign;
use malachite::base::num::basic::traits::One;
use malachite::base::num::basic::traits::Zero;

/// Accumulate a multiplier and a divisor which can be applied to a natural number at a later time.
///
/// Invariant: the division must be exact.
#[derive(Debug, Clone, Eq, PartialEq)]
pub struct MultiplyAndDivide {
    multiplier: Natural,
    divisor: Natural,
}

impl Default for MultiplyAndDivide {
    fn default() -> Self {
        Self {
            multiplier: Natural::ONE,
            divisor: Natural::ONE,
        }
    }
}

impl MultiplyAndDivide {
    pub fn new(multiplier: Natural, divisor: Natural) -> Self {
        let this = Self {
            multiplier,
            divisor,
        };

        this.validate();

        this
    }

    /// Multiply the multiplier and the divisor by the given values respectively.
    pub fn update(&mut self, multiplier: &Natural, divisor: &Natural) {
        self.multiplier *= multiplier;
        self.divisor *= divisor;

        self.validate();
    }

    #[inline(always)]
    fn validate(&self) {
        assert_ne!(self.divisor, 0, "Expected nonzero divisor");
    }

    /// Perform the multiplication followed by the division on a natural number.
    pub fn apply(&self, number: Natural) -> Natural {
        let mut number = number;

        self.apply_mut(&mut number);

        number
    }

    /// Perform the multiplication followed by the division on a natural number.
    pub fn apply_ref(&self, number: &Natural) -> Natural {
        self.apply(number.clone())
    }

    /// Perform the multiplication followed by the division on a natural number.
    pub fn apply_mut(&self, number: &mut Natural) {
        number.mul_assign(&self.multiplier);

        debug_assert_eq!(
            &*number % &self.divisor,
            Natural::ZERO,
            "Expected the division to be exact (number={number} divisor={divisor})",
            divisor = &self.divisor
        );

        number.div_exact_assign(&self.divisor);
    }
}