problemreductions/models/misc/
paintshop.rs

1//! Paint Shop problem implementation.
2//!
3//! In the Paint Shop problem, we have a sequence of cars to paint.
4//! Each car appears exactly twice in the sequence and must be painted
5//! one color at its first occurrence and another at its second.
6//! The goal is to minimize color switches between adjacent positions.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Min;
11use serde::{Deserialize, Serialize};
12use std::collections::{HashMap, HashSet};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "PaintShop",
17        display_name: "Paint Shop",
18        aliases: &[],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Misc,
21        module_path: module_path!(),
22        description: "Minimize color changes in paint shop sequence",
23        fields: &[
24            FieldInfo { name: "sequence", type_name: "Vec<String>", description: "Car labels (each must appear exactly twice)" },
25        ],
26    }
27}
28
29/// The Paint Shop problem.
30///
31/// Given a sequence where each car appears exactly twice, assign colors
32/// (0 or 1) to each car to minimize color switches in the sequence.
33///
34/// # Example
35///
36/// ```
37/// use problemreductions::models::misc::PaintShop;
38/// use problemreductions::{Problem, BruteForce};
39///
40/// // Sequence: a, b, a, c, c, b
41/// let problem = PaintShop::new(vec!["a", "b", "a", "c", "c", "b"]);
42///
43/// let solver = BruteForce::new();
44/// let solutions = solver.find_all_witnesses(&problem).unwrap();
45///
46/// // The minimum number of color switches
47/// for sol in &solutions {
48///     let switches = problem.count_switches(sol).unwrap();
49///     println!("Switches: {}", switches);
50/// }
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct PaintShop {
54    /// The sequence of car labels (as indices into unique cars).
55    sequence_indices: Vec<usize>,
56    /// Original car labels.
57    car_labels: Vec<String>,
58    /// Which positions are the first occurrence of each car.
59    is_first: Vec<bool>,
60    /// Number of unique cars.
61    num_cars: usize,
62}
63
64impl PaintShop {
65    /// Create a new Paint Shop problem from string labels.
66    ///
67    /// Each element in the sequence must appear exactly twice.
68    pub fn new<S: AsRef<str>>(sequence: Vec<S>) -> Self {
69        let sequence: Vec<String> = sequence.iter().map(|s| s.as_ref().to_string()).collect();
70        Self::from_strings(sequence)
71    }
72
73    /// Create from a vector of strings.
74    pub fn from_strings(sequence: Vec<String>) -> Self {
75        // Build car-to-index mapping and count occurrences
76        let mut car_count: HashMap<String, usize> = HashMap::new();
77        let mut car_to_index: HashMap<String, usize> = HashMap::new();
78        let mut car_labels: Vec<String> = Vec::new();
79
80        for item in &sequence {
81            let count = car_count.entry(item.clone()).or_insert(0);
82            if *count == 0 {
83                car_to_index.insert(item.clone(), car_labels.len());
84                car_labels.push(item.clone());
85            }
86            *count += 1;
87        }
88
89        // Verify each car appears exactly twice
90        for (car, count) in &car_count {
91            assert_eq!(
92                *count, 2,
93                "Each car must appear exactly twice, but '{}' appears {} times",
94                car, count
95            );
96        }
97
98        // Convert sequence to indices
99        let sequence_indices: Vec<usize> = sequence.iter().map(|item| car_to_index[item]).collect();
100
101        // Determine which positions are first occurrences
102        let mut seen: HashSet<usize> = HashSet::new();
103        let is_first: Vec<bool> = sequence_indices
104            .iter()
105            .map(|&idx| seen.insert(idx))
106            .collect();
107
108        let num_cars = car_labels.len();
109
110        Self {
111            sequence_indices,
112            car_labels,
113            is_first,
114            num_cars,
115        }
116    }
117
118    /// Get the sequence length.
119    pub fn sequence_len(&self) -> usize {
120        self.sequence_indices.len()
121    }
122
123    /// Get the sequence length (alias for `sequence_len()`).
124    pub fn num_sequence(&self) -> usize {
125        self.sequence_len()
126    }
127
128    /// Get the number of unique cars.
129    pub fn num_cars(&self) -> usize {
130        self.num_cars
131    }
132
133    /// Get the car labels.
134    pub fn car_labels(&self) -> &[String] {
135        &self.car_labels
136    }
137
138    /// Get the sequence as car indices.
139    pub fn sequence_indices(&self) -> &[usize] {
140        &self.sequence_indices
141    }
142
143    /// Get whether each position is the first occurrence of its car.
144    pub fn is_first(&self) -> &[bool] {
145        &self.is_first
146    }
147
148    /// Get the coloring of the sequence from a configuration.
149    ///
150    /// Config assigns a color (0 or 1) to each car for its first occurrence.
151    /// The second occurrence gets the opposite color.
152    pub fn get_coloring(
153        &self,
154        config: &[bool],
155    ) -> Result<Vec<bool>, crate::traits::EvaluationError> {
156        if config.len() != self.num_cars {
157            return Err(crate::traits::EvaluationError::InvalidConfiguration(
158                "paint assignment length does not match the cars".into(),
159            ));
160        }
161        Ok(self
162            .sequence_indices
163            .iter()
164            .enumerate()
165            .map(|(i, &car_idx)| {
166                let first_color = config[car_idx];
167                if self.is_first[i] {
168                    first_color
169                } else {
170                    !first_color // Opposite color for second occurrence
171                }
172            })
173            .collect())
174    }
175
176    /// Count the number of color switches in the sequence.
177    pub fn count_switches(&self, config: &[bool]) -> Result<i64, crate::traits::EvaluationError> {
178        let coloring = self.get_coloring(config)?;
179        let count = coloring.windows(2).filter(|w| w[0] != w[1]).count();
180        i64::try_from(count).map_err(|_| {
181            crate::traits::EvaluationError::IntegerOverflow(
182                "converting paint-switch count to i64".into(),
183            )
184        })
185    }
186}
187
188/// Count color switches in a painted sequence.
189#[cfg(test)]
190pub(crate) fn count_paint_switches(coloring: &[bool]) -> usize {
191    coloring.windows(2).filter(|w| w[0] != w[1]).count()
192}
193
194impl Problem for PaintShop {
195    const NAME: &'static str = "PaintShop";
196    type Solution = Vec<bool>;
197    type Value = Min<i64>;
198
199    crate::problem_parameters![("num_cars", num_cars), ("num_sequence", num_sequence),];
200
201    fn evaluate(
202        &self,
203        config: &Self::Solution,
204    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
205        Ok({
206            // All configurations are valid (no hard constraints).
207            Min(Some(self.count_switches(config)?))
208        })
209    }
210
211    fn variant() -> Vec<(&'static str, &'static str)> {
212        crate::variant_params![]
213    }
214}
215
216impl crate::solvers::BruteForceProblem for PaintShop {
217    fn dimensions(&self) -> Vec<usize> {
218        vec![2; self.num_cars]
219    }
220}
221
222crate::declare_variants! {
223    default PaintShop => "2^num_cars",
224}
225
226crate::register_brute_force! {
227    PaintShop decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
228}
229
230#[cfg(feature = "example-db")]
231pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
232    vec![crate::example_db::specs::ModelExampleSpec {
233        id: "paintshop",
234        instance: Box::new(PaintShop::new(vec!["A", "B", "A", "C", "B", "C"])),
235        optimal_config: serde_json::json!(vec![false, false, true]),
236        optimal_value: serde_json::json!(2),
237    }]
238}
239
240#[cfg(test)]
241#[path = "../../unit_tests/models/misc/paintshop.rs"]
242mod tests;
problemreductions/models/misc/paintshop.rs

problemreductions/models/misc/
paintshop.rs
