logoChat01.ai

A cryptarithm is a mathematical puzzle where the g...

Tạo vào: 23 tháng 6, 2025

Trả lời bằng O3 bởi Chat01

Câu hỏi

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.

Example

For crypt = ["SEND", "MORE", "MONEY"], the output should be solution(crypt) = 1, because there is only one solution to this cryptarithm: O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9 (9567 + 1085 = 10652).

For crypt = ["GREEN", "BLUE", "BLACK"], the output should be solution(crypt) = 12, because there are 12 possible valid solutions:

54889 + 6138 = 61027
18559 + 2075 = 20634
72449 + 8064 = 80513
48229 + 5372 = 53601
47119 + 5261 = 52380
36887 + 4028 = 40915
83447 + 9204 = 92651
74655 + 8326 = 82981

in c++ without comments

Suy nghĩ

Providing solution in C++

I see the user wants a C++ solution for counting valid cryptarithm solutions, with up to 10 unique letters. I'll use backtracking to assign digits to characters, making sure no leading letter gets assigned zero. After each assignment, I'll check if the equation holds (word1 + word2 == word3). If there are more than 10 unique letters, I'll return 0, ensuring the solution is viable. I'll avoid adding comments and provide it in a simple, clean manner. Time to write the code!

Thought for 11 seconds

Trả lời

cpp
#include <bits/stdc++.h>
using namespace std;

long long wordValue(const string& w, const int m[]) {
    long long v = 0;
    for (char c : w) v = v * 10 + m[c - 'A'];
    return v;
}

int solution(const vector<string>& crypt) {
    vector<char> letters;
    bool present[26] = {};
    for (const string& w : crypt)
        for (char c : w)
            if (!present[c - 'A']) {
                present[c - 'A'] = true;
                letters.push_back(c);
            }
    if (letters.size() > 10) return 0;

    int map[26];
    fill(begin(map), end(map), -1);
    bool used[10] = {};
    int n = letters.size();
    long long cnt = 0;

    function<void(int)> dfs = [&](int idx) {
        if (idx == n) {
            for (int i = 0; i < 3; ++i)
                if (crypt[i].size() > 1 && map[crypt[i][0] - 'A'] == 0)
                    return;
            long long a = wordValue(crypt[0], map);
            long long b = wordValue(crypt[1], map);
            long long c = wordValue(crypt[2], map);
            if (a + b == c) ++cnt;
            return;
        }
        for (int d = 0; d < 10; ++d) {
            if (used[d]) continue;
            used[d] = true;
            map[letters[idx] - 'A'] = d;
            dfs(idx + 1);
            used[d] = false;
        }
    };
    dfs(0);
    return static_cast<int>(cnt);
}

Câu hỏi

Givint time limit exceeded

Suy nghĩ

Optimizing for testing

I want to test the example quickly. I’ll try running a Python translation of the current code to verify it. We trust the overall approach but need to make sure it compiles and makes sense. I’m considering potential optimizations, especially regarding the order of digit loops. There's a risk of unintentionally duplicating digits when the same letter appears in different positions across the words. It's rare, but I should keep an eye on that to avoid possible mistakes. I’ll finalize the code now.

Ensuring unique assignments

I’m thinking about how the loops work with repeated letters. If the same letter appears in multiple positions, the loops may treat them independently, but we don’t want to assign different digits to the same letter. The algorithm ensures that each letter gets a fixed digit only when first encountered. Later columns will refer to the existing assignment. Though there can be symmetrical permutations, each path is unique due to this rule. The solution should be unique, even in cases of potential duplicates in the column explorations.

Thought for 1m 39s

Trả lời

cpp
#include <bits/stdc++.h>
using namespace std;

long long solveColumn(const vector<string>& w, int col, int len, const int m[]) {
    if (col >= len) return 0;
    char ch = w[col];
    return ch ? m[ch - 'A'] : 0;
}

int solution(const vector<string>& crypt) {
    vector<string> w = crypt;
    for (string& s : w) reverse(s.begin(), s.end());

    bool present[26] = {}, lead[26] = {};
    for (int i = 0; i < 3; ++i) {
        if (crypt[i].size() > 1) lead[crypt[i][0] - 'A'] = true;
        for (char c : crypt[i]) present[c - 'A'] = true;
    }
    int letters = accumulate(begin(present), end(present), 0);
    if (letters > 10) return 0;

    int m[26]; fill(begin(m), end(m), -1);
    bool used[10] = {};
    int len[3] = { (int)crypt[0].size(), (int)crypt[1].size(), (int)crypt[2].size() };
    int L = max({ len[0], len[1], len[2] });
    long long ans = 0;

    function<void(int,int)> dfs = [&](int pos, int carry) {
        if (pos == L) {
            if (!carry) ++ans;
            return;
        }
        char a = pos < len[0] ? crypt[0][len[0] - 1 - pos] : 0;
        char b = pos < len[1] ? crypt[1][len[1] - 1 - pos] : 0;
        char c = pos < len[2] ? crypt[2][len[2] - 1 - pos] : 0;

        int va = a ? m[a - 'A'] : 0;
        int vb = b ? m[b - 'A'] : 0;
        int vc = c ? m[c - 'A'] : 0;

        vector<int> da, db;
        if (!a) da = {0};
        else if (va != -1) da = {va};
        else {
            for (int d = 0; d < 10; ++d)
                if (!used[d] && (!lead[a - 'A'] || d))
                    da.push_back(d);
        }

        for (int x : da) {
            bool asgA = a && va == -1;
            if (asgA) { m[a - 'A'] = x; used[x] = true; }
            if (!b) db = {0};
            else if (vb != -1) db = {vb};
            else {
                db.clear();
                for (int d = 0; d < 10; ++d)
                    if (!used[d] && (!lead[b - 'A'] || d))
                        db.push_back(d);
            }
            for (int y : db) {
                bool asgB = b && vb == -1;
                if (asgB) { m[b - 'A'] = y; used[y] = true; }

                int sum = x + y + carry;
                int z = sum % 10, nc = sum / 10;
                if (!c) {
                    if (!z) dfs(pos + 1, nc);
                } else {
                    if (vc != -1) {
                        if (vc == z) dfs(pos + 1, nc);
                    } else if (!used[z] && (!lead[c - 'A'] || z)) {
                        m[c - 'A'] = z; used[z] = true;
                        dfs(pos + 1, nc);
                        used[z] = false; m[c - 'A'] = -1;
                    }
                }

                if (asgB) { used[y] = false; m[b - 'A'] = -1; }
            }
            if (asgA) { used[x] = false; m[a - 'A'] = -1; }
        }
    };
    dfs(0, 0);
    return (int)ans;
}

Chia sẻ Q&A này