字母算术

描述

这是Exercism中的题目，主要是通过字母计算公式推算出每个字母对应的数字。
比如字母公式：SEND + MORE = MONEY

  S E N D
  M O R E +
-----------
M O N E Y

可以推算出如下：

  9 5 6 7
  1 0 8 5 +
-----------
1 0 6 5 2

注意有几个限制

1. 每个单词所对应的首字母不能为0
2. 每个字母对应的数字范围在0～9
3. 公式中不能出现俩个字母对应的数字相同

解决方案

可以通过递归的方式解决，主要步骤如下

1. 简化公式，并筛选出首字母

   (1000S + 100E + 10N + D) + (1000M + 100O + 10R + E) = 10000M + 1000O + 100N + 10E + Y
   
   
   1000S + 91E + D + 10R - 9000M - 900O - 90N  - Y = 0

/// 返回元组，（字母，倍数，是否首字母）
fn parse(input: &str) -> Vec<(char, i64, bool)> {
    // 存储字母对应倍数
    let mut ans = HashMap::new();
    // 存储首字母
    let mut leading = HashSet::new();
    let mut prev = ' ';
    let mut value = -1;
    for ch in input.chars().rev() {
        match ch {
            'A'..='Z' => {
                *ans.entry(ch).or_insert(0) += value;
                value *= 10;
                prev = ch;
            }
            _ => {
                value = 1;
                leading.insert(prev);
            },
        }
    }
    leading.insert(prev);
    ans.iter().map(|(&k, &v)|(k, v, leading.contains(&k))).collect()
}

2. 递归查询每个字母对应的数字

/// 寻找count为的字符对应的数字，并存储在ans对应的索引上，digits这是可选的数字
fn find(count: usize, ans: &mut Vec<u8>, digits: &Vec<u8>, values: &Vec<(char, i64, bool)>)  -> Option<HashMap<char, u8>> {
    
    if count == values.len() {
      // 表示已经递归最后一位的字母，cal函数是计算公式是否相等
        return if cal(ans, values) {
            Some(ans.iter().zip(values.iter()).map(|(&digit, &(ch, _, _))| (ch, digit)).collect())
        }
        else {
            None
        };
    }
    // 针对可选数字（digits）进行循环，查找可让公式相等的值
    for (i, &digit) in digits.iter().enumerate() {
        if digit == 0 && values[count].2 {
            continue;
        }
        // 当前索引位置的字母对应数字设置
        ans[count] = digit as u8;
        // 取出当前位置设置的数据，获取下一个字母位置所能够设置的值的集合
        let mut digits2 = digits.clone();
        digits2.remove(i);
        // 递归查找每个位置的字母所对应的数字
        if let Some(solution) = find(count + 1, ans, &digits2, values) {
            return Some(solution);
        }
    }
    None
}

完整代码

use std::collections::HashMap;
use std::collections::HashSet;

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    let mut values = parse(input);
    values.sort();
    let mut ans = vec![0; values.len()];
    return find(0, &mut ans, &(0..10).collect(), &values);
}

fn parse(input: &str) -> Vec<(char, i64, bool)> {
    let mut ans = HashMap::new();
    let mut leading = HashSet::new();
    let mut prev = ' ';
    let mut value = -1;
    for ch in input.chars().rev() {
        match ch {
            'A'..='Z' => {
                *ans.entry(ch).or_insert(0) += value;
                value *= 10;
                prev = ch;
            }
            _ => {
                value = 1;
                leading.insert(prev);
            },
        }
    }
    leading.insert(prev);
    ans.iter().map(|(&k, &v)|(k, v, leading.contains(&k))).collect()
}

fn find(count: usize, ans: &mut Vec<u8>, digits: &Vec<u8>, values: &Vec<(char, i64, bool)>)  -> Option<HashMap<char, u8>> {
    if count == values.len() {
        return if cal(ans, values) {
            Some(ans.iter().zip(values.iter()).map(|(&digit, &(ch, _, _))| (ch, digit)).collect())
        }
        else {
            None
        };
    }
    for (i, &digit) in digits.iter().enumerate() {
        if digit == 0 && values[count].2 {
            continue;
        }
        ans[count] = digit as u8;
        let mut digits2 = digits.clone();
        digits2.remove(i);
        if let Some(solution) = find(count + 1, ans, &digits2, values) {
            return Some(solution);
        }
    }
    None
}

fn cal(ans: &Vec<u8>, values: &Vec<(char, i64, bool)>) -> bool {
    let mut total = 0;
    for (i, &digit) in ans.iter().enumerate() {
        total += digit as i64 * values[i].1;
    }
    total == 0
}