//-------------------------------------------------------------------
// enigma1354.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "Sound Idea" by Bob Walker, New Scientist, 20 August 2005, page 51.
//
// A wind chime, with 10 chimes of lengths 1 cm to 10 cm, placed
// uniform distances apart around the circumference of a round
// disk so they are "balanced perfectly." The 10 lengths of the  
// chimes in this sequence form an 11-digit number. What's the 
// smallest possible number for balanced chimes?
//
// This number obviously begins with 10, and the next digit ideally
// is 1. Where we go from there depends on what balances.
//
// The weight of each chime is proportional to its length, so the 
// total weight of the chimes is 55 whatevers. 
//
// Although I can't demonstrate this mathematically, it seems likely 
// that we want a situation where any line through the center of the 
// disk divides the weights into 27 on one side and 28 on another. If 
// we imagine this dividing line as rotating around the center of the
// disk, we see that any chime of weight n should be balanced on
// the opposite side by a weight of n+1 or n-1. If a chime of 
// weight n is balanced on the opposite by n+1, then the chime 
// adjancent to n (m, say) must be balanced with m-1.
//
// So, the 10 chime must be opposite the 9 chime. Here's a view of
// the disk where the plus size indicates the center:
//
//  10   +   9
//
// If the 1 chime is adjacent to the 10, then 2 must be adjacent to 9:
//
//          2
//  10   +   9
//    1
//
// The chime opposite 10 is 10-1. The chime opposite the 1 is 1+1. 
// The next chime after the 1 (n, say) has to be opposite n-1. 
// Aiming for the lowest possible number, the next chime has to be 4
// and the opposite chime is 4-1:
//
//        3
//          2
//  10   +   9
//    1
//      4
//
// The next one can be 5, opposite 5+1:
//
//      6 3
//          2
//  10   +   9
//    1
//      4 5 
//
// And then 8, opposite 8-1:
//
//      6 3
//    7     2
//  10   +   9
//    1     8
//      4 5 
//
// So, any dividing line through the center splits the chimes into 27
// on one side and 28 on another. As that line is rotated around the
// center and passes each opposite pair, the weight shifts on one side 
// from 27 to 28, and on the other from 28 to 27.
//
// The answer, I conclude, is the number 10,145,892,367.
//
// But I'm not happy with this at all because I'm not sure how to 
// verify that this configuration is actually "balanced perfectly" 
// without getting down and dirty calculating the center of gravity.
//
// It is easy to calculate a center of gravity between two weights.
// A Weight w1 at point (x1, y1) and a weight w2 at (x2, y2) is 
// equivalent to weight (w1 + w2) at the center of gravity at the
// point (x,y) where:
// 
// 	x = (x1 * w1 + x2 * w2) / (w1 + w2)
//      y = (y1 * w1 + y2 * w2) / (w1 + w2)
// 
// A center of gravity among 10 points can be calculated similarly as
// a series of pairs. Any two weights are equivalent to the combined 
// weight at the center of gravity. 
//
// The code shown below loops through all the possible configurations
// of chimes and calculates a center of gravity. If that center of
// gravity coincides with the center of the disk, then the configuration 
// is balanced.
//---------------------------------------------------------------------

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

// Define Pi and a Point structure.

#define Pi acos(-1)

typedef struct
{
	double X, Y;
} 
Point;

int main(void)
{

	int Chimes, ChimesTest, i, DigitTaken[10], Weight;
	Point Center, HangPoint[10];

	// HangPoint are the coordinates of each chime based on a unit circle
	// where the origin is the center of the disk.
	for (i = 0; i < 10; i++)
	{
		HangPoint[i].X = cos(i * 2 * Pi / 10);
		HangPoint[i].Y = sin(i * 2 * Pi / 10);
	}

	// Loop through the possible orders of the nine chimes after chime "10".
	for (Chimes = 123456789; Chimes <= 987654321; Chimes++)
	{
		// Initialize the DigitTaken array
		for (i = 0; i < 10; i++)
			DigitTaken[i] = 0;

		// Store the Chimes value for mangling.
		ChimesTest = Chimes;

		// Loop through the 9 digits of Chimes.
		// We want to prevent digits of zero, and all the 
		//	digits need to be unique.
		for (i = 0; i < 9; i++)
		{
			// Get the least significant digit.
			int LastDigit = ChimesTest % 10;

			// If it's zero, we're not interested in that Chimes value.
			if (LastDigit == 0)
				break;

			// If the digit was already present, ditto.
			if (DigitTaken[LastDigit] > 0)
				break;

			// Mark the digit as taken.
			++DigitTaken[LastDigit];

			// Prepare for the next digit.
			ChimesTest /= 10;
		}
		// Check if the loop was completed successfully.
		if (i < 9)
			continue;

		// Initialize Center of gravity and Weight with Chime "10".
		Center = HangPoint[0];
		Weight = 10;

		// Store the Chimes value for mangling again.
		ChimesTest = Chimes;

		// Loop through the 9 digits of Chimes.
		// We want to calculate a new center of gravity and total weight.
		for (i = 0; i < 9; i++)
		{
			int ChimeWeight = ChimesTest % 10;
			Point ChimePoint = HangPoint[9 - i];	// could also be [i + 1]

			// Calculate the new center of gravity based on weighted averages.
			Center.X = (Weight * Center.X + ChimeWeight * ChimePoint.X) / (Weight + ChimeWeight);
			Center.Y = (Weight * Center.Y + ChimeWeight * ChimePoint.Y) / (Weight + ChimeWeight);

			Weight += ChimeWeight;

			// Prepare for the next digit.
			ChimesTest /= 10;
		}

		// Check if the center of gravity is close to the origin.
		if (fabs(Center.X) < 0.000001 && fabs(Center.Y) < 0.000001)
		{
			printf("10,%i Center = (%20.17f, %20.17f)\n", Chimes, Center.X, Center.Y);
		}

		// For all printed configurations, the centers of gravity are as close
		// to the origin as the precision of IEEE double-precision allows.
		// The smallest number is the solution to the problem.
	}
	return 0;
}