//-------------------------------------------------------------------
// enigma1353.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "Three Cubed" by Richard England, from New Scientist, 13 August 2005, page 54.
//
// Four cubes (two 4-digit, one 3-digit, one 5-digit) arranged in the
// following pattern:
//
//	* * * *
//	      *
//	  * * *
//	      *
//	* * * *
//
// Three solutions use nine of the ten digits, but two of those use the 
// same nine digits. What's the third solution?

#include <stdio.h>
#include <math.h>

// Macro to extract the i'th digit from number n.
#define DIGIT(n,i) ((n)/(int)(pow(10,(i))+.5)%10)

int main (void)
{
	int i1, i2, i3, i4;

	// Loop through four integers that when cubed
	// are 4, 3, 4, and 5 digits in length.
	for (i1 = 10; i1 < 22; i1++)
	for (i2 =  5; i2 < 10; i2++)
	for (i3 = 10; i3 < 22; i3++)
	for (i4 = 22; i4 < 47; i4++)
	{
		// Calculate the cubes.
		int c1 = i1 * i1 * i1;
		int c2 = i2 * i2 * i2;
		int c3 = i3 * i3 * i3;
		int c4 = i4 * i4 * i4;

		// See if the digits match up.
		if (DIGIT(c1,0) == DIGIT(c4,4) &&
		    DIGIT(c2,0) == DIGIT(c4,2) &&
		    DIGIT(c3,0) == DIGIT(c4,0))
		{
			// Now determine if there are nine digits used,
			// and what the unused digit is.
			int i, DigitsUsed[10], UnusedDigit, DigitCount = 0;

			for (i = 0; i < 10; i++)
				DigitsUsed[i] = 0;

			for (i = 0; i < 3; i++)
				DigitsUsed[DIGIT(c2,i)] = 1;

			for (i = 0; i < 4; i++)
			{
				DigitsUsed[DIGIT(c1,i)] = 1;
				DigitsUsed[DIGIT(c3,i)] = 1;
			}

			for (i = 0; i < 5; i++)
				DigitsUsed[DIGIT(c4,i)] = 1;

			for (i = 0; i < 10; i++)
				if (DigitsUsed[i])
					DigitCount ++;
				else
					UnusedDigit = i;

			// Print the result.
			if (DigitCount == 9)
			{
				printf("Cubes = %i %i %i %i Unused digit = %i\n", 
					c1, c2, c3, c4, UnusedDigit);
			}
		}


	}
	return 0;
}