alphametic.cpp

#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>

using namespace std;

int countBit(unsigned int n)
{
    n = (0x55555555 & n) + (0x55555555 & (n >> 1));
    n = (0x33333333 & n) + (0x33333333 & (n >> 2));
    n = (0x0F0F0F0F & n) + (0x0F0F0F0F & (n >> 4));
    n = (0x00FF00FF & n) + (0x00FF00FF & (n >> 8));
    n = (0x0000FFFF & n) + (0x0000FFFF & (n >> 16));
    return n;
}

vector<vector<int>> get_combinations(int n)
{
    vector<vector<int>> ret;
    if (n < 1 || 10 < n) return ret;

    unsigned int N = 1 << 10;
    for (unsigned int i = 0; i < N; ++i)
    {
        if (countBit(i) == n)
        {
            vector<int> tmp;
            unsigned int t = i;
            for (int j = 0; j < 10; ++j)
            {
                if (t & 1) tmp.push_back(j);
                t >>= 1;
            }
            ret.push_back(tmp);
        }
    }
    return ret;
}

vector<vector<int>> get_permutations(int n)
{
    vector<vector<int>> ret;
    if (n < 1 || 10 < n) return ret;

    vector<vector<int>> data = get_combinations(n);
    for (auto list : data)
    {
        do {
            ret.push_back(vector<int>(list));
        } while (next_permutation(list.begin(), list.end()));
    }
    return ret;
}

int main()
{
    string param1 = "SEND";  cin >> param1;
    string param2 = "MORE";  cin >> param2;
    string answer = "MONEY"; cin >> answer;

    string params[3] = {param1, param2, answer};

    set<char> st;
    for (auto s : params) for (auto c : s) st.insert(c);

    int len[3];
    for (int i = 0; i < 3; ++i)
        len[i] = params[i].length();

    cout << endl;

    int maxLen = max({len[0], len[1], len[2]});
    int cntAns = 0;
    vector<vector<int>> perm = get_permutations(st.size());
    for (auto list : perm)
    {
        map<char, int> table;
        int i = 0;
        for (auto a : st)
        {
            if (table.find(a) == table.end())
                table[a] = list[i++];
        }

        if (table[params[0][0]] == 0) continue;
        if (table[params[1][0]] == 0) continue;
        if (table[params[2][0]] == 0) continue;

        int ans[] = {0, 0, 0};
        for (int j = 0; j < 3; ++j)
        {
            for (int k = 0; k < len[j]; ++k)
            {
                ans[j] += table[params[j][k]] * pow(10, len[j] - k - 1);
            }
        }

        if (ans[0] + ans[1] == ans[2])
        {
            cout << "  " << setw(maxLen + 1) << ans[0] << endl;
            cout << "+)" << setw(maxLen + 1) << ans[1] << endl;
            cout << string(maxLen + 4, '-') << endl;
            cout << "  " << setw(maxLen + 1) << ans[2] << endl;
            cout << endl;

            for (auto c : st)
            {
                //cout << c << " = " << table[c] << endl;
            }
            //cout << endl;

            ++cntAns;
        }
    }

    cout << "Answers: " << cntAns << endl;
    return 0;
}