problemreductions/solvers/
brute_force.rs

1//! Registered brute-force reference solver.
2
3use std::any::Any;
4
5use crate::solvers::SolveError;
6use crate::traits::Problem;
7use crate::types::{Aggregate, SolutionAggregate};
8
9type CartesianWitness<P> = Option<(<P as Problem>::Solution, <P as Problem>::Value)>;
10
11#[doc(hidden)]
12pub type BruteForceDimensionsFn = fn(&dyn Any) -> Vec<usize>;
13#[doc(hidden)]
14pub type BruteForceSolveFn =
15    fn(&dyn Any) -> Result<Option<(serde_json::Value, String)>, SolveError>;
16#[doc(hidden)]
17pub type BruteForceSolveTypedFn = fn(&dyn Any) -> Result<Option<Box<dyn Any>>, SolveError>;
18#[doc(hidden)]
19pub type BruteForceSolveTypedWithWitnessesFn = fn(&dyn Any) -> Result<Box<dyn Any>, SolveError>;
20
21/// Type-erased registration for one finite Cartesian reference solver.
22#[derive(Debug)]
23#[doc(hidden)]
24pub struct BruteForceRegistration {
25    pub source_name: &'static str,
26    pub source_variant_fn: fn() -> Vec<(&'static str, &'static str)>,
27    pub dimensions_fn: BruteForceDimensionsFn,
28    pub solve_fn: BruteForceSolveFn,
29    pub solve_typed_fn: BruteForceSolveTypedFn,
30    pub solve_typed_with_witnesses_fn: BruteForceSolveTypedWithWitnessesFn,
31}
32
33inventory::collect!(BruteForceRegistration);
34
35/// A problem with a finite Cartesian coordinate space for reference solving.
36pub trait BruteForceProblem: Problem {
37    /// Cardinality of each coordinate in the brute-force search space.
38    fn dimensions(&self) -> Vec<usize>;
39
40    /// Number of coordinates in the brute-force search space.
41    fn num_variables(&self) -> usize {
42        self.dimensions().len()
43    }
44}
45
46pub(crate) struct CartesianIndices {
47    dimensions: Vec<usize>,
48    current: Option<Vec<usize>>,
49    remaining: usize,
50}
51
52impl CartesianIndices {
53    pub(crate) fn new(dimensions: Vec<usize>) -> Result<Self, SolveError> {
54        let total = if dimensions.is_empty() {
55            1
56        } else if dimensions.contains(&0) {
57            0
58        } else {
59            dimensions.iter().try_fold(1usize, |total, &dimension| {
60                total
61                    .checked_mul(dimension)
62                    .ok_or_else(|| SolveError::SearchSpaceOverflow(dimensions.clone()))
63            })?
64        };
65        Ok(Self {
66            current: (total != 0).then(|| vec![0; dimensions.len()]),
67            dimensions,
68            remaining: total,
69        })
70    }
71}
72
73impl Iterator for CartesianIndices {
74    type Item = Vec<usize>;
75
76    fn next(&mut self) -> Option<Self::Item> {
77        let current = self.current.take()?;
78        let mut next = current.clone();
79        for index in (0..self.dimensions.len()).rev() {
80            next[index] += 1;
81            if next[index] < self.dimensions[index] {
82                break;
83            }
84            next[index] = 0;
85        }
86        self.remaining -= 1;
87        if self.remaining != 0 {
88            self.current = Some(next);
89        }
90        Some(current)
91    }
92
93    fn size_hint(&self) -> (usize, Option<usize>) {
94        (self.remaining, Some(self.remaining))
95    }
96}
97
98impl ExactSizeIterator for CartesianIndices {}
99
100/// Exact reference solver for variants with a registered finite enumeration.
101#[derive(Debug, Clone, Default)]
102pub struct BruteForce;
103
104impl BruteForce {
105    /// Create a new brute-force reference solver.
106    pub fn new() -> Self {
107        Self
108    }
109
110    fn registration<P: Problem>(&self) -> Result<&'static BruteForceRegistration, SolveError> {
111        let key = crate::solvers::ExactProblemKey::new(
112            P::NAME,
113            P::variant()
114                .into_iter()
115                .map(|(name, value)| (name.to_string(), value.to_string()))
116                .collect(),
117        );
118        crate::solvers::registry::brute_force_registration(&key)
119            .map_err(SolveError::InvalidRegistry)?
120            .ok_or_else(|| SolveError::MissingRegistration(P::NAME.to_string()))
121    }
122
123    /// Solve a registered finite problem and return one solution when feasible.
124    pub fn solve<P>(&self, problem: &P) -> Result<Option<P::Solution>, SolveError>
125    where
126        P: Problem + 'static,
127        P::Solution: 'static,
128        P::Value: SolutionAggregate + 'static,
129    {
130        let solution = (self.registration::<P>()?.solve_typed_fn)(problem as &dyn Any)?;
131        solution
132            .map(|solution| {
133                solution
134                    .downcast::<P::Solution>()
135                    .map(|value| *value)
136                    .map_err(|_| {
137                        SolveError::RegistrationTypeMismatch(format!(
138                            "{} solution registration returned the wrong type",
139                            P::NAME
140                        ))
141                    })
142            })
143            .transpose()
144    }
145
146    /// Find all witnesses for a registered finite reference solve.
147    pub fn find_all_witnesses<P>(&self, problem: &P) -> Result<Vec<P::Solution>, SolveError>
148    where
149        P: Problem + 'static,
150        P::Solution: 'static,
151        P::Value: SolutionAggregate + 'static,
152    {
153        self.solve_with_witnesses(problem)
154            .map(|(_, witnesses)| witnesses)
155    }
156
157    /// Solve a problem and collect every contributing witness.
158    pub fn solve_with_witnesses<P>(
159        &self,
160        problem: &P,
161    ) -> Result<(P::Value, Vec<P::Solution>), SolveError>
162    where
163        P: Problem + 'static,
164        P::Solution: 'static,
165        P::Value: SolutionAggregate + 'static,
166    {
167        (self.registration::<P>()?.solve_typed_with_witnesses_fn)(problem as &dyn Any)?
168            .downcast::<(P::Value, Vec<P::Solution>)>()
169            .map(|result| *result)
170            .map_err(|_| {
171                SolveError::RegistrationTypeMismatch(format!(
172                    "{} aggregate-and-witness registration returned the wrong type",
173                    P::NAME
174                ))
175            })
176    }
177
178    pub(crate) fn solve_cartesian<P, F>(
179        &self,
180        problem: &P,
181        decode: F,
182    ) -> Result<P::Value, SolveError>
183    where
184        P: BruteForceProblem,
185        P::Value: Aggregate,
186        F: Fn(Vec<usize>) -> P::Solution,
187    {
188        let mut total = P::Value::identity();
189        for indices in CartesianIndices::new(problem.dimensions())? {
190            total = total.combine(problem.evaluate(&decode(indices))?)?;
191            if total.is_absorbing() {
192                break;
193            }
194        }
195        Ok(total)
196    }
197
198    pub(crate) fn solve_with_witnesses_cartesian<P, F>(
199        &self,
200        problem: &P,
201        decode: F,
202    ) -> Result<(P::Value, Vec<P::Solution>), SolveError>
203    where
204        P: BruteForceProblem,
205        P::Value: SolutionAggregate,
206        F: Fn(Vec<usize>) -> P::Solution,
207    {
208        let total = self.solve_cartesian(problem, &decode)?;
209        let mut witnesses = Vec::new();
210        for indices in CartesianIndices::new(problem.dimensions())? {
211            let solution = decode(indices);
212            let value = problem.evaluate(&solution)?;
213            if P::Value::contributes_to_solution(&value, &total) {
214                witnesses.push(solution);
215            }
216        }
217        Ok((total, witnesses))
218    }
219
220    pub(crate) fn find_cartesian<P, F>(
221        &self,
222        problem: &P,
223        decode: F,
224    ) -> Result<CartesianWitness<P>, SolveError>
225    where
226        P: BruteForceProblem,
227        P::Value: SolutionAggregate,
228        F: Fn(Vec<usize>) -> P::Solution,
229    {
230        let total = self.solve_cartesian(problem, &decode)?;
231        for indices in CartesianIndices::new(problem.dimensions())? {
232            let solution = decode(indices);
233            let value = problem.evaluate(&solution)?;
234            if P::Value::contributes_to_solution(&value, &total) {
235                return Ok(Some((solution, value)));
236            }
237        }
238        Ok(None)
239    }
240}
241
242#[cfg(test)]
243#[path = "../unit_tests/solvers/brute_force.rs"]
244mod tests;
problemreductions/solvers/brute_force.rs

problemreductions/solvers/
brute_force.rs
