problemreductions/models/misc/
minimum_register_sufficiency_for_loops.rs

1//! Minimum Register Sufficiency for Loops problem implementation.
2//!
3//! Given a loop of length N and a set of variables, each active during a
4//! contiguous circular arc of timesteps, assign registers to variables
5//! minimizing the number of distinct registers used, such that no two
6//! conflicting (overlapping) variables share the same register.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Min;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinimumRegisterSufficiencyForLoops",
16        display_name: "Minimum Register Sufficiency for Loops",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Assign registers to loop variables minimizing register count, no two conflicting variables share a register",
22        fields: &[
23            FieldInfo { name: "loop_length", type_name: "usize", description: "Loop length N (number of timesteps)" },
24            FieldInfo { name: "variables", type_name: "Vec<(usize, usize)>", description: "Variables as (start_time, duration) circular arcs" },
25        ],
26    }
27}
28
29/// The Minimum Register Sufficiency for Loops problem.
30///
31/// Given a loop of length N (representing N timesteps arranged in a circle)
32/// and a set of variables, each active during a contiguous circular arc of
33/// timesteps specified by (start_time, duration), assign a register index
34/// to each variable such that:
35/// - No two variables with overlapping circular arcs share the same register
36/// - The number of distinct registers used is minimized
37///
38/// This is equivalent to the circular arc graph coloring problem, where each
39/// variable corresponds to a circular arc and registers correspond to colors.
40///
41/// # Representation
42///
43/// Each variable is assigned a register index from `{0, ..., n-1}` where n is
44/// the number of variables. The configuration `config[i]` gives the register
45/// assigned to variable i.
46///
47/// # Example
48///
49/// ```
50/// use problemreductions::models::misc::MinimumRegisterSufficiencyForLoops;
51/// use problemreductions::{Problem, BruteForce, Min};
52///
53/// // 3 variables on a loop of length 6, all pairs conflict
54/// let problem = MinimumRegisterSufficiencyForLoops::new(
55///     6,
56///     vec![(0, 3), (2, 3), (4, 3)],
57/// );
58/// let solver = BruteForce::new();
59/// let solution = solver.solve(&problem).unwrap();
60/// assert!(solution.is_some());
61/// let val = problem.evaluate(&solution.unwrap()).unwrap();
62/// assert_eq!(val, Min(Some(3)));
63/// ```
64#[derive(Debug, Clone, Serialize, Deserialize)]
65#[serde(try_from = "MinimumRegisterSufficiencyForLoopsData")]
66pub struct MinimumRegisterSufficiencyForLoops {
67    /// Loop length N (number of timesteps in the circular loop).
68    loop_length: usize,
69    /// Variables as (start_time, duration) pairs representing circular arcs.
70    variables: Vec<(usize, usize)>,
71}
72
73#[derive(Deserialize)]
74struct MinimumRegisterSufficiencyForLoopsData {
75    loop_length: usize,
76    variables: Vec<(usize, usize)>,
77}
78
79impl TryFrom<MinimumRegisterSufficiencyForLoopsData> for MinimumRegisterSufficiencyForLoops {
80    type Error = crate::registry::ConstructionError;
81    fn try_from(data: MinimumRegisterSufficiencyForLoopsData) -> Result<Self, Self::Error> {
82        Self::try_new(data.loop_length, data.variables)
83    }
84}
85
86impl MinimumRegisterSufficiencyForLoops {
87    /// Create a new Minimum Register Sufficiency for Loops instance.
88    ///
89    /// # Panics
90    ///
91    /// Panics if `loop_length` is zero, if any duration is zero or exceeds
92    /// `loop_length`, or if any `start_time >= loop_length`.
93    pub fn new(loop_length: usize, variables: Vec<(usize, usize)>) -> Self {
94        Self::try_new(loop_length, variables).unwrap_or_else(|error| panic!("{error}"))
95    }
96
97    fn try_new(
98        loop_length: usize,
99        variables: Vec<(usize, usize)>,
100    ) -> Result<Self, crate::registry::ConstructionError> {
101        if loop_length == 0 {
102            return Err("loop_length must be positive".into());
103        }
104        for (i, &(start, dur)) in variables.iter().enumerate() {
105            if start >= loop_length {
106                return Err(format!(
107                    "Variable {} start_time {} >= loop_length {}",
108                    i, start, loop_length
109                )
110                .into());
111            }
112            if dur == 0 || dur > loop_length {
113                return Err(format!(
114                    "Variable {} duration {} must be in [1, {}]",
115                    i, dur, loop_length
116                )
117                .into());
118            }
119        }
120        Ok(Self {
121            loop_length,
122            variables,
123        })
124    }
125
126    /// Get the loop length N.
127    pub fn loop_length(&self) -> usize {
128        self.loop_length
129    }
130
131    /// Get the number of variables.
132    pub fn num_variables(&self) -> usize {
133        self.variables.len()
134    }
135
136    /// Get the variables as (start_time, duration) pairs.
137    pub fn variables(&self) -> &[(usize, usize)] {
138        &self.variables
139    }
140
141    /// Check if two circular arcs overlap.
142    ///
143    /// Arc [s, s+l) mod N covers timesteps {s, s+1, ..., s+l-1} mod N.
144    /// Two arcs overlap iff their covered timestep sets intersect.
145    fn arcs_overlap(s1: usize, l1: usize, s2: usize, l2: usize, n: usize) -> bool {
146        // Use the modular distance check:
147        // Timestep t is in arc [s, s+l) mod N iff (t - s) mod N < l
148        // Two arcs are disjoint iff arc2 fits entirely in the gap of arc1
149        // or arc1 fits entirely in the gap of arc2.
150        // Gap of arc [s, s+l) is [(s+l) mod N, s) with length N-l.
151
152        // If either arc covers the entire loop, they always overlap (if both non-empty)
153        if l1 == n || l2 == n {
154            return true;
155        }
156
157        // Check if arc2 is entirely in the gap of arc1.
158        // Gap of arc1 starts at (s1+l1) % n and has length n-l1.
159        // Arc2 fits in this gap if the "gap distance" of s2 from gap_start
160        // plus l2 <= n - l1.
161        let gap1_start = (s1 + l1) % n;
162        let dist_s2_in_gap1 = (s2 + n - gap1_start) % n;
163        if dist_s2_in_gap1 + l2 <= n - l1 {
164            return false;
165        }
166
167        // Check if arc1 is entirely in the gap of arc2.
168        let gap2_start = (s2 + l2) % n;
169        let dist_s1_in_gap2 = (s1 + n - gap2_start) % n;
170        if dist_s1_in_gap2 + l1 <= n - l2 {
171            return false;
172        }
173
174        true
175    }
176}
177
178impl Problem for MinimumRegisterSufficiencyForLoops {
179    const NAME: &'static str = "MinimumRegisterSufficiencyForLoops";
180    type Solution = Vec<usize>;
181    type Value = Min<i64>;
182
183    crate::problem_parameters![
184        ("loop_length", loop_length),
185        ("num_variables", num_variables),
186    ];
187
188    fn variant() -> Vec<(&'static str, &'static str)> {
189        crate::variant_params![]
190    }
191
192    fn evaluate(
193        &self,
194        config: &Self::Solution,
195    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
196        Ok({
197            let n = self.variables.len();
198            if config.len() != n {
199                return Err(crate::traits::EvaluationError::InvalidConfiguration(
200                    "register assignment length does not match the variables".into(),
201                ));
202            }
203            // Check all register indices are in valid range
204            if config.iter().any(|&register| register >= n) {
205                return Err(crate::traits::EvaluationError::InvalidConfiguration(
206                    "register assignment contains an out-of-range register".into(),
207                ));
208            }
209            // Check for conflicts: no two overlapping variables share a register
210            for i in 0..n {
211                for j in (i + 1)..n {
212                    if config[i] == config[j] {
213                        let (s1, l1) = self.variables[i];
214                        let (s2, l2) = self.variables[j];
215                        if Self::arcs_overlap(s1, l1, s2, l2, self.loop_length) {
216                            return Ok(Min(None));
217                        }
218                    }
219                }
220            }
221
222            // Count distinct registers used
223            let mut used = vec![false; n];
224            for &r in config {
225                used[r] = true;
226            }
227            let count = used.iter().filter(|&&u| u).count();
228            Min(Some(i64::try_from(count).map_err(|_| {
229                crate::traits::EvaluationError::IntegerOverflow(
230                    "converting register count to i64".into(),
231                )
232            })?))
233        })
234    }
235}
236
237impl crate::solvers::BruteForceProblem for MinimumRegisterSufficiencyForLoops {
238    fn dimensions(&self) -> Vec<usize> {
239        let n = self.variables.len();
240        vec![n; n]
241    }
242}
243
244crate::declare_variants! {
245    default MinimumRegisterSufficiencyForLoops => "num_variables ^ num_variables",
246}
247
248crate::register_brute_force! {
249    MinimumRegisterSufficiencyForLoops,
250}
251
252#[cfg(feature = "example-db")]
253pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
254    vec![crate::example_db::specs::ModelExampleSpec {
255        id: "minimum_register_sufficiency_for_loops",
256        // 3 variables on a loop of length 6, all pairs conflict (K3)
257        // Optimal: 3 registers (chromatic number of K3)
258        instance: Box::new(MinimumRegisterSufficiencyForLoops::new(
259            6,
260            vec![(0, 3), (2, 3), (4, 3)],
261        )),
262        optimal_config: serde_json::json!(vec![0, 1, 2]),
263        optimal_value: serde_json::json!(3),
264    }]
265}
266
267#[cfg(test)]
268#[path = "../../unit_tests/models/misc/minimum_register_sufficiency_for_loops.rs"]
269mod tests;
problemreductions/models/misc/minimum_register_sufficiency_for_loops.rs

problemreductions/models/misc/
minimum_register_sufficiency_for_loops.rs
