Alphametic solves up to 10 letter problems but with large number of addends fails

Question

Decided to try the alphametics problem on Exercism and using a brute force but concurrent approach I solve all but the final test in fairly efficient manner. I can't figure out why the final test is failing as the only extra complexity is the number of addends. I assume it's an issue with how I'm handling the carry digit for a column but that should have tripped me up on the other tests too. My code:

use combination::combine::*;
use combination::permutate::*;
use rayon::prelude::*;
use std::collections::HashMap;
use std::collections::HashSet;

const DIGITS: [u8; 10] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    let alphametic = Alphametic::from_str(input);
    alphametic.brute_force()
}

#[derive(Debug, Clone)]
struct Alphametic {
    firsts: HashSet<char>,
    columns: Vec<Vec<char>>,
    keys: HashSet<char>,
}

impl Alphametic {
    fn from_str(input: &str) -> Self {
        let mut firsts = HashSet::new();
        let terms = input
            .split_whitespace()
            .rev()
            .filter(|&sub| sub != "+" && sub != "==")
            .map(|sub| {
                firsts.insert(sub.chars().next().unwrap());
                sub
            })
            .map(|sub| sub.chars().rev().collect::<Vec<char>>())
            .collect::<Vec<Vec<char>>>();
        let max_cols = terms[0].len();
        let mut columns = vec![];
        for i in 0..max_cols {
            columns.push(
                terms
                    .iter()
                    .filter(|term| !(term.len() <= i))
                    .map(|term| term[i])
                    .collect::<Vec<char>>(),
            )
        }
        let keys = terms
            .iter()
            .flatten()
            .map(|&c| c)
            .collect::<HashSet<char>>();
        Alphametic {
            firsts,
            columns,
            keys,
        }
    }

    fn brute_force(&self) -> Option<HashMap<char, u8>> {
        let combo_len = self.keys.len();
        let combos = combine_vec(&DIGITS.to_vec(), combo_len);

        if let Some(soln) = combos
            .par_iter()
            .map(|combo| {
                let perms = permutate_vec(&combo);
                perms
                    .par_iter()
                    .map(|perm| self.to_guess(&perm))
                    .filter(|guess| self.no_leading_zeros(guess))
                    .find_first(|guess| self.guess_columns(guess.clone(), 0, 0).is_some())
            })
            .find_first(|x| x.is_some())
        {
            soln
        } else {
            None
        }
    }

    fn no_leading_zeros(&self, guess: &HashMap<char, u8>) -> bool {
        self.firsts.iter().all(|c| guess.get(c).unwrap_or(&0) > &0)
    }

    fn guess_columns(
        &self,
        guess: HashMap<char, u8>,
        column: usize,
        carry: u8,
    ) -> Option<HashMap<char, u8>> {
        if column >= self.columns.len() {
            Some(guess)
        } else {
            let col = &self.columns[column];
            let sum = *guess.get(&col[0]).unwrap();
            let addition = col[1..].iter().map(|c| guess.get(c).unwrap()).sum::<u8>() + carry;
            if sum == addition % 10 {
                self.guess_columns(guess, column + 1, addition / 10)
            } else {
                None
            }
        }
    }

    fn to_guess(&self, perm: &&Vec<u8>) -> HashMap<char, u8> {
        self.keys
            .iter()
            .zip(*perm)
            .map(|(k, v)| (*k, *v))
            .collect::<HashMap<char, u8>>()
    }
}

test input:

fn test_puzzle_with_ten_letters_and_199_addends() {
    assert_alphametic_solution_eq(
        "THIS + A + FIRE + THEREFORE + FOR + ALL + HISTORIES + I + TELL + A + TALE + THAT + FALSIFIES + ITS + TITLE + TIS + A + LIE + THE + TALE + OF + THE + LAST + FIRE + HORSES + LATE + AFTER + THE + FIRST + FATHERS + FORESEE + THE + HORRORS + THE + LAST + FREE + TROLL + TERRIFIES + THE + HORSES + OF + FIRE + THE + TROLL + RESTS + AT + THE + HOLE + OF + LOSSES + IT + IS + THERE + THAT + SHE + STORES + ROLES + OF + LEATHERS + AFTER + SHE + SATISFIES + HER + HATE + OFF + THOSE + FEARS + A + TASTE + RISES + AS + SHE + HEARS + THE + LEAST + FAR + HORSE + THOSE + FAST + HORSES + THAT + FIRST + HEAR + THE + TROLL + FLEE + OFF + TO + THE + FOREST + THE + HORSES + THAT + ALERTS + RAISE + THE + STARES + OF + THE + OTHERS + AS + THE + TROLL + ASSAILS + AT + THE + TOTAL + SHIFT + HER + TEETH + TEAR + HOOF + OFF + TORSO + AS + THE + LAST + HORSE + FORFEITS + ITS + LIFE + THE + FIRST + FATHERS + HEAR + OF + THE + HORRORS + THEIR + FEARS + THAT + THE + FIRES + FOR + THEIR + FEASTS + ARREST + AS + THE + FIRST + FATHERS + RESETTLE + THE + LAST + OF + THE + FIRE + HORSES + THE + LAST + TROLL + HARASSES + THE + FOREST + HEART + FREE + AT + LAST + OF + THE + LAST + TROLL + ALL + OFFER + THEIR + FIRE + HEAT + TO + THE + ASSISTERS + FAR + OFF + THE + TROLL + FASTS + ITS + LIFE + SHORTER + AS + STARS + RISE + THE + HORSES + REST + SAFE + AFTER + ALL + SHARE + HOT + FISH + AS + THEIR + AFFILIATES + TAILOR + A + ROOFS + FOR + THEIR + SAFE == FORTRESSES",
        &[
            ('A', 1),
            ('E', 0),
            ('F', 5),
            ('H', 8),
            ('I', 7),
            ('L', 2),
            ('O', 6),
            ('R', 3),
            ('S', 4),
            ('T', 9),
        ],
    );

I know the correct guess is being generated because if insert a conditional checking for the hashmap the test expects it succeeds.

Any tips for how to debug this?

Answer 1

Overflowing u8 on the addition. Fixed with some casts to u64.