Are you looking for just the challenge with no spoilers? Stop now, go back to last weeks post!
Still here? Great! Let's dive in to the solution. Why did I do this in rust? Well.. it's not because I had the need for extreme memory safety. I didn't need the zero cost abstractions, but i guess they are nice. The thick and well supplied third party ecosystem wasn't needed. Didn't need the safe concurrency.
I chose rust because I'm interested in the language, and I wanted to pick it up again.
Recently, I went along to the local rust meetup in Christchurch, and I enjoyed the vibe. People are interested in talking allocations, safe handling of errors, and working with systems that require some high performance.
Writing systems that need to go fast is really fun. You get a sweet dopamine hit from making memory go down and cpu flame graphs chill out.
My hope is that rust is a tool that helps me stretch that urge, and at some point in the future I would very much like to apply it to a professional problem.
So let's dive in to the code. I'm going to skip over the boring bits, and focus on the interesting parts.
Let's start by building our dictionary of possible words. I'm depending on the built in dictionary file in linux, on my machine I chose /usr/share/dict/american-english.
fn get_dictionary(dictionary_path: &str) -> Vec<String> {
let mut words = Vec::new();
for line in read_to_string(dictionary_path).unwrap().lines() {
// if it contains ' then strip it out and save it...
let mut thisline = line.to_string();
if line.contains("'") {
thisline = thisline.replace("'", "").to_string();
}
words.push(thisline.to_uppercase());
}
words
}
As you can see, I'm reading the file in to a string, and then iterating over the lines. I'm also stripping out the ' character, because it is not a valid character in our code cracker alphabet.
Next we need to represent our hint and substitute alphabet as a type. As what you might find after years and years of programming, most problems can be solved with simple vectors and hashmaps. So let's represent our substitution alphabet with an array, and our hint with a vec.
// a hint is a Vec<i32> where each item in the hint represents an index into our substituion alphabet
struct Problem {
code: [Option<char>; 26],
hints: Vec<Vec<i32>>
}
fn find_options(hint: &Vec<i32>, code:[Option<char>; 26], words: &Vec<String>) -> Vec<String> {
let word_length = hint.len();
let mut options = Vec::new();
'outer: for word in words.iter() {
if word.len() != word_length {
continue
}
// this might be it!
options.push(word.clone())
}
options
}
In this super simple first cut, we just iterate through all the possible words, and check if the length of the word matchces the hint, if it does, push it on to the options vector.
We are going to extend find_options so that we can select just the words that make sense. To do this we need a function to fill in the known parts of our hint word with the actual char from the substitution alphabet.
fn to_letter_map(hint: &Vec<i32>, code: [Option<char>; 26]) -> HashMap<usize, char> {
let mut out = HashMap::new();
for n in 0..hint.len() {
let elem = hint[n];
let codeindex = (elem - 1) as usize;
let opt = code[codeindex];
match opt {
Some(v) => {
out.insert(n, v);
}
None => {
continue
}
}
}
out
}
This one builds up a HashMap that maps the substitution alphabet value to it's actual character, so we can easily lookup what letters to search for.
Now we have what we need to breakdown words with letters that are already known, lets attempt to filter the word list even more by checking that they match the 'pattern' laid out by the hint.
So for our hint 1 7 7 R 7 21 we would expect the word to have the same letter for the 2nd, 3rd and 5th letters. We implement a check_word function to do so.
fn check_word(hint: &Vec<i32>, code:[Option<char>; 26], word: &String) -> bool {
assert_eq!(hint.len() , word.len(), "should be the same length");
let mut code = code.clone();
for (i, c) in hint.iter().enumerate() {
let current_word_char = word.chars().nth(i).unwrap();
let id = (c-1)as usize;
let matches_code = code[id];
match matches_code {
Some(code_value) => {
// if the current value exists as a code but doesn't match the current word
if current_word_char != code_value {
return false
}
},
None => {
code[id] = Some(current_word_char);
}
}
}
return true
}
Of note in this function, we use a 'clone()` on our substitution alphabet (code). This is important because we want to not mutate the original one, and this function will be called many times as we check each candidate word.
Now we can extend the find_options function, putting together our word_map and check_word functions into the loop.
fn find_options(hint: &Vec<i32>, code:[Option<char>; 26], words: &Vec<String>) -> Vec<String> {
let word_length = hint.len();
// word_vec is a map of index of hint -> char, built from referencing the code (substitution alphabet)
let word_vec = to_letter_map(hint, code);
let mut options = Vec::new();
'outer: for word in words.iter() {
if word.len() != word_length {
continue
}
// NEW: in this loop we check that the candidate word matches the letters already known from the hint.
for (index, word_char) in word_vec.iter() {
if word.chars().nth(*index).is_some_and(|c| c != *word_char){
continue 'outer // if it's not then bail to the outer loop `outer
}
}
let matches_pattern = check_word(hint, code, word);
if !matches_pattern {
continue 'outer
}
// this might be it!
options.push(word.clone())
}
options
}
This is how far I got with the challenge! you can check out the code on github.
I'm really new to rust, and this was a fun one to flex my Rustacean skills. Looking forward to putting new skills to use in real projects some time in the near future :)