rust/alphametics/src/lib.rs - master - asmody/exercism

rust/alphametics/src/lib.rs
127 строк3 KB
Victor Asmody Sakhnov
fsharp
29 окт 2025, 21:10
29 окт 2025, 21:101d2db36
use std::collections::{HashMap, HashSet};

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    let (left, right) = parse_equation(input)?;
    let letters = get_unique_letters(&left, &right);
    let first_letters = get_first_letters(&left, &right);
    
    let mut solution = HashMap::new();
    let mut used_digits = HashSet::new();
    
    if solve_recursive(
        &letters,
        &first_letters,
        &left,
        &right,
        &mut solution,
        &mut used_digits,
    ) {
        Some(solution)
    } else {
        None
    }
}

fn parse_equation(input: &str) -> Option<(Vec<&str>, &str)> {
    let parts: Vec<&str> = input.split("==").collect();
    if parts.len() != 2 {
        return None;
    }
    
    let left: Vec<&str> = parts[0]
        .split('+')
        .map(|s| s.trim())
        .filter(|s| !s.is_empty())
        .collect();
    
    let right = parts[1].trim();
    
    if left.is_empty() || right.is_empty() {
        return None;
    }
    
    Some((left, right))
}

fn get_unique_letters(left: &[&str], right: &str) -> Vec<char> {
    let mut letters = HashSet::new();
    
    for word in left {
        for c in word.chars() {
            letters.insert(c);
        }
    }
    
    for c in right.chars() {
        letters.insert(c);
    }
    
    letters.into_iter().collect()
}

fn get_first_letters(left: &[&str], right: &str) -> HashSet<char> {
    let mut first_letters = HashSet::new();
    
    for word in left {
        if let Some(c) = word.chars().next() {
            first_letters.insert(c);
        }
    }
    
    if let Some(c) = right.chars().next() {
        first_letters.insert(c);
    }
    
    first_letters
}

fn solve_recursive(
    letters: &[char],
    first_letters: &HashSet<char>,
    left: &[&str],
    right: &str,
    solution: &mut HashMap<char, u8>,
    used_digits: &mut HashSet<u8>,
) -> bool {
    if letters.is_empty() {
        return is_valid_solution(left, right, solution);
    }
    
    let current_letter = letters[0];
    let start_digit = if first_letters.contains(&current_letter) { 1 } else { 0 };
    
    for digit in start_digit..=9 {
        if used_digits.contains(&digit) {
            continue;
        }
        
        solution.insert(current_letter, digit);
        used_digits.insert(digit);
        
        if solve_recursive(&letters[1..], first_letters, left, right, solution, used_digits) {
            return true;
        }
        
        solution.remove(&current_letter);
        used_digits.remove(&digit);
    }
    
    false
}

fn is_valid_solution(left: &[&str], right: &str, solution: &HashMap<char, u8>) -> bool {
    let left_sum: u64 = left
        .iter()
        .map(|word| word_to_number(word, solution))
        .sum();
    
    let right_sum = word_to_number(right, solution);
    
    left_sum == right_sum
}

fn word_to_number(word: &str, solution: &HashMap<char, u8>) -> u64 {
    word.chars()
        .map(|c| *solution.get(&c).unwrap() as u64)
        .fold(0, |acc, digit| acc * 10 + digit)
}