Identify valid words with one different letter (Lewis Caroll duplet transformations)

transformations.rs

use std::io::prelude::*;
use std::io::{self, BufReader};
use std::fs::File;
use std::error::Error;
use std::path::Path;
use std::collections::HashMap;

/// Map describing which words have a character at a given index
/// { letter: { letter_position: Vec<word_id> } }
/// e.g. {'a': {0: [1]}} means "word 1 has an 'a' at position 0"
type LetterPositions = HashMap<char, HashMap<usize, Vec<usize>>>;

pub struct Solver {
    /// All available words
    dictionary: Vec<String>,
    /// The `LetterWordMap generated from the dictionary above
    letter_positions: LetterPositions,
}

impl Solver {
    fn new(dictionary: Vec<String>) -> Solver {
        // build letter_positions
        let mut letter_positions: LetterPositions = HashMap::new();

        dbg!("building letter word map...");
        // build a dict of keys of letter positions, and the letters
        // and their parent word: {pos: {letter: [word_index*]}}
        for (word_id, word) in dictionary.iter().enumerate() {
            for (letter_pos, letter) in word.chars().enumerate() {
                letter_positions.entry(letter)
                    .or_default()
                    .entry(letter_pos)
                    .or_default()
                    .push(word_id);
            }
        }

        Solver {
            letter_positions,
            dictionary,
        }
    }

    fn from_file<P: AsRef<Path>>(path: P) -> io::Result<Solver> {
        dbg!("loading dictionary...");
        // read lines
        BufReader::new(File::open(path)?)
            .lines()
            .collect::<io::Result<Vec<String>>>()
            .map(|d| Solver::new(d))
    }

    /// return the id of each word in the dictionary which contains `letter` at `letter_pos`
    fn words_containing(&self, letter: char, letter_pos: usize) -> Option<&Vec<usize>> {
        self.letter_positions.get(&letter).and_then(|l| l.get(&letter_pos))
    }

    /// Omit the letter at `transformation_pos` in `word`.
    ///
    /// For each other letter in word, give score + 1 to each dictionary word which contains
    /// that letter at its position in `word`.
    ///
    /// Returns all words which have a score of exactly `word.len() - 1`, i.e. words which contain
    /// all letters except the omitted in the same position, have the same length as `word`,
    fn get_transformations(&self, word: &str, transformation_pos: usize) -> Vec<String> {
        // counts how many letters a word has in common with parent_word
        let mut match_scores: HashMap<usize, usize> = HashMap::new();

        for (letter_pos, letter) in word.chars().enumerate() {
            // omit letter at `transformation_pos`
            if letter_pos == transformation_pos {
                continue;
            }

            // find words which contain `letter` at `letter_pos`
            if let Some(letter_matches) = self.words_containing(letter, letter_pos) {
                for match_id in letter_matches {
                    let matched_word = &self.dictionary[*match_id];
                    if matched_word.len() == word.len() && matched_word.as_str() != word {
                        *match_scores.entry(*match_id).or_insert(0) += 1;
                    }
                }
            }
        }

        let req_score = word.len() - 1;

        match_scores.iter()
            .filter(|(_, &score)| score == req_score)
            .map(|(&word_id, _)| self.dictionary[word_id].clone())
            .collect()
    }

    fn get_all_transformations(&self, word: &str) -> Vec<String> {
        (0..word.len()).flat_map(|tp| self.get_transformations(word, tp)).collect()
    }
}

fn main() -> Result<(), Box<dyn Error>> {
    let solver = Solver::from_file("dictionary.txt")?;

    dbg!(solver.get_all_transformations("bad"));

    Ok(())
}