[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionAlphametics are word arithmetic problems where each letter value is associated one to one with a specific digit 0-9. This means that no 2 letters are assigned the same digit values and no 2 digits are assigned to the same letter. Also the value assigned to a letter that starts a word cannot be 0. The first published Alphametic was in 1924 by a well known puzzler, H.E. Dudeney (SEND + MORE = MONEY). The problem here is to write a program to solve Alphametics. Background & TechniquesI'm sure there are lots of techniques to improve an exhaustive search algorithm, but for this first cut, we'll just brute force it - try all possible arrangements of numbers assigned to letters. This is the first program with 2 units - I've taken the permutations code developed in the Permutes1 program and turned it into functions in a separate unit, U_Permutes. The main unit, U_Alphametics, has a Uses U_Permutes clause at the top of the Implementation section so that Delphi knows where to find the new functions. The plan is to scan the input text equation and extract two pieces of information. We'll make one string with all of the unique characters, call it AllChars, that we can use to associate with trial arrangements of digits. Let's says that there are R different letters - then the length of Allchars string is R. Secondly, we'll build an array of words be added up and a final string with the result word. Once this is done, we can start testing all arrangements of R digits out of 10. I wrote two functions to retrieve the permutations - InitPermutes(R,N:integer) initializes things to retrieve all arrangements of R things selected from N. It also returns as count of total permutations. This is used to display progress as the program runs. Function GetnextPermute (var s: array of integer):boolean returns value true and the next arrangement to try in array S as long as there are more to try. It returns false when all permutations have been returned. For each arrangement, we'll translate the letters to digits by assigning the first digit in S to the first letter in AllChars string, the 2nd digit to the 2nd letter, etc. After we do this, we can evaluate each word, add up the values and compare them to the value of the word to the right of the equals sign. Running/Exploring the Program
Suggestions for Further ExplorationsA bug: I just realized that Alphametics returns too many solutions. It doesn't exclude solutions that replace the first letter of a word with 0. Have a try at fixing it for me. (Oops - I think I might have fixed it already.) We could work on speeding up the calculations. When I get to it, I'll write a page on how to add timing to a program so that we could compare before and after run times. One obvious one, as in SEND+MORE=MONEY is to preset M to 1 - since S+M+possible carry=MO, M must be 1. We would then exclude M from the Allchars string, reduce R by one and reducing run times by a significant factor. Google found 291 hits on Alphametics if you want to learn more. The Alphametics web page has many additional examples.
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |