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)]
53#[serde(try_from = "PaintShopData")]
54pub struct PaintShop {
55    /// The sequence of car labels (as indices into unique cars).
56    sequence_indices: Vec<usize>,
57    /// Original car labels.
58    car_labels: Vec<String>,
59    /// Which positions are the first occurrence of each car.
60    is_first: Vec<bool>,
61    /// Number of unique cars.
62    num_cars: usize,
63}
64
65#[derive(Deserialize)]
66struct PaintShopData {
67    sequence_indices: Vec<usize>,
68    car_labels: Vec<String>,
69}
70
71impl TryFrom<PaintShopData> for PaintShop {
72    type Error = crate::registry::ConstructionError;
73
74    fn try_from(data: PaintShopData) -> Result<Self, Self::Error> {
75        let sequence = data
76            .sequence_indices
77            .into_iter()
78            .map(|index| {
79                data.car_labels.get(index).ok_or_else(|| {
80                    crate::registry::ConstructionError::from(format!(
81                        "car index {index} is outside car_labels"
82                    ))
83                })
84            })
85            .collect::<Result<Vec<_>, _>>()?;
86        Self::try_new(sequence)
87    }
88}
89
90impl PaintShop {
91    /// Create a new Paint Shop problem from string labels.
92    ///
93    /// Each element in the sequence must appear exactly twice.
94    pub fn new<S: AsRef<str>>(sequence: Vec<S>) -> Self {
95        Self::try_new(sequence).unwrap_or_else(|error| panic!("{error}"))
96    }
97
98    fn try_new<S: AsRef<str>>(
99        sequence: Vec<S>,
100    ) -> Result<Self, crate::registry::ConstructionError> {
101        // Build car-to-index mapping and count occurrences
102        let mut car_count: HashMap<&str, usize> = HashMap::new();
103        let mut car_to_index: HashMap<&str, usize> = HashMap::new();
104        let mut car_labels: Vec<String> = Vec::new();
105
106        for item in &sequence {
107            let item = item.as_ref();
108            let count = car_count.entry(item).or_insert(0);
109            if *count == 0 {
110                car_to_index.insert(item, car_labels.len());
111                car_labels.push(item.to_owned());
112            }
113            *count += 1;
114        }
115
116        // Verify each car appears exactly twice
117        for (car, count) in &car_count {
118            if *count != 2 {
119                return Err(format!(
120                    "each car must appear exactly twice, but '{car}' appears {count} times"
121                )
122                .into());
123            }
124        }
125
126        // Convert sequence to indices
127        let sequence_indices: Vec<usize> = sequence
128            .iter()
129            .map(|item| car_to_index[item.as_ref()])
130            .collect();
131
132        // Determine which positions are first occurrences
133        let mut seen: HashSet<usize> = HashSet::new();
134        let is_first: Vec<bool> = sequence_indices
135            .iter()
136            .map(|&idx| seen.insert(idx))
137            .collect();
138
139        let num_cars = car_labels.len();
140
141        Ok(Self {
142            sequence_indices,
143            car_labels,
144            is_first,
145            num_cars,
146        })
147    }
148
149    /// Get the sequence length.
150    pub fn sequence_len(&self) -> usize {
151        self.sequence_indices.len()
152    }
153
154    /// Get the sequence length (alias for `sequence_len()`).
155    pub fn num_sequence(&self) -> usize {
156        self.sequence_len()
157    }
158
159    /// Get the number of unique cars.
160    pub fn num_cars(&self) -> usize {
161        self.num_cars
162    }
163
164    /// Get the car labels.
165    pub fn car_labels(&self) -> &[String] {
166        &self.car_labels
167    }
168
169    /// Get the sequence as car indices.
170    pub fn sequence_indices(&self) -> &[usize] {
171        &self.sequence_indices
172    }
173
174    /// Get whether each position is the first occurrence of its car.
175    pub fn is_first(&self) -> &[bool] {
176        &self.is_first
177    }
178
179    /// Get the coloring of the sequence from a configuration.
180    ///
181    /// Config assigns a color (0 or 1) to each car for its first occurrence.
182    /// The second occurrence gets the opposite color.
183    pub fn get_coloring(
184        &self,
185        config: &[bool],
186    ) -> Result<Vec<bool>, crate::traits::EvaluationError> {
187        if config.len() != self.num_cars {
188            return Err(crate::traits::EvaluationError::InvalidConfiguration(
189                "paint assignment length does not match the cars".into(),
190            ));
191        }
192        Ok(self
193            .sequence_indices
194            .iter()
195            .enumerate()
196            .map(|(i, &car_idx)| {
197                let first_color = config[car_idx];
198                if self.is_first[i] {
199                    first_color
200                } else {
201                    !first_color // Opposite color for second occurrence
202                }
203            })
204            .collect())
205    }
206
207    /// Count the number of color switches in the sequence.
208    pub fn count_switches(&self, config: &[bool]) -> Result<i64, crate::traits::EvaluationError> {
209        let coloring = self.get_coloring(config)?;
210        let count = coloring.windows(2).filter(|w| w[0] != w[1]).count();
211        i64::try_from(count).map_err(|_| {
212            crate::traits::EvaluationError::IntegerOverflow(
213                "converting paint-switch count to i64".into(),
214            )
215        })
216    }
217
218    /// Create from a vector of strings.
219    pub fn from_strings(sequence: Vec<String>) -> Self {
220        Self::new(sequence)
221    }
222}
223
224/// Count color switches in a painted sequence.
225#[cfg(test)]
226pub(crate) fn count_paint_switches(coloring: &[bool]) -> usize {
227    coloring.windows(2).filter(|w| w[0] != w[1]).count()
228}
229
230impl Problem for PaintShop {
231    const NAME: &'static str = "PaintShop";
232    type Solution = Vec<bool>;
233    type Value = Min<i64>;
234
235    crate::problem_parameters![("num_cars", num_cars), ("num_sequence", num_sequence),];
236
237    fn evaluate(
238        &self,
239        config: &Self::Solution,
240    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
241        Ok({
242            // All configurations are valid (no hard constraints).
243            Min(Some(self.count_switches(config)?))
244        })
245    }
246
247    fn variant() -> Vec<(&'static str, &'static str)> {
248        crate::variant_params![]
249    }
250}
251
252impl crate::solvers::BruteForceProblem for PaintShop {
253    fn dimensions(&self) -> Vec<usize> {
254        vec![2; self.num_cars]
255    }
256}
257
258crate::declare_variants! {
259    default PaintShop => "2^num_cars",
260}
261
262crate::register_brute_force! {
263    PaintShop decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
264}
265
266#[cfg(feature = "example-db")]
267pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
268    vec![crate::example_db::specs::ModelExampleSpec {
269        id: "paintshop",
270        instance: Box::new(PaintShop::new(vec!["A", "B", "A", "C", "B", "C"])),
271        optimal_config: serde_json::json!(vec![false, false, true]),
272        optimal_value: serde_json::json!(2),
273    }]
274}
275
276#[cfg(test)]
277#[path = "../../unit_tests/models/misc/paintshop.rs"]
278mod tests;
problemreductions/models/misc/paintshop.rs

problemreductions/models/misc/
paintshop.rs
