Quelqu'un peut-il abuser de LINQ et résoudre ce puzzle d'argent?

Question

Pour le plaisir, j'aimerais voir quelqu'un utiliser et abuser de LINQ pour résoudre ce problème d'argent. Je n'ai vraiment aucune idée de la façon dont vous le feriez - je suppose que vous remplissez un ensemble puis que vous le sélectionnez.

Si le nombre total de pièces est donné et le montant total de toutes les pièces ajoutées: Afficher toutes les combinaisons possibles de pièces. Les pièces sont des quarts (.25), des dixièmes (.10) des nids (.05) et des centimes (.01)

Inclure l'option pour qu'il puisse y avoir zéro d'un type de pièce de monnaie ou il doit y avoir au moins 1 de chaque. Exemple: Problème: Si j'ai 19 pièces et que les pièces totalisent 1,56 $, il doit y avoir au moins 1 pièce de chaque type.

la réponse serait:

1 Quarters, 9 Dimes, 8 Nickels, 1 Pennies

2 trimestres, 5 Dimes, 11 Nickels, 1 Pennies

2 trimestres, 9 Dimes , 2 Nickels, 6 Pennies

3 trimestres, 1 Dimes, Nickels, 14 1 Pennies

3 trimestres, 5 Dimes, 5 Nickels, 6 Pennies

4 quarts, 1 Dimes, 8 Nickels, 6 Pennies

5 trimestres, 1 Dimes, 2 Nickels, 11 Pennies

et si nous a permis de zéro pour un coint nous 0 Quarts, 13 Dimes, 5 Nickels, 1 Pennies

Voici un exemple de code C# utilisant une méthode de force brute pour résoudre le problème. Ne vous embêtez pas à améliorer l'échantillon, voyons juste une solution utilisant Linq. // Essayez de ne pas utiliser de code de boucle regualar C# si 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

Non testé, mais:

 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); 
     } 

---

En fait, à des fins de vente au détail - peut-être une meilleure question est "ce qui est des pièces plus petit nombre que je peux donner des"? Remplacer par:

... 
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 
... 

et utiliser soit First() ou Take(...) ;-P

Vous pouvez également réduire probablement le nombre de cas vérifiés en soustrayant (par exemple) q dans le test maxDimes (et ainsi de suite .. .) - quelque chose comme (simplifié):

 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 };