project-euler

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

Euler_43.cpp (1788B)

      1 #include <algorithm>
      2 #include <numeric>
      3 
      4 #include "Euler.h"
      5 
      6 void recursePermutations(std::string &current, std::vector<llui> &dps, std::vector<std::vector<std::string>> &psl, int pos)
      7 {
      8     for (std::string s : psl[pos])
      9         if (s.substr(1, 2) == current.substr(0, 2))
     10         {
     11             if (current.find(s.substr(0, 1)) == std::string::npos)
     12             {
     13                 std::string concat = s.substr(0, 1) + current;
     14 
     15                 if (pos == 0)
     16                     dps.push_back(EulerUtility::digitsTollui(concat));
     17                 else
     18                     recursePermutations(concat, dps, psl, pos - 1);
     19             }
     20         }
     21 }
     22 
     23 void findDivisiblePermutations(std::vector<llui> &dps, std::vector<std::vector<std::string>> &psl, int pos)
     24 {
     25     for (std::string s : psl[pos])
     26         recursePermutations(s, dps, psl, pos - 1);
     27 
     28     for (unsigned i = 0; i < dps.size(); ++i)
     29         for (int j = 0; j <= 9; ++j)
     30             if (std::to_string(dps[i]).find(std::to_string(j)) == std::string::npos)
     31                 dps[i] = EulerUtility::digitsTollui(std::to_string(j) + std::to_string(dps[i]));
     32 }
     33 
     34 BigInteger Euler::SubStringDivisibility()
     35 {
     36     std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(18);
     37     std::vector<std::vector<std::string>> potentialSubLex(7, std::vector<std::string>());
     38     std::vector<llui> divisiblePermutations;
     39 
     40     for (int i = 0; i < 7; ++i)
     41         for (int j = 12; j <= 987; ++j)
     42             if ((j % primes[i] == 0) && (EulerUtility::hasUniqueDigits(j, true)))
     43                     potentialSubLex[i].push_back(((j < 100) ? "0" : "") + std::to_string(j));
     44 
     45     findDivisiblePermutations(divisiblePermutations, potentialSubLex, 6);
     46 
     47     BigInteger i = 0;
     48 
     49     for (uint64_t ul : divisiblePermutations)
     50         i += ul;
     51 
     52     return i;
     53 }