problemreductions/solvers/
brute_force.rs

1//! Brute force solver that enumerates all configurations.
2
3use crate::config::DimsIterator;
4use crate::solvers::Solver;
5use crate::traits::Problem;
6use crate::types::Aggregate;
7
8/// A brute force solver that enumerates all possible configurations.
9///
10/// This solver is exponential in the number of variables but guarantees
11/// finding the full aggregate value and all witness configurations when the
12/// aggregate type supports witnesses.
13#[derive(Debug, Clone, Default)]
14pub struct BruteForce;
15
16impl BruteForce {
17    /// Create a new brute force solver.
18    pub fn new() -> Self {
19        Self
20    }
21
22    /// Find one witness configuration when the aggregate value admits them.
23    pub fn find_witness<P>(&self, problem: &P) -> Option<Vec<usize>>
24    where
25        P: Problem,
26        P::Value: Aggregate,
27    {
28        self.find_all_witnesses(problem).into_iter().next()
29    }
30
31    /// Find all witness configurations for witness-supporting aggregates.
32    pub fn find_all_witnesses<P>(&self, problem: &P) -> Vec<Vec<usize>>
33    where
34        P: Problem,
35        P::Value: Aggregate,
36    {
37        let total = self.solve(problem);
38
39        if !P::Value::supports_witnesses() {
40            return vec![];
41        }
42
43        DimsIterator::new(problem.dims())
44            .filter(|config| {
45                let value = problem.evaluate(config);
46                P::Value::contributes_to_witnesses(&value, &total)
47            })
48            .collect()
49    }
50
51    /// Solve a problem and collect all witness configurations in one passable API.
52    pub fn solve_with_witnesses<P>(&self, problem: &P) -> (P::Value, Vec<Vec<usize>>)
53    where
54        P: Problem,
55        P::Value: Aggregate,
56    {
57        let total = self.solve(problem);
58
59        if !P::Value::supports_witnesses() {
60            return (total, vec![]);
61        }
62
63        let witnesses = DimsIterator::new(problem.dims())
64            .filter(|config| {
65                let value = problem.evaluate(config);
66                P::Value::contributes_to_witnesses(&value, &total)
67            })
68            .collect();
69
70        (total, witnesses)
71    }
72}
73
74impl Solver for BruteForce {
75    fn solve<P>(&self, problem: &P) -> P::Value
76    where
77        P: Problem,
78        P::Value: Aggregate,
79    {
80        DimsIterator::new(problem.dims())
81            .map(|config| problem.evaluate(&config))
82            .fold(P::Value::identity(), P::Value::combine)
83    }
84}
85
86#[cfg(test)]
87#[path = "../unit_tests/solvers/brute_force.rs"]
88mod tests;
problemreductions/solvers/brute_force.rs

problemreductions/solvers/
brute_force.rs
