project-euler

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

Euler_68.cpp (2048B)

      1 #include <algorithm>
      2 #include <set>
      3 #include "Euler.h"
      4 
      5 std::string magicString(std::vector<int**> rows)
      6 {
      7     int lowestIndex = 0;
      8     int lowestVal = 11;
      9 
     10     for (int i = 0; i < 5; ++i)
     11     {
     12         if (*rows[i][0] < lowestVal)
     13         {
     14             lowestVal = *rows[i][0];
     15             lowestIndex = i;
     16         }
     17     }
     18 
     19     std::string magic5;
     20 
     21     for (int i = 0; i < 5; ++i)
     22     {
     23         int index = (i + lowestIndex) % 5;
     24 
     25         if ( *rows[index][0] == 10)
     26         {
     27             magic5.push_back('1');
     28             magic5.push_back('0');
     29         }
     30         else
     31         {
     32             magic5.push_back(*rows[index][0] + '0');
     33         }
     34 
     35         magic5.push_back(*rows[index][1] + '0');
     36         magic5.push_back(*rows[index][2] + '0');
     37     }
     38 
     39     return magic5;
     40 }
     41 
     42 int sumRow(int* row[])
     43 {
     44     return *row[0] + *row[1] + *row[2];
     45 }
     46 
     47 std::string Euler::Magic5GonRing()
     48 {
     49     std::vector<int> nodes;
     50     std::set<std::string> magicStrings;
     51 
     52     for (int i = 1; i <= 10; ++i)
     53         nodes.push_back(i);
     54 
     55     int* row1[] = { &nodes[0], &nodes[1], &nodes[2] };
     56     int* row2[] = { &nodes[3], &nodes[2], &nodes[4] };
     57     int* row3[] = { &nodes[5], &nodes[4], &nodes[6] };
     58     int* row4[] = { &nodes[7], &nodes[6], &nodes[8] };
     59     int* row5[] = { &nodes[9], &nodes[8], &nodes[1] };
     60 
     61     std::vector<int**> rows;
     62 
     63     rows.push_back(row1);
     64     rows.push_back(row2);
     65     rows.push_back(row3);
     66     rows.push_back(row4);
     67     rows.push_back(row5);
     68 
     69     for (int i = 1; i < EulerUtility::factorial(10); ++i)
     70     {
     71         std::next_permutation(nodes.begin(), nodes.end());
     72 
     73         int val = sumRow(row1);
     74 
     75         if ((*row1[0] == 10 || *row2[0] == 10 || *row3[0] == 10 || *row4[0] == 10 || *row5[0] == 10)
     76             && ((sumRow(row2) == val) && (sumRow(row3) == val) && (sumRow(row4) == val) && (sumRow(row5) == val)))
     77             magicStrings.insert(magicString(rows));
     78     }
     79 
     80     std::set<std::string>::iterator it;
     81     std::string last;
     82 
     83     for (it = magicStrings.begin(); it != magicStrings.end(); ++it)
     84         last = *it;
     85 
     86     return last;
     87 }