//----------------------------------------------------------------------
// 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 <stdio.h>
#include <string.h>

// 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;
}