Solve a Three-Letter Alphametic
Autumn Tournament (2007)
Submission name: rebus.cpp
Problem summary
Replace each used letter A, B or C with a decimal digit so that the given addition is correct. Different letters require different digits. Print any solution without leading zeros in multi-digit numbers.
Input
One expression X+Y=Z containing only A, B, C, + and =.
Output
The same expression with its letters replaced by a valid digit assignment.
Constraints
Each number has at most 9 letters. There is exactly one + and one =. A solution is guaranteed.
Worked example
Original statement sample.
Input
AB+B=BA
Output
89+9=98
Solution analysis
- There are at most three letters, so try digit choices for A, B and C. Requiring three distinct choices gives only 10·9·8=720 assignments. Assigning unused letters too is harmless: at most three of ten digits are needed.
- Split the expression at + and =. For each assignment reject a multi-digit word whose first letter receives zero. Convert each word left to right using value=10·value+digit, and test whether the first two sum to the third.
- For AB+B=BA, the equality is 10A+2B=10B+A, or 9A=8B. A=8 and B=9 satisfy it, giving 89+9=98. A single-letter number may legally be zero.
Why it works
The loops enumerate every injective digit assignment to the used letters. Leading-zero checks remove precisely the forbidden representations. Integer evaluation tests the exact equality, so the first accepted assignment is a valid solution; the guarantee ensures one exists.
Watch out. Do not require an unused letter to occur. Reject leading zeros only for words longer than one character. Constructive solutions need not match a particular sample assignment.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<string>
using namespace std;
long long valueOf(const string&word,const array<int,3>&digit){
if(word.size()>1&&digit[word[0]-'A']==0){
return -1;
}
long long value=0;
for(char letter:word){
value=10*value+digit[letter-'A'];
}
return value;
}
int main(){
string expression;
cin>>expression;
size_t plus=expression.find('+');
size_t equals=expression.find('=');
string first=expression.substr(0,plus);
string second=expression.substr(plus+1,equals-plus-1);
string result=expression.substr(equals+1);
for(int a=0;a<=9;a++){
for(int b=0;b<=9;b++){
for(int c=0;c<=9;c++){
if(a==b||a==c||b==c){
continue;
}
array<int,3>digit{a,b,c};
long long x=valueOf(first,digit);
long long y=valueOf(second,digit);
long long z=valueOf(result,digit);
if(x>=0&&y>=0&&z>=0&&x+y==z){
// Replace letters only; preserve the two operators.
for(char symbol:expression){
if(symbol>='A'&&symbol<='C'){
cout<<digit[symbol-'A'];
}
else{
cout<<symbol;
}
}
cout<<'\n';
return 0;
}
}
}
}
}