minesweeprs 0.2.0

#![doc = include_str!("../README.md")]
#![allow(clippy::too_many_lines)]
use std::cmp::{max, min, Ordering};
use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};
use std::fmt::Debug;
use std::hash::Hash;
use std::iter::{empty, once, Rev};
use std::ops::RangeInclusive;

use either::Either;
use internal_util::{
    comb,
    fact_div,
    graph_traverse,
    map_reduce,
    peek,
    pop,
    CustomInto,
    FrozenMap,
    FrozenSet,
};
use itertools::Itertools;
use typed_arena::Arena;
mod internal_util;
pub mod util;

type SuperCell<'arena, 'cell, T> = &'arena FrozenSet<&'cell T>;

pub trait Cell: Hash + Eq + Debug {}
impl<T: Hash + Eq + Debug + ?Sized> Cell for T {
}

/// Represents the board geometry for traditional minesweeper, where the board
/// has fixed dimensions and a fixed total of mines.
#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
pub struct BoardInfo {
    /// Total number of cells on the board; all cells contained in rules and all
    /// 'uncharted' (completely unknown) cells
    pub total_cells: usize,
    /// Total number of mines contained within cells counted in total_cells
    pub total_mines: usize,
}

pub type Error = &'static str;

/// Solve a minesweeper board.
///
/// Takes in a list of rules, information about the board (either a
/// [`BoardInfo`] representing the board data, or an [`f64`] representing the
/// fixed probability of an unknown cell being a mine), and a tag to use for any
/// cells not explicitly mentioned in the rules.
pub fn solve<'cell, T: Cell + ?Sized>(
    rules: &[Rule<'cell, T>],
    mine_prevalence: impl CustomInto<Either<BoardInfo, f64>>,
    other_tag: impl Into<&'cell T>,
) -> Result<HashMap<&'cell T, f64>, Error> {
    // - Single cells are allocated by the caller, and passed in to `Rule` as
    //   references.
    // - Super-cells are allocated by `condense_supercells()`, but are stored in an
    //   arena due to lifetime requirements.
    // - All other allocations require their own arenas, to avoid reliance on `Rc`,
    //   and `Shared` (essentially a wrapper around `Rc<RefCell>`).
    //   - `InternalRule`s may be allocated dynamically, such as by generating them
    //     from a `PermutationSet`, and so must be stored in the arena.
    //   - Super-cell groups are allocated dynamically, for construction of `Rule`s
    let rule_arena = Arena::new();
    let super_cell_arena = Arena::new();
    let ruleset_arena = Arena::new();
    let permutation_arena = Arena::new();
    let permutation_set_arena = Arena::new();
    let super_cell_group_arena = Arena::new();

    // fn solve<'arena, 'cell: 'arena, T: Cell + ?Sized>(
    //     rules: &[Rule<'cell, T>],
    //     mine_prevalence: impl CustomInto<Either<BoardInfo, f64>>,
    //     other_tag: impl Into<&'cell T>,
    //     rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
    //     ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell,
    // T>>>,     super_cell_arena: &'arena Arena<FrozenSet<&'cell T>>,
    //     permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
    //     permutation_set_arena: &'arena Arena<PermutationSet<'arena, 'cell, T>>,
    //     super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell,
    // T>>>, ) -> Result<HashMap<&'cell T, f64>, Error> {
    let mine_prevalence = mine_prevalence.into();
    let (internal_rules, all_cells) = condense_supercells(
        rules,
        &rule_arena,
        &super_cell_arena,
        &super_cell_group_arena,
    )?;
    let mut reduced = reduce_rules(
        &internal_rules,
        &rule_arena,
        &ruleset_arena,
        &super_cell_group_arena,
    );

    let mut determined = reduced
        .iter()
        .filter(|r| r.is_trivial())
        .cloned()
        .collect::<HashSet<_>>();
    reduced.retain(|r| !r.is_trivial());

    let mut fronts = permute_and_interfere(
        ruleset_arena.alloc(reduced),
        &rule_arena,
        &ruleset_arena,
        &permutation_arena,
        &permutation_set_arena,
        &super_cell_group_arena,
    )?
    .split_fronts(&ruleset_arena, &permutation_arena, &permutation_set_arena);

    determined.extend(
        fronts
            .iter()
            .filter(|f| f.is_trivial())
            .map(PermutedRuleset::trivial_rule),
    );
    fronts.retain(|f| !f.is_trivial());

    let mut stats = fronts
        .into_iter()
        .map(|f| enumerate_front(f))
        .collect::<Result<Vec<_>, _>>()?;
    stats.extend(determined.into_iter().map(|r| r.tally()));

    let cell_probs = cell_probabilities(stats, mine_prevalence, all_cells)?;
    let cells = expand_cells::<'_, 'cell, _>(cell_probs, other_tag.into()).collect();
    Ok(cells)
    // }
    // solve(
    //     rules,
    //     mine_prevalence,
    //     other_tag,
    //     &rule_arena,
    //     &ruleset_arena,
    //     &super_cell_arena,
    //     &permutation_arena,
    //     &permutation_set_arena,
    //     &super_cell_group_arena,
    // )
}

/// Basic representation of an axiom from a minesweeper game; N mines contained
/// within a set of M cells.
///
/// This is only used during the very early stages of the algorithm; it's
/// quickly converted into an [`InternalRule`]
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Rule<'cell, T: Cell + ?Sized> {
    /// How many mines are contained within the cells.
    num_mines: usize,
    /// The cells used by the rule. Each cell is a unique, identifying tag that
    /// represents that cell.
    cells: FrozenSet<&'cell T>,
}
impl<'cell, T: Cell + ?Sized> Rule<'cell, T> {
    pub fn new(num_mines: usize, cells: impl IntoIterator<Item = &'cell T>) -> Self {
        Self {
            num_mines,
            cells: cells.into_iter().collect(),
        }
    }

    /// Condense super-cells and convert into an [`InternalRule`].
    ///
    /// `rule_supercells_map` is a pre-computed super-cell mapping.
    fn condensed<'arena>(
        &self,
        rule_supercells_map: &HashMap<
            &Self,
            &'arena FrozenSet<SuperCell<'arena, 'cell, T>>,
        >,
        rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) -> Result<&'arena InternalRule<'arena, 'cell, T>, Error> {
        InternalRule::new(
            self.num_mines,
            // default to handle degenerate rules
            rule_supercells_map
                .get(self)
                .copied()
                .unwrap_or_else(|| &*super_cell_group_arena.alloc(FrozenSet::new())),
            self.cells.len(),
        )
        .map(|rule| &*rule_arena.alloc(rule))
    }
}

/// Analogue of [`Rule`] but containing super-cells (set of cells that only ever
/// appear together).
///
/// This is the common rule form used throughout most of the algorithm.
#[derive(Copy, Debug, PartialEq, Eq, Hash)]
struct InternalRule<'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// The total number of mines
    num_mines: usize,
    /// The total number of base cells
    num_cells: usize,
    /// The super-cells used by the rule
    super_cells: &'arena FrozenSet<SuperCell<'arena, 'cell, T>>,
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> Clone for InternalRule<'arena, 'cell, T> {
    fn clone(&self) -> Self {
        Self {
            num_mines: self.num_mines,
            num_cells: self.num_cells,
            super_cells: self.super_cells,
        }
    }
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> InternalRule<'arena, 'cell, T> {
    pub fn new(
        num_mines: usize,
        super_cells: &'arena FrozenSet<SuperCell<'arena, 'cell, T>>,
        num_cells: usize,
    ) -> Result<Self, Error> {
        if num_mines <= num_cells {
            Ok(Self {
                num_mines,
                num_cells,
                super_cells,
            })
        } else {
            Err("Rule with more mines than cells")
        }
    }

    /// If the rule is completely full or completely empty of mines, split into
    /// a sub-rule for each super-cell.
    pub fn decompose(
        &self,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) -> Box<dyn Iterator<Item = Self> + '_> {
        if self.num_mines == 0 || self.num_mines == self.num_cells {
            // Degenerate rules (those with no cells) disappear here
            Box::new(self.super_cells.iter().map(|&super_cell| {
                let size = super_cell.len();
                Self::new(
                    if self.num_mines > 0 { size } else { 0 },
                    super_cell_group_arena.alloc([super_cell].into()),
                    size,
                )
                .expect("Decomposing a rule should always be valid")
            }))
        } else {
            Box::new(once(self.clone()))
        }
    }

    /// If another rule is a sub-rule of this one, return a new rule covering
    /// only the difference
    pub fn subtract(
        &self,
        other: &Self,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) -> Self {
        Self::new(
            self.num_mines - other.num_mines,
            super_cell_group_arena.alloc(self.super_cells - &other.super_cells),
            self.num_cells - other.num_cells,
        )
        .expect("Subtracting a rule should always result in a valid rule")
    }

    /// Generate all possible mine permutations for this rule
    pub fn permute(&self) -> impl Iterator<Item = Permutation<'arena, 'cell, T>> + '_ {
        /// Generate all permutations of `count` mines among `cells`.
        ///
        /// `permu` represents the sub-permutation in progress, and is used by
        /// recursive calls.
        fn permute<'arena, 'cell: 'arena, T: Cell + ?Sized>(
            count: usize,
            mut cells: VecDeque<&'arena FrozenSet<&'cell T>>,
            permu: HashSet<(&'arena FrozenSet<&'cell T>, usize)>,
        ) -> Box<dyn Iterator<Item = Permutation<'arena, 'cell, T>> + 'arena> {
            if count == 0 {
                Box::new(once(Permutation::new(
                    permu
                        .union(&cells.iter().map(|&cell| (cell, 0)).collect())
                        .cloned(),
                )))
            } else {
                let remaining_size = cells.iter().map(|cell| cell.len()).sum::<usize>();
                if remaining_size == count {
                    Box::new(once(Permutation::new(
                        permu
                            .union(
                                &cells.iter().map(|&cell| (cell, cell.len())).collect(),
                            )
                            .cloned(),
                    )))
                } else if remaining_size >= count {
                    struct Iter<'a, 'arena: 'a, 'cell: 'arena, T: Cell + ?Sized> {
                        cell: &'arena FrozenSet<&'cell T>,
                        multiplicity: usize,
                        multiplicity_iter: Rev<RangeInclusive<usize>>,
                        inner: Box<
                            dyn Iterator<Item = Permutation<'arena, 'cell, T>> + 'a,
                        >,
                        cells: VecDeque<&'arena FrozenSet<&'cell T>>,
                        count: usize,
                        permu: HashSet<(&'arena FrozenSet<&'cell T>, usize)>,
                    }
                    impl<'a, 'arena: 'a, 'cell: 'arena, T: Cell + ?Sized> Iterator
                        for Iter<'a, 'arena, 'cell, T>
                    {
                        type Item = Permutation<'arena, 'cell, T>;

                        fn next(&mut self) -> Option<Self::Item> {
                            match self.inner.next() {
                                Some(permutation) => Some(permutation),
                                None => {
                                    self.multiplicity =
                                        self.multiplicity_iter.next()?;
                                    self.inner = permute(
                                        self.count - self.multiplicity,
                                        self.cells.clone(),
                                        self.permu
                                            .union(
                                                &[(self.cell, self.multiplicity)]
                                                    .into(),
                                            )
                                            .cloned()
                                            .collect(),
                                    );
                                    self.next()
                                },
                            }
                        }
                    }
                    let cell = cells.pop_front().expect(concat!(
                        "count >= 1, remaining_size >= count, so",
                        " cells must not be empty",
                    ));
                    Box::new(Iter {
                        cell,
                        multiplicity: 0,
                        multiplicity_iter: (0..=min(count, cell.len())).rev(),
                        inner: Box::new(empty()),
                        cells,
                        count,
                        permu,
                    })
                } else {
                    Box::new(empty())
                }
            }
        }

        let cells = self.super_cells.iter().cloned().collect();
        permute(self.num_mines, cells, HashSet::new())
            .collect_vec()
            .into_iter()
    }

    /// Returns `true` if this rule is a sub-rule of `other`.
    ///
    /// 'sub-rule' means that this rule's cells are a subset of the super-rule's
    /// cells. Equivalent rules are sub-rules of each other.
    pub fn is_subule_of(&self, other: &Self) -> bool {
        self.super_cells.is_subset(&other.super_cells)
    }

    /// Returns `true` if this rule is trivial, i.e. has only one permutation.
    pub fn is_trivial(&self) -> bool {
        self.super_cells.len() == 1
    }

    /// Build a [`FrontTally`] from this *trivial* rule only.
    ///
    /// # Panics
    ///
    /// Panics if this rule is not trivial.
    pub fn tally(&self) -> FrontTally<'arena, 'cell, T> {
        FrontTally::from_rule(self)
    }
}

/// Condense super-cells by finding sets of ordinary cells that only ever appear
/// together. Returns a set of [`InternalRule`] corresponding to the original
/// ruleset.
///
/// Note that *all* cells are converted into super-cells for ease of processing
/// later (and type-safety), even if that cell does not group with any others.
/// The result would be a singleton super-cell.
///
/// # Arguments
///
/// * `rules` - The rules to condense
fn condense_supercells<'arena, 'cell: 'arena, T: Cell + ?Sized>(
    rules: &[Rule<'cell, T>],
    rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
    super_cell_arena: &'arena Arena<FrozenSet<&'cell T>>,
    super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
) -> Result<
    (
        Vec<&'arena InternalRule<'arena, 'cell, T>>,
        Vec<&'arena FrozenSet<&'cell T>>,
    ),
    Error,
> {
    // For each cell, the rules it appears in
    let cell_rules_map = map_reduce(
        rules.iter(),
        |rule| rule.cells.iter().map(move |&cell| (cell, rule)),
        |rules| rules.into_iter().collect::<FrozenSet<_>>(),
    );

    // For each group of rules a cell appears in, the cells that share those rules
    // (these cells thus only ever appear together in the same rules)
    let rules_supercell_map = map_reduce(
        cell_rules_map.into_iter(),
        |(cell, rules)| [(rules, cell)].into_iter(),
        |cells| &*super_cell_arena.alloc(cells.into_iter().collect::<FrozenSet<_>>()),
    );

    // For each original rule, the super cells appearing in that rule
    let rule_supercells_map = map_reduce(
        rules_supercell_map.iter(),
        |(rules, cell)| {
            rules
                .iter()
                .map(|&rule| (rule, &**cell))
                .collect_vec()
                .into_iter()
        },
        |cells| {
            &*super_cell_group_arena.alloc(cells.into_iter().collect::<FrozenSet<_>>())
        },
    );

    Ok((
        rules
            .iter()
            .map(|rule| {
                rule.condensed(&rule_supercells_map, rule_arena, super_cell_group_arena)
            })
            .collect::<Result<Vec<_>, Error>>()?,
        rules_supercell_map.into_values().collect(),
    ))
}

/// Reduce the ruleset using logical deduction.
fn reduce_rules<'arena, 'cell: 'arena, T: Cell + ?Sized>(
    rules: &[&'arena InternalRule<'arena, 'cell, T>],
    rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
    ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
    super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
) -> HashSet<&'arena InternalRule<'arena, 'cell, T>> {
    let mut reducer = RuleReducer::new();
    reducer.add_rules(
        rules.iter().copied(),
        rule_arena,
        ruleset_arena,
        super_cell_group_arena,
    );
    reducer.reduce_all(rule_arena, ruleset_arena, super_cell_group_arena)
}

/// During the logical deduction phase, if all rules are nodes in a graph, this
/// represents a directed edge in that graph indicating that `super_rule` can be
/// reduced by `sub_rule`.
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
struct Reduceable<'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// The larger rule.
    super_rule: &'arena InternalRule<'arena, 'cell, T>,
    /// The smaller rule, that can reduce the larger rule.
    sub_rule: &'arena InternalRule<'arena, 'cell, T>,
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> Reduceable<'arena, 'cell, T> {
    pub fn new(
        super_rule: &'arena InternalRule<'arena, 'cell, T>,
        sub_rule: &'arena InternalRule<'arena, 'cell, T>,
    ) -> Self {
        Self {
            super_rule,
            sub_rule,
        }
    }

    /// Calculate the attractiveness of this reduction. Favour reductions that
    /// involve larger rules, and amongst same-sized rules, those that yield
    /// mine counts towards the extremes - such rules have fewer permutations.
    pub fn metric(&self) -> (usize, usize, usize) {
        let num_reduced_cells = self.super_rule.num_cells - self.sub_rule.num_cells;
        let num_reduced_mines = self.super_rule.num_mines - self.sub_rule.num_mines;
        (
            self.super_rule.num_cells,
            self.sub_rule.num_cells,
            num_reduced_mines.abs_diff(num_reduced_cells / 2),
        )
    }

    /// Perform the reduction.
    pub fn reduce(
        &self,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) -> InternalRule<'arena, 'cell, T> {
        self.super_rule
            .subtract(&self.sub_rule, super_cell_group_arena)
    }

    /// Is this reduction contained within the given set of rules?
    pub fn contained_within(
        &self,
        rules: &HashSet<&'arena InternalRule<'arena, 'cell, T>>,
    ) -> bool {
        rules.contains(&self.super_rule) && rules.contains(&self.sub_rule)
    }
}
impl<T: Cell + ?Sized> Ord for Reduceable<'_, '_, T> {
    /// Use the metric to determine the ordering.
    fn cmp(&self, other: &Self) -> Ordering {
        self.metric().cmp(&other.metric())
    }
}
impl<T: Cell + ?Sized> PartialOrd for Reduceable<'_, '_, T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// A utility structure, mapping cells to the rules they appear in.
#[derive(Debug, PartialEq, Eq)]
struct CellRulesMap<'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// Cell -> Rules the cell appears in.
    map: HashMap<
        SuperCell<'arena, 'cell, T>,
        &'arena mut HashSet<&'arena InternalRule<'arena, 'cell, T>>,
    >,
    /// All rules known to the map.
    rules: HashSet<&'arena InternalRule<'arena, 'cell, T>>,
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> CellRulesMap<'arena, 'cell, T> {
    pub fn new() -> Self {
        Self {
            map: HashMap::new(),
            rules: HashSet::new(),
        }
    }

    pub fn add_rules(
        &mut self,
        rules: impl Iterator<Item = &'arena InternalRule<'arena, 'cell, T>>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
    ) {
        for rule in rules {
            self.add_rule(rule, ruleset_arena);
        }
    }

    pub fn add_rule(
        &mut self,
        rule: &'arena InternalRule<'arena, 'cell, T>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
    ) {
        for super_cell in rule.super_cells.iter() {
            (*self
                .map
                .entry(super_cell)
                .or_insert_with(|| ruleset_arena.alloc(HashSet::new())))
            .insert(rule);
        }
        self.rules.insert(rule);
    }

    pub fn remove_rule(&mut self, rule: &InternalRule<'arena, 'cell, T>) {
        for super_cell in rule.super_cells.iter() {
            self.map
                .get_mut(super_cell)
                .expect("Attempted to remove a rule that was not present")
                .remove(rule);
        }
        self.rules.remove(rule);
    }

    /// Return the set of rules that overlap `rule` i.e. share at least one
    /// cell.
    pub fn overlapping_rules(
        &self,
        rule: &InternalRule<'arena, 'cell, T>,
    ) -> HashSet<&'arena InternalRule<'arena, 'cell, T>> {
        let empty = HashSet::new();
        let mut rules = rule
            .super_cells
            .iter()
            .flat_map(|&super_cell| {
                self.map
                    .get(super_cell)
                    .map(|val| &**val)
                    .map_or_else(|| empty.iter(), |map| map.iter())
                    .copied()
            })
            .collect::<HashSet<_>>();
        rules.remove(rule);
        rules
    }

    /// Return pairs of all rules that overlap each other. Each pair is
    /// represented twice (`(a, b)` and `(b, a)`) to support processing of
    /// asymmetric relationships.
    pub fn interference_edges(
        &self,
    ) -> HashSet<(
        &'arena InternalRule<'arena, 'cell, T>,
        &'arena InternalRule<'arena, 'cell, T>,
    )> {
        self.rules
            .iter()
            .flat_map(|&rule| {
                self.overlapping_rules(rule)
                    .into_iter()
                    .map(move |overlapping| (rule, overlapping))
            })
            .collect()
    }

    /// Partition the ruleset into disjoint sub-rulesets of related rules.
    ///
    /// That is, all rules in a sub-ruleset are related to each other in some
    /// way through some number of overlaps, and no rules from separate
    /// sub-rulesets overlap each other. Returns a set of partitions, each a set
    /// of rules.
    pub fn partition(
        &self,
    ) -> HashSet<FrozenSet<&'arena InternalRule<'arena, 'cell, T>>> {
        let mut related_rules: HashMap<_, _> = self
            .rules
            .iter()
            .map(|&rule| (rule, self.overlapping_rules(rule)))
            .collect();
        let mut partitions = HashSet::new();
        while !related_rules.is_empty() {
            let start = peek(related_rules.keys());
            let partition = graph_traverse(&related_rules, start);
            for rule in &partition {
                related_rules.remove(rule);
            }
            partitions.insert(partition.into());
        }
        partitions
    }

    /// Return all cells contained in the ruleset.
    pub fn super_cells(&self) -> FrozenSet<SuperCell<'arena, 'cell, T>> {
        self.map.keys().cloned().collect()
    }
}

/// Manager structure that performs the 'logical deduction' phase of the solver.
/// Maintains a set of active rules, tracks which rules overlap with other
/// rules, and iteratively reduces them until no further reductions are
/// possible.
#[derive(Debug)]
struct RuleReducer<'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// Current set of active rules.
    active_rules: HashSet<&'arena InternalRule<'arena, 'cell, T>>,
    /// Lookup for rules containing a given cell.
    cell_rules_map: CellRulesMap<'arena, 'cell, T>,
    /// Current list of all possible reductions.
    candidate_reductions: BinaryHeap<Reduceable<'arena, 'cell, T>>,
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> RuleReducer<'arena, 'cell, T> {
    pub fn new() -> Self {
        Self {
            active_rules: HashSet::new(),
            cell_rules_map: CellRulesMap::new(),
            candidate_reductions: BinaryHeap::new(),
        }
    }

    /// Add a set of rules to the active ruleset.
    pub fn add_rules<'a>(
        &mut self,
        rules: impl Iterator<Item = &'a InternalRule<'arena, 'cell, T>>,
        rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) where
        'arena: 'a,
    {
        for rule in rules {
            self.add_rule(rule, rule_arena, ruleset_arena, super_cell_group_arena);
        }
    }

    /// Add a single rule to the active ruleset.
    pub fn add_rule(
        &mut self,
        rule: &InternalRule<'arena, 'cell, T>,
        rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) {
        for base_rule in rule.decompose(super_cell_group_arena) {
            self.add_base_rule(rule_arena.alloc(base_rule), ruleset_arena);
        }
    }

    /// Helper for adding a rule
    pub fn add_base_rule(
        &mut self,
        rule: &'arena InternalRule<'arena, 'cell, T>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
    ) {
        self.active_rules.insert(rule);
        self.cell_rules_map.add_rule(rule, ruleset_arena);
        self.update_reduceables(rule);
    }

    /// Add a new reduction to the list of possible reductions.
    pub fn add_reduceable(&mut self, reduction: Reduceable<'arena, 'cell, T>) {
        self.candidate_reductions.push(reduction);
    }

    /// Update the index of which rules are reduceable by others.
    pub fn update_reduceables(&mut self, rule: &'arena InternalRule<'arena, 'cell, T>) {
        for overlapping in self.cell_rules_map.overlapping_rules(rule) {
            if overlapping.is_subule_of(rule) {
                // This path is followed if the rules are equivalent
                self.add_reduceable(Reduceable::new(rule, overlapping));
            } else if rule.is_subule_of(&overlapping) {
                self.add_reduceable(Reduceable::new(overlapping, rule));
            }
        }
    }

    /// Remove a rule from the active ruleset/index; presumably because it was
    /// reduced away.
    pub fn remove_rule(&mut self, rule: &InternalRule<'arena, 'cell, T>) {
        self.active_rules.remove(rule);
        self.cell_rules_map.remove_rule(rule);
        // Can't remove the inner contents of candidate_reductions, so instead
        // rules are checked for validity when they're popped.
    }

    /// Get the next reduction that can be performed, highest-value first.
    pub fn get_next_reduction(&mut self) -> Option<Reduceable<'arena, 'cell, T>> {
        while let Some(reduction) = self.candidate_reductions.pop() {
            if reduction.contained_within(&self.active_rules) {
                return Some(reduction);
            }
        }
        None
    }

    /// Perform a single reduction.
    pub fn reduce(
        &mut self,
        reduction: Reduceable<'arena, 'cell, T>,
        rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) {
        let reduced_rule = reduction.reduce(super_cell_group_arena);
        self.remove_rule(&reduction.super_rule);
        self.add_rule(
            &reduced_rule,
            rule_arena,
            ruleset_arena,
            super_cell_group_arena,
        );
    }

    /// Perform all possible reductions and return the resulting reduced
    /// ruleset.
    pub fn reduce_all(
        mut self,
        rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) -> HashSet<&'arena InternalRule<'arena, 'cell, T>> {
        while let Some(reduction) = self.get_next_reduction() {
            self.reduce(reduction, rule_arena, ruleset_arena, super_cell_group_arena);
        }
        self.active_rules
    }
}

/// A single permutation of N mines among a set of (super-)cells.
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
struct Permutation<'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// Super-cell -> number of mines in that super-cell
    ///
    /// The cell set is determined implicitly from the mapping, so all cells in
    /// the set must have an entry, even if they have 0 mines.
    mapping: FrozenMap<SuperCell<'arena, 'cell, T>, usize>,
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> Permutation<'arena, 'cell, T> {
    pub fn new(
        mapping: impl IntoIterator<Item = (SuperCell<'arena, 'cell, T>, usize)>,
    ) -> Self {
        Self {
            mapping: mapping.into_iter().collect(),
        }
    }

    /// Return a sub-permutation containing only the cells in `sub_cells`.
    pub fn subset(
        &self,
        sub_cells: impl Iterator<Item = SuperCell<'arena, 'cell, T>>,
    ) -> Self {
        Self::new(sub_cells.map(|cell| {
            let mapped = self.mapping[&cell];
            (cell, mapped)
        }))
    }

    /// Is this permutation consistent with `other`? I.E. do the cells they have
    /// in common have matching numbers of mines assigned?
    pub fn is_compatible(&self, other: &Self) -> bool {
        let overlap = self
            .cells()
            .intersection(&other.cells())
            .cloned()
            .collect::<HashSet<_>>();
        self.subset(overlap.iter().cloned()) == other.subset(overlap.into_iter())
    }

    /// Combine two permutations, assuming they are compatible.
    ///
    /// # Panics
    ///
    /// Panics if the permutations are not compatible.
    pub fn combine(&self, other: &Self) -> Self {
        assert!(self
            .mapping
            .iter()
            .filter(|(cell, _)| other.mapping.contains_key(*cell))
            .all(|(cell, value)| other.mapping[cell] == *value));
        let mut map = self.mapping.clone().into_inner();
        for (&k, &v) in other.mapping.iter() {
            map.insert(k, v);
        }
        Self::new(map)
    }

    /// Return the total number of mines in this permutation.
    pub fn k(&self) -> usize {
        self.mapping.values().sum::<usize>()
    }

    /// Return the set of cells in this permutation.
    pub fn cells(&self) -> HashSet<SuperCell<'arena, 'cell, T>> {
        self.mapping.keys().copied().collect()
    }

    /// Count the number of permutations this permutation would correspond to if
    /// each super-cell were broken up into singleton cells.
    ///
    /// E.G. `N` mines in a super-cell of `M` cells has `comb(M, N)` actual
    /// configurations.
    pub fn multiplicity(&self) -> usize {
        self.mapping
            .iter()
            .map(|(&super_cell, &k)| comb(super_cell.len(), k))
            .product::<usize>()
    }
}

/// A set of permutations of the same cell set and total number of mines.
///
/// Might by the full set of possible permutations, or a subset as particular
/// permutations may be removed due to outside conflicts.
#[derive(Debug, PartialEq, Eq)]
struct PermutationSet<'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// The set of super-cells that this permutation set is over.
    super_cells: &'arena FrozenSet<SuperCell<'arena, 'cell, T>>,
    /// The total number of mines in this permutation set.
    k: usize,
    /// The set of [`Permutation`]s - all permutations must share the same set
    /// of cells and number of mines (`super_cells` and `k`)
    permutations: HashSet<&'arena Permutation<'arena, 'cell, T>>,
    /// Whether this set has been constrained by outside information. Accurate
    /// only if the `PermutationSet` was created with the full set of
    /// possibilities (or if `true`).
    constrained: bool,
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> Clone
    for PermutationSet<'arena, 'cell, T>
{
    fn clone(&self) -> Self {
        Self {
            super_cells: self.super_cells,
            k: self.k,
            permutations: self.permutations.clone(),
            constrained: self.constrained,
        }
    }
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> PermutationSet<'arena, 'cell, T> {
    pub fn new(
        super_cells: &'arena FrozenSet<SuperCell<'arena, 'cell, T>>,
        k: usize,
        permutations: impl IntoIterator<Item = &'arena Permutation<'arena, 'cell, T>>,
    ) -> Self {
        Self {
            super_cells,
            k,
            permutations: permutations.into_iter().collect(),
            constrained: false,
        }
    }

    /// Build a `PermutationSet` from all possible permutations of the given
    /// rule.
    pub fn from_rule(
        rule: &InternalRule<'arena, 'cell, T>,
        permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
    ) -> Self {
        Self::new(
            rule.super_cells,
            rule.num_mines,
            rule.permute().map(|perm| &*permutation_arena.alloc(perm)),
        )
    }

    /// Create an [`InternalRule`] from this set.
    ///
    /// Note that the set generated by `Self::from_rule(self.to_rule())` may not
    /// match this set, as it cannot account for permutations removed from this
    /// set due to outside constraints.
    pub fn to_rule(&self) -> InternalRule<'arena, 'cell, T> {
        InternalRule::new(
            self.k,
            self.super_cells,
            self.super_cells
                .iter()
                .map(|super_cell| super_cell.len())
                .sum::<usize>(),
        )
        .expect("Should be impossible to create an invalid rule from a PermutationSet")
    }

    /// Iterate over the [`Permutation`]s in this set.
    pub fn iter(
        &self,
    ) -> impl Iterator<Item = &'arena Permutation<'arena, 'cell, T>> + '_ {
        self.permutations.iter().copied()
    }

    /// Does this set contain the given [`Permutation`]?
    pub fn contains(&self, p: &Permutation<'arena, 'cell, T>) -> bool {
        self.permutations.contains(p)
    }

    /// Remove the given [`Permutation`] from this set, for example if that
    /// permutation conflicts with another rule.
    pub fn remove(&mut self, permu: &Permutation<'arena, 'cell, T>) {
        self.permutations.remove(permu);
        self.constrained = true;
    }

    /// Is this set empty?
    pub fn is_empty(&self) -> bool {
        self.permutations.is_empty()
    }

    /// Return a new `PermutationSet` containing only the [`Permutation`]s that
    /// are compatible with `permu`.
    pub fn compatible(&self, permu: &Permutation<'arena, 'cell, T>) -> Self {
        Self::new(
            self.super_cells,
            self.k,
            self.permutations
                .iter()
                .filter(|p| p.is_compatible(permu))
                .cloned(),
        )
    }

    /// Return a new `PermutationSet` consisting of the sub-setted
    /// [`Permutation`]s from this set.
    pub fn subset(
        &self,
        cell_subset: &'arena FrozenSet<SuperCell<'arena, 'cell, T>>,
        permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
    ) -> Option<Self> {
        let permu_subset = self
            .permutations
            .iter()
            .map(|p| &*permutation_arena.alloc(p.subset(cell_subset.iter().cloned())))
            .collect::<HashSet<_>>();
        let mut k_sub = permu_subset.iter().map(|p| p.k()).collect::<HashSet<_>>();
        if k_sub.len() == 1 {
            Some(Self::new(
                cell_subset,
                pop(&mut k_sub).unwrap(),
                permu_subset,
            ))
        } else {
            None
        }
    }

    /// Determine if the `PermutationSet` is the cartesian product of `N`
    /// smaller permutation sets; if so, return the decomposition.
    ///
    /// This set may be constrained, in which case at least one subset of the
    /// decomposition (if one exists) will also be constrained.
    ///
    /// Optimises if the set has not been constrained; full permutation-sets
    /// decompose to themselves.
    pub fn decompose(
        &self,
        permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) -> Vec<Self> {
        if self.constrained {
            self.force_decompose(1, permutation_arena, super_cell_group_arena)
        } else {
            vec![self.clone()]
        }
    }

    /// Determine if the `PermutationSet` is the cartesian product of `N`
    /// smaller permutation sets; if so, return the decomposition.
    ///
    /// This set may be constrained, in which case at least one subset of the
    /// decomposition (if one exists) will also be constrained.
    fn force_decompose(
        &self,
        k_floor: usize,
        permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) -> Vec<Self> {
        for k in k_floor..=(self.super_cells.len() / 2) {
            for cell_subset in self.super_cells.iter().combinations(k) {
                let cell_subset = &*super_cell_group_arena
                    .alloc(cell_subset.into_iter().cloned().collect::<FrozenSet<_>>());
                let Some((
                    permu_subset,
                    permu_remainder,
                )) = self.split(cell_subset, permutation_arena, super_cell_group_arena)
                else {
                    continue;
                };

                // We've found a cartesian divisor!
                let mut divisors = vec![permu_subset];
                divisors.extend(permu_remainder.force_decompose(
                    k,
                    permutation_arena,
                    super_cell_group_arena,
                ));
                return divisors;
            }
        }
        vec![self.clone()]
    }

    /// Helper function for [`Self::decompose()`]. Given a subset of cells,
    /// return the two `PermutationSet`s for the subset and the set of remaining
    /// cells, provided `cell_subset` is a valid decomposor; return `None` if
    /// not.
    fn split(
        &self,
        cell_subset: &'arena FrozenSet<SuperCell<'arena, 'cell, T>>,
        permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) -> Option<(Self, Self)> {
        let cell_remainder = super_cell_group_arena.alloc(
            self.super_cells
                .difference(cell_subset)
                .cloned()
                .collect::<FrozenSet<_>>(),
        );
        let permu_subset = self.subset(cell_subset, permutation_arena)?;

        let mut permu_remainders = map_reduce(
            self.permutations.iter().copied(),
            |p| [(p.subset(cell_subset.iter().copied()), p)].into_iter(),
            |pv| {
                pv.into_iter()
                    .map(|p| {
                        permutation_arena
                            .alloc(p.subset(cell_remainder.iter().copied()))
                    })
                    .collect::<FrozenSet<_>>()
            },
        )
        .into_values()
        .collect::<HashSet<_>>();

        if permu_remainders.len() == 1 {
            let permu_remainders = pop(&mut permu_remainders).unwrap();
            let other_k = permu_subset.k;
            Some((
                permu_subset,
                Self::new(
                    cell_remainder,
                    self.k - other_k,
                    permu_remainders.into_iter().map(|p| &*p),
                ),
            ))
        } else {
            None
        }
    }
}

/// A set of rules and the available permutations for each, eliminating
/// permutations which are mutually-inconsistent across the ruleset.
#[derive(Debug, PartialEq, Eq)]
struct PermutedRuleset<'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// The ruleset.
    rules: &'arena mut HashSet<&'arena InternalRule<'arena, 'cell, T>>,
    /// Lookup for cell -> rules containing that cell.
    cell_rules_map: CellRulesMap<'arena, 'cell, T>,
    /// The supercells of the ruleset.
    super_cells: FrozenSet<SuperCell<'arena, 'cell, T>>,
    /// `InternalRule` -> `PermutationSet` for that rule.
    permu_map: HashMap<
        &'arena InternalRule<'arena, 'cell, T>,
        &'arena mut PermutationSet<'arena, 'cell, T>,
    >,
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> PermutedRuleset<'arena, 'cell, T> {
    /// # Arguments
    ///
    /// * `permu_map`: If creating a subset of another `PermutedRuleset`, will
    ///   be the `permu_map` for the new PermutedRuleset; for a new one, will be
    ///   computed automatically.
    pub fn new(
        rules: &'arena mut HashSet<&'arena InternalRule<'arena, 'cell, T>>,
        permu_map: Option<
            HashMap<
                &'arena InternalRule<'arena, 'cell, T>,
                &'arena mut PermutationSet<'arena, 'cell, T>,
            >,
        >,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
        permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
        permutation_set_arena: &'arena Arena<PermutationSet<'arena, 'cell, T>>,
    ) -> Self {
        let mut cell_rules_map = CellRulesMap::new();
        cell_rules_map.add_rules(rules.iter().cloned(), ruleset_arena);
        let super_cells = cell_rules_map.super_cells();
        Self {
            cell_rules_map,
            super_cells,
            permu_map: match permu_map {
                Some(permu_map) => {
                    // Pre-processed by Self::filter
                    permu_map
                },
                None => {
                    rules
                        .iter()
                        .map(|&rule| {
                            (
                                rule,
                                permutation_set_arena.alloc(PermutationSet::from_rule(
                                    rule,
                                    permutation_arena,
                                )),
                            )
                        })
                        .collect()
                },
            },
            rules,
        }
    }

    /// Determine what permutations are possible for each rule, taking into
    /// account the constraints of all overlapping rules. Eliminate impossible
    /// permutations.
    pub fn cross_eliminate(&mut self) -> Result<(), Error> {
        let mut interferences = self.cell_rules_map.interference_edges();
        // We can't just iterate over `interferences`, as eliminating a permutation may
        // in turn invalidate permutations in other overlapping rules that have already
        // been processed, causing a cascade effect. Therefore, treat the list of
        // interferences like a queue.
        while let Some((rule, overlapping)) = pop(&mut interferences) {
            let mut changed = false;
            for permu in self.permu_map[&rule].iter().collect_vec() {
                // Copy the set into a list so we can mutate it
                if self.permu_map[&overlapping].compatible(&permu).is_empty() {
                    // This permutation has no compatible permutation in the
                    // overlapping rule. Therefore, it can never occur.
                    self.permu_map
                        .get_mut(&rule)
                        .expect("self.permu_map[rule] has already been accessed")
                        .remove(&permu);
                    changed = true;
                }
            }

            if self.permu_map[&rule].is_empty() {
                // No possible configurations for this rule remain.
                return Err(
                    "Rule is constrained such that it has no valid mine permutations"
                );
            } else if changed {
                // Other rules that overlap this one must be recalculated.
                interferences.extend(
                    self.cell_rules_map
                        .overlapping_rules(&rule)
                        .into_iter()
                        .map(|other| (other, rule)),
                );
            }
        }
        Ok(())
    }

    /// After computing the possible permutations of the rules, analyse and
    /// decompose rules into sub-rules, if possible. This can eliminate
    /// dependencies among the initial set of rules, and thus potentially split
    /// what would have been one rule front into several.
    ///
    /// This is analogous to the previous `reduce_rules` step, but with more
    /// advanced logical analysis - exploiting information gained from the
    /// permutation phase.
    ///
    /// Some unproven postulates:
    /// - Among all cartesian decompositions from all rules, none will be
    ///   reduceable with another (decomposed rules may have duplicates,
    ///   though).
    /// - Cartesian decomposition will have effectively re-reduced all rules in
    ///   the set, even non-decomposed rules; there will be no possible
    ///   reductions between a decomposed rule and an original rule.
    /// - Re-permuting amongst the decomposed ruleset will produce the same
    ///   permutation sets
    pub fn rereduce(
        &mut self,
        rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
        permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
        permutation_set_arena: &'arena Arena<PermutationSet<'arena, 'cell, T>>,
        super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
    ) {
        let mut superseded_rules = HashSet::new();
        let mut decompositions = HashMap::new();
        for (&rule, permu_set) in self.permu_map.iter() {
            let decomp = permu_set.decompose(permutation_arena, super_cell_group_arena);
            if decomp.len() > 1 {
                superseded_rules.insert(rule);
                // Collapse duplicate decompositions by keying by cell set
                decompositions
                    .extend(decomp.into_iter().map(|dc| (dc.super_cells, dc)));
            }
        }

        for rule in superseded_rules {
            self.remove_rule(rule);
        }
        for permu_set in decompositions.into_values() {
            self.add_permu_set(
                permutation_set_arena.alloc(permu_set),
                rule_arena,
                ruleset_arena,
            );
        }
    }

    pub fn remove_rule(&mut self, rule: &InternalRule<'arena, 'cell, T>) {
        self.rules.remove(rule);
        self.cell_rules_map.remove_rule(rule);
        self.permu_map.remove(rule);
    }

    /// Add a decomposed rule to the ruleset.
    pub fn add_permu_set(
        &mut self,
        permu_set: &'arena mut PermutationSet<'arena, 'cell, T>,
        rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
    ) {
        let rule = rule_arena.alloc(permu_set.to_rule());
        self.rules.insert(rule);
        self.cell_rules_map.add_rule(rule, ruleset_arena);
        self.permu_map.insert(rule, permu_set);
    }

    /// Return a `PermutedRuleset` built from this one containing only a subset
    /// of its rules.
    pub fn filter(
        &mut self,
        rule_subset: &'arena mut HashSet<&'arena InternalRule<'arena, 'cell, T>>,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
        permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
        permutation_set_arena: &'arena Arena<PermutationSet<'arena, 'cell, T>>,
    ) -> Self {
        // This works because the sets are independent; all rules are used exactly once
        let permu_map = rule_subset
            .iter()
            .map(|&rule| {
                self.permu_map
                    .remove_entry(rule)
                    .expect("Entry should be present")
            })
            .collect();
        Self::new(
            rule_subset,
            Some(permu_map),
            ruleset_arena,
            permutation_arena,
            permutation_set_arena,
        )
    }

    /// Split the ruleset into combinatorially-independent 'fronts'.
    pub fn split_fronts(
        mut self,
        ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
        permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
        permutation_set_arena: &'arena Arena<PermutationSet<'arena, 'cell, T>>,
    ) -> Vec<Self> {
        self.cell_rules_map
            .partition()
            .into_iter()
            .map(|rule_subset| {
                self.filter(
                    ruleset_arena.alloc(rule_subset.iter().cloned().collect()),
                    ruleset_arena,
                    permutation_arena,
                    permutation_set_arena,
                )
            })
            .collect()
    }

    /// Is this ruleset trivial? (i.e. does it contain only one rule?)
    pub fn is_trivial(&self) -> bool {
        self.rules.len() == 1
    }

    /// If this ruleset is trivial, return the single rule it contains.
    ///
    /// # Panics
    ///
    /// Panics if the ruleset is not trivial.
    pub fn trivial_rule(&self) -> &'arena InternalRule<'arena, 'cell, T> {
        assert!(self.is_trivial());
        let singleton = peek(self.rules.iter().cloned());
        // Postulate: Any singleton rule must also be trivial
        assert!(singleton.is_trivial());
        singleton
    }

    /// Enumerate all possible mine configurations for this ruleset.
    pub fn enumerate(
        &self,
    ) -> Box<dyn Iterator<Item = Permutation<'arena, 'cell, T>> + '_> {
        EnumerationState::new(self).enumerate()
    }
}

/// Process the set of rules and analyse the relationships and constraints among
/// them.
fn permute_and_interfere<'arena, 'cell: 'arena, T: Cell + ?Sized>(
    rules: &'arena mut HashSet<&'arena InternalRule<'arena, 'cell, T>>,
    rule_arena: &'arena Arena<InternalRule<'arena, 'cell, T>>,
    ruleset_arena: &'arena Arena<HashSet<&'arena InternalRule<'arena, 'cell, T>>>,
    permutation_arena: &'arena Arena<Permutation<'arena, 'cell, T>>,
    permutation_set_arena: &'arena Arena<PermutationSet<'arena, 'cell, T>>,
    super_cell_group_arena: &'arena Arena<FrozenSet<SuperCell<'arena, 'cell, T>>>,
) -> Result<PermutedRuleset<'arena, 'cell, T>, Error> {
    let mut permuted_ruleset = PermutedRuleset::new(
        rules,
        None,
        ruleset_arena,
        permutation_arena,
        permutation_set_arena,
    );
    permuted_ruleset.cross_eliminate()?;
    permuted_ruleset.rereduce(
        rule_arena,
        ruleset_arena,
        permutation_arena,
        permutation_set_arena,
        super_cell_group_arena,
    );
    Ok(permuted_ruleset)
}

/// A helper structure to enumerate through all possible mine configurations for
/// a given ruleset.
#[derive(Debug, PartialEq, Eq)]
struct EnumerationState<'rules, 'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// The set of [`Permutation`]s (one per rule) that have been 'fixed' for
    /// the current configuration-in-progress.
    fixed: HashSet<&'arena Permutation<'arena, 'cell, T>>,
    /// The [`PermutedRuleset`] that we are enumerating.
    ruleset: &'rules PermutedRuleset<'arena, 'cell, T>,
    /// The subset of `ruleset` whose permutations are still 'open'
    free: HashMap<
        &'arena InternalRule<'arena, 'cell, T>,
        HashSet<&'arena Permutation<'arena, 'cell, T>>,
    >,
    /// Index for constraining overlapping permutations.
    /// Mapping from (permutation, overlapping_rule) to the [`PermutationSet`]
    /// of valid permutations for the overlapping rule.
    compatible_rule_index: HashMap<
        (
            &'arena Permutation<'arena, 'cell, T>,
            &'arena InternalRule<'arena, 'cell, T>,
        ),
        PermutationSet<'arena, 'cell, T>,
    >,
}
impl<'rules, 'arena, 'cell: 'arena, T: Cell + ?Sized> Clone
    for EnumerationState<'rules, 'arena, 'cell, T>
{
    fn clone(&self) -> Self {
        Self {
            fixed: self.fixed.clone(),
            ruleset: self.ruleset,
            free: self.free.clone(),
            compatible_rule_index: self.compatible_rule_index.clone(),
        }
    }
}
impl<'rules, 'arena, 'cell: 'arena, T: Cell + ?Sized>
    EnumerationState<'rules, 'arena, 'cell, T>
{
    pub fn new(ruleset: &'rules PermutedRuleset<'arena, 'cell, T>) -> Self {
        let mut rv = Self {
            fixed: HashSet::new(),
            ruleset,
            free: ruleset
                .permu_map
                .iter()
                .map(|(&rule, permu_set)| (rule, permu_set.iter().collect()))
                .collect(),
            compatible_rule_index: HashMap::new(),
        };
        rv.build_compatibility_index(&ruleset.permu_map);
        rv
    }

    /// Helper to reduce typing when accessing the overlapping rules.
    pub fn overlapping_rules(
        &self,
        rule: &InternalRule<'arena, 'cell, T>,
    ) -> HashSet<&'arena InternalRule<'arena, 'cell, T>> {
        self.ruleset.cell_rules_map.overlapping_rules(rule)
    }

    /// Generate the constraint index.
    pub fn build_compatibility_index(
        &mut self,
        map: &HashMap<
            &'arena InternalRule<'arena, 'cell, T>,
            &'arena mut PermutationSet<'arena, 'cell, T>,
        >,
    ) {
        for (rule, permu_set) in map.iter() {
            for permu in permu_set.iter() {
                for overlapping in self.overlapping_rules(rule) {
                    let v = map[&overlapping].compatible(permu);
                    self.compatible_rule_index.insert((permu, overlapping), v);
                }
            }
        }
    }

    /// Is the configuration complete? I.E. have all rules been fixed?
    pub fn is_complete(&self) -> bool {
        self.free.is_empty()
    }

    /// Pick an 'open' rule at random and 'fix' each possible permutation for
    /// that rule. In this manner, when done recursively, all valid combinations
    /// are enumerated.
    pub fn into_iter(
        mut self,
    ) -> impl Iterator<Item = EnumerationState<'rules, 'arena, 'cell, T>> + 'rules {
        let state = self.clone();
        let rule = peek(state.free.keys().copied());
        // let permus = self.free[rule].clone();
        // permus
        self.free
            .remove_entry(rule)
            .expect("Rule was taken out of keys")
            .1
            .into_iter()
            .filter_map(move |permu| state.propagate(&rule, permu))
    }

    /// 'Fix' a permutation for a given rule.
    pub fn propagate(
        &self,
        rule: &'arena InternalRule<'arena, 'cell, T>,
        permu: &'arena Permutation<'arena, 'cell, T>,
    ) -> Option<Self> {
        let mut state = self.clone();
        state.propagate_in_place(rule, permu)?;
        Some(state)
    }

    /// 'Fix' a rule permutation and constrain the available permutations of all
    /// overlapping rules, in-place.
    fn propagate_in_place(
        &mut self,
        rule: &'arena InternalRule<'arena, 'cell, T>,
        permu: &'arena Permutation<'arena, 'cell, T>,
    ) -> Option<()> {
        self.fixed.insert(permu);
        self.free.remove(rule)?;

        // Constrain overlapping rules
        let mut cascades = Vec::new();
        for related_rule in self
            .overlapping_rules(rule)
            .into_iter()
            .filter(|r| self.free.contains_key(r))
            .collect_vec()
        {
            // `PermutationSet` of the related rule, constrained *only* by the
            // rule/permutation just fixed
            let allowed_permus =
                self.compatible_rule_index.get(&(permu, related_rule))?;
            // Further constrain the related rule with this new set - is now properly
            // constrained by all fixed rules
            self.free
                .get_mut(related_rule)?
                .retain(|p| allowed_permus.contains(p));

            let linked_permus = self.free.get(&related_rule)?;
            if linked_permus.is_empty() {
                // Conflict - no possible configurations
                return None;
            } else if linked_permus.len() == 1 {
                // Only one possibility - constrain further
                cascades.push((related_rule, peek(linked_permus.iter().cloned())));
            }
        }

        // Cascade if any other rules are now fully constrained
        for (related_rule, constrained_permu) in cascades {
            // May have already been constrained by a prior recursive call
            if self.free.contains_key(&related_rule) {
                self.propagate_in_place(&related_rule, constrained_permu)?;
            }
        }
        Some(())
    }

    /// Convert the set of fixed permutations into a single [`Permutation`]
    /// encompassing the mine configuration for the entire ruleset.
    pub fn mine_config(&self) -> Permutation<'arena, 'cell, T> {
        self.fixed
            .iter()
            .fold(Permutation::new(empty()), |a, b| a.combine(b))
    }

    /// Recursively generate all possible mine configurations for the ruleset.
    pub fn enumerate(
        self,
    ) -> Box<dyn Iterator<Item = Permutation<'arena, 'cell, T>> + 'rules> {
        if self.is_complete() {
            Box::new(once(self.mine_config()))
        } else {
            Box::new(self.into_iter().flat_map(|s| s.enumerate()))
        }
    }
}

/// Tabulation of per-cell mine frequencies.
#[derive(Clone, Debug, PartialEq)]
struct FrontTally<'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// Number of mines in configuration -> Sub-tally of configurations with
    /// that number of mines.
    subtallies: HashMap<usize, FrontSubtally<'arena, 'cell, T>>,
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> FrontTally<'arena, 'cell, T> {
    pub fn new(
        data: impl Iterator<Item = (usize, FrontSubtally<'arena, 'cell, T>)>,
    ) -> Self {
        Self {
            subtallies: data.collect(),
        }
    }

    /// Tally all possible configurations for a front (ruleset).
    ///
    /// The tallies for different total numbers of mines must be maintained
    /// separately, as these will be given different statistical weights later
    /// on.
    pub fn tally(
        &mut self,
        front: PermutedRuleset<'arena, 'cell, T>,
    ) -> Result<(), Error> {
        for config in front.enumerate() {
            (self
                .subtallies
                .entry(config.k())
                .or_insert_with(FrontSubtally::new))
            .add(&config);
        }

        if self.subtallies.is_empty() {
            return Err("Mine front has no possible configurations");
        }

        self.finalise();

        Ok(())
    }

    /// Finalise all sub-tallies (convert running totals to
    /// probabilities/expected values).
    pub fn finalise(&mut self) {
        for subtally in self.subtallies.values_mut() {
            subtally.finalise();
        }
    }

    /// Minimum number of mines found across all configurations.
    pub fn min_mines(&self) -> usize {
        self.subtallies
            .keys()
            .copied()
            .min()
            .expect("Mine front has no possible configurations")
    }

    /// Maximum number of mines found across all configurations.
    pub fn max_mines(&self) -> usize {
        self.subtallies
            .keys()
            .copied()
            .max()
            .expect("Mine front has no possible configurations")
    }

    /// Whether all configurations have the same number of mines (simplifies
    /// statistical weighting later).
    pub fn is_static(&self) -> bool {
        self.subtallies.len() == 1
    }

    pub fn iter(
        &self,
    ) -> impl Iterator<Item = (usize, &FrontSubtally<'arena, 'cell, T>)> + '_ {
        self.subtallies.iter().map(|(&k, v)| (k, v))
    }

    /// Normalise sub-tally totals into relative weights such that sub-totals
    /// remain proportional to each other, and the grand total across all
    /// sub-tallies is `1.0`.
    pub fn normalise(&mut self) {
        let total = self.subtallies.values().map(|s| s.total).sum::<f64>();
        for subtally in self.subtallies.values_mut() {
            subtally.total /= total;
        }
    }

    /// Calculate the per-cell expected mine values, summed and weighted across
    /// all sub-tallies.
    pub fn collapse(
        &mut self,
    ) -> HashMap<Either<SuperCell<'arena, 'cell, T>, UnchartedCell>, f64> {
        self.normalise();
        let collapsed = map_reduce(
            self.subtallies.values(),
            |subtally| subtally.collapse().collect_vec().into_iter(),
            |values| values.into_iter().sum(),
        );
        collapsed
    }

    /// Scale each sub-tally's weight/total according to `scale_func`.
    ///
    /// # Arguments
    ///
    /// * `scale_func` - Function that takes the number of mines in a sub-tally,
    ///   and returns a factor by which to scale the sub-tally (multiplier).
    ///
    /// # Errors
    ///
    /// If `scale_func` returns an error, the error is propagated and processing
    /// does not continue. This `FrontTally` is left in an unspecified state
    /// if this occurs, and should not be used.
    pub fn scale_weights(
        &mut self,
        scale_func: impl Fn(usize) -> Result<f64, Error>,
    ) -> Result<(), Error> {
        for (&num_mines, subtally) in self.subtallies.iter_mut() {
            subtally.total *= scale_func(num_mines)?;
        }
        Ok(())
    }

    /// Update each sub-tally's weight/total according to the given weights.
    pub fn update_weights(&mut self, weights: &HashMap<usize, f64>) {
        for (&num_mines, subtally) in self.subtallies.iter_mut() {
            subtally.total *= weights.get(&num_mines).copied().unwrap_or(0.0);
        }
    }

    /// Tally a trivial rule
    ///
    /// # Panics
    ///
    /// Panics if the rule is not trivial.
    pub fn from_rule(rule: &InternalRule<'arena, 'cell, T>) -> Self {
        assert!(rule.is_trivial());
        Self::new(
            [(
                rule.num_mines,
                FrontSubtally::from_data(
                    comb(rule.num_cells, rule.num_mines) as f64,
                    [(
                        Either::Left(peek(rule.super_cells.iter().cloned())),
                        rule.num_mines as f64,
                    )]
                    .into_iter(),
                ),
            )]
            .into_iter(),
        )
    }

    /// Create a meta-tally representing the mine distribution of all 'other'
    /// cells.
    ///
    /// # Arguments
    ///
    /// * `num_uncharted_cells` - Number of 'other' cells, that are not
    ///   otherwise accounted for.
    /// * `mine_totals` - A mapping suitable for [`Self::update_weights()`];
    ///   number of mines in 'other' region -> relative likelihood.
    pub fn for_other(
        num_uncharted_cells: usize,
        mine_totals: &HashMap<usize, f64>,
    ) -> Self {
        let meta_cell = UnchartedCell::new(num_uncharted_cells);
        Self::new(mine_totals.iter().map(|(&num_mines, &k)| {
            (
                num_mines,
                FrontSubtally::from_data(
                    k,
                    [(Either::Right(meta_cell), num_mines as f64)].into_iter(),
                ),
            )
        }))
    }
}

type CollapseResult<'arena, 'cell, T> =
    (Either<SuperCell<'arena, 'cell, T>, UnchartedCell>, f64);

/// Sub-tabulation of per-cell mine frequencies.
#[derive(Clone, Debug, PartialEq)]
struct FrontSubtally<'arena, 'cell: 'arena, T: Cell + ?Sized> {
    /// The 'weight' of this sub-tally among the others in the [`FrontTally`].
    /// Initially will be a raw count of the configurations in this sub-tally,
    /// but later will be weighted and normalised.
    total: f64,
    /// Per-cell mine counts (pre-finalising) or mine likelihoods
    /// (post-finalising).
    ///
    /// Mapping:
    ///
    /// - Key: A super-cell
    /// - Value:
    ///   - Pre-finalise: Total number of mines in the cell, summed across all
    ///     configurations
    ///   - Post-finalise: Expected number of mines in the cell
    tally: HashMap<Either<SuperCell<'arena, 'cell, T>, UnchartedCell>, f64>,
}
impl<'arena, 'cell: 'arena, T: Cell + ?Sized> FrontSubtally<'arena, 'cell, T> {
    pub fn new() -> Self {
        Self {
            total: 0.0,
            tally: HashMap::new(),
        }
    }

    /// Add a configuration to the tally.
    pub fn add(&mut self, config: &Permutation<'arena, 'cell, T>) {
        let mult = config.multiplicity() as f64;
        self.total += mult;
        for (&super_cell, &n) in config.mapping.iter() {
            *self.tally.entry(Either::Left(super_cell)).or_insert(0.0) +=
                n as f64 * mult;
        }
    }

    /// After all configurations have been summed, compute relative prevalence
    /// from totals.
    pub fn finalise(&mut self) {
        self.tally.values_mut().for_each(|n| *n /= self.total);
    }

    /// Helper function for [`FrontTally::collapse()`]. Emit all cell expected
    /// mine values weighted by this sub-tally's weight.
    pub fn collapse(
        &self,
    ) -> impl Iterator<Item = CollapseResult<'arena, 'cell, T>> + '_ {
        self.tally.iter().map(|(super_cell, &expected_mines)| {
            (super_cell.clone(), self.total * expected_mines)
        })
    }

    /// Build a sub-tally manually. Tally data is expected to be pre-finalised.
    pub fn from_data(
        total: f64,
        tally: impl Iterator<Item = CollapseResult<'arena, 'cell, T>>,
    ) -> Self {
        Self {
            total,
            tally: tally.collect(),
        }
    }
}

/// Enumerate and tabulate all mine configurations for the given front.
///
/// Return a tally where sub-totals are split out by total number of mines in
/// the configuration, and each sub-tally contains a total count of matching
/// configurations, and an expected number of mines in each cell.
fn enumerate_front<'arena, 'cell: 'arena, T: Cell + ?Sized>(
    front: PermutedRuleset<'arena, 'cell, T>,
) -> Result<FrontTally<'arena, 'cell, T>, Error> {
    let mut tally = FrontTally::new(empty());
    tally.tally(front)?;
    Ok(tally)
}

/// Generate the final expected values for all cells in all fronts.
///
/// # Arguments
///
/// * `tallies` - The [`FrontTally`]s to collapse.
/// * `mine_prevalence` - Either the [`BoardInfo`] for the board, or the
///   probability that an individual cell is a mine.
/// * `all_cells` - The set of all (super-)cells from all rules.
///
/// # Returns
///
/// A stream of (cell, expected number of mines) pairs for all cells.
fn cell_probabilities<'arena, 'cell: 'arena, T: Cell + ?Sized>(
    tallies: Vec<FrontTally<'arena, 'cell, T>>,
    mine_prevalence: Either<BoardInfo, f64>,
    all_cells: Vec<SuperCell<'arena, 'cell, T>>,
) -> Result<impl Iterator<Item = CollapseResult<'arena, 'cell, T>>, Error> {
    struct Iter<
        'arena,
        'cell: 'arena,
        T: Cell + ?Sized + 'cell,
        I: Iterator<Item = CollapseResult<'arena, 'cell, T>>,
        J: Iterator<Item = CollapseResult<'arena, 'cell, T>>,
    > {
        inner: Either<I, J>,
    }
    impl<
            'arena,
            'cell: 'arena,
            T: Cell + ?Sized + 'cell,
            I: Iterator<Item = CollapseResult<'arena, 'cell, T>>,
            J: Iterator<Item = CollapseResult<'arena, 'cell, T>>,
        > Iterator for Iter<'arena, 'cell, T, I, J>
    {
        type Item = CollapseResult<'arena, 'cell, T>;

        fn next(&mut self) -> Option<Self::Item> {
            match &mut self.inner {
                Either::Left(iter) => iter.next(),
                Either::Right(iter) => iter.next(),
            }
        }
    }
    Ok(
        weight_subtallies(tallies, mine_prevalence, all_cells)?.flat_map(|tally| {
            Iter {
                inner: match tally {
                    Either::Left(mut tally) => {
                        Either::Left(tally.collapse().into_iter())
                    },
                    Either::Right(tally) => Either::Right(tally.collapse()),
                },
            }
        }),
    )
}

/// Analyse all [`FrontTally`]s as a whole and weight the likelihood of each
/// sub-tally using probability analysis.
fn weight_subtallies<'arena, 'cell: 'arena, T: Cell + ?Sized>(
    mut tallies: Vec<FrontTally<'arena, 'cell, T>>,
    mine_prevalence: Either<BoardInfo, f64>,
    all_cells: Vec<SuperCell<'arena, 'cell, T>>,
) -> Result<
    Box<
        dyn Iterator<Item = Either<FrontTally<'arena, 'cell, T>, FixedProbTally>>
            + 'arena,
    >,
    Error,
> {
    Ok(match mine_prevalence {
        Either::Left(board_info) => {
            // Traditional minesweeper - fixed total number of mines
            let num_uncharted_cells = check_count_consistency(
                &tallies.iter().collect_vec(),
                board_info,
                all_cells,
            )?;
            // Tallies with only one sub-tally don't need weighting.
            let (static_tallies, mut dyn_tallies) = {
                let mut static_tallies = vec![];
                let mut dyn_tallies = vec![];
                for tally in tallies {
                    if tally.is_static() {
                        static_tallies.push(tally);
                    } else {
                        dyn_tallies.push(tally);
                    }
                }
                (static_tallies, dyn_tallies)
            };

            let num_static_mines = static_tallies
                .iter()
                .map(|tally| tally.max_mines())
                .sum::<usize>();
            let at_large_mines = board_info.total_mines - num_static_mines;

            let tally_uncharted =
                combine_fronts(&mut dyn_tallies, num_uncharted_cells, at_large_mines);
            Box::new(
                static_tallies
                    .into_iter()
                    .chain(dyn_tallies.into_iter())
                    .chain(once(tally_uncharted))
                    .map(Either::Left),
            )
        },
        Either::Right(mine_probability) => {
            // Fixed probability of a mine in any given cell - total number of mines
            // varies per game
            let tally_uncharted = weight_nondiscrete(
                tallies.iter_mut().filter(|tally| tally.is_static()),
                mine_probability,
            )?;
            Box::new(
                tallies
                    .into_iter()
                    .map(Either::Left)
                    .chain(once(Either::Right(tally_uncharted))),
            )
        },
    })
}

/// Weight the relative likelihood of each sub-tally in a 'fixed
/// chance'/'variable-mine-count'-style game.
///
/// In this scenario, all fronts are completely independent; no front affects
/// the likelihoods for any other front.
fn weight_nondiscrete<'a, 'arena: 'a, 'cell: 'arena, T: Cell + ?Sized + 'cell>(
    dyn_tallies: impl IntoIterator<Item = &'a mut FrontTally<'arena, 'cell, T>>,
    mine_probability: f64,
) -> Result<FixedProbTally, Error> {
    for tally in dyn_tallies.into_iter() {
        let min_mines = tally.min_mines() as f64;
        tally.scale_weights(|num_mines| {
            nondiscrete_relative_likelihood(
                mine_probability,
                num_mines as f64,
                min_mines,
            )
        })?;
    }

    // Return the fixed mine probability as the chance for 'other' cells. Slightly
    // redundant but saves the client a step. Note that since we don't count the
    // total number of cells in this mode, this is *not* a guarantee that any given
    // game state actually has any 'other' cells.
    Ok(FixedProbTally::new(mine_probability))
}

/// Ensure the minimum/maximum number of mines required across all fronts is
/// compatible with the total number of mines, and remaining space available on
/// the board.
///
/// In the process, compute and return the remaining available space (i.e. the
/// number of 'other' cells not referenced in any rule).
fn check_count_consistency<T: Cell + ?Sized>(
    tallies: &[&FrontTally<'_, '_, T>],
    board_info: BoardInfo,
    all_cells: Vec<&FrozenSet<&T>>,
) -> Result<usize, Error> {
    let (min_possible_mines, max_possible_mines) =
        possible_mine_limits(tallies.into_iter().copied());
    let num_uncharted_cells = board_info.total_cells
        - all_cells
            .into_iter()
            .map(|super_cell| super_cell.len())
            .sum::<usize>();
    if min_possible_mines > board_info.total_mines {
        Err("Minimum possible number of mines exceeds supplied mine count")
    } else if board_info.total_mines > max_possible_mines + num_uncharted_cells {
        Err("Supplied mine count exceeds maximum possible number of mines")
    } else {
        Ok(num_uncharted_cells)
    }
}

/// Assign relative weights to all sub-tallies in all fronts. Because the total
/// number of mines is fixed, we must do a combinatorial analysis to compute the
/// likelihood of each front containing each possible number of mines. In the
/// process, compute the mine count likelihood for the 'other' cells, not part
/// of any front, and return a meta-front encapsulating them.
fn combine_fronts<'arena, 'cell: 'arena, T: Cell + ?Sized>(
    tallies: &mut Vec<FrontTally<'arena, 'cell, T>>,
    num_uncharted_cells: usize,
    at_large_mines: usize,
) -> FrontTally<'arena, 'cell, T> {
    /// Tracks, for a constituent front, how many configurations for each number
    /// of mines in the front.
    struct FrontPerMineTotals {
        /// Mapping: number of mines in front -> number of configurations
        totals: HashMap<usize, f64>,
    }
    impl FrontPerMineTotals {
        pub fn singleton(num_mines: usize, total: f64) -> Self {
            Self {
                totals: [(num_mines, total)].into(),
            }
        }

        /// Total number of configurations across all possible numbers of mines.
        pub fn total_count(&self) -> f64 {
            self.totals.values().sum::<f64>()
        }

        /// Multiply every configuration's count by a fixed factor.
        pub fn multiply(&self, n: f64) -> Self {
            Self {
                totals: self.totals.iter().map(|(&k, &v)| (k, v * n)).collect(),
            }
        }

        /// Compute an aggregate sum of several mappings.
        pub fn sum<'a>(front_totals: impl Iterator<Item = &'a Self>) -> Self {
            Self {
                totals: map_reduce(
                    front_totals,
                    |front_totals| front_totals.totals.iter().map(|(&k, &v)| (k, v)),
                    |vals| vals.into_iter().sum::<f64>(),
                ),
            }
        }
    }

    /// Tracks, for a given number of mines in the [`CombinedFront`], the
    /// [`FrontPerMineTotals`]s corresponding to each constituent front.
    struct AllFrontsPerMineTotals {
        /// A list of [`FrontPerMineTotals`]s
        front_totals: Vec<FrontPerMineTotals>,
    }
    impl AllFrontsPerMineTotals {
        /// The total number of configurations for the given total number of
        /// mines in the combined front.
        pub fn total_count(&self) -> f64 {
            // The count should match for each constituent front, but we don't check
            // The null case is just normalised to 1.0 (I think this is because it's the
            // multiplicative identity)
            self.front_totals
                .get(0)
                .map_or(1.0, |front_total| front_total.total_count())
        }

        pub fn null() -> Self {
            Self {
                front_totals: Vec::new(),
            }
        }

        pub fn singleton(num_mines: usize, total: f64) -> Self {
            Self {
                front_totals: vec![FrontPerMineTotals::singleton(num_mines, total)],
            }
        }

        /// Merge two [`AllFrontsPerMineTotals`]s, by joining them into a single
        /// list and performing the necessary cross-multiplication.
        pub fn join_with(&self, other: &Self) -> Self {
            Self {
                front_totals: self
                    .front_totals
                    .iter()
                    .map(|f| f.multiply(other.total_count()))
                    .chain(
                        other
                            .front_totals
                            .iter()
                            .map(|f| f.multiply(self.total_count())),
                    )
                    .collect(),
            }
        }

        /// Sum a list of [`AllFrontsPerMineTotals`]s on a per-constituent-front
        /// basis.
        pub fn sum(front_sets: &[Self]) -> Self {
            if front_sets.is_empty() {
                return Self::null();
            }
            Self {
                front_totals: {
                    let mut results = vec![];
                    for i in 0..front_sets
                        .iter()
                        .map(|set| set.front_totals.len())
                        .min()
                        .expect("Already validated that there is at least one element")
                    {
                        let mut el = vec![];
                        for front in front_sets {
                            el.push(&front.front_totals[i]);
                        }
                        results.push(FrontPerMineTotals::sum(el.into_iter()));
                    }
                    results
                },
            }
        }
    }

    /// A representation of a combinatorial fusing of multiple fronts/tallies.
    /// Essentially, track (total number of mines in the combined front) -> (for
    /// each front (total number of mines in the constituent front) -> (total
    /// number of configurations for that number of mines))
    struct CombinedFront {
        /// A mapping of (total number of mines in the combined front) -> an
        /// [`AllFrontsPerMineTotals`]
        totals: HashMap<usize, AllFrontsPerMineTotals>,
    }
    impl CombinedFront {
        /// Returns the minimum and maximum number of mines in the combined
        /// front.
        ///
        /// If this `CombinedFront` does not contain *any* elements (should
        /// never be true as creating a null front adds an empty element),
        /// returns `(usize::MAX, 0)`.
        pub fn min_max_mines(&self) -> (usize, usize) {
            self.totals
                .keys()
                .fold((usize::MAX, 0), |(lowest, highest), &next| {
                    (min(lowest, next), max(highest, next))
                })
        }

        /// Create an 'empty' combined front.
        pub fn null() -> Self {
            Self {
                totals: [(0, AllFrontsPerMineTotals::null())].into(),
            }
        }

        /// Build a starter combined front using known counts for each number of
        /// mines.
        pub fn from_counts_per_num_mines(
            mines_with_count: impl Iterator<Item = (usize, f64)>,
        ) -> Self {
            Self {
                totals: mines_with_count
                    .map(|(num_mines, total)| {
                        (
                            num_mines,
                            AllFrontsPerMineTotals::singleton(num_mines, total),
                        )
                    })
                    .collect(),
            }
        }

        /// Build a starter combined front from a [`FrontTally`].
        pub fn from_tally<T: Cell + ?Sized>(tally: &FrontTally<'_, '_, T>) -> Self {
            Self::from_counts_per_num_mines(
                tally
                    .iter()
                    .map(|(num_mines, subtally)| (num_mines, subtally.total)),
            )
        }

        /// Build a starter combined front to represent the 'uncharted cells'
        /// region.
        pub fn for_other(
            min_mines: usize,
            max_mines: usize,
            relative_likelihood: impl Fn(usize) -> f64,
        ) -> Self {
            Self::from_counts_per_num_mines(
                (min_mines..=max_mines).map(|n| (n, relative_likelihood(n))),
            )
        }

        /// Combine two `CombinedFront`s. The two `remaining_mines` parameters
        /// represent the total remaining mines available in all fronts yet to
        /// be combined (excluding `other`). This helps avoid computing
        /// combinations which have a total number of mines that can never
        /// occur. This is also how we converge to a single total number of
        /// mines upon combining all fronts. `at_large_mines` represents the
        /// total number of mines left to be placed.
        pub fn join_with(
            &self,
            other: &Self,
            min_remaining_mines: usize,
            max_remaining_mines: usize,
            at_large_mines: usize,
        ) -> Self {
            let cross_entry = |((a_num_mines, a_fronts), (b_num_mines, b_fronts)): (
                (&usize, &AllFrontsPerMineTotals),
                (&usize, &AllFrontsPerMineTotals),
            )| {
                let combined_mines = a_num_mines + b_num_mines;
                let min_mines_at_end = combined_mines + min_remaining_mines;
                let max_mines_at_end = combined_mines + max_remaining_mines;
                if min_mines_at_end > at_large_mines
                    || max_mines_at_end < at_large_mines
                {
                    None
                } else {
                    Some((combined_mines, a_fronts.join_with(b_fronts)))
                }
            };

            let cross_entries = self
                .totals
                .iter()
                .cartesian_product(other.totals.iter())
                .filter_map(cross_entry);

            let new_totals = map_reduce(cross_entries, once, |vals| {
                AllFrontsPerMineTotals::sum(&vals)
            });
            Self {
                totals: new_totals,
            }
        }

        /// Once all fronts are combined, unwrap the data and return the
        /// underlying counts corresponding to each front.
        pub fn collapse(self) -> impl Iterator<Item = HashMap<usize, f64>> {
            assert_eq!(self.totals.len(), 1);
            let item = peek(self.totals.into_iter());
            item.1.front_totals.into_iter().map(|e| e.totals)
        }
    }

    let (min_tallied_mines, max_tallied_mines) = possible_mine_limits(tallies.iter());
    let min_other_mines = at_large_mines.saturating_sub(max_tallied_mines);
    // `min_tallied_mines` known to be <= `at_large_mines` due to
    // `check_count_consistency()`
    let max_other_mines = min(at_large_mines - min_tallied_mines, num_uncharted_cells);

    let relative_likelihood = |num_free_mines: usize| {
        discrete_relative_likelihood(
            num_uncharted_cells,
            num_free_mines,
            max_other_mines,
        )
        .expect(concat!(
            "num_free_mines and max_other_mines should always",
            " be <= num_uncharted_cells",
        ))
    };

    let all_fronts = tallies
        .iter()
        .map(|t| CombinedFront::from_tally(&t))
        .chain(once(CombinedFront::for_other(
            min_other_mines,
            max_other_mines,
            relative_likelihood,
        )))
        .collect_vec();
    let (mut min_remaining_mines, mut max_remaining_mines) = {
        let (mins, maxs): (Vec<_>, Vec<_>) =
            all_fronts.iter().map(|f| f.min_max_mines()).unzip();
        (
            mins.into_iter().sum::<usize>(),
            maxs.into_iter().sum::<usize>(),
        )
    };
    let mut combined = CombinedFront::null();
    for f in all_fronts {
        // Note that it's only correct to use min/max mines in this way before the front
        // has been combined or modified.
        let (front_min, front_max) = f.min_max_mines();
        min_remaining_mines -= front_min;
        max_remaining_mines -= front_max;
        combined = combined.join_with(
            &f,
            min_remaining_mines,
            max_remaining_mines,
            at_large_mines,
        );
    }

    let front_totals = combined.collapse().collect_vec();
    let (uncharted_total, front_totals) = front_totals
        .split_last()
        .expect("Should always get at least one total out of collapse");

    // Update tallies with adjusted weights
    for (tally, front_total) in tallies.iter_mut().zip(front_totals) {
        tally.update_weights(front_total);
    }

    FrontTally::for_other(num_uncharted_cells, uncharted_total)
}

/// Return the total minimum and maximum possible number of mines across all
/// tallied fronts. Returns (min, max).
fn possible_mine_limits<'a, T: Cell + ?Sized + 'a>(
    tallies: impl Iterator<Item = &'a FrontTally<'a, 'a, T>>,
) -> (usize, usize) {
    tallies
        .map(|tally| (tally.min_mines(), tally.max_mines()))
        .reduce(|(min, max), (tmin, tmax)| (min + tmin, max + tmax))
        .unwrap_or((0, 0))
}

/// Given binomial probability (*p*, *k*, *n*) -> *p*^*k* * (1 - *p*)^(*n* -
/// *k*), return binom_prob(*p*, *k*, *n*) / binom_prob(*p*, *k0*, *n*).
///
/// Note that *n* isn't actually needed! This is because we're calculating a
/// per-configuration weight, and in a true binomial distribution we'd then
/// multiply by `comb(n, k)` - however, we've effectively done that already with
/// the enumeration and tallying phase.
fn nondiscrete_relative_likelihood(p: f64, k: f64, k0: f64) -> Result<f64, Error> {
    if (0.0..=1.0).contains(&p) {
        Ok((p / (1.0 - p)).powf(k - k0))
    } else {
        Err("p must be in [0, 1]")
    }
}

/// Return `comb(n, k) / comb(n, k0)`.
fn discrete_relative_likelihood(n: usize, k: usize, k0: usize) -> Result<f64, Error> {
    if k > n || k0 > n {
        Err("k, k0 must be in [0, n]")
    } else {
        Ok(fact_div(k0, k) * fact_div(n - k0, n - k))
    }
}

/// A meta-cell that represents all the 'other' cells on the board that aren't
/// explicitly mentioned in a rule. See `expand_cells()`.
#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
struct UnchartedCell {
    /// The number of 'other' cells.
    pub len: usize,
}
impl UnchartedCell {
    pub fn new(len: usize) -> Self {
        Self {
            len,
        }
    }
}

/// A meta-tally to represent when all 'other' cells are uncounted and assumed
/// to have a fixed chance of being a mine.
struct FixedProbTally {
    p: f64,
}
impl FixedProbTally {
    pub fn new(p: f64) -> Self {
        Self {
            p,
        }
    }

    pub fn collapse<'arena, 'cell: 'arena, T: Cell + ?Sized + 'cell>(
        &self,
    ) -> impl Iterator<Item = CollapseResult<'arena, 'cell, T>> {
        once((Either::Right(UnchartedCell::new(1)), self.p))
    }
}

type ExpandResult<'cell, T> = (&'cell T, f64);

/// Back-convert the expected values for all super-cells into per-cell
/// probabilities for each cell.
fn expand_cells<'arena, 'cell: 'arena, T: Cell + ?Sized>(
    cell_probs: impl Iterator<Item = CollapseResult<'arena, 'cell, T>> + 'arena,
    other_tag: &'cell T,
) -> impl Iterator<Item = (&'cell T, f64)> + 'arena {
    struct Iter<
        'arena,
        'cell: 'arena,
        T: Hash + Eq + ?Sized,
        I: Iterator<Item = CollapseResult<'arena, 'cell, T>>,
    > {
        cell_probs: I,
        inner: Either<
            <HashSet<&'cell T> as IntoIterator>::IntoIter,
            <Option<(&'cell T, f64)> as IntoIterator>::IntoIter,
        >,
        p: f64,
        other_tag: &'cell T,
    }
    impl<
            'arena,
            'cell,
            T: Hash + Eq + ?Sized,
            I: Iterator<Item = CollapseResult<'arena, 'cell, T>>,
        > Iterator for Iter<'arena, 'cell, T, I>
    {
        type Item = ExpandResult<'cell, T>;

        fn next(&mut self) -> Option<Self::Item> {
            match self.inner {
                Either::Left(ref mut inner) => inner.next().map(|t| (t, self.p)),
                Either::Right(ref mut inner) => inner.next(),
            }
            .or_else(|| {
                let (super_cell, p) = self.cell_probs.next()?;
                self.p = p;
                self.inner = match super_cell {
                    Either::Left(cells) => Either::Left((*cells).clone().into_iter()),
                    Either::Right(uncharted) => {
                        Either::Right(
                            // Skip the "other" cells if there aren't any - otherwise,
                            // include exactly one entry.
                            if uncharted.len != 0 {
                                Some((self.other_tag, self.p / (uncharted.len as f64)))
                            } else {
                                None
                            }
                            .into_iter(),
                        )
                    },
                };
                self.next()
            })
        }
    }
    Iter {
        cell_probs,
        inner: Either::Right(None.into_iter()),
        p: 0.0,
        other_tag,
    }
}