Verbal Arithmetic Puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
    bool isSolvable(vector<string>& words, string result) {
        unordered_set<char> chars_set;
        for (auto& w : words) for (char c : w) chars_set.insert(c);
        for (char c : result) chars_set.insert(c);
        if (chars_set.size() > 10) return false;
        vector<char> chars(chars_set.begin(), chars_set.end());
        unordered_set<char> first_letters;
        for (auto& w : words) first_letters.insert(w[0]);
        first_letters.insert(result[0]);
        unordered_map<char, int> coeff;
        for (auto& w : words) for (int i = 0; i < w.size(); ++i) coeff[w[w.size()-1-i]] += pow(10, i);
        for (int i = 0; i < result.size(); ++i) coeff[result[result.size()-1-i]] -= pow(10, i);
        vector<int> used(10, 0);
        unordered_map<char, int> char_to_digit;
        function<bool(int)> backtrack = [&](int idx) {
            if (idx == chars.size()) {
                long long total = 0;
                for (auto& [c, v] : coeff) total += v * char_to_digit[c];
                return total == 0;
            }
            char c = chars[idx];
            for (int d = 0; d < 10; ++d) {
                if (used[d]) continue;
                if (d == 0 && first_letters.count(c)) continue;
                char_to_digit[c] = d; used[d] = 1;
                if (backtrack(idx+1)) return true;
                used[d] = 0; char_to_digit.erase(c);
            }
            return false;
        };
        return backtrack(0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

func isSolvable(words []string, result string) bool {
    charsSet := map[byte]struct{}{}
    for _, w := range words {
        for i := 0; i < len(w); i++ {
            charsSet[w[i]] = struct{}{}
        }
    }
    for i := 0; i < len(result); i++ {
        charsSet[result[i]] = struct{}{}
    }
    if len(charsSet) > 10 {
        return false
    }
    chars := make([]byte, 0, 10)
    for c := range charsSet {
        chars = append(chars, c)
    }
    firstLetters := map[byte]struct{}{}
    for _, w := range words {
        firstLetters[w[0]] = struct{}{}
    }
    firstLetters[result[0]] = struct{}{}
    coeff := map[byte]int{}
    for _, w := range words {
        for i := 0; i < len(w); i++ {
            coeff[w[len(w)-1-i]] += pow10(i)
        }
    }
    for i := 0; i < len(result); i++ {
        coeff[result[len(result)-1-i]] -= pow10(i)
    }
    used := make([]bool, 10)
    charToDigit := map[byte]int{}
    var backtrack func(idx int) bool
    backtrack = func(idx int) bool {
        if idx == len(chars) {
            total := 0
            for c, v := range coeff {
                total += v * charToDigit[c]
            }
            return total == 0
        }
        c := chars[idx]
        for d := 0; d < 10; d++ {
            if used[d] { continue }
            if d == 0 {
                if _, ok := firstLetters[c]; ok { continue }
            }
            charToDigit[c] = d; used[d] = true
            if backtrack(idx+1) { return true }
            used[d] = false; delete(charToDigit, c)
        }
        return false
    }
    return backtrack(0)
}
func pow10(n int) int { res := 1; for i := 0; i < n; i++ { res *= 10 }; return res }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.util.*;
class Solution {
    public boolean isSolvable(String[] words, String result) {
        Set<Character> charsSet = new HashSet<>();
        for (String w : words) for (char c : w.toCharArray()) charsSet.add(c);
        for (char c : result.toCharArray()) charsSet.add(c);
        if (charsSet.size() > 10) return false;
        List<Character> chars = new ArrayList<>(charsSet);
        Set<Character> firstLetters = new HashSet<>();
        for (String w : words) firstLetters.add(w.charAt(0));
        firstLetters.add(result.charAt(0));
        Map<Character, Integer> coeff = new HashMap<>();
        for (String w : words) for (int i = 0; i < w.length(); i++) coeff.put(w.charAt(w.length()-1-i), coeff.getOrDefault(w.charAt(w.length()-1-i), 0) + (int)Math.pow(10, i));
        for (int i = 0; i < result.length(); i++) coeff.put(result.charAt(result.length()-1-i), coeff.getOrDefault(result.charAt(result.length()-1-i), 0) - (int)Math.pow(10, i));
        boolean[] used = new boolean[10];
        Map<Character, Integer> charToDigit = new HashMap<>();
        return backtrack(0, chars, used, charToDigit, coeff, firstLetters);
    }
    private boolean backtrack(int idx, List<Character> chars, boolean[] used, Map<Character, Integer> charToDigit, Map<Character, Integer> coeff, Set<Character> firstLetters) {
        if (idx == chars.size()) {
            long total = 0;
            for (char c : coeff.keySet()) total += coeff.get(c) * charToDigit.get(c);
            return total == 0;
        }
        char c = chars.get(idx);
        for (int d = 0; d < 10; d++) {
            if (used[d]) continue;
            if (d == 0 && firstLetters.contains(c)) continue;
            charToDigit.put(c, d); used[d] = true;
            if (backtrack(idx+1, chars, used, charToDigit, coeff, firstLetters)) return true;
            used[d] = false; charToDigit.remove(c);
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    fun isSolvable(words: Array<String>, result: String): Boolean {
        val charsSet = mutableSetOf<Char>()
        words.forEach { w -> w.forEach { charsSet.add(it) } }
        result.forEach { charsSet.add(it) }
        if (charsSet.size > 10) return false
        val chars = charsSet.toList()
        val firstLetters = (words.map { it[0] } + result[0]).toSet()
        val coeff = mutableMapOf<Char, Int>()
        words.forEach { w -> w.reversed().forEachIndexed { i, c -> coeff[c] = coeff.getOrDefault(c, 0) + Math.pow(10.0, i.toDouble()).toInt() } }
        result.reversed().forEachIndexed { i, c -> coeff[c] = coeff.getOrDefault(c, 0) - Math.pow(10.0, i.toDouble()).toInt() }
        val used = BooleanArray(10)
        val charToDigit = mutableMapOf<Char, Int>()
        fun backtrack(idx: Int): Boolean {
            if (idx == chars.size) {
                var total = 0L
                for ((c, v) in coeff) total += v * charToDigit[c]!!
                return total == 0L
            }
            val c = chars[idx]
            for (d in 0..9) {
                if (used[d]) continue
                if (d == 0 && c in firstLetters) continue
                charToDigit[c] = d; used[d] = true
                if (backtrack(idx + 1)) return true
                used[d] = false; charToDigit.remove(c)
            }
            return false
        }
        return backtrack(0)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

from typing import List
def isSolvable(words: List[str], result: str) -> bool:
    from collections import defaultdict
    # Step 1: Collect all unique characters
    chars = set(''.join(words) + result)
    if len(chars) > 10:
        return False
    chars = list(chars)
    # Step 2: Prepare for backtracking
    first_letters = set(w[0] for w in words + [result])
    n = len(chars)
    char_to_digit = {}
    used = [False] * 10
    # Precompute the coefficients for each character
    coeff = defaultdict(int)
    for w in words:
        for i, c in enumerate(w[::-1]):
            coeff[c] += 10 ** i
    for i, c in enumerate(result[::-1]):
        coeff[c] -= 10 ** i
    def backtrack(idx=0):
        if idx == n:
            # Check if the current assignment is valid
            total = 0
            for c in coeff:
                total += coeff[c] * char_to_digit[c]
            return total == 0
        c = chars[idx]
        for d in range(10):
            if used[d]:
                continue
            if d == 0 and c in first_letters:
                continue
            char_to_digit[c] = d
            used[d] = True
            if backtrack(idx + 1):
                return True
            used[d] = False
            del char_to_digit[c]
        return False
    return backtrack()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

use std::collections::{HashMap, HashSet};
fn pow10(n: usize) -> i64 { (0..n).fold(1, |acc, _| acc * 10) }
pub fn is_solvable(words: Vec<&str>, result: &str) -> bool {
    let mut chars_set = HashSet::new();
    for w in &words { for c in w.chars() { chars_set.insert(c); } }
    for c in result.chars() { chars_set.insert(c); }
    if chars_set.len() > 10 { return false; }
    let chars: Vec<_> = chars_set.iter().cloned().collect();
    let mut first_letters = HashSet::new();
    for w in &words { first_letters.insert(w.chars().next().unwrap()); }
    first_letters.insert(result.chars().next().unwrap());
    let mut coeff = HashMap::new();
    for w in &words {
        for (i, c) in w.chars().rev().enumerate() {
            *coeff.entry(c).or_insert(0) += pow10(i) as i32;
        }
    }
    for (i, c) in result.chars().rev().enumerate() {
        *coeff.entry(c).or_insert(0) -= pow10(i) as i32;
    }
    let mut used = [false; 10];
    let mut char_to_digit = HashMap::new();
    fn backtrack(idx: usize, chars: &[char], used: &mut [bool; 10], char_to_digit: &mut HashMap<char, i32>, coeff: &HashMap<char, i32>, first_letters: &HashSet<char>) -> bool {
        if idx == chars.len() {
            let mut total = 0i64;
            for (&c, &v) in coeff.iter() {
                total += v as i64 * *char_to_digit.get(&c).unwrap() as i64;
            }
            return total == 0;
        }
        let c = chars[idx];
        for d in 0..10 {
            if used[d] { continue; }
            if d == 0 && first_letters.contains(&c) { continue; }
            char_to_digit.insert(c, d as i32); used[d] = true;
            if backtrack(idx+1, chars, used, char_to_digit, coeff, first_letters) { return true; }
            used[d] = false; char_to_digit.remove(&c);
        }
        false
    }
    backtrack(0, &chars, &mut used, &mut char_to_digit, &coeff, &first_letters)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

function isSolvable(words: string[], result: string): boolean {
    const charsSet = new Set<string>();
    for (const w of words) for (const c of w) charsSet.add(c);
    for (const c of result) charsSet.add(c);
    if (charsSet.size > 10) return false;
    const chars = Array.from(charsSet);
    const firstLetters = new Set<string>([...words.map(w => w[0]), result[0]]);
    const coeff: Record<string, number> = {};
    for (const w of words) for (let i = 0; i < w.length; i++) coeff[w[w.length-1-i]] = (coeff[w[w.length-1-i]] ?? 0) + Math.pow(10, i);
    for (let i = 0; i < result.length; i++) coeff[result[result.length-1-i]] = (coeff[result[result.length-1-i]] ?? 0) - Math.pow(10, i);
    const used = Array(10).fill(false);
    const charToDigit: Record<string, number> = {};
    function backtrack(idx: number): boolean {
        if (idx === chars.length) {
            let total = 0;
            for (const c in coeff) total += coeff[c] * charToDigit[c];
            return total === 0;
        }
        const c = chars[idx];
        for (let d = 0; d < 10; d++) {
            if (used[d]) continue;
            if (d === 0 && firstLetters.has(c)) continue;
            charToDigit[c] = d; used[d] = true;
            if (backtrack(idx + 1)) return true;
            used[d] = false; delete charToDigit[c];
        }
        return false;
    }
    return backtrack(0);
}