problemreductions/models/misc/
string_to_string_correction.rs

1//! String-to-String Correction problem implementation.
2//!
3//! Given a source string `s` and a target string `t` over a finite alphabet,
4//! and a bound `K`, the problem asks whether `t` can be derived from `s`
5//! using at most `K` operations, where each operation is either a deletion
6//! of a character or a swap of two adjacent characters.
7//!
8//! The configuration is a vector of length `K`, where each entry encodes one
9//! operation. For a source of length `n`, each entry is in `{0, ..., 2n}`:
10//! - `0..current_len` → delete the character at that index
11//! - `current_len..2n` → swap the character at position `value - current_len`
12//!   with its right neighbor
13//! - `2n` → no-op (skip this operation slot)
14//!
15//! This problem is NP-complete (Wagner, 1975).
16
17use crate::registry::{CreateSpec, ProblemSchemaEntry};
18use crate::traits::Problem;
19use serde::{Deserialize, Serialize};
20
21inventory::submit! {
22    ProblemSchemaEntry {
23        name: "StringToStringCorrection",
24        display_name: "String-to-String Correction",
25        aliases: &[],
26        dimensions: &[],
27        category: crate::registry::ProblemCategory::Misc,
28        module_path: module_path!(),
29        description: "Derive target string from source using at most K deletions and adjacent swaps",
30        fields: StringToStringCorrectionCreateSpec::FIELDS,
31    }
32}
33
34/// The String-to-String Correction problem.
35///
36/// Given an alphabet of size `a`, a source string `s` over `{0, ..., a-1}`,
37/// a target string `t` over the same alphabet, and a bound `K`, determine
38/// whether `t` can be obtained from `s` by applying at most `K` operations,
39/// where each operation is either a character deletion or a swap of two
40/// adjacent characters.
41///
42/// # Representation
43///
44/// The configuration is a vector of length `K`. For a source string of
45/// length `n`, each entry is in `{0, ..., 2n}`:
46/// - Values `0..current_len` delete the character at that index in the
47///   current working string.
48/// - Values `current_len..2n` swap the character at position
49///   `value - current_len` with its right neighbor.
50/// - Value `2n` is a no-op (skip this slot).
51///
52/// The domain size per slot is fixed at `2n + 1` regardless of how
53/// deletions shorten the working string; as the working string shrinks,
54/// some encodings that were valid before may become invalid.
55///
56/// # Example
57///
58/// ```
59/// use problemreductions::models::misc::StringToStringCorrection;
60/// use problemreductions::{Problem, BruteForce};
61///
62/// // source = [0,1,2,3,1,0], target = [0,1,3,2,1], bound = 2
63/// let problem = StringToStringCorrection::new(4, vec![0,1,2,3,1,0], vec![0,1,3,2,1], 2);
64/// let solver = BruteForce::new();
65/// let solution = solver.solve(&problem).unwrap();
66/// assert!(solution.is_some());
67/// ```
68#[derive(Debug, Clone, Serialize, Deserialize)]
69pub struct StringToStringCorrection {
70    alphabet_size: usize,
71    source: Vec<usize>,
72    target: Vec<usize>,
73    bound: usize,
74}
75
76#[derive(Debug, Deserialize, crate::CreateSpec)]
77struct StringToStringCorrectionCreateSpec {
78    /// Optional alphabet size; omitted values are inferred from both strings.
79    alphabet_size: Option<usize>,
80    /// Source string.
81    #[create(codec = "comma-separated")]
82    source_string: Vec<usize>,
83    /// Target string.
84    #[create(codec = "comma-separated")]
85    target_string: Vec<usize>,
86    /// Maximum number of correction operations.
87    bound: usize,
88}
89
90impl TryFrom<StringToStringCorrectionCreateSpec> for StringToStringCorrection {
91    type Error = crate::registry::ConstructionError;
92
93    fn try_from(spec: StringToStringCorrectionCreateSpec) -> Result<Self, Self::Error> {
94        let inferred_alphabet_size = spec
95            .source_string
96            .iter()
97            .chain(&spec.target_string)
98            .copied()
99            .max()
100            .map(|symbol| {
101                symbol
102                    .checked_add(1)
103                    .ok_or_else(|| "inferred alphabet size overflows usize".to_string())
104            })
105            .transpose()?
106            .unwrap_or(0);
107        let alphabet_size = spec.alphabet_size.unwrap_or(inferred_alphabet_size);
108        if alphabet_size < inferred_alphabet_size {
109            return Err(format!(
110                "alphabet size {alphabet_size} is smaller than inferred alphabet size {inferred_alphabet_size}"
111            ).into());
112        }
113        if alphabet_size == 0 && (!spec.source_string.is_empty() || !spec.target_string.is_empty())
114        {
115            return Err("alphabet size must be positive when either string is non-empty".into());
116        }
117
118        Ok(Self {
119            alphabet_size,
120            source: spec.source_string,
121            target: spec.target_string,
122            bound: spec.bound,
123        })
124    }
125}
126
127impl StringToStringCorrection {
128    /// Create a new StringToStringCorrection instance.
129    ///
130    /// # Panics
131    ///
132    /// Panics if `alphabet_size` is 0 when the source or target string is
133    /// non-empty, or if any symbol in `source` or `target` is
134    /// `>= alphabet_size`.
135    pub fn new(alphabet_size: usize, source: Vec<usize>, target: Vec<usize>, bound: usize) -> Self {
136        assert!(
137            alphabet_size > 0 || (source.is_empty() && target.is_empty()),
138            "alphabet_size must be > 0 when source or target is non-empty"
139        );
140        assert!(
141            source.iter().all(|&s| s < alphabet_size),
142            "all source symbols must be < alphabet_size"
143        );
144        assert!(
145            target.iter().all(|&s| s < alphabet_size),
146            "all target symbols must be < alphabet_size"
147        );
148        Self {
149            alphabet_size,
150            source,
151            target,
152            bound,
153        }
154    }
155
156    /// Returns the alphabet size.
157    pub fn alphabet_size(&self) -> usize {
158        self.alphabet_size
159    }
160
161    /// Returns the source string.
162    pub fn source(&self) -> &[usize] {
163        &self.source
164    }
165
166    /// Returns the target string.
167    pub fn target(&self) -> &[usize] {
168        &self.target
169    }
170
171    /// Returns the operation bound.
172    pub fn bound(&self) -> usize {
173        self.bound
174    }
175
176    /// Returns the length of the source string.
177    pub fn source_length(&self) -> usize {
178        self.source.len()
179    }
180
181    /// Returns the length of the target string.
182    pub fn target_length(&self) -> usize {
183        self.target.len()
184    }
185}
186
187impl Problem for StringToStringCorrection {
188    const NAME: &'static str = "StringToStringCorrection";
189    type Solution = Vec<usize>;
190    type Value = crate::types::Or;
191
192    crate::problem_parameters![("bound", bound), ("source_length", source_length),];
193
194    fn variant() -> Vec<(&'static str, &'static str)> {
195        crate::variant_params![]
196    }
197
198    fn evaluate(
199        &self,
200        config: &Self::Solution,
201    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
202        Ok({
203            crate::types::Or({
204                if config.len() != self.bound {
205                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
206                        "edit-program length does not match the operation bound".into(),
207                    ));
208                }
209                if self.target.len() > self.source.len()
210                    || self.target.len() < self.source.len().saturating_sub(self.bound)
211                {
212                    return Ok(crate::types::Or(false));
213                }
214                let n = self.source.len();
215                let domain = 2 * n + 1;
216                if config.iter().any(|&v| v >= domain) {
217                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
218                        "edit program contains an out-of-range operation".into(),
219                    ));
220                }
221                let noop = 2 * n;
222                let mut working = self.source.clone();
223                for &op in config {
224                    if op == noop {
225                        // no-op
226                        continue;
227                    }
228                    let current_len = working.len();
229                    if op < current_len {
230                        // delete at index op
231                        working.remove(op);
232                    } else {
233                        let swap_pos = op - current_len;
234                        if swap_pos + 1 < current_len {
235                            working.swap(swap_pos, swap_pos + 1);
236                        } else {
237                            // invalid operation for current string state
238                            return Ok(crate::types::Or(false));
239                        }
240                    }
241                }
242                working == self.target
243            })
244        })
245    }
246}
247
248impl crate::solvers::BruteForceProblem for StringToStringCorrection {
249    fn dimensions(&self) -> Vec<usize> {
250        vec![2 * self.source.len() + 1; self.bound]
251    }
252}
253
254crate::declare_variants! {
255    default StringToStringCorrection => "(2 * source_length + 1) ^ bound" create StringToStringCorrectionCreateSpec,
256}
257
258crate::register_brute_force! {
259    StringToStringCorrection,
260}
261
262#[cfg(feature = "example-db")]
263pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
264    vec![crate::example_db::specs::ModelExampleSpec {
265        id: "string_to_string_correction",
266        // source has length 6. Domain = 2*6+1 = 13. No-op = 12.
267        // First operation: swap at positions 2,3 → value = 6 + 2 = 8
268        // Second operation: delete at position 5
269        instance: Box::new(StringToStringCorrection::new(
270            4,
271            vec![0, 1, 2, 3, 1, 0],
272            vec![0, 1, 3, 2, 1],
273            2,
274        )),
275        optimal_config: serde_json::json!(vec![8, 5]),
276        optimal_value: serde_json::json!(true),
277    }]
278}
279
280#[cfg(test)]
281#[path = "../../unit_tests/models/misc/string_to_string_correction.rs"]
282mod tests;
problemreductions/models/misc/string_to_string_correction.rs

problemreductions/models/misc/
string_to_string_correction.rs
