1 files changed, 127 insertions, 0 deletions
diff --git a/unsolved/kattis-kth-adk-spelling/src/main.rs b/unsolved/kattis-kth-adk-spelling/src/main.rs
new file mode 100644
index 0000000..020b630
--- /dev/null
+++ b/unsolved/kattis-kth-adk-spelling/src/main.rs
@@ -0,0 +1,127 @@
+use std::{
+    collections::HashSet,
+    io::{stdin, Read},
+    mem,
+};
+
+fn to_str(v: &[u8]) -> String {
+    let mut res = String::with_capacity(v.len() * 3 / 2);
+    for &c in v {
+        res.push(match c {
+            b'a'..=b'z' => c as char,
+            b'1' => 'å',
+            b'2' => 'ä',
+            b'3' => 'ö',
+            _ => unreachable!(c),
+        });
+    }
+    res
+}
+
+fn main() {
+    let mut input = String::new();
+    let _ = stdin().lock().read_to_string(&mut input);
+
+    let lines: Vec<Vec<u8>> = input
+        .lines()
+        .map(|l| {
+            l.chars()
+                .map(|c| match c {
+                    'a'..='z' => c as u32 as u8,
+                    'å' => b'1',
+                    'ä' => b'2',
+                    'ö' => b'3',
+                    '#' => b'#',
+                    _ => unreachable!(),
+                })
+                .collect()
+        })
+        .collect();
+    let (wordlist, words) = {
+        let mut s = lines.splitn(2, |l| l == &[b'#']);
+        (s.next().unwrap(), s.next().unwrap())
+    };
+
+    let mut wordset = HashSet::new();
+    let mut chars = vec![HashSet::<u8>::new(); 42];
+    for w in wordlist {
+        wordset.insert(w);
+        for (i, &c) in w.iter().enumerate() {
+            chars[i].insert(c);
+        }
+    }
+    let longest = wordlist.iter().fold(0, |acc, w| acc.max(w.len()));
+    let shortest = wordlist.iter().fold(69, |acc, w| acc.min(w.len()));
+
+    for start in words {
+        let mut curr = vec![start.clone()];
+        let mut next: Vec<Vec<u8>> = vec![];
+        let mut visited = HashSet::new();
+
+        let mut found = vec![];
+        let mut depth = 0;
+        loop {
+            for mut w in curr.drain(..) {
+                if visited.contains(&w) {
+                    continue;
+                }
+                visited.insert(w.clone());
+                if wordset.contains(&w) {
+                    found.push(w);
+                    continue;
+                }
+                if !found.is_empty() {
+                    continue;
+                }
+                for i in 0..w.len() {
+                    let orig_c = w[i];
+                    for &c in b"qwfpbkluy2arstgmneio1zxcdvjh3" {
+                        if !chars[i].contains(&c) {
+                            continue;
+                        }
+                        w[i] = c;
+                        next.push(w.clone());
+                    }
+                    w[i] = orig_c;
+                    if w.len() < longest {
+                        for &c in b"qwfpbkluy2arstgmneio1zxcdvjh3" {
+                            if !chars[i].contains(&c) {
+                                continue;
+                            }
+                            let mut cpy = w[..i].to_owned();
+                            cpy.push(c);
+                            cpy.append(&mut w[i..].to_owned());
+                            next.push(cpy);
+                        }
+                    }
+                    if w.len() > shortest {
+                        let mut cpy = w[..i].to_owned();
+                        cpy.append(&mut w[i + 1..].to_owned());
+                        next.push(cpy);
+                    }
+                }
+                if w.len() < longest {
+                    for &c in b"qwfpbkluy2arstgmneio1zxcdvjh3" {
+                        if !chars[w.len()].contains(&c) {
+                            continue;
+                        }
+                        let mut cpy = w.clone();
+                        cpy.push(c);
+                        next.push(cpy);
+                    }
+                }
+            }
+            if !found.is_empty() {
+                break;
+            }
+            mem::swap(&mut curr, &mut next);
+            depth += 1;
+        }
+        found.sort();
+        print!("{} ({})", to_str(&start), depth);
+        for w in found {
+            print!(" {}", to_str(&w));
+        }
+        println!();
+    }
+}