Czy ktoś może nadużywać LINQ i rozwiązać tę zagadkę?

Question

Dla zabawy, chciałbym zobaczyć, jak ktoś używa i nadużywa LINQ, aby rozwiązać ten problem z pieniędzmi. Naprawdę nie mam pojęcia, jak byś to zrobił - przypuszczam, że wypełniłem jakiś zestaw, a następnie wybrałem go.

Jeśli podana jest całkowita liczba monet i łączna suma wszystkich monet dodanych razem: Pokaż każdą możliwą kombinację monet. Monety to ćwiartki (.25), dziesiętne (.10) nikiel (.05) i grosze (.01)

Uwzględnij opcję, aby liczba monet wynosiła zero lub musi być co najmniej 1 każdy.

Przykładowy problem: jeśli posiadam 19 monet, a monety sumują się do 1,56 USD i musi być przynajmniej 1 każdego rodzaju monet.

będzie odpowiedź:

1 ćwiartek, 9 dimes 8 Nickels, 1 Pennies

dwóch ćwiartek, 5 dimes 11 Nickels, 1 Pennies

2 ćwiartek, 9 Dimes 2 Nickels 6 Groszy

3 Dimes ćwiartek, 1, 14, 1 Nickels Pennies

trzy czwarte, 5 monet dziesięciocentowych, 5 Nickels 6 Groszy

4 Ćwierćtusze, 1 dimes 8 Nickels 6 Groszy

5 Ćwierćtusze, 1 dimes 2 Nickels, 11 Groszy

, a jeśli to dozwolone zero dla COINT my dozwolone uzyskać dodatkowe 0 kwartałów, 13 Dimes, 5 Nickels, 1 Pennies

Oto niektóre przykładowy kod C# za pomocą metody brute force, aby rozwiązać problem. Nie próbuj ulepszać próbki, zobaczmy tylko rozwiązanie z Linq. // Staraj się nie używać żadnego regularnego kodu pętlowego C#, jeśli to możliwe.

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

Nietestowane, ale:

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

---

Faktycznie, w celach handlowych - być może lepiej zapytanie jest "to, co jest Najmniej monety mogę dać się"? Zamień na:

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

i użyć First() lub Take(...) ;-P

Można też prawdopodobnie zmniejszenie liczby skontrolowanych przypadkach poprzez odjęcie (na przykład) q w teście maxDimes (i tak dalej .. .) - coś podobnego (uproszczonego):

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