Programming assignments 3 and 4 (Do NOT work in groups for programming assignments.)

A cryptarithm is a puzzle in which letters are substituted for numbers in an equation. The term was coined by Maurice Vatriquant in 'Sphinx' magazine in 1931. The following are examples of cryptarithms:

S E N D
M O R E
G O L D
M O N E Y / 5 4 7 8
1 6 2 4
9 6 3 8
1 6 7 4 0
V E N U S
- E A R T H
M A R S / 5 4 7 3 9
4 6 1 2 0
8 6 1 9

NO HEAR LINDON
GUN THOSE * B

+ NO +THREE JOHNSON
HUNT CHEERS

In this assignment, you are to use PERL to find the solution for cryptarithms. Our puzzles will be stated as a string. For example,

$puzzle = “SEND+MORE+GOLD==MONEY”;

You will write the solution as:

5478+1624+9638==16740

Part 1 (Program 3, 20 points)

If we use tr to translate the unique letters of the $puzzle (namely YMRLESONDG) into the digits 0-9, the puzzle becomes 5478+1624+9638==16740

Then, we can directly evaluate $puzzle using the perl function eval. If it returns true, we have found the correct mapping. Pretty slick, huh?

WARNING: Anything that begins with a 0 is treated as octal, so

a solution to “NO+GUN+NO=HUNT” is found as “52+135+52==0357” because 0357 is in octal. Let’s just consider that a feature and accept it.

To do this, we need two helper functions which you will write:

Function 1 (10 points):

findunique: Given the puzzle, findunique returns a string of all the unique letters. The returned string should be of length ten, so you may need to pad with spaces for some inputs.

$char = &findunique($puzzle);

So for example $char might be SONYEMDRGL

Test this function for both puzzles.

Function 2 (10 points):

docheck($soln,$puzzle) returns the puzzle (with the replacement) if $soln represents a solution to $puzzle and returns 0 otherwise.

If $soln= “YMRLESONDG" this means you are asking docheck to see if Y=0, M=1,R=2,L=3,E=4,S=5,O=6,N=7,D=8,G=9 is a solution to the puzzle.

So the call might look like:

$res = &docheck("YMRLESONDG",$puzzle);

if ($res) { print "The solution is $res";}

Verify docheck works by testing it with several solution strings and puzzles.

HINT: I found myself using a variety of things such as split, join, tr, and eval.

Part 2 (Program 4, 20 points)

Finish the assignment by finding all solutions to a provided puzzle. You can do this any way you like. The following is only a suggestion. You do not need to solve the problem this way.

Suggestion:

Write a recursive function to permute the unique letters of the puzzle so that all possible permutations are found. Note, that you do not expect this to run quickly as the number of permutations is ten factorial! Show that your permutation routine works by showing all permutations of “ABCD”. (This is a good testing technique. Try with something small so you can follow the recursion and it doesn’t take forever.)

HINT: you will need to worry about the distinction between local variables and global variables. Remember that in PERL, all variables are global unless specified otherwise. Thus, your parameters and even your loop variables need to be declared as local.

The following is a C++ version of the permute algorithm.

// v is the array of integers to be sorted

// start is the current location in the array (you are only to worry about permuting from start to the end)

// n is the length of the array

//Given an array of v with the elements before start fixed, print out all copies of v with the //remaining elements permuted.

void permute(int v[], int start, int n)

{

if (start == n-1) {

print(v, n);

}

else {

for (int i = start; i < n; i++) {

int tmp = v[i];

v[i] = v[start];

v[start] = tmp;

permute(v, start+1, n);

v[start] = v[i];

v[i] = tmp;

}

}

}

Finally: Using all the pieces you have created, solve the puzzle.

In our case, create a version of the permute function which calls docheck with each permutation instead of printing a permutation. (Leave the printing version of permute in place for grading purposes.) Try each permutation of your unique letters in docheck until all solutions are found. This is slow, so put your feet up and take a nap while you churn out the answer. During debugging, I found myself wanting some feedback from the brute force trials. I did this via a statement like: if ($ct++ %500 == 0){print "=> @all";} to periodically print out the permutations I was considering in the recursion.