project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_74.cpp (2676B)

      1 #include <algorithm>
      2 #include <set>
      3 
      4 #include "Euler.h"
      5 
      6 int recurseChain(llui head, std::set<llui> &chain, int factorials[], uint64_t size)
      7 {    
      8     llui tempHead = head;
      9     llui newHead = 0;
     10     
     11     while (tempHead != 0)
     12     {
     13         newHead += factorials[tempHead % 10];
     14         tempHead /= 10;
     15     }
     16 
     17     //found in problem 34
     18     if (newHead == 1 || newHead == 2 || newHead == 145 || newHead == 40585)
     19         return size + 1;
     20 
     21     //cycles given in the problem
     22     if (newHead == 871 || newHead == 872 || newHead == 45361 || newHead == 45362)
     23         return size + 2;
     24     if (newHead == 169 || newHead == 1454 || newHead == 363601)
     25         return size + 3;
     26 
     27     chain.insert(newHead);
     28 
     29     if (chain.size() == size || chain.size() > 60)
     30     {
     31         return chain.size();
     32     }
     33 
     34     return recurseChain(newHead, chain, factorials, chain.size());
     35 }
     36 
     37 int Euler::DigitFactorialChains()
     38 {
     39     int total = 0;
     40     int factorials[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
     41 
     42     std::vector<std::vector<int>> solutions;
     43 
     44     for (uint64_t i = 1; i < 1e6; ++i)
     45     {
     46         bool ordered = true;
     47     
     48         for (int temp = i; temp != 0; temp /= 10)
     49         {
     50             if (((temp % 10) < ((temp / 10) % 10)) && ((temp % 10) != 0))
     51             {
     52                 ordered = false;
     53                 break;
     54             }
     55         }
     56 
     57         //we only check ascending values, e.g. 1243 has the same chain as 1234.
     58         //zero is a wild card, therfore 1034 counts as ascending.
     59         if (ordered)
     60         {
     61             std::set<llui> chain;
     62 
     63             chain.insert(i);
     64 
     65             if (recurseChain(i, chain, factorials, chain.size()) == 60)
     66             {
     67                 //this uniqueness check is necessary because solutions containing zero break the ascending rule
     68                 std::vector<int> digits = EulerUtility::intToDigits(i);
     69                 bool unique = true;
     70 
     71                 for (std::vector<int> s : solutions)
     72                     if (std::is_permutation(digits.begin(), digits.end(), s.begin()))
     73                         unique = false;
     74 
     75                 if (unique)
     76                 {
     77                     solutions.push_back(digits);
     78 
     79                     int sum = EulerUtility::factorial(digits.size()) / EulerUtility::factorial(digits.size() - std::set<int>(digits.begin(), digits.end()).size() + 1);
     80 
     81                     int zeroCount = std::count(digits.begin(), digits.end(), 0);
     82 
     83                     if (zeroCount > 0)
     84                         sum = ((sum / digits.size()) * (digits.size() - 1)) / EulerUtility::factorial(zeroCount);
     85 
     86                     total += sum;
     87                 }
     88             }
     89         }
     90     }
     91 
     92     return total;
     93 }