project-euler

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

Euler_61.cpp (1860B)

      1 #include <numeric>
      2 
      3 #include "Euler.h"
      4 
      5 bool match(int a, int b)
      6 {
      7     std::vector<int> digits_a = EulerUtility::intToDigits(a);
      8     std::vector<int> digits_b = EulerUtility::intToDigits(b);
      9 
     10     return (digits_a[2] == digits_b[0] && digits_a[3] == digits_b[1]);
     11 }
     12 
     13 int recurseFigurates(std::vector<int> cycle, std::vector<std::vector<int>> &figurates, std::vector<int> indices, int index)
     14 {
     15     for (int swap_index = index + 1; swap_index < 7; ++swap_index)
     16     {
     17         for (int i : figurates[indices[index]])
     18         {
     19             if (match(cycle[cycle.size() - 1], i))
     20             {
     21                 cycle.push_back(i);
     22 
     23                 int answer = ((cycle.size() == 6) && (match(cycle[cycle.size() - 1], cycle[0]))) ?
     24                     std::accumulate(cycle.begin(), cycle.end(), 0) : ((cycle.size() == 6) || (index >= 5)) ? 0 :
     25                     recurseFigurates(cycle, figurates, indices, index + 1);
     26 
     27                 if (answer != 0)
     28                 {
     29                     return answer;
     30                 }
     31 
     32                 cycle.pop_back();
     33             }
     34         }
     35 
     36         if (swap_index < 6)
     37         {
     38             int temp = indices[swap_index];
     39             indices.erase(indices.begin() + swap_index);
     40             indices.insert(indices.begin() + index, temp);
     41         }
     42     }
     43 
     44     return 0;
     45 }
     46 
     47 int Euler::CyclicFigurateNumbers()
     48 {
     49     std::vector<std::vector<int>> figurates;
     50     std::vector<int> indices;
     51     std::vector<int> cycle;
     52 
     53     for (int i = 0; i < 6; ++i)
     54     {
     55         indices.push_back(i);
     56         figurates.push_back(EulerUtility::getFigurates(i + 3, 1000, 10000));
     57     }
     58 
     59     for (int i : figurates[0])
     60     {
     61         cycle.push_back(i);
     62 
     63         int answer = recurseFigurates(cycle, figurates, indices, 1);
     64 
     65         if (answer != 0)
     66         {
     67             return answer;
     68         }
     69 
     70         cycle.pop_back();
     71     }
     72 
     73     return 0;
     74 }