p61.cpp

/**
 * Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers
 * are all figurate (polygonal) numbers and are generated by the following
 * formulae:
 *
 *   Triangle   P3(n)=n(n+1)/2    1, 3, 6, 10, 15, ...
 *   Square     P4(n)=n^2         1, 4, 9, 16, 25, ...
 *   Pentagonal P5(n)=n(3n-1)/2   1, 5, 12, 22, 35, ...
 *   Hexagonal  P6(n)=n(2n-1)     1, 6, 15, 28, 45, ...
 *   Heptagonal P7(n)=n(5n-3)/2   1, 7, 18, 34, 55, ...
 *   Octagonal  P8(n)=n(3n-2)     1, 8, 21, 40, 65, ...
 *
 * The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three
 * interesting properties:
 * - The set is cyclic, in that the last two digits of each number is the
 *   first two digits of the next number (including the last number with
 *   the first).
 * - Each polygonal type: triangle P3(127)=8128, square P4(91)=8281, and
 *   pentagonal P5(44)=2882, is represented by a different number in the set.
 * - This is the only set of 4-digit numbers with this property.
 *
 * Find the sum of the only ordered set of six cyclic 4-digit numbers for
 * which each polygonal type: triangle, square, pentagonal, hexagonal,
 * heptagonal, and octagonal, is represented by a different number in the set.
 *
 * ANSWER: 28684.
 */

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
#include "euler.h"

BEGIN_PROBLEM(61, solve_problem_61)
  PROBLEM_TITLE("Cyclical figurate numbers")
  PROBLEM_ANSWER("28684")
  PROBLEM_DIFFICULTY(1)
  PROBLEM_FUN_LEVEL(1)
  PROBLEM_TIME_COMPLEXITY("?")
  PROBLEM_SPACE_COMPLEXITY("?")
END_PROBLEM()

// Generate four-digit figurate numbers n and store them in vector P.
// n = (a*n^2 + b*n) / d
static void generate(std::vector<uint16_t> &P, int a, int b, int d)
{
  int p = (a + b) / d;
  int n = 1;
  while (p < 10000)
  {
    if (p >= 1000)
    {
      P.push_back(static_cast<uint16_t>(p));
    }
    p += (2*a*n + a + b) / d;
    n++;
  }
}

static std::vector<uint16_t> P[6];

void find_cycle(bool exists[6], uint16_t list[6], int count)
{
  if (count == 6)
  {
    if (list[5] % 100 == list[0] / 100)
    {
      // std::cout << list[0] << std::endl;
      int sum = std::accumulate(list+0, list+6, 0);
      std::cout << sum << std::endl;
    }
  }
  else if (count == 0)
  {
    exists[0] = true;
    for (uint16_t v: P[0])
    {
      list[0] = v;
      find_cycle(exists, list, 1);
    }
    exists[0] = false;
  }
  else
  {
    uint16_t match = list[count-1] % 100;
    for (int k = 1; k <= 5; k++)
    {
      if (!exists[k])
      {
        exists[k] = true;
        auto it = std::lower_bound(P[k].cbegin(), P[k].cend(), match * 100);
        for (; (it != P[k].cend()) && (*it / 100 == match); ++it)
        {
          list[count] = *it;
          find_cycle(exists, list, count+1);
        }
        exists[k] = false;
      }
    }
  }
}

static void solve_problem_61()
{
  // Generate four-digit triangle-octagonal numbers.
  generate(P[0], 1,  1, 2); // triangle
  generate(P[1], 1,  0, 1); // square
  generate(P[2], 3, -1, 2); // pentagonal
  generate(P[3], 2, -1, 1); // hexagonal
  generate(P[4], 5, -3, 2); // heptagonal
  generate(P[5], 3, -2, 1); // octagonal

  // Find the cyclic list.
  bool exists[6] = {false};
  uint16_t list[6];
  find_cycle(exists, list, 0);
}