problemreductions/models/misc/
integer_expression_membership.rs

1//! Integer Expression Membership problem implementation.
2//!
3//! Given a recursive integer expression tree built from singleton positive integers
4//! combined with union (∪) and Minkowski sum (+) operations, and a target integer K,
5//! decide whether K belongs to the set represented by the expression.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Or;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "IntegerExpressionMembership",
15        display_name: "Integer Expression Membership",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Decide whether a target integer belongs to the set represented by an expression tree over union and Minkowski sum",
21        fields: &[
22            FieldInfo { name: "expression", type_name: "IntExpr", description: "Recursive expression tree" },
23            FieldInfo { name: "target", type_name: "i64", description: "Target integer K" },
24        ],
25    }
26}
27
28/// A recursive integer expression tree.
29///
30/// Represents a set of positive integers built from:
31/// - `Atom(n)`: the singleton set {n}
32/// - `Union(f, g)`: set union F ∪ G
33/// - `Sum(f, g)`: Minkowski sum {m + n : m ∈ F, n ∈ G}
34#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
35pub enum IntExpr {
36    /// Singleton set {n} for a positive integer n.
37    Atom(i64),
38    /// Set union: F ∪ G.
39    Union(Box<IntExpr>, Box<IntExpr>),
40    /// Minkowski sum: {m + n : m ∈ F, n ∈ G}.
41    Sum(Box<IntExpr>, Box<IntExpr>),
42}
43
44impl IntExpr {
45    /// Returns true if all atoms in the expression are positive (> 0).
46    pub fn all_atoms_positive(&self) -> bool {
47        match self {
48            IntExpr::Atom(n) => *n > 0,
49            IntExpr::Union(l, r) | IntExpr::Sum(l, r) => {
50                l.all_atoms_positive() && r.all_atoms_positive()
51            }
52        }
53    }
54
55    /// Count the total number of nodes in the expression tree.
56    pub fn size(&self) -> usize {
57        match self {
58            IntExpr::Atom(_) => 1,
59            IntExpr::Union(l, r) | IntExpr::Sum(l, r) => 1 + l.size() + r.size(),
60        }
61    }
62
63    /// Count the number of Union nodes in the expression tree.
64    pub fn count_union_nodes(&self) -> usize {
65        match self {
66            IntExpr::Atom(_) => 0,
67            IntExpr::Union(l, r) => 1 + l.count_union_nodes() + r.count_union_nodes(),
68            IntExpr::Sum(l, r) => l.count_union_nodes() + r.count_union_nodes(),
69        }
70    }
71
72    /// Count the number of Atom nodes in the expression tree.
73    pub fn count_atoms(&self) -> usize {
74        match self {
75            IntExpr::Atom(_) => 1,
76            IntExpr::Union(l, r) | IntExpr::Sum(l, r) => l.count_atoms() + r.count_atoms(),
77        }
78    }
79
80    /// Compute the depth of the expression tree (0 for a single Atom).
81    pub fn depth(&self) -> usize {
82        match self {
83            IntExpr::Atom(_) => 0,
84            IntExpr::Union(l, r) | IntExpr::Sum(l, r) => 1 + l.depth().max(r.depth()),
85        }
86    }
87
88    /// Evaluate the expression given union choices from config.
89    ///
90    /// `counter` tracks which union node we are at (DFS order).
91    /// Returns `Some(value)` if the config is valid, `None` otherwise.
92    fn evaluate_with_config(&self, config: &[bool], counter: &mut usize) -> Option<i64> {
93        match self {
94            IntExpr::Atom(n) => Some(*n),
95            IntExpr::Union(left, right) => {
96                let idx = *counter;
97                *counter += 1;
98                if idx >= config.len() {
99                    return None;
100                }
101                if config[idx] {
102                    right.evaluate_with_config(config, counter)
103                } else {
104                    left.evaluate_with_config(config, counter)
105                }
106            }
107            IntExpr::Sum(left, right) => {
108                let l = left.evaluate_with_config(config, counter)?;
109                let r = right.evaluate_with_config(config, counter)?;
110                l.checked_add(r)
111            }
112        }
113    }
114}
115
116/// The Integer Expression Membership problem.
117///
118/// Given an integer expression `e` over union (∪) and Minkowski sum (+)
119/// operations on singleton positive integers, and a target integer `K`,
120/// decide whether `K ∈ eval(e)`.
121///
122/// # Configuration
123///
124/// Each Union node has a binary variable (0 = left, 1 = right).
125/// A configuration assigns a branch choice to every Union node in DFS order.
126/// The expression then collapses to a chain of Sum and Atom nodes,
127/// evaluating to a single integer.
128///
129/// # Example
130///
131/// ```
132/// use problemreductions::models::misc::{IntegerExpressionMembership, IntExpr};
133/// use problemreductions::{Problem, BruteForce};
134///
135/// // e = (1 ∪ 4) + (3 ∪ 6) + (2 ∪ 5), target K = 12
136/// let expr = IntExpr::Sum(
137///     Box::new(IntExpr::Sum(
138///         Box::new(IntExpr::Union(
139///             Box::new(IntExpr::Atom(1)),
140///             Box::new(IntExpr::Atom(4)),
141///         )),
142///         Box::new(IntExpr::Union(
143///             Box::new(IntExpr::Atom(3)),
144///             Box::new(IntExpr::Atom(6)),
145///         )),
146///     )),
147///     Box::new(IntExpr::Union(
148///         Box::new(IntExpr::Atom(2)),
149///         Box::new(IntExpr::Atom(5)),
150///     )),
151/// );
152/// let problem = IntegerExpressionMembership::new(expr, 12);
153/// let solver = BruteForce::new();
154/// let solution = solver.solve(&problem).unwrap();
155/// assert!(solution.is_some());
156/// ```
157#[derive(Debug, Clone, Serialize, Deserialize)]
158pub struct IntegerExpressionMembership {
159    /// The recursive expression tree.
160    expression: IntExpr,
161    /// The target integer K.
162    target: i64,
163}
164
165impl IntegerExpressionMembership {
166    /// Create a new IntegerExpressionMembership instance.
167    ///
168    /// # Arguments
169    /// * `expression` - The integer expression tree
170    /// * `target` - The target integer K
171    pub fn new(expression: IntExpr, target: i64) -> Self {
172        assert!(target > 0, "target must be a positive integer (got 0)");
173        assert!(
174            expression.all_atoms_positive(),
175            "all Atom values must be positive (> 0)"
176        );
177        Self { expression, target }
178    }
179
180    /// Returns a reference to the expression tree.
181    pub fn expression(&self) -> &IntExpr {
182        &self.expression
183    }
184
185    /// Returns the target integer K.
186    pub fn target(&self) -> i64 {
187        self.target
188    }
189
190    /// Returns the total number of nodes in the expression tree.
191    pub fn expression_size(&self) -> usize {
192        self.expression.size()
193    }
194
195    /// Returns the number of Union nodes in the expression tree.
196    pub fn num_union_nodes(&self) -> usize {
197        self.expression.count_union_nodes()
198    }
199
200    /// Returns the number of Atom nodes in the expression tree.
201    pub fn num_atoms(&self) -> usize {
202        self.expression.count_atoms()
203    }
204
205    /// Returns the depth of the expression tree.
206    pub fn expression_depth(&self) -> usize {
207        self.expression.depth()
208    }
209
210    /// Evaluate the expression for a given config and return the resulting integer.
211    ///
212    /// Returns `Some(value)` if the config is valid, `None` otherwise.
213    pub fn evaluate_config(&self, config: &[bool]) -> Option<i64> {
214        let mut counter = 0;
215        self.expression.evaluate_with_config(config, &mut counter)
216    }
217}
218
219impl Problem for IntegerExpressionMembership {
220    const NAME: &'static str = "IntegerExpressionMembership";
221    type Solution = Vec<bool>;
222    type Value = Or;
223
224    crate::problem_parameters![("num_union_nodes", num_union_nodes),];
225
226    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
227        Ok({
228            Or({
229                if config.len() != self.num_union_nodes() {
230                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
231                        "union-choice length does not match the expression".into(),
232                    ));
233                }
234                match self.evaluate_config(config) {
235                    Some(value) => value == self.target,
236                    None => false,
237                }
238            })
239        })
240    }
241
242    fn variant() -> Vec<(&'static str, &'static str)> {
243        crate::variant_params![]
244    }
245}
246
247impl crate::solvers::BruteForceProblem for IntegerExpressionMembership {
248    fn dimensions(&self) -> Vec<usize> {
249        vec![2; self.num_union_nodes()]
250    }
251}
252
253crate::declare_variants! {
254    default IntegerExpressionMembership => "2^num_union_nodes",
255}
256
257crate::register_brute_force! {
258    IntegerExpressionMembership decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
259}
260
261#[cfg(feature = "example-db")]
262pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
263    // e = (1 ∪ 4) + (3 ∪ 6) + (2 ∪ 5), K = 12
264    // 3 union nodes → 8 configs. Set = {6, 9, 12, 15}.
265    // Witness: choose right(4), right(6), left(2) → 4+6+2=12, config=[1,1,0]
266    let expr = IntExpr::Sum(
267        Box::new(IntExpr::Sum(
268            Box::new(IntExpr::Union(
269                Box::new(IntExpr::Atom(1)),
270                Box::new(IntExpr::Atom(4)),
271            )),
272            Box::new(IntExpr::Union(
273                Box::new(IntExpr::Atom(3)),
274                Box::new(IntExpr::Atom(6)),
275            )),
276        )),
277        Box::new(IntExpr::Union(
278            Box::new(IntExpr::Atom(2)),
279            Box::new(IntExpr::Atom(5)),
280        )),
281    );
282    vec![crate::example_db::specs::ModelExampleSpec {
283        id: "integer_expression_membership",
284        instance: Box::new(IntegerExpressionMembership::new(expr, 12)),
285        optimal_config: serde_json::json!(vec![true, true, false]),
286        optimal_value: serde_json::json!(true),
287    }]
288}
289
290#[cfg(test)]
291#[path = "../../unit_tests/models/misc/integer_expression_membership.rs"]
292mod tests;
problemreductions/models/misc/integer_expression_membership.rs

problemreductions/models/misc/
integer_expression_membership.rs
