Alphametics

1. Readme

算术谜题

写一个函数来解决字母谜题.

Alphametics是一个拼图，其中单词中的字母被数字替换.

例如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

这是正确的，因为每个字母都被不同的数字替换，之后单词会被翻译成数字，然后产生有效的总和。

每个字母必须代表不同的数字，并且多位数的首数字不能是 0 。

写一个函数来解决字母谜题.

2. 开始你的表演

 
use std::collections::HashMap;

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
   unimplemented!("Solve the alphametic {:?}", input)
}

3. 测试代码查看

 

# #![allow(unused_variables)]
#fn main() {
// use std::collections::HashMap;

fn assert_alphametic_solution_eq(puzzle: &str, solution: &[(char, u8)]) {
   let answer = solve(puzzle);
   let solution: HashMap<char, u8> = solution.iter().cloned().collect();
   assert_eq!(answer, Some(solution));
}

#[test]
fn test_with_three_letters() {
   assert_alphametic_solution_eq("I + BB == ILL", &[('I', 1), ('B', 9), ('L', 0)]);
}

#[test]
//#[ignore]
fn test_must_have_unique_value_for_each_letter() {
   let answer = solve("A == B");
   assert_eq!(answer, None);
}

#[test]
//#[ignore]
fn test_leading_zero_solution_is_invalid() {
   let answer = solve("ACA + DD == BD");
   assert_eq!(answer, None);
}

#[test]
//#[ignore]
fn test_puzzle_with_four_letters() {
   assert_alphametic_solution_eq("AS + A == MOM", &[('A', 9), ('S', 2), ('M', 1), ('O', 0)]);
}

#[test]
//#[ignore]
fn test_puzzle_with_six_letters() {
   assert_alphametic_solution_eq(
       "NO + NO + TOO == LATE",
       &[('N', 7), ('O', 4), ('T', 9), ('L', 1), ('A', 0), ('E', 2)],
   );
}

#[test]
//#[ignore]
fn test_puzzle_with_seven_letters() {
   assert_alphametic_solution_eq(
       "HE + SEES + THE == LIGHT",
       &[
           ('E', 4),
           ('G', 2),
           ('H', 5),
           ('I', 0),
           ('L', 1),
           ('S', 9),
           ('T', 7),
       ],
   );
}

#[test]
//#[ignore]
fn test_puzzle_with_eight_letters() {
   assert_alphametic_solution_eq(
       "SEND + MORE == MONEY",
       &[
           ('S', 9),
           ('E', 5),
           ('N', 6),
           ('D', 7),
           ('M', 1),
           ('O', 0),
           ('R', 8),
           ('Y', 2),
       ],
   );
}

#[test]
//#[ignore]
fn test_puzzle_with_ten_letters() {
   assert_alphametic_solution_eq(
       "AND + A + STRONG + OFFENSE + AS + A + GOOD == DEFENSE",
       &[
           ('A', 5),
           ('D', 3),
           ('E', 4),
           ('F', 7),
           ('G', 8),
           ('N', 0),
           ('O', 2),
           ('R', 1),
           ('S', 6),
           ('T', 9),
       ],
   );
}

#}

4. 答案

 


# #![allow(unused_variables)]
#fn main() {
// This is a brute-force solution, use `cargo test --release` for faster testing

extern crate itertools;
extern crate permutohedron;

use itertools::Itertools;
use permutohedron::Heap as Permutations;

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

fn test_equation(puzzle: &str, substitutions: &HashMap<char, u8>) -> bool {
   // Create a new String with characters changed to numbers
   let puzzle: String = puzzle
       .chars()
       .map(|c| {
           if let Some(&n) = substitutions.get(&c) {
               // If the character is in the substitutions, get the number and
               // convert it to a char
               char::from_digit(n as u32, 10).unwrap()
           } else {
               // Otherwise just copy over the character
               c
           }
       })
       .collect();

   // Split the puzzle into left and right side
   let equation: Vec<&str> = puzzle.split("==").collect();

   // Parse the number on the right side
   let right = equation[1].trim().parse::<u32>().unwrap();

   // Sum the parts on the left side
   let left: u32 = equation[0]
       .split('+')
       .map(str::trim)
       .map(|n| n.parse::<u32>().unwrap())
       .sum();

   // Create a String with just the numbers and spaces
   let just_numbers = puzzle
       .chars()
       .filter(|c| c.is_digit(10) || c.is_whitespace())
       .collect::<String>();
   // Split this into the numbers and check every number's first character
   let no_leading_zeroes = just_numbers
       .split_whitespace()
       .all(|number| number.chars().next().unwrap() != '0');

   // Return true if left and right side is equal and the equation doesnt
   // contain leading zeroes.
   left == right && no_leading_zeroes
}

pub fn solve(puzzle: &str) -> Option<HashMap<char, u8>> {
   // Get unique letters from the puzzle
   let letters: HashSet<char> = puzzle
       .chars()
       .filter(|&c| c.is_alphabetic() && c.is_uppercase())
       .collect();
   let letters: Vec<char> = letters.into_iter().collect();

   // All available numbers for substitution
   let numbers: &[u8] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

   // Iterate every combination with the length of unique letters in the puzzle
   for combinations in numbers.iter().combinations(letters.len()) {
       let mut c = combinations;
       let permutations = Permutations::new(&mut c);
       // Iterate every permutation of a letter combination
       for p in permutations {
           let substitution: HashMap<char, u8> =
               letters.iter().zip(p).map(|(&c, &n)| (c, n)).collect();
           if test_equation(puzzle, &substitution) {
               // We found a good substitution
               return Some(substitution);
           }
       }
   }
   // If we tested every combination and did not found a solution then return None
   None
}

#}

填充/相关