2 hours ago

Sarthak • 10

Hyderabad

Question: Cryptarithm Solver

Problem Statement: A cryptarithm is a mathematical puzzle where the goal is to find the correspondence between letters and digits such that the given arithmetic equation consisting of letters holds true.

Given a cryptarithm as an array of strings crypt, count the number of its valid solutions.

The solution is valid if each letter represents a different digit, and the leading digit of any multi-digit number is not zero.

crypt has the following structure: [word1, word2, word3], which stands for the word1 + word2 = word3 cryptarithm.

3 minutes ago

admin 1.9k

Hyderabad

Solution: Cryptarithm Solver

Overview

A cryptarithm is a type of mathematical puzzle where each letter represents a unique digit from 0 to 9. The challenge is to find a mapping that satisfies a specific arithmetic equation, usually an addition like Word1 + Word2 = Word3. There are two strict rules:

1. Uniqueness: No two different letters can represent the same digit.
2. No Leading Zeros: For any word with more than one character, the letter in the most significant position (the first letter) cannot be assigned the digit 0.

Approach

1. Identify Unique Letters: Extract all unique characters from the three words provided in the crypt array. If the count of unique characters exceeds 10, return 0 immediately, as there are only 10 available digits.
2. Permutation Generation: Since the number of unique letters k is at most 10, the total number of ways to assign digits is P(10, k). Even for k=10, 10! (3,628,800) is a manageable number for a brute-force check in most languages.
3. Constraint Filtering: For each permutation of digits assigned to the letters:
   • Check Leading Zeros: Identify the first letter of each word. If any of these letters are mapped to 0 and the word's length is greater than 1, discard this permutation.
   • Calculate Word Values: Convert each word into its numeric value by replacing letters with their assigned digits and calculating the base-10 sum (e.g., "SEND" becomes S \cdot 1000 + E \cdot 100 + N \cdot 10 + D).
4. Verify the Equation: Check if Value(Word1) + Value(Word2) = Value(Word3).
5. Count and Return: Increment a counter for every valid mapping found and return the final total.

Efficiency Note

While brute-forcing all permutations works for k <= 10, a more advanced Backtracking approach can prune the search space by checking the addition column-by-column (from right to left). This allows you to discard invalid mappings as soon as a single column's sum (including the carry) fails to match.

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

// Helper to convert a string to a number based on current character mapping
long long stringToLong(const string& s, const vector<int>& mapping, const vector<char>& uniqueChars) {
    long long num = 0;
    for (char c : s) {
        int digit = -1;
        for (int i = 0; i < uniqueChars.size(); ++i) {
            if (uniqueChars[i] == c) {
                digit = mapping[i];
                break;
            }
        }
        num = num * 10 + digit;
    }
    return num;
}

int solveCryptarithm(vector<string> crypt) {
    set<char> charSet;
    for (const string& word : crypt) {
        for (char c : word) charSet.insert(c);
    }

    // If there are more than 10 unique characters, no solution exists
    if (charSet.size() > 10) return 0;

    vector<char> uniqueChars(charSet.begin(), charSet.end());
    int k = uniqueChars.size();

    // Identify which characters are leading characters
    vector<bool> isLeading(k, false);
    for (const string& word : crypt) {
        if (word.length() > 1) {
            for (int i = 0; i < k; ++i) {
                if (uniqueChars[i] == word[0]) {
                    isLeading[i] = true;
                }
            }
        }
    }

    // Prepare digits 0-9 for permutation
    vector<int> digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int solutionsCount = 0;

    // We only need to permute the first 'k' digits out of 10.
    // However, std::next_permutation works on the whole range.
    // To optimize, we can use a recursive backtracking approach.
    
    sort(digits.begin(), digits.end());

    do {
        bool leadingZero = false;
        for (int i = 0; i < k; ++i) {
            if (isLeading[i] && digits[i] == 0) {
                leadingZero = true;
                break;
            }
        }

        if (!leadingZero) {
            long long val1 = stringToLong(crypt[0], digits, uniqueChars);
            long long val2 = stringToLong(crypt[1], digits, uniqueChars);
            long long val3 = stringToLong(crypt[2], digits, uniqueChars);

            if (val1 + val2 == val3) {
                solutionsCount++;
            }
        }
        
        // Advanced: std::next_permutation on 10 elements is 3.6 million iterations.
        // To only permute the first K elements, we handle the tail.
        reverse(digits.begin() + k, digits.end());
    } while (next_permutation(digits.begin(), digits.end()));

    return solutionsCount;
}

int main() {
    // Example: SEND + MORE = MONEY
    vector<string> crypt = {"SEND", "MORE", "MONEY"};
    cout << "Number of solutions: " << solveCryptarithm(crypt) << endl;
    return 0;
}