Alphametics

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

Alphametics 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 & Techniques

I'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 

bulletDownload project source    
bulletDownload executable 

Suggestions for Further Explorations

A 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-2017, Gary Darby    All rights reserved.