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}
50
51impl CartesianIndices {
52    pub(crate) fn new(dimensions: Vec<usize>) -> Result<Self, SolveError> {
53        let current = if dimensions.contains(&0) {
54            None
55        } else {
56            let mut current = Vec::new();
57            current.try_reserve_exact(dimensions.len())?;
58            current.resize(dimensions.len(), 0);
59            Some(current)
60        };
61        Ok(Self {
62            current,
63            dimensions,
64        })
65    }
66}
67
68impl Iterator for CartesianIndices {
69    type Item = Vec<usize>;
70
71    fn next(&mut self) -> Option<Self::Item> {
72        let current = self.current.take()?;
73        let mut next = current.clone();
74        for index in (0..self.dimensions.len()).rev() {
75            next[index] += 1;
76            if next[index] < self.dimensions[index] {
77                self.current = Some(next);
78                break;
79            }
80            next[index] = 0;
81        }
82        Some(current)
83    }
84
85    fn size_hint(&self) -> (usize, Option<usize>) {
86        if self.current.is_some() {
87            (1, None)
88        } else {
89            (0, Some(0))
90        }
91    }
92}
93
94/// Exact reference solver for variants with a registered finite enumeration.
95#[derive(Debug, Clone, Default)]
96pub struct BruteForce;
97
98impl BruteForce {
99    /// Create a new brute-force reference solver.
100    pub fn new() -> Self {
101        Self
102    }
103
104    fn registration<P: Problem>(&self) -> Result<&'static BruteForceRegistration, SolveError> {
105        let key = crate::solvers::ExactProblemKey::new(
106            P::NAME,
107            P::variant()
108                .into_iter()
109                .map(|(name, value)| (name.to_string(), value.to_string()))
110                .collect(),
111        );
112        crate::solvers::registry::brute_force_registration(&key)
113            .map_err(SolveError::InvalidRegistry)?
114            .ok_or_else(|| SolveError::MissingRegistration(P::NAME.to_string()))
115    }
116
117    /// Solve a registered finite problem and return one solution when feasible.
118    pub fn solve<P>(&self, problem: &P) -> Result<Option<P::Solution>, SolveError>
119    where
120        P: Problem + 'static,
121        P::Solution: 'static,
122        P::Value: SolutionAggregate + 'static,
123    {
124        let solution = (self.registration::<P>()?.solve_typed_fn)(problem as &dyn Any)?;
125        solution
126            .map(|solution| {
127                solution
128                    .downcast::<P::Solution>()
129                    .map(|value| *value)
130                    .map_err(|_| {
131                        SolveError::RegistrationTypeMismatch(format!(
132                            "{} solution registration returned the wrong type",
133                            P::NAME
134                        ))
135                    })
136            })
137            .transpose()
138    }
139
140    /// Find all witnesses for a registered finite reference solve.
141    pub fn find_all_witnesses<P>(&self, problem: &P) -> Result<Vec<P::Solution>, SolveError>
142    where
143        P: Problem + 'static,
144        P::Solution: 'static,
145        P::Value: SolutionAggregate + 'static,
146    {
147        self.solve_with_witnesses(problem)
148            .map(|(_, witnesses)| witnesses)
149    }
150
151    /// Solve a problem and collect every contributing witness.
152    pub fn solve_with_witnesses<P>(
153        &self,
154        problem: &P,
155    ) -> Result<(P::Value, Vec<P::Solution>), SolveError>
156    where
157        P: Problem + 'static,
158        P::Solution: 'static,
159        P::Value: SolutionAggregate + 'static,
160    {
161        (self.registration::<P>()?.solve_typed_with_witnesses_fn)(problem as &dyn Any)?
162            .downcast::<(P::Value, Vec<P::Solution>)>()
163            .map(|result| *result)
164            .map_err(|_| {
165                SolveError::RegistrationTypeMismatch(format!(
166                    "{} aggregate-and-witness registration returned the wrong type",
167                    P::NAME
168                ))
169            })
170    }
171
172    pub(crate) fn solve_cartesian<P, F>(
173        &self,
174        problem: &P,
175        decode: F,
176    ) -> Result<P::Value, SolveError>
177    where
178        P: BruteForceProblem,
179        P::Value: Aggregate,
180        F: Fn(Vec<usize>) -> P::Solution,
181    {
182        let mut total = P::Value::identity();
183        for indices in CartesianIndices::new(problem.dimensions())? {
184            total = total.combine(problem.evaluate(&decode(indices))?)?;
185            if total.is_absorbing() {
186                break;
187            }
188        }
189        Ok(total)
190    }
191
192    pub(crate) fn solve_with_witnesses_cartesian<P, F>(
193        &self,
194        problem: &P,
195        decode: F,
196    ) -> Result<(P::Value, Vec<P::Solution>), SolveError>
197    where
198        P: BruteForceProblem,
199        P::Value: SolutionAggregate,
200        F: Fn(Vec<usize>) -> P::Solution,
201    {
202        let total = self.solve_cartesian(problem, &decode)?;
203        let mut witnesses = Vec::new();
204        for indices in CartesianIndices::new(problem.dimensions())? {
205            let solution = decode(indices);
206            let value = problem.evaluate(&solution)?;
207            if P::Value::contributes_to_solution(&value, &total) {
208                witnesses.push(solution);
209            }
210        }
211        Ok((total, witnesses))
212    }
213
214    pub(crate) fn find_cartesian<P, F>(
215        &self,
216        problem: &P,
217        decode: F,
218    ) -> Result<CartesianWitness<P>, SolveError>
219    where
220        P: BruteForceProblem,
221        P::Value: SolutionAggregate,
222        F: Fn(Vec<usize>) -> P::Solution,
223    {
224        let total = self.solve_cartesian(problem, &decode)?;
225        for indices in CartesianIndices::new(problem.dimensions())? {
226            let solution = decode(indices);
227            let value = problem.evaluate(&solution)?;
228            if P::Value::contributes_to_solution(&value, &total) {
229                return Ok(Some((solution, value)));
230            }
231        }
232        Ok(None)
233    }
234}
235
236#[cfg(test)]
237#[path = "../unit_tests/solvers/brute_force.rs"]
238mod tests;
problemreductions/solvers/brute_force.rs

problemreductions/solvers/
brute_force.rs
