/* This program will solve puzzles called Alphametics or Cryptarithms. */
/* It can also be used to find new puzzles. */
/* */
/* For an explanation of this type of puzzle and a description of how */
/* to run this program either invoke the program with the -help switch */
/* or look at the function print_usage below. */
/* */
/* I have written this to be as fast as possible because the procedure */
/* of looking for these puzzles given a set of words is quite time */
/* intensive. Because of this, I haven't broken up the functions into */
/* as small units as would be good for readability. I previously */
/* wrote a program to solve this sort of puzzle and did it using */
/* recursion. It was cleaner and easier to understand, but it was */
/* significantly slower. This program uses a single function to find */
/* solutions to a puzzle and it makes no function calls. I have */
/* commented the code well, but it's still not as clear as a slower */
/* more modular layout would have been. */
/* */
/* This program was written in C++, although it doesn't use any */
/* classes. It wouldn't be too difficult to convert to C. I used */
/* stdio.h rather than stream.h to save executable size. */
/* */
/* Here are some examples of puzzles that this can solve or generate: */
/* */
/* I SEND */
/* +BB +MORE */
/* --- ----- */
/* ILL MONEY */
/* */
/* Try swp -solve send more money */
/* swp -find money hello send goodbye more */
/* */
/* Both solving puzzles and looking for them can be done by invoking */
/* with just the -solve or -find argument and letting the program */
/* prompt for the appropriate input. This allows more flexibility */
/* particularly with -find. The base to use as well as what puzzles */
/* are acceptable can be specified if just the command line isn't */
/* used. */
/* */
/* By Truman Collins */
/* 1988 */
/* May and June 1998 */
/* */
/* Copyright 1998 by Truman Collins */
#include
#include
#include
#include
#include
typedef unsigned long ulong;
/* For the sake of efficiency, we limit the maximum base to 16 and */
/* the maximum length of a string to 16 characters. These can */
/* be increased. MAX_BASE can be increased arbitrarily. MAX_LEN */
/* must be increased by powers of two and MAX_LEN_SHIFT must be */
/* increased so that 2^MAX_LEN_SHIFT == MAX_LEN */
const int MAX_BASE = 16;
const int MAX_LEN = 16;
const int MAX_LEN_SHIFT = 4;
/* We won't allocate an array for the summands, but will use a */
/* static one if there are this many or fewer. */
const int MAX_STATIC_SUMMANDS = 6;
const int MAX_WORDS = 2000;
/* Min and max inlines. */
int min_of_two(int x, int y)
{
return((x < y) ? x : y);
}
int max_of_two(int x, int y)
{
return((x > y) ? x : y);
}
/* Define this to 1 to print the estimated difficulty of solved */
/* and found puzzles. Define to 0 if you don't want the difficulty printed. */
#define DIFF_PRINT 0
/* I have included some pretty verbose debugging code. If DEBUG_SOLVE_FLAG */
/* is defined then the debug code will be compiled and executed for the */
/* solve function. If DEBUG_FIND_FLAG is defined, then debugging will be */
/* enabled for finding puzzles. When these are not defined, no debugging */
/* will be generated. */
/* #define DEBUG_SOLVE_FLAG */
#ifdef DEBUG_SOLVE_FLAG
#define DBG_SOLVE(statement) { \
statement \
}
#else
#define DBG_SOLVE(statement)
#endif
/* #define DEBUG_FIND_FLAG */
#ifdef DEBUG_FIND_FLAG
#define DBG_FIND(statement) { \
statement \
}
#else
#define DBG_FIND(statement)
#endif
void print_solution(
int number_map[128],
int map_count[128]
)
/* Print the mappings for this solution. The mappings will be in */
/* alphabetical order. */
{
int i;
for(i = 0; i < 128; i++) {
/* Test map_count because number_map is not initialized. */
if(map_count[i]) {
printf("%c=%d ", (char) i, number_map[i]);
}
}
printf("\n");
}
int difficulty_conv(
ulong backtracks
)
/* Return a difficulty rating based on the number of backtracks. */
{
if(backtracks <= 100) {
return(1);
}
if(backtracks <= 600) {
return(2);
}
if(backtracks <= 4000) {
return(3);
}
if(backtracks <= 20000) {
return(4);
}
return(5);
}
/* Macro to simulate multi-dimensional array reference. */
/* Note that this can't be an inline because the array is internal to the */
/* function. Used only by the solve function. */
#define summand_char(row, column) (reform_smnds[((row) << MAX_LEN_SHIFT) + \
(column)])
int solve(
char **summands, /* An array of pointers to the summands. */
int summand_count, /* The number of summands. */
int *summand_lengths, /* An array with the lengths o the summands. */
int longest_summand, /* The number of chars in the longest summand. */
char *sum, /* The word representing the sum. */
int base, /* The base to solve the puzzle in. */
int print, /* 1 if results to be printed, 0 otherwise. */
int just_one, /* 1 if to leave after first solution. */
int *difficulty /* The difficulty on a scale of 1 to 10. */
)
/* This function will find solutions to the given alphametic puzzle. */
/* It returns the number of solutions found. If just_one is set to */
/* a non-zero value, the function will return after finding the first */
/* solution. If print is set to a non-zero value, each solution found */
/* will be printed to stdout. */
/* I have written this to be as fast as possible because one of its */
/* intended uses is to check a huge number of potential puzzles for */
/* ones that have a solution. Because searches of this kind can be */
/* very time consuming, even small efficiencies in this function are */
/* significant. Because of this, all of the work is done is this one */
/* function, so it is very long. I had previously written a recursive */
/* version of this that was more easily understandable, but it was */
/* significantly slower. */
{
int allocated_smnds_array;
int backtrack;
ulong backtrack_count = 0;
char *ch_p;
int column;
int column_lengths[MAX_LEN + 1];
char curr_char;
int curr_column;
int curr_smnd_row;
int i, j;
char letter_map[MAX_BASE];
char letter_used[128];
int map_count[128];
int min_possible;
int min_value[128];
int max;
int max_carry[MAX_LEN + 1];
int max_digit = base - 1;
int max_possible;
int max_value[128];
int needed_carry[MAX_LEN];
int needed_sum;
int number_map[128];
char *reform_smnds;
char smnd_char;
int solutions_found = 0;
char static_summands[MAX_LEN * MAX_STATIC_SUMMANDS];
int sum_length = 0;
int total_letters_used = 0;
int value;
int zero_or_one_start[128];
/* Initialize in case of an error. */
*difficulty = 0;
/* Figure out the length of the sum and at the same time count */
/* the different characters used in the sum. We will later */
/* add to this count to find the number of different letters */
/* used in the whole puzzle. */
memset(letter_used, 0, sizeof(letter_used));
for(ch_p = sum; *ch_p; ch_p++) {
if(letter_used[*ch_p] == 0) {
letter_used[*ch_p] = 1;
total_letters_used++;
}
sum_length++;
}
/* See if any of the strings is too long. If so print message */
/* and return zero. */
if(sum_length > MAX_LEN || longest_summand > MAX_LEN) {
printf("Words must all be %d characters or less.\n", MAX_LEN);
return(0);
}
/* If a summand is longer than the sum, then there is no solution. */
if(longest_summand > sum_length) {
return(0);
}
/* Initialize column lengths and needed_carry to 0. */
memset(column_lengths, 0, sizeof(column_lengths));
memset(needed_carry, 0, sizeof(needed_carry));
/* Initialize the array used to count mappings for each character. */
memset(map_count, 0, sizeof(map_count));
/* Initialize the lowest value for each character to be zero. We */
/* later set those letters at the front of strings to one. */
memset(zero_or_one_start, 0, sizeof(zero_or_one_start));
/* Because malloc is somewhat expensive, and this routine needs to */
/* be as fast as possible, only allocate this array if there are */
/* too many summands to fit in the array on the stack. This one */
/* will hold MAX_STATIC_SUMMANDS. */
if(summand_count <= MAX_STATIC_SUMMANDS) {
reform_smnds = static_summands;
allocated_smnds_array = 0;
} else {
reform_smnds = malloc(MAX_LEN * summand_count);
allocated_smnds_array = 1;
}
/* Zero the array used to map numbers to characters. */
memset(letter_map, 0, sizeof(letter_map));
/* Reformat summands. We want the columns to match with the */
/* sum string, but we want all of the letters crammed up to */
/* the top rows. For example: */
/* */
/* I S E N I S */
/* I T A I T */
/* N O T => O T */
/* E A S Y S Y */
/* T O T O */
/* */
/* We don't care what's in the other places since the */
/* column_lengths array keeps us from accessing a character */
/* that's not filled. */
/* While we're doing this, we note those characters at the */
/* front of the strings to insure that they can't be set */
/* to zero. We also count the number of different characters */
/* in the puzzle. We will use this to insure there aren't */
/* more characters than digits. */
for(i = 0; i < summand_count; i++) {
for(j = 0; j < summand_lengths[i]; j++) {
column = sum_length - (summand_lengths[i] - j);
curr_char = summands[i][j];
summand_char(column_lengths[column], column) = curr_char;
column_lengths[column]++;
/* Note which letters are used. */
if(letter_used[curr_char] == 0) {
letter_used[curr_char] = 1;
total_letters_used++;
}
/* If this is the first character in a string make sure it */
/* can never be set to zero. */
if(j == 0) {
zero_or_one_start[curr_char] = 1;
}
}
}
/* Note that the first letter of the sum also can't be a zero. */
zero_or_one_start[sum[0]] = 1;
/* See if we have more letters than digits, in which case a */
/* solution is impossible. */
if(total_letters_used > base) {
if(allocated_smnds_array) {
free(reform_smnds);
}
return(0);
}
/* Figure out what the maximum carry is from each column. */
/* Note that the max carry from a specific column can depend */
/* on the max carry on the column immediately to the right. */
/* We initialize the max carry of the column one past the */
/* last one to zero. */
/* There is one possible improvement here and that is to do */
/* some analysis of the letters in each column. If they are */
/* different, then the highest total from that row is a bit */
/* less than the number of summands times the max digit. */
/* This improvement is probably more expensive than it's */
/* worth. */
max_carry[sum_length] = 0;
for(i = sum_length - 1; i >= 0; i--) {
max_carry[i] = (max_digit * column_lengths[i] +
max_carry[i + 1]) / base;
}
/* When debugging, print out the summands in their new form. */
DBG_SOLVE(
for(i = 0; i < summand_count; i++) {
for(j = 0; j < MAX_LEN; j++) {
if(i < column_lengths[j]) {
printf("%c", summand_char(i, j));
} else {
printf(" ");
}
}
printf("\n");
}
for(i = 0; i < strlen(sum); i++) {
printf("-");
}
printf("\n%s\n", sum);
);
/* Now all of the initialization is done and it is time to start */
/* the analysis. We start at the leftmost character in the sum */
/* and work our way up the column of summands above. When we get */
/* to the top of it, we move to the next sum character and continue. */
/* At each point we determine the possible values the current */
/* character could take and for each one of these values, try all */
/* downstream possibilities. If we find a value for the topmost */
/* summand in the rightmost column and no carry is required from */
/* the next column, we have a solution. When we run across a */
/* dead end, we backtrack to the previous character. */
/* We start with column 0 and the first move isn't a backtrack. */
curr_column = 0;
backtrack = 0;
while(1) {
/* See if we've found a solution */
if(curr_column == sum_length) {
/* This is only a solution if the needed carry here is zero. */
/* Even if it isn't we need to backtrack from here. */
if(needed_carry[curr_column] == 0) {
/* Record that we found a solution and print it if desired. */
/* backtrack to the previous column. */
solutions_found++;
if(print) {
print_solution(number_map, map_count);
}
/* If we just wanted to see if there were any solutions, */
/* return right now. */
if(just_one) {
if(allocated_smnds_array) {
free(reform_smnds);
}
return(1);
}
}
/* Backtrack and see if we can find another. */
curr_column--;
curr_smnd_row = 0;
backtrack = 1;
smnd_char = summand_char(curr_smnd_row, curr_column);
/* We want to skip looking at the sum character in this column */
/* because there isn't one. */
} else {
/* We're now working on the sum character in the */
/* curr_column position. There are two main */
/* possibilities. Either we are moving forward at this */
/* time, or we are backtracking to this location. If */
/* we're moving forward, we either use a value chosen */
/* earlier in the search for this letter, or if this is */
/* the first occurance, select a value to try. If we're */
/* backtracking at this point, either select the next */
/* available value for this letter, or if it already has a */
/* value then backtrack more. After dealing with the */
/* value for this letter, we will either move forward and */
/* investigate the values of the summands above, or we'll */
/* backtrack again. */
curr_char = sum[curr_column];
DBG_SOLVE(
if(backtrack) {
printf("Back");
} else {
printf("Forward");
}
printf(" to sum char %c(%d)...", curr_char, curr_column);
);
if(backtrack) {
/* We got here by backtracking, so we assigned this character a */
/* value the last time through. */
if(map_count[curr_char] == 1) {
/* This was the first occurance of this character. Since */
/* we've backtracked to here, try to find the next available */
/* number in the range. */
value = number_map[curr_char];
letter_map[value] = '\0';
do {
value++;
} while(value <= max_value[curr_char] &&
letter_map[value] != '\0');
if(value > max_value[curr_char]) {
/* We didn't find an available number in the range so */
/* we want to backtrack from here. */
backtrack = 1;
backtrack_count++;
map_count[curr_char]--;
DBG_SOLVE(
printf("no more values in range.\n");
);
} else {
/* Go forward with this new value. No change in map_count */
/* for this character because we unmapped one and mapped */
/* another. */
backtrack = 0;
letter_map[value] = curr_char;
number_map[curr_char] = value;
DBG_SOLVE(
printf("next value in range: %d\n", value);
);
}
} else {
/* Since there is another one of these characters mapped */
/* behind us, we can't change the mapping here. We want */
/* to backtrack. Decrement the number of times this */
/* character has been mapped. The letter itself is still */
/* mapped from a previous character. */
backtrack = 1;
backtrack_count++;
map_count[curr_char]--;
DBG_SOLVE(
printf("previously mapped character.\n");
);
}
} else {
/* Here, we've moved forward to this sum character. */
if(map_count[curr_char]) {
/* A value has already been chosen for this character. Use */
/* it and move on. */
value = number_map[curr_char];
map_count[curr_char]++;
DBG_SOLVE(
printf("previously chosen value %d\n", value);
);
} else {
/* Here no value has been chosen for this letter. We */
/* will determine the range of values that could work */
/* for it and choose the first available to try. */
/* The min is always going to be either zero or one. */
/* It's one only if this letter is at the beginning of */
/* one of the words. The max is a little more */
/* complicated. It is the maximum that the summands in */
/* this column can add up to plus the maximum carry */
/* from the next column minus the needed carry times */
/* the base here. */
min_value[curr_char] = zero_or_one_start[curr_char];
max_possible = max_carry[curr_column + 1] +
max_digit * column_lengths[curr_column] -
needed_carry[curr_column] * base;
max_value[curr_char] = min_of_two(max_digit, max_possible);
DBG_SOLVE(
printf("range chosen [%d-%d] ", min_value[curr_char], max_
value[curr_char]);
);
/* Find the first available value in this range. If there */
/* aren't any available, then we will backtrack. */
value = min_value[curr_char];
while(value <= max_value[curr_char] &&
letter_map[value] != '\0') {
value++;
}
if(value > max_value[curr_char]) {
/* We didn't find an available number in the range so */
/* we want to backtrack from here. */
backtrack = 1;
backtrack_count++;
DBG_SOLVE(
printf("none available.\n");
);
} else {
backtrack = 0;
map_count[curr_char]++;
letter_map[value] = curr_char;
number_map[curr_char] = value;
DBG_SOLVE(
printf("using %d\n", value);
);
}
} /* else */
} /* else */
/* Okay, we've come to this sum character either by backtracking */
/* or not and we've decided what to do from here. Now we check */
/* how the backtracking flag is set now to determine where to */
/* go from here. We make sure needed_sum is updated appropriately. */
if(backtrack) {
/* Move to the previous column and set to the summand with */
/* index zero. We set needed_sum to what the code for a */
/* summand will expect. We need to to check for a column */
/* without summands */
needed_sum = needed_carry[curr_column];
curr_column--;
if(curr_column == -1 || column_lengths[curr_column] == 0) {
curr_smnd_row = -1;
} else {
curr_smnd_row = 0;
}
} else {
/* Move on to the highest index summand in this column, and */
/* compute the needed sum. Also do some bookkeeping. */
curr_smnd_row = column_lengths[curr_column] - 1;
needed_sum = value + base * needed_carry[curr_column];
/* Check for no summands here. If there aren't any, */
/* curr_smnd_row will be set to -1 and we will skip the */
/* summand work below and move directly to the next sum */
/* character. We have to update the needed carry for */
/* the new column in this case. */
if(curr_smnd_row < 0) {
curr_column++;
needed_carry[curr_column] = needed_sum;
continue;
}
}
} /* else */
/* We now have a summand to look at. The variable curr_column */
/* indicates the column of the puzzle we're working on and the */
/* variable curr_smnd_row indicates the specific summand letter */
/* from zero to the number of summands minus one. The other */
/* relevant value here is needed_sum, which indicates the sum */
/* required for the summands from this one up to index zero and */
/* the carry from the next column. */
/* First check if we've backtracked off the left end, in which */
/* case we've checked all possibilities. */
if(curr_column == -1) {
break;
}
/* See if we're done. If we've gone through all of the possibilities */
/* for the first sum character, then we've tried it all. */
while(curr_smnd_row >= 0) {
curr_char = summand_char(curr_smnd_row, curr_column);
DBG_SOLVE(
if(backtrack) {
printf("Back");
} else {
printf("Forward");
}
printf(" to summand char %c(%d)...", curr_char, curr_column);
);
/* We need to see whether we came to the current character */
/* moving forward or backtracking. */
if(backtrack) {
/* We backtracked here. */
if(map_count[curr_char] == 1) {
/* This was the first occurance of this character. Since */
/* we've backtracked to here, try to find the next available */
/* number in the range. */
value = number_map[curr_char];
needed_sum += value;
letter_map[value] = '\0';
do {
value++;
} while(value <= max_value[curr_char] &&
letter_map[value] != '\0');
if(value > max_value[curr_char]) {
/* We didn't find an available number in the range so */
/* we want to backtrack from here. */
backtrack = 1;
backtrack_count++;
map_count[curr_char]--;
DBG_SOLVE(
printf("no more values in range.\n");
);
} else {
/* Go forward with this new value. */
backtrack = 0;
letter_map[value] = curr_char;
number_map[curr_char] = value;
DBG_SOLVE(
printf("next value in range: %d\n", value);
);
}
} else {
/* Since there is another one of these characters mapped */
/* behind us, we can't change the mapping here. We want */
/* to backtrack. */
backtrack = 1;
map_count[curr_char]--;
needed_sum += number_map[curr_char];
DBG_SOLVE(
printf("previously mapped character.\n");
);
}
} else {
/* We are to move forward. */
if(map_count[curr_char]) {
/* A value has already been chosen for this character. Use */
/* it and move on. */
value = number_map[curr_char];
/* See if this value is too big or not. */
if(value > needed_sum) {
backtrack = 1;
backtrack_count++;
DBG_SOLVE(
printf("previously chosen value %d too large\n", value)
;
);
} else {
map_count[curr_char]++;
backtrack = 0;
DBG_SOLVE(
printf("previously chosen value %d\n", value);
);
}
} else {
/* Here no value has been chosen for this letter. We */
/* will determine the range of values that might work */
/* for it and choose the first available to try. */
min_possible = needed_sum - max_digit * curr_smnd_row -
max_carry[curr_column + 1];
min_value[curr_char] = max_of_two(min_possible,
zero_or_one_start[curr_char]);
max_value[curr_char] = min_of_two(max_digit, needed_sum);
DBG_SOLVE(
printf("range chosen [%d-%d] ", min_value[curr_char], max_
value[curr_char]);
);
/* Find the first available value in this range. If there */
/* aren't any available, then we will backtrack. */
value = min_value[curr_char];
while(value <= max_value[curr_char] &&
letter_map[value] != '\0') {
value++;
}
if(value > max_value[curr_char]) {
/* We didn't find an available number in the range so */
/* we want to backtrack from here. */
backtrack = 1;
backtrack_count++;
DBG_SOLVE(
printf("none available.\n");
);
} else {
backtrack = 0;
map_count[curr_char]++;
letter_map[value] = curr_char;
number_map[curr_char] = value;
DBG_SOLVE(
printf("using %d\n", value);
);
}
} /* else */
} /* else */
/* Now that we have decided whether we're moving forward */
/* from here or backtracking, do the appropriate things. */
if(backtrack) {
if(curr_smnd_row == column_lengths[curr_column] - 1) {
/* We've backtracked all the way back to the sum. */
/* Just break out of the summand loop and we'll */
/* look at the sum. */
break;
} else {
/* Go to the previous summand. Note that needed_sum */
/* has already been updated. */
curr_smnd_row++;
}
} else {
if(curr_smnd_row == 0) {
/* Set our focus to the next column. Record what */
/* carry we need from there to make the column we */
/* just finished work correctly. Either we are */
/* done, or we will next work on the sum character */
/* in the next column. We break out of the summand */
/* loop. */
curr_column++;
needed_sum -= value;
needed_carry[curr_column] = needed_sum;
break;
} else {
/* Go to the next summand, and adjust the needed_sum. */
curr_smnd_row--;
needed_sum -= value;
}
} /* else */
} /* while (summands) */
} /* while (columns) */
/* Get rid of the summands array if it was allocated. */
if(allocated_smnds_array) {
free(reform_smnds);
}
/* Return the number of solutions we found. If we only cared if more */
/* than one was found, we returned above. */
*difficulty = difficulty_conv(backtrack_count);
return(solutions_found);
}
int upcase_and_check_legality(
char *string, /* The string to upcase and check. */
int *string_length /* Return the length of the string here. */
)
/* This function will upcase the string passsed in as well as */
/* checking to make sure it only contains letters and that it is no */
/* longer than MAX_LEN. Any leading or following whitespace will */
/* be removed. If there is a problem with the string, an */
/* appropriate error message will be generated and zero will be */
/* returned. A good string results in this returning 1. */
{
char *ch_p = string;
char *ch1_p;
int length = strlen(string);
char *new_p;
char *new_str;
int result = 1;
/* Allocate space to copy the string into. We don't just modify */
/* it in place so that if we have to print an error message */
/* the string is still in its original form. */
new_str = malloc(length + 1);
new_p = new_str;
/* Detect any leading whitespace and ignore it. */
while(*ch_p == ' ' || *ch_p == '\t') {
ch_p++;
}
/* Now move through the string upcasing any characters and insuring */
/* that all characters are alphabetic. Copy them to the new string */
/* as we go. */
while(*ch_p != '\0' && *ch_p != ' ' && *ch_p != '\t') {
/* Check for bad character. */
if(result && !isalpha(*ch_p)) {
printf("Words must contain only letters. Problem with: %s\n", string);
result = 0;
}
/* Upcase this character. */
*new_p++ = toupper(*ch_p++);
}
/* If there is whitespace, it's either at the end of the string */
/* and we'll just ignore it or it's in the middle, in which case */
/* it's an error. Search for the first non-whitespace character. */
ch1_p = ch_p;
while(*ch_p == ' ' || *ch_p == '\t') {
ch_p++;
}
/* If we found a null, all is okay. Put a null at the end of */
/* the string. Note that if there was no whitespace at the end, */
/* this is a no-op. Report an error if we didn't find a null. */
*new_p = '\0';
if(result && *ch_p != '\0') {
printf("Words must contain only letters. Problem with: %s\n", string)
;
result = 0;
}
/* Check the length of the string and report an error if too long. */
length = new_p - new_str;
if(new_p - new_str > MAX_LEN) {
printf("Words can't be longer than %d characters. %s is too long.\n",
MAX_LEN, string);
result = 0;
}
/* Now copy the upcased string back to the one passed in, delete */
/* the allocated memory, and return the result. */
strcpy(string, new_str);
free(new_str);
*string_length = length;
return(result);
}
unsigned int look_for_puzzles_specific_count(
char **words,
int word_count,
int base,
int *word_lengths,
int *bit_count,
int *letters_used,
int summand_count,
int exactly_one,
int disallow_rep,
int first_sum_only,
unsigned int *search_count
)
/* This function will look for puzzles with solutions (one or many) */
/* given the list of words and the various information about them */
/* in the other parameters. This function returns the number of */
/* good puzzles found. It also returns the number searched in the */
/* parameter search_count. */
{
int backtrack;
int difficulty;
unsigned int good_puzzles = 0;
int i;
int index_limit;
int letter_map;
int *longest_smnd;
int new_letter_map;
unsigned int puzzles_tried = 0;
int smnd_index;
int *smnd_word_index;
int *smnd_word_lengths;
char **smnd_word_ptrs;
int *smnd_letter_map;
int solutions;
char *sum;
int sum_index;
int sum_index_limit;
int sum_length;
int total_letters;
int try_ind;
/* Allocate arrays for summands. */
longest_smnd = malloc(summand_count * sizeof(int));
smnd_word_index = malloc(summand_count * sizeof(int));
smnd_word_ptrs = malloc(summand_count * sizeof(char *));
smnd_word_lengths = malloc(summand_count * sizeof(int));
smnd_letter_map = malloc(summand_count * sizeof(int));
/* Try each word as the sum. */
sum_index_limit = (first_sum_only) ? 1 : word_count;
for(sum_index = 0; sum_index < sum_index_limit; sum_index++) {
sum = words[sum_index];
sum_length = word_lengths[sum_index];
DBG_FIND(
printf("Sum is %s\n", sum);
);
/* Find summand_count words other than sum such that */
/* no more than base characters are used and all of */
/* the summand words are not longer than the sum's length. */
smnd_index = 0;
backtrack = 0;
while(smnd_index >= 0) {
/* See if we have a possible set of summands. */
if(smnd_index == summand_count) {
/* We have a set of words to try. */
solutions = solve(smnd_word_ptrs, summand_count,
smnd_word_lengths, longest_smnd[smnd_index - 1], sum,
base, 0, 0, &difficulty);
puzzles_tried++;
DBG_FIND(
printf(" Trying ");
for(i = 0; i < summand_count; i++) {
if(i != 0) {
printf(" + ");
}
printf("%s", smnd_word_ptrs[i]);
}
printf("\n");
);
/* If one solution was returned, then we want to print */
/* this one. Note that this is the correct thing to do */
/* whether we were looking for puzzles with exaclty one */
/* solution or not. */
if(solutions == 1 || (solutions > 0 && !exactly_one)) {
good_puzzles++;
if(!exactly_one) {
printf("(%d) ", solutions);
}
for(i = 0; i < summand_count; i++) {
if(i != 0) {
printf(" + ");
}
printf("%s", smnd_word_ptrs[i]);
}
letter_map = smnd_letter_map[smnd_index - 1];
total_letters = bit_count[letter_map & 0x1ff]
+ bit_count[(letter_map >> 9) & 0x1ff]
+ bit_count[(letter_map >> 18) & 0x1ff];
printf(" = %s", sum);
if(DIFF_PRINT) {
printf(" difficulty: %d", difficulty);
}
printf("\n");
}
/* Backtrack from here to try another. */
backtrack = 1;
smnd_index--;
continue;
} else {
if(backtrack) {
/* We've backtracked to this position in the summand array. */
/* Try to find a new index for this position after */
/* the one here currently. */
try_ind = smnd_word_index[smnd_index] + 1;
} else {
/* We've come to this position in the summand array */
/* going forward. Starting at the start of the word */
/* array, find one for this spot in the summands array. */
try_ind = (smnd_index == 0) ? 0
: smnd_word_index[smnd_index - 1] + disallow_rep;
}
/* Now look for a possible word starting at the index try_ind. */
/* We stop when we reach either word count in the case where */
/* repetition of words is allowed or the number of sumands */
/* left subtracted from word_count where repetition isn't */
/* allowed. */
if(disallow_rep) {
index_limit = (word_count -
(summand_count - smnd_index - 1));
} else {
index_limit = word_count;
}
while(try_ind < index_limit) {
/* The sum can't be included in the summands. */
if(try_ind == sum_index) {
try_ind++;
continue;
}
/* A summand can't be longer than the sum. */
if(word_lengths[try_ind] > sum_length) {
try_ind++;
continue;
}
/* See how many total letters there will be after we */
/* add this word. If there are more than base, there */
/* can't be a solution. */
new_letter_map = (smnd_index == 0)
? letters_used[sum_index] | letters_used[try_ind]
: smnd_letter_map[smnd_index - 1]
| letters_used[try_ind];
total_letters = bit_count[new_letter_map & 0x1ff]
+ bit_count[(new_letter_map >> 9) & 0x1ff]
+ bit_count[(new_letter_map >> 18) & 0x1ff];
if(total_letters > base) {
try_ind++;
continue;
}
/* This one looks okay. */
break;
}
/* See if we found a summand word to try in this place. */
/* If not, backtrack. If so, go to next summand spot. */
if(try_ind >= index_limit) {
backtrack = 1;
smnd_index--;
} else {
/* When we go forward, we have to keep track of the */
/* index into the words array this summand is, its */
/* lengths, a pointer to the word, and the bit map */
/* of letters used to this point. */
backtrack = 0;
smnd_word_index[smnd_index] = try_ind;
smnd_word_ptrs[smnd_index] = words[try_ind];
smnd_word_lengths[smnd_index] = word_lengths[try_ind];
smnd_letter_map[smnd_index] = new_letter_map;
if(smnd_index == 0) {
longest_smnd[smnd_index] = word_lengths[try_ind];
} else {
if(word_lengths[try_ind] >
longest_smnd[smnd_index - 1]) {
longest_smnd[smnd_index] = word_lengths[try_ind];
} else {
longest_smnd[smnd_index] =
longest_smnd[smnd_index - 1];
}
}
/* Set index to next summand space. */
smnd_index++;
}
}
}
}
/* Now free the arrays we allocated. */
free(smnd_word_index);
free(smnd_word_ptrs);
free(smnd_word_lengths);
free(smnd_letter_map);
free(longest_smnd);
/* Return the number of good puzzles found and the number tried. */
*search_count = puzzles_tried;
return(good_puzzles);
}
unsigned int look_for_puzzles(
char **words,
int word_count,
int *word_lengths,
int base,
int low_summand_count,
int high_summand_count,
int exactly_one,
int disallow_rep,
int first_sum_only,
unsigned int *total_searched
)
/* This function will look for puzzles with solutions using the words */
/* given. It will search for them among all possible combinations */
/* from low_summand_count to high_summand_count summands. If */
/* exactly_one is set, then it will only generate puzzles that have */
/* exactly one solution. Otherwise it will generate puzzles that */
/* have at least one solution. */
{
int bit_count[512];
int bits;
char ch;
int i;
int j;
int length;
int *letters_used;
unsigned int number_found = 0;
unsigned int search_count;
int summand_count;
/* Initialize search count. */
*total_searched = 0;
/* First fill in the bit_count array. This holds the number */
/* of set bits in the the index number. This could be made static. */
for(i = 0; i < 512; i++) {
bits = 0;
for(j = 0; j < 9; j++ ) {
bits += ((i >> j) & 0x1);
}
bit_count[i] = bits;
}
/* Determine the letters used by each word. */
letters_used = malloc(word_count * sizeof(int));
for(i = 0; i < word_count; i++) {
letters_used[i] = 0;
for(j = 0; j < word_lengths[i]; j++) {
letters_used[i] |= (1 << (words[i][j] - 'A'));
}
}
/* Now go through the different summand counts. */
for(summand_count = low_summand_count;
summand_count <= high_summand_count;
summand_count++) {
/* Now call the function that looks for puzzles with a */
/* specific number of summands. */
number_found += look_for_puzzles_specific_count(words,
word_count, base, word_lengths,
bit_count, letters_used, summand_count,
exactly_one, disallow_rep, first_sum_only,
&search_count);
*total_searched += search_count;
}
/* Get rid of the arrays we allocated. */
free(letters_used);
return(number_found);
}
void print_usage()
{
printf("This program will solve and search for alphametic puzzles involvi
ng\n");
printf("addition. An alphametic puzzle is an equation involving words wh
ere a\n");
printf("substitution of digits for letters can be found so that the equat
ion\n");
printf("comes out correctly. For example the alphametic (I + BB = ILL) c
an be\n");
printf("solved in only one way. That solution is I = 1, B = 9, and L = 0
.\n");
printf("Each digit can only substitute for one letter, and all of a speci
fic\n");
printf("letter must be substituted by the same digit. The left-most lett
er in\n");
printf("a word can never be substituted for by zero.\n");
printf("\n");
printf("To solve a known alphametic puzzle using this program the -solve\
n");
printf("option is used. Either the whole puzzle is given on the command
line\n");
printf("or it and the base are prompted for later.\n");
printf("\n");
printf(" swp -solve\n");
printf("\n");
printf("The program will ask for the base to solve the puzzle in (almost\
n");
printf("always 10). It will then ask for the summand words to be input a
nd\n");
printf("finally the sum. If the base used is to be 10, then the command
line\n");
printf("alone can be used as:\n");
printf("\n");
printf(" swp -solve {summands} sum\n");
printf("\n");
printf(" where any number of summands are given separated by spaces.\n")
;
printf("\n");
printf("To search for alphametic puzzles among a list of words the -find\
n");
printf("option is used. Once again, either just the command line can be
used\n");
printf("or the words and other options can be prompted for.\n");
printf("\n");
printf(" swp -find\n");
printf("\n");
printf("The program will ask for the base to use and the minimum and maxi
mum\n");
printf("number of summands in a puzzle. It will then ask if it should re
port\n");
printf("puzzles with duplicate words and if it should only report puzzles
with\n");
printf("exactly one solution.\n");
printf("\n");
printf("Just the command line may be used if the base to use is 10 and\n"
);
printf("duplicates are allowed and only puzzles with exactly one solution
are\n");
printf("wanted. The syntax for command line invokation is:\n");
printf("\n");
printf(" swp -find {words}\n");
printf("\n");
printf("Summary of usage:\n");
printf(" 'swp -solve {summands} sum' Solve puzzle in base 10.\n");
printf(" 'swp -solve' Solve a puzzle. Prompt for base, summands, and su
m.\n");
printf(" 'swp -find {words}' Look for puzzles. Base 10. Duplication &
one solution.\n");
printf(" 'swp -find' Look for puzzles. Prompt for words and info.\n");
printf(" 'swp -usage' Generates this usage message.\n");
printf(" 'swp -help' Generates this usage message.\n");
}
char **read_words(
int *word_count,
int *longest_word_length,
int **lengths,
int *error
)
{
char ch;
char *ch_p;
const int chunk_size = 20;
int curr_word_index = 0;
int i;
char in_string[200];
int last_char_ind;
int word_array_size = chunk_size;
int *word_lengths;
char **word_transfer;
char **words;
*error = 0;
words = malloc(word_array_size * sizeof(char *));
while(1) {
/* Read a string. */
fgets(in_string, 200, stdin);
last_char_ind = strlen(in_string) - 1;
if(in_string[last_char_ind] == '\n') {
in_string[last_char_ind] = '\0';
}
/* Check for string WAY too long. If the string didn't overflow, */
/* the next character should be the newline. Exit if there */
/* was a problem. */
if(strlen(in_string) >= MAX_LEN) {
printf("String was too long. Limit is %d characters.\n", MAX_LEN);
exit(1);
}
/* Find the first non-whitespace character. If it's null, then */
/* we're done. */
ch_p = in_string;
while(*ch_p == ' ' || *ch_p == '\t') {
ch_p++;
}
/* If this is the empty string, then we are done. */
if(strcmp(ch_p, "") == 0) {
break;
}
/* Make sure there's room for the string. If not, */
/* allocate a new array somewhat bigger and copy the */
/* old one over. Do the same for the lengths array. */
if(curr_word_index == word_array_size) {
word_array_size += chunk_size;
word_transfer = malloc(word_array_size * sizeof(char *));
for(i = 0; i < curr_word_index; i++) {
word_transfer[i] = words[i];
}
free(words);
words = word_transfer;
}
/* Allocate space for the string and copy it in. */
words[curr_word_index] = malloc(strlen(in_string) + 1);
strcpy(words[curr_word_index], in_string);
curr_word_index++;
}
/* Check for errors in the strings read in. Set error flag */
/* if errors found. While we're at it, get the lengths. */
word_lengths = malloc(curr_word_index * sizeof(int));
*longest_word_length = 0;
for(i = 0; i < curr_word_index; i++) {
if(!upcase_and_check_legality(words[i], &word_lengths[i])) {
*error = 1;
}
if(word_lengths[i] > *longest_word_length) {
*longest_word_length = word_lengths[i];
}
}
/* Return the number of words and the array they're in. */
*word_count = curr_word_index;
*lengths = word_lengths;
return(words);
}
int main(int argc, char *argv[])
{
int bad_input;
int base = 10;
char ch;
int curr_summand_index;
int curr_word_index;
int difficulty;
int disallow_rep;
long elapsed_time;
long end_time;
int error;
int exactly_one;
int first_sum_only;
int i;
char in_string[200];
int j;
int last_char_ind;
int longest_summand;
int longest_word;
int max_summands;
int min_summands;
unsigned int number_found;
long start_time;
char *sum;
int sum_length;
int summand_count;
int *summand_lengths;
char **summands;
unsigned int total_searched;
int word_count;
int *word_lengths;
char **words;
/* If no arguments are given, or usage is requested, */
/* print usage info and exit. */
if(argc == 1 || strcmp(argv[1], "-usage") == 0
|| strcmp(argv[1], "-help") == 0) {
print_usage();
return(0);
}
/* See if we are to solve a puzzle. */
if(strcmp(argv[1], "-solve") == 0) {
if(argc >= 4) {
/* Allocate an array of pointers to the strings passed in as well */
/* as an array of integers that are the lengths of these string. */
summand_count = argc - 3;
summands = malloc(summand_count * sizeof(char *));
summand_lengths = malloc(summand_count * sizeof(int));
/* Get the summands first then the sum. For each, make sure it */
/* doesn't have illegal characters. */
bad_input = 0;
longest_summand = 0;
for(i = 0; i < summand_count; i++) {
summands[i] = argv[i + 2];
if(!upcase_and_check_legality(summands[i],
&summand_lengths[i])) {
bad_input = 1;
}
if(summand_lengths[i] > longest_summand) {
longest_summand = summand_lengths[i];
}
}
sum = argv[argc - 1];
if(!upcase_and_check_legality(sum, &sum_length)) {
bad_input = 1;
}
/* Call the routine to look for solutions and print them */
/* unless there were errors in the input. */
if(!bad_input) {
solve(summands, summand_count, summand_lengths,
longest_summand, sum, base, 1, 0, &difficulty);
if(DIFF_PRINT) {
printf("Difficulty: %d\n", difficulty);
}
}
/* Free the two allocated arrays and leave. */
free(summands);
free(summand_lengths);
return(bad_input);
} else {
/* We need to prompt for the information from the user. */
/* Get the base to solve the puzzle in. */
do {
printf("Input the base to solve the puzzle in (2 to 16).\n");
scanf("%d", &base);
getchar();
} while(base < 2 || base > 16);
/* Get the summands. */
printf("Input summands one per line. Press return when done.\n");
summands = read_words(&summand_count, &longest_summand,
&summand_lengths, &error);
/* If there wasn't an error with the summands, go ahead and */
/* get the sum. */
if(!error) {
/* Now get the sum. */
printf("\nInput the sum.\n");
fgets(in_string, 200, stdin);
last_char_ind = strlen(in_string) - 1;
if(in_string[last_char_ind] == '\n') {
in_string[last_char_ind] = '\0';
}
if(strlen(in_string) >= MAX_LEN) {
printf("Sum string was too long.\n");
error = 1;
}
sum = in_string;
/* If the sum was made of legal characters, look for solutions. */
if(!error &&
upcase_and_check_legality(in_string, &sum_length)) {
/* Call the routine to look for solutions and print them. */
solve(summands, summand_count, summand_lengths,
longest_summand, sum, base, 1, 0, &difficulty);
if(DIFF_PRINT) {
printf("Difficulty: %d\n", difficulty);
}
}
}
/* Free allocated memory and leave. */
for(i = 0; i < summand_count; i++) {
free(summands[i]);
}
free(summands);
free(summand_lengths);
return(error);
}
}
/* See if we are to look for solutions among a list of words. */
if(strcmp(argv[1], "-find") == 0) {
/* See if they put the words on the command line. */
if(argc >= 4) {
/* Get the words. */
word_count = argc - 2;
words = malloc(word_count * sizeof(char *));
word_lengths = malloc(word_count * sizeof(int));
/* Get the words, determine the lengths of them and check them */
/* for illegal characters. */
error = 0;
for(i = 0; i < word_count; i++) {
words[i] = argv[i + 2];
if(!upcase_and_check_legality(words[i], &word_lengths[i])) {
error = 1;
}
}
if(!error) {
/* Note the time we started looking. */
time(&start_time);
/* Call the routine that looks for puzzles with solutions. */
/* Use 2 and the number of words - 1 for the min and max */
/* summands. */
number_found = look_for_puzzles(words, word_count, word_lengths,
base, 2, word_count - 1, 1, 0, 0,
&total_searched);
}
free(word_lengths);
free(words);
} else {
/* We need to prompt for the information from the user. */
/* Get the base to solve the puzzle in and the min and max */
/* number of summands. */
do {
printf("Input the base to solve the puzzle in (2 to 16).\n");
scanf("%d", &base);
getchar();
} while(base < 2 || base > 16);
printf("Input the minimum number of summands.\n");
scanf("%d", &min_summands);
getchar();
printf("Input the maximum number of summands.\n");
scanf("%d", &max_summands);
getchar();
printf("Disallow repetition of summands (Y or N)?\n");
scanf("%c", &ch);
getchar();
if(ch == 'y' || ch == 'Y') {
disallow_rep = 1;
} else {
disallow_rep = 0;
}
printf("Only puzzles with one solution(Y or N)?\n");
scanf("%c", &ch);
getchar();
if(ch == 'y' || ch == 'Y') {
exactly_one = 1;
} else {
exactly_one = 0;
}
printf("Use only the first word for the sum(Y or N)?\n");
scanf("%c", &ch);
getchar();
if(ch == 'y' || ch == 'Y') {
first_sum_only = 1;
} else {
first_sum_only = 0;
}
/* Get the words to search for valid puzzles with. */
printf("Input words one per line. Press return when done.\n");
words = read_words(&word_count, &longest_word,
&word_lengths, &error);
/* If there wasn't an error, then go ahead and look for puzzles. */
if(!error) {
/* Note the time we started looking. */
time(&start_time);
/* Call the routine that looks for puzzles with solutions. */
number_found = look_for_puzzles(words, word_count, word_lengths,
base, min_summands, max_summands, exactly_one,
disallow_rep, first_sum_only, &total_searched);
}
/* Free allocated memory. */
for(i = 0; i < word_count; i++) {
free(words[i]);
}
free(word_lengths);
free(words);
}
if(!error) {
/* See how long the search took. */
time(&end_time);
elapsed_time = end_time - start_time;
printf("Elapsed time was %d seconds.\n", elapsed_time);
printf("Found %d good puzzles after searching %d\n", number_found,
total_searched);
}
}
return(error);
}