Saturday, 15 January, 2005

Sometimes, you come across a computing problem and when you solve it you're proud at the elegancy of your solution. This week I had one of those moments. Here is the problem, suppose you have a currency and your currency only allows certain denominations, in my case: 25, 50, 100, 150, 500. The aim was to find an algorithm that given an integer n where n is divisible by twenty-five that would give you the shortest sequence of coins to make up that value.

The solution:

public static int[] calculateTarrif(int creditPrice)
{
	int[] smsTarrifs = {500,150, 100, 50, 25};
	ArrayList result = new ArrayList();

	while(creditPrice > 0)
	{
		// Loop through each tarrif. By having the tarrifs order in decreasing size we ensure the optimal tarrifs configuration.
		for(int i=0; i<smsTarrifs.Length; i++)
		{
        		// Calculate what the remainder of creditPrice would be if we deducted the current tarrif
			int reducedPrice = creditPrice - smsTarrifs[i];
					
			// If reducedPrice is great or equal to zero than we can safely include the current tarrif in our output.
			if (reducedPrice >= 0)
			{
        			result.Add(smsTarrifs[i]);
				creditPrice = reducedPrice;
				break; // Restart the loop to ensure we try the heaviest tarriff first.
			}
        	}
    	}

	return (int[]) result.ToArray(typeof(int));
}	

Nice eh! Emoticon: Smile However, it turned out that the piece of code I've written here doesn't actually work for the intended purpose. The method should have found the most profitable sequence of reverse bill SMS messages to send to a user, this is not the same as the shortest sequence of messages. Doh! Unfortunately, the correct algorithm is a tad more ugly.

Simon.

13:53:45 GMT | #Programming | Permalink
XML View Previous Posts