//-------------------------------------------------------------------
// enigma1357.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "Diminishing Powers" by Richard England, 
//	from New Scientist, 10 September 2005, page 54.
//
// Integers from 1 to 12 are divided into two groups where the sum
// of the cubes of the integers are equal.  A minimum number of 
// integers are switched from one group to another so that the
// sums of the squares are equal.  A minimum number of integers 
// are switched from one group to another so that the sum of the
// integers are equal.  What integers were switched?
//-------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

// A function that counts the number of 1 bits in its argument.
int CountBits(int number)
{
	int i, bit = 1, total = 0;

	for (i = 0; i < 31; i++, bit <<= 1)
		if (number & bit)
			total++;

	return total;
}

int main(void)
{
	int i, split, sum1 = 0, sum2 = 0, sum3 = 0;
	int numSplit1 = 0, numSplit2 = 0, numSplit3 = 0;
	int * pSplit1 = 0, * pSplit2 = 0, * pSplit3 = 0;
	int bit, i1, i2, i3, numChange, index1, index2, index3;

	// Sum the integers from 1 to 12, their squares, and their cubes
	for (i = 1; i <= 12; i++)
	{
		sum1 +=	i;
		sum2 +=	i * i;
		sum3 +=	i * i * i;
	}

	// Now split will be a integer between 0 and 0xFFF, where the bits 
	// represent the distribution of the integers 1 to 12 between
	// two groups, ie, 0 bit means one group, 1 bit means the other.
	for (split = 0; split < 0xFFF; split++)
	{
		int subsum1 = 0, subsum2 = 0, subsum3 = 0;

		// The three subsum's are the sums of the integers, squares,
		// or cubes in one of the groups.
		for (i = 1, bit = 1; i <= 12; i++, bit <<= 1)
		{
			if (split & bit)
			{
				subsum1 += i;
				subsum2 += i * i;
				subsum3 += i * i * i;
			}
		}

		// If the split divides the sum in half (that is, subsum is half
		// of sum), then store the value of split. 
		if (subsum1 == sum1 / 2)
		{
			pSplit1 = realloc(pSplit1, ++numSplit1 * sizeof(int));
			pSplit1[numSplit1 - 1] = split;
		}

		if (subsum2 == sum2 / 2)
		{
			pSplit2 = realloc(pSplit2, ++numSplit2 * sizeof(int));
			pSplit2[numSplit2 - 1] = split;
		}
		if (subsum3 == sum3 / 2)
		{
			pSplit3 = realloc(pSplit3, ++numSplit3 * sizeof(int));
			pSplit3[numSplit3 - 1] = split;
		}
	}

	// Now find the smallest number of bits for the various splits
	// from cubes to squares.
	numChange = 12;

	for (i2 = 0; i2 < numSplit2; i2++)
	for (i3 = 0; i3 < numSplit3; i3++)
	{
		int numSwitch = CountBits(pSplit2[i2] ^ pSplit3[i3]);

		if (numSwitch != 0 && numSwitch < numChange)
		{
			index2 = i2;
			index3 = i3;
			numChange = numSwitch;
		}
	}

	// Now find the smallest number of bits for splits from the
	// square split found above to the integer split.
	numChange = 12;

	for (i1 = 0; i1 < numSplit1; i1++)
	{
		int numSwitch = CountBits(pSplit1[i1] ^ pSplit2[index2]);

		if (numSwitch != 0 && numSwitch < numChange)
		{
			index1 = i1;
			numChange = numSwitch;
		}
	}
	printf("%0.4x --> %0.4x --> %0.4x\n", pSplit3[index3], pSplit2[index2], pSplit1[index1]);

	// Print the actual numbers changing from one group to the other.
	printf("Transfer ");

	for (i = 0, bit = 1; i < 12; i++, bit <<= 1)
		if ((pSplit2[index2] ^ pSplit3[index3]) & bit)
			printf("%i ", i + 1);

	printf("then ");

	for (i = 0, bit = 1; i < 12; i++, bit <<= 1)
		if ((pSplit2[index2] ^ pSplit1[index1]) & bit)
			printf("%i ", i + 1);

	printf("\n");
	return 0;
}