AlphameticsAlphametics are puzzles in which letters are substituted for the digits in an arithmetic calculation, and the words formed by the operands and answer produce a sensible phrase. The goal is to find the digits that can be substituted for the letters to produce a correct addition statement.Consider the program demonstrated to the right. It decomposes each command line argument into its constituent characters, sorts the characters, goes through all permutations of all combinations of 10 digits taken 4 at a time in search of the solution, reports each solution, and the total number of permutations tested. How does a person solve this puzzle? How should a program go about solving this puzzle? Is it possible and desirable to enumerate and test all combinations of the digits '0' through '9'? Do you need to test all permutations of each combination? Can you compute the total number of permutations and combinations that will need to be tested? For example: is there a formula that will give you the total number of permutations of all combinations of 10 digits taken 4 at a time? The following class is available upon request.
int* digits = new int[ number_of_letters ];
// Enumerate all combinations of 10 digits taken
// "number_of_letters" at a time
Combinations combos( 10, number_of_letters );
while (combos.next( digits ))
{
...
}
The standard library of C++ provides the function "bool
next_permutation(array)". It allows the user to
enumerate all permutations of the supplied array.What indirection (e.g. data structures) would offer interesting leverage?
Notice the "three three two two one" puzzle below – in addition to the normal puzzle dimension, the numbers named actually add up to "eleven" as well.
A cradle-to-grave discussion of Alphametics
Here is a skeleton you might consider ...
// Find all the letters, and put them in a sorted
// list
map<char,int> letters;
// Create an array of digits that is the same size
// as the array of letters
int* digits = new int[ letters.size() ];
// Report the array of letters
// Iterate through all combinations, and all
// permutations of each combination
Combinations combos( 10, number_of_letters );
while (combos.next( digits ))
do {
.
.
// Test each permutation & report the answer
.
.
} while (next_permutation( digits ));
impl
|
% alphametics i did too
d i o t
1 9 0 2
i 9
did 191
--- ---
too 200
count is 5040
% alphametics hes the best
b e h s t
1 2 4 6 8
hes 426
the 842
---- ----
best 1268
count is 30240
% alphametics no no too late
a e l n o t
0 2 1 7 4 9
no 74
no 74
too 944
---- ----
late 1092
count is 151200
% alphametics base ball games
a b e g l m s
4 7 3 1 5 9 8
base 7483
ball 7455
----- -----
games 14938
count is 604800
% alphametics usa ussr peace
a c e p r s u
2 7 0 1 8 3 9
usa 932
ussr 9338
----- -----
peace 10270
count is 604800
% alphametics send more money
d e m n o r s y
7 5 1 6 0 8 9 2
send 9567
more 1085
----- -----
money 10652
count is 1814400
% alphametics three three two two one
e h l n o r t v w eleven
1 4 7 9 3 6 8 2 0
three 84611
three 84611
two 803
two 803
one 391
------ ------
eleven 171219
count is 3628800
% alphametics double double toil trouble
b d e i l o r t u
0 7 4 3 6 9 5 1 8
double 798064
double 798064
toil 1936
------- -------
trouble 1598064
count is 3628800
% alphametics world trade center
a c d e l n o r t w
0 1 4 2 8 9 3 6 7 5
world 53684
trade 76042
------ ------
center 129726
count is 3628800
% alphametics this isa great time waster
a e g h i m r s t w
0 4 9 6 2 3 7 8 5 1
this 5628
isa 280
great 97405
time 5234
------ ------
waster 108547
count is 3628800
|