Aaron Gadberry

Help – v. helped, help·ing, helps

Was this site helpful?
My Amazon.com Wishlist

Cryptarithmatic

26th January 2006 - By Paradochs

Original Assignment

Write a program to solve a simple class of cryptarithmetic problems MORE EFFICIENTLY THAN BY BRUTE FORCE (EXHAUSTIVE SEARCH) by using deductions about even/odd, digit range, etc. For example, in the test case

CADET
+CORPS
———
TROOP

given below your program can deduce that C<5. (You do not have to use this deduction; this is just an example of a deduction which would reduce the search space.) By convention, each letter stands for a different digit and there are no leading zeroes. You program should read strings (hint: in C, use fgets), right justify the strings to make an addition problem, and find a solution. If there is more than one solution, you only need to find one. For the example in Figure 5.2, the input would be TWO TWO FOUR Run your program on this example plus the following: JAVA OOP LANG CADET CORPS TROOP KYLE FIELD AGGIE The grader will also run your project on additional problems. You may assume the input contains only upper case letters, and no more than 10 different letters.

My Solution

Firstly, I did not find one answer. I found them all.
Second, I found them all in under a second in every case I tried
Third, parts of the code and design may not be pretty, but they went way above and beyond the requirements and the time frame I was given to code this.

Data & Algorithm

I set up data structures to hold all of the possible values of every letter. Yes, all 26 letters. There can only be 10 unique letters in each puzzle though.

The next thing I did was to try and narrow down each of those lists using simple rules. The easiest rule is that if the character doesn’t appear in the puzzle, it has no possible values. That eliminates at least 160 numbers in your list (16 letters * 10 numbers).

There are several other rules that can be stated.

Rules

  1. If the two letters added together are identical characters, the one below them must be even. That eliminates half of the numbers available for that character.
  2. If the far two characters that add together are different, but the character they add up to be is the same as one of them, the other one must be equal to 0. ( A+B=A : B=0) Note: This only works for the far right-hand column as other columns might have a carry.
  3. On the far left columns, if the answer word is longer than both the added words, the farthest left digit of the answer word is a 1.

I believe these are the only ones I implemented, but there might be more and better ones out there if you think hard enough.

I then order the characters from the top right to the bottom left, going down first. IE for the example with JAVA above, the order would be APGVONJL. Only count each character once and do it in the order you naturally add in. This is the order in which I solved.

I then did a brute force set of for loops, in which I set every letter to the numbers it could possibly be, starting the outside loop with the first letter of the solving order (above). After every time I set three characters, I test the partial results. If the numbers that are set add up, then I continue with the rest of the for loops. If is doesn’t add up, then I break back down a loop and continue the iterations of the previous number. By doing this I find problems early in the assigning of numbers and incredibly reduce the amount of time needed to find all solutions. I record the number of solutions I take to completion and the number of correct answers. Because my program finds most of the problems before assigning all of the numbers, the number of completed assignments is not much greater than the number of solutions in most cases.

Web Based Attempt

I tried to put this on the web using a php script and html forms. I never could get it working quite right due to compiling issues on the server (ie we don’t allow compiling on the server). I tried using a virtual machine with the same OS as the server, but to no triumph. If anyone has any tips on how to get it to work, let me know.

Files and C++ Code

This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.

3 Responses to “Cryptarithmatic”

  1. indu Says:

    hey,

    tht was cool. wud da src code wrk on a vc++ compiler??

    thanks
    I.

  2. Travis Says:

    I agree, it was a fun project to work on.

    I don’t remember which compiler I used. Could have been VS.net, gcc, or any number of others. It should compile (or almost compile) on most compilers because it is a only a console application with some input/output and some math.

  3. Travis Says:

    Oh, I see at the bottom that it was VS.net.
    I recommend just trying it and seeing if it will compile. It’s all available.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>