problemreductions/models/misc/
closest_string.rs

1//! Closest String problem implementation.
2//!
3//! Given a finite alphabet `{0, ..., alphabet_size - 1}` and a list of input
4//! strings of equal length `m`, find a center string `c` of length `m` over the
5//! same alphabet that minimizes the maximum Hamming distance from `c` to any
6//! input string.
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: "ClosestString",
16        display_name: "Closest String",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Find a center string of fixed length that minimizes the maximum Hamming distance to a list of equal-length input strings",
22        fields: &[
23            FieldInfo {
24                name: "alphabet_size",
25                type_name: "usize",
26                description: "Size q of the finite alphabet {0, ..., q-1}",
27            },
28            FieldInfo {
29                name: "strings",
30                type_name: "Vec<Vec<usize>>",
31                description: "Input strings s_1, ..., s_n over the alphabet, all of equal length m",
32            },
33        ],
34    }
35}
36
37/// The Closest String problem.
38///
39/// Given a finite alphabet `Sigma = {0, ..., q - 1}` and `n` input strings
40/// `s_1, ..., s_n` in `Sigma^m` (all of common length `m`), find a center
41/// string `c` in `Sigma^m` minimizing
42///
43/// `max_{1 <= i <= n} d_H(c, s_i)`,
44///
45/// where `d_H` is the Hamming distance. Every center in the discrete cube is
46/// syntactically feasible; the objective is its worst-case Hamming distance
47/// to the input strings.
48#[derive(Debug, Clone, Serialize, Deserialize)]
49#[serde(try_from = "ClosestStringData")]
50pub struct ClosestString {
51    alphabet_size: usize,
52    strings: Vec<Vec<usize>>,
53}
54
55#[derive(Deserialize)]
56struct ClosestStringData {
57    alphabet_size: usize,
58    strings: Vec<Vec<usize>>,
59}
60
61impl TryFrom<ClosestStringData> for ClosestString {
62    type Error = crate::registry::ConstructionError;
63
64    fn try_from(data: ClosestStringData) -> Result<Self, Self::Error> {
65        Self::try_new(data.alphabet_size, data.strings)
66    }
67}
68
69impl ClosestString {
70    /// Create a new `ClosestString` instance.
71    ///
72    /// # Panics
73    ///
74    /// Panics if:
75    /// - `strings` is empty (the problem requires at least one input string),
76    /// - input strings do not all have the same length,
77    /// - `alphabet_size == 0` while any input string is non-empty,
78    /// - any symbol in any input string is `>= alphabet_size`.
79    pub fn new(alphabet_size: usize, strings: Vec<Vec<usize>>) -> Self {
80        Self::try_new(alphabet_size, strings).unwrap_or_else(|error| panic!("{error}"))
81    }
82
83    fn try_new(
84        alphabet_size: usize,
85        strings: Vec<Vec<usize>>,
86    ) -> Result<Self, crate::registry::ConstructionError> {
87        if strings.is_empty() {
88            return Err("ClosestString requires at least one input string".into());
89        }
90        let string_length = strings[0].len();
91        if !(strings.iter().all(|s| s.len() == string_length)) {
92            return Err("all input strings must have the same length".into());
93        }
94        if !(alphabet_size > 0 || string_length == 0) {
95            return Err("alphabet_size must be > 0 when input strings are non-empty".into());
96        }
97        if !(strings
98            .iter()
99            .flat_map(|s| s.iter())
100            .all(|&symbol| symbol < alphabet_size))
101        {
102            return Err("input symbols must be less than alphabet_size".into());
103        }
104        Ok(Self {
105            alphabet_size,
106            strings,
107        })
108    }
109
110    /// Returns the alphabet size `q`.
111    pub fn alphabet_size(&self) -> usize {
112        self.alphabet_size
113    }
114
115    /// Returns the input strings.
116    pub fn strings(&self) -> &[Vec<usize>] {
117        &self.strings
118    }
119
120    /// Returns the number of input strings `n`.
121    pub fn num_strings(&self) -> usize {
122        self.strings.len()
123    }
124
125    /// Returns the common string length `m`.
126    pub fn string_length(&self) -> usize {
127        self.strings[0].len()
128    }
129
130    /// Returns the total input length `num_strings * string_length`.
131    pub fn total_length(&self) -> usize {
132        self.num_strings() * self.string_length()
133    }
134}
135
136impl Problem for ClosestString {
137    const NAME: &'static str = "ClosestString";
138    type Solution = Vec<usize>;
139    type Value = Min<i64>;
140
141    crate::problem_parameters![
142        ("alphabet_size", alphabet_size),
143        ("num_strings", num_strings),
144        ("string_length", string_length),
145        ("total_length", total_length),
146    ];
147
148    fn variant() -> Vec<(&'static str, &'static str)> {
149        crate::variant_params![]
150    }
151
152    fn evaluate(
153        &self,
154        config: &Self::Solution,
155    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
156        Ok({
157            let m = self.string_length();
158            if config.len() != m {
159                return Err(crate::traits::EvaluationError::InvalidConfiguration(
160                    "candidate string length does not match the instance strings".into(),
161                ));
162            }
163            if config.iter().any(|&symbol| symbol >= self.alphabet_size) {
164                return Err(crate::traits::EvaluationError::InvalidConfiguration(
165                    "candidate string contains an out-of-range symbol".into(),
166                ));
167            }
168            // Maximum Hamming distance from the center to any input string.
169            let mut max_distance = 0_i64;
170            for string in &self.strings {
171                let distance = i64::try_from(
172                    config
173                        .iter()
174                        .zip(string.iter())
175                        .filter(|(center, target)| center != target)
176                        .count(),
177                )
178                .map_err(|_| {
179                    crate::traits::EvaluationError::IntegerOverflow(
180                        "converting Hamming distance to i64".into(),
181                    )
182                })?;
183                max_distance = max_distance.max(distance);
184            }
185            Min(Some(max_distance))
186        })
187    }
188}
189
190impl crate::solvers::BruteForceProblem for ClosestString {
191    fn dimensions(&self) -> Vec<usize> {
192        vec![self.alphabet_size; self.string_length()]
193    }
194}
195
196crate::declare_variants! {
197    default ClosestString => "alphabet_size ^ string_length",
198}
199
200crate::register_brute_force! {
201    ClosestString,
202}
203
204#[cfg(feature = "example-db")]
205pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
206    vec![crate::example_db::specs::ModelExampleSpec {
207        id: "closest_string",
208        instance: Box::new(ClosestString::new(
209            2,
210            vec![vec![0, 0, 0], vec![0, 1, 1], vec![1, 0, 1], vec![1, 1, 0]],
211        )),
212        optimal_config: serde_json::json!(vec![0, 0, 0]),
213        optimal_value: serde_json::json!(2),
214    }]
215}
216
217#[cfg(test)]
218#[path = "../../unit_tests/models/misc/closest_string.rs"]
219mod tests;
problemreductions/models/misc/closest_string.rs

problemreductions/models/misc/
closest_string.rs
