//---------------------------------------------------------------------- // enigma1361.c (c) 2005 by Charles Petzold (www.charlespetzold.com) // // "Enigma Variation" by Richard England, New Scientist, 8 October 2005, page 58. // // The 9th of Edward Elgar's "Enigma Variations" is titled "Nimrod," // and this puzzle presents a summation: // // E L G A R // + E N I G M A // ----------- // N I M R O D // // where the letters correspond to digits 0 through 9, and the letter 0 // is the digit 0. What is "ENIGMA"? // // It's possible to observe a few simple characteristics of these letters. // For example, there must be a carry into the most-significant column, // so that N = E + 1. In the second most significant column, E + N // (plus a possible carry) must equal 10 + I, which implies E is 5 or // greater, and N is 6 or greater. // // There must be a carry from the 2nd column (from the right) into the // third column, so R is odd. // // In this way, the number of possibilities can be narrowed. The // following program just pursues a brute-force solution. //---------------------------------------------------------------------- #include #include // A few definitions to clarify things. typedef int BOOL; #define TRUE 1; #define FALSE 0; void Swap(int arr[], int i1, int i2) { int temp = arr[i1]; arr[i1] = arr[i2]; arr[i2] = temp; } // The 'arr' argument is initially 'num' increasing integers representing // array indices. // When the array is uniformly decreasing, the function returns FALSE. BOOL NextPermutation(int arr[], int num) { int i, j, k; // This simple case happens in half the calls. if (arr[num - 1] > arr[num - 2]) { Swap(arr, num - 1, num - 2); return TRUE; } i = num - 2; while (i >= 0 && arr[i] > arr[i + 1]) i--; if (i < 0) return FALSE; // arr[i] is lower than anything to the right of it. // We now need to find the lowest number to the right // of arr[i]. for (j = k = i + 1; j < num; j++) if (arr[j] > arr[i] && arr[j] < arr[k]) k = j; Swap(arr, i, k); i++; // The remainder are sorted to be ascending. for ( ; i < num - 1; i++) for (j = i + 1; j < num; j++) if (arr[i] > arr[j]) Swap(arr, i, j); return TRUE; } // Converts a character string to a number based on the indexing // of the 'letters' array from the 'numbers' array. int LettersToNumber(char * str, int digits[]) { static char * letters = "OADEIGLMNR"; int result = 0; int mult = 1; int i; for (i = strlen(str) - 1; i >= 0; i--) { result += mult * digits[strchr(letters, str[i]) - letters]; mult *= 10; } return result; } int main(void) { // The array of integers to be permuted. int digits[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; do { int num1 = LettersToNumber("ELGAR", digits); int num2 = LettersToNumber("ENIGMA", digits); int num3 = LettersToNumber("NIMROD", digits); if (num1 + num2 == num3) printf("%i\n", num2); } while (NextPermutation(digits + 1, 9)); // Notice that NextPermutation is passed digits + 1 so that the first // element (0) remains in place. return 0; }