problemreductions/models/misc/
closest_substring.rs

1//! Closest Substring problem implementation.
2//!
3//! Given a finite alphabet `{0, ..., alphabet_size - 1}`, a list of input
4//! strings (not necessarily of equal length), and a substring length `ell`,
5//! find a center string `c` of length `ell` and one length-`ell` window per
6//! input string that together minimize the maximum Hamming distance from `c`
7//! to any selected window.
8
9use crate::registry::{FieldInfo, ProblemSchemaEntry};
10use crate::traits::Problem;
11use crate::types::Min;
12use serde::{Deserialize, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "ClosestSubstring",
17        display_name: "Closest Substring",
18        aliases: &[],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Misc,
21        module_path: module_path!(),
22        description: "Find a center string of fixed length and one length-ell window per input string that minimize the maximum Hamming distance between the center and any selected window",
23        fields: &[
24            FieldInfo {
25                name: "alphabet_size",
26                type_name: "usize",
27                description: "Size q of the finite alphabet {0, ..., q-1}",
28            },
29            FieldInfo {
30                name: "strings",
31                type_name: "Vec<Vec<usize>>",
32                description: "Input strings s_1, ..., s_n over the alphabet (possibly of different lengths)",
33            },
34            FieldInfo {
35                name: "substring_length",
36                type_name: "usize",
37                description: "Common window length ell; every input string must have length at least substring_length",
38            },
39        ],
40    }
41}
42
43/// The Closest Substring problem.
44///
45/// Given a finite alphabet `Sigma = {0, ..., q - 1}`, `n` input strings
46/// `s_1, ..., s_n` over `Sigma` (not necessarily of equal length), and a
47/// window length `ell` with `ell <= |s_i|` for every `i`, find a center
48/// `c in Sigma^ell` and per-string window start positions `p_i in {0, ..., W_i - 1}`
49/// (where `W_i = |s_i| - ell + 1`) minimizing
50///
51/// `max_{1 <= i <= n} d_H(c, s_i[p_i .. p_i + ell))`,
52///
53/// where `d_H` is the Hamming distance. Every choice in the discrete cube is
54/// syntactically feasible.
55#[derive(Debug, Clone, Serialize)]
56pub struct ClosestSubstring {
57    alphabet_size: usize,
58    strings: Vec<Vec<usize>>,
59    substring_length: usize,
60}
61
62#[derive(Deserialize)]
63struct ClosestSubstringData {
64    alphabet_size: usize,
65    strings: Vec<Vec<usize>>,
66    substring_length: usize,
67}
68
69impl<'de> Deserialize<'de> for ClosestSubstring {
70    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
71    where
72        D: serde::Deserializer<'de>,
73    {
74        let data = ClosestSubstringData::deserialize(deserializer)?;
75        Self::new(data.alphabet_size, data.strings, data.substring_length)
76            .map_err(serde::de::Error::custom)
77    }
78}
79
80impl ClosestSubstring {
81    /// Create a new `ClosestSubstring` instance.
82    ///
83    pub fn new(
84        alphabet_size: usize,
85        strings: Vec<Vec<usize>>,
86        substring_length: usize,
87    ) -> Result<Self, crate::registry::ConstructionError> {
88        if strings.is_empty() {
89            return Err("ClosestSubstring requires at least one input string".into());
90        }
91        if strings.iter().any(|s| s.len() < substring_length) {
92            return Err("substring_length must be <= |s_i| for every input string".into());
93        }
94        if alphabet_size == 0 && substring_length > 0 {
95            return Err("alphabet_size must be > 0 when substring_length > 0".into());
96        }
97        if strings
98            .iter()
99            .flat_map(|s| s.iter())
100            .any(|&symbol| symbol >= alphabet_size)
101        {
102            return Err("input symbols must be less than alphabet_size".into());
103        }
104        substring_length
105            .checked_add(strings.len())
106            .ok_or("configuration length exceeds usize")?;
107        strings
108            .iter()
109            .try_fold(0_usize, |total, string| total.checked_add(string.len()))
110            .ok_or("total input length exceeds usize")?;
111        strings
112            .iter()
113            .map(|string| string.len() - substring_length + 1)
114            .try_fold(0_usize, usize::checked_add)
115            .ok_or("total number of windows exceeds usize")?;
116        strings
117            .iter()
118            .map(|string| string.len() - substring_length + 1)
119            .try_fold(1_usize, usize::checked_mul)
120            .ok_or("window-choice count exceeds usize")?;
121        Ok(Self {
122            alphabet_size,
123            strings,
124            substring_length,
125        })
126    }
127
128    /// Returns the alphabet size `q`.
129    pub fn alphabet_size(&self) -> usize {
130        self.alphabet_size
131    }
132
133    /// Returns the input strings.
134    pub fn strings(&self) -> &[Vec<usize>] {
135        &self.strings
136    }
137
138    /// Returns the number of input strings `n`.
139    pub fn num_strings(&self) -> usize {
140        self.strings.len()
141    }
142
143    /// Returns the common window length `ell`.
144    pub fn substring_length(&self) -> usize {
145        self.substring_length
146    }
147
148    /// Returns the sum of input string lengths.
149    pub fn total_length(&self) -> usize {
150        self.strings.iter().map(|s| s.len()).sum()
151    }
152
153    /// Returns `sum_i W_i`, where `W_i = |s_i| - substring_length + 1`.
154    pub fn total_num_windows(&self) -> usize {
155        self.strings
156            .iter()
157            .map(|s| s.len() - self.substring_length + 1)
158            .sum()
159    }
160
161    /// Returns `prod_i W_i`, the number of distinct window-selection tuples.
162    ///
163    pub fn num_window_choice_product(&self) -> usize {
164        self.strings
165            .iter()
166            .map(|s| s.len() - self.substring_length + 1)
167            .try_fold(1usize, usize::checked_mul)
168            .expect("validated window-choice count must fit usize")
169    }
170}
171
172impl Problem for ClosestSubstring {
173    const NAME: &'static str = "ClosestSubstring";
174    type Solution = Vec<usize>;
175    type Value = Min<i64>;
176
177    crate::problem_parameters![
178        ("alphabet_size", alphabet_size),
179        ("num_strings", num_strings),
180        ("substring_length", substring_length),
181        ("total_length", total_length),
182        ("total_num_windows", total_num_windows),
183        ("num_window_choice_product", num_window_choice_product),
184    ];
185
186    fn variant() -> Vec<(&'static str, &'static str)> {
187        crate::variant_params![]
188    }
189
190    fn evaluate(
191        &self,
192        config: &Self::Solution,
193    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
194        Ok({
195            let ell = self.substring_length;
196            let n = self.num_strings();
197            if config.len() != ell + n {
198                return Err(crate::traits::EvaluationError::InvalidConfiguration(
199                    "substring witness length does not match the instance".into(),
200                ));
201            }
202            let (center, window_starts) = config.split_at(ell);
203            if center.iter().any(|&symbol| symbol >= self.alphabet_size) {
204                return Ok(Min(None));
205            }
206            for (i, &start) in window_starts.iter().enumerate() {
207                let w_i = self.strings[i].len() - ell + 1;
208                if start >= w_i {
209                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
210                        "substring witness contains an out-of-range window start".into(),
211                    ));
212                }
213            }
214            // Maximum Hamming distance from the center to the chosen window of each string.
215            let mut max_distance = 0_i64;
216            for (i, &start) in window_starts.iter().enumerate() {
217                let window = &self.strings[i][start..start + ell];
218                let distance = i64::try_from(
219                    center
220                        .iter()
221                        .zip(window.iter())
222                        .filter(|(center_symbol, target_symbol)| center_symbol != target_symbol)
223                        .count(),
224                )
225                .map_err(|_| {
226                    crate::traits::EvaluationError::IntegerOverflow(
227                        "converting substring Hamming distance to i64".into(),
228                    )
229                })?;
230                max_distance = max_distance.max(distance);
231            }
232            Min(Some(max_distance))
233        })
234    }
235}
236
237impl crate::solvers::BruteForceProblem for ClosestSubstring {
238    fn dimensions(&self) -> Vec<usize> {
239        let ell = self.substring_length;
240        let mut dims = vec![self.alphabet_size; ell];
241        dims.extend(self.strings.iter().map(|s| s.len() - ell + 1));
242        dims
243    }
244}
245
246crate::declare_variants! {
247    default ClosestSubstring => "alphabet_size ^ substring_length * num_window_choice_product",
248}
249
250crate::register_brute_force! {
251    ClosestSubstring,
252}
253
254#[cfg(feature = "example-db")]
255pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
256    vec![crate::example_db::specs::ModelExampleSpec {
257        id: "closest_substring",
258        instance: Box::new(
259            ClosestSubstring::new(
260                2,
261                vec![
262                    vec![0, 0, 0, 1, 1],
263                    vec![1, 0, 1, 0, 0],
264                    vec![1, 1, 0, 0, 1],
265                ],
266                3,
267            )
268            .unwrap(),
269        ),
270        // Center c = [0, 1, 0]; windows (0, 1, 0) selecting s_1[0..3] = 000,
271        // s_2[1..4] = 010, s_3[0..3] = 110 with distances 1, 0, 1 and radius 1.
272        optimal_config: serde_json::json!(vec![0, 1, 0, 0, 1, 0]),
273        optimal_value: serde_json::json!(1),
274    }]
275}
276
277#[cfg(test)]
278#[path = "../../unit_tests/models/misc/closest_substring.rs"]
279mod tests;
problemreductions/models/misc/closest_substring.rs

problemreductions/models/misc/
closest_substring.rs
