// 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 = new char[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) { delete [] 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) { delete [] 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) { delete [] 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 = new char[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); delete [] 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 = new int[summand_count]; smnd_word_index = new int[summand_count]; smnd_word_ptrs = new char*[summand_count]; smnd_word_lengths = new int[summand_count]; smnd_letter_map = new int[summand_count]; // 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. delete [] smnd_word_index; delete [] smnd_word_ptrs; delete [] smnd_word_lengths; delete [] smnd_letter_map; delete [] 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 = new int[word_count]; 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. delete [] 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 = new char*[word_array_size]; 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 = new char*[word_array_size]; for(i = 0; i < curr_word_index; i++) { word_transfer[i] = words[i]; } delete [] words; words = word_transfer; } // Allocate space for the string and copy it in. words[curr_word_index] = new char[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 = new int[curr_word_index]; *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 = new char*[summand_count]; summand_lengths = new int[summand_count]; // 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. delete [] summands; delete [] 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++) { delete [] summands[i]; } delete [] summands; delete [] 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 = new char*[word_count]; word_lengths = new int[word_count]; // 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); } delete [] word_lengths; delete [] 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++) { delete [] words[i]; } delete [] word_lengths; delete [] 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); }