Can someone abuse LINQ and solve this money problem?

Question

For the fun of it, I would like to see someone use and abuse LINQ to solve this money problem. I really have no idea how you would do it - I suppose Populating some set and then selecting off of it.

If given a total number of coins and give the total amount of all coins added together: Show every possible combination of coins. Coins are Quarters(.25), Dimes(.10) Nickels(.05) and Pennies(.01)

Include the option so that there can be zero of a type of coin or there must be at least 1 of each.

Sample Problem: If I have 19 coins and the coins add up to $1.56 and there must be at least 1 of every type of coin.

The answer would be:

1 Quarters, 9 Dimes, 8 Nickels, 1 Pennies

2 Quarters, 5 Dimes, 11 Nickels, 1 Pennies

2 Quarters, 9 Dimes, 2 Nickels, 6 Pennies

3 Quarters, 1 Dimes, 14 Nickels, 1 Pennies

3 Quarters, 5 Dimes, 5 Nickels, 6 Pennies

4 Quarters, 1 Dimes, 8 Nickels, 6 Pennies

5 Quarters, 1 Dimes, 2 Nickels, 11 Pennies

And if we allowed zero for a coint we allowed get an additional 0 Quarters, 13 Dimes, 5 Nickels, 1 Pennies

Here is some sample C# code using a brute force method to solve the problem. Don't bother improving the sample, let's just see a solution using Linq. //Try not to use any regualar c# looping code if possible.

private void SolveCoinProblem(int totalNumberOfCoins, double totalAmount, int minimumNumberOfEachCoin)
    {
        int foundCount = 0;
        long numberOfTries = 0;
        Console.WriteLine(String.Format("Solving Coin Problem:TotalNumberOfCoins={0}TotalAmount={1}MinimumNumberOfEachCoin{2}", totalNumberOfCoins, totalAmount, minimumNumberOfEachCoin));
        for (int totalQuarters = minimumNumberOfEachCoin; totalQuarters < totalNumberOfCoins; totalQuarters++)
        {
            for (int totalDimes = minimumNumberOfEachCoin; totalDimes < totalNumberOfCoins; totalDimes++)
            {
                for (int totalNickels = minimumNumberOfEachCoin; totalNickels < totalNumberOfCoins; totalNickels++)
                {
                    for (int totalPennies = minimumNumberOfEachCoin; totalPennies < totalNumberOfCoins; totalPennies++)
                    {
                        numberOfTries++;
                        if (totalQuarters + totalDimes + totalNickels + totalPennies == totalNumberOfCoins)
                        {
                            if (Math.Round((totalQuarters * .25) + (totalDimes * .10) + (totalNickels * .05) + (totalPennies * .01),2) == totalAmount)
                            {
                                Console.WriteLine(String.Format("{0} Quarters, {1} Dimes, {2} Nickels, {3} Pennies", totalQuarters, totalDimes, totalNickels, totalPennies));
                                foundCount++;
                            }
                        }
                    }
                }
            }
        }
        Console.WriteLine(String.Format("{0} Combinations Found. We tried {1} combinations.", foundCount, numberOfTries));
    }

Answer 1

Untested, but:

        int minQuarters = 1, minDimes = 1,
            minNickels = 1, minPennies = 1,
            maxQuarters = 19, maxDimes = 19,
            maxNickels = 19, maxPennies = 19,
            coinCount = 19, total = 156;
        var qry = from q in Enumerable.Range(minQuarters, maxQuarters)
                  from d in Enumerable.Range(minDimes, maxDimes)
                  from n in Enumerable.Range(minNickels, maxNickels)
                  from p in Enumerable.Range(minPennies, maxPennies)
                  where q + d + n + p == coinCount
                  where q * 25 + d * 10 + n * 5 + p == total
                  select new {q,d,n,p};
        foreach (var row in qry)
        {
            Console.WriteLine("{0} quarter(s), {1} dime(s), {2} nickel(s) and {3} pennies",
                row.q, row.d, row.n, row.p);
        }

---

Actually, for retail purposes - perhaps a better query is "what is the fewest coins I can give out"? Replace with:

...
from p in Enumerable.Range(minPennies, maxPennies)
where q + d + n + p <= coinCount
where q * 25 + d * 10 + n * 5 + p == total
orderby q + d + n + p
...

and use either First() or Take(...) ;-p

You could also probably reduce the number of checked cases by subtracting (for example) q in the maxDimes test (and so on...) - something like (simplified):

        int minCount = 1,
            coinCount = 19, total = 156;
        var qry = from q in Enumerable.Range(minCount, coinCount - (3 * minCount))
                  where q * 25 <= total
                  from d in Enumerable.Range(minCount, coinCount - (q + (2 * minCount)))
                  where q * 25 + d * 10 <= total
                  from n in Enumerable.Range(minCount, coinCount - (q + d + minCount))
                  where q * 25 + d * 10 + n * 5 <= total
                  from p in Enumerable.Range(minCount, coinCount - (q + d + n))
                  where q + d + n + p == coinCount
                  where q * 25 + d * 10 + n * 5 + p == total
                  select new { q, d, n, p };