euler-0061.cpp

// ////////////////////////////////////////////////////////
// # Title
// Cyclical figurate numbers
//
// # URL
// https://projecteuler.net/problem=61
// http://euler.stephan-brumme.com/61/
//
// # Problem
// Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:
//
// ||    6       ||         11          ||     9                 ||
// || Triangle   || `P_{3,n}=n(n+1)/2`  || 1, 3, 6, 10, 15, ...  ||
// || Square     || `P_{4,n}=n^2`       || 1, 4, 9, 16, 25, ...  ||
// || Pentagonal || `P_{5,n}=n(3n-1)/2` || 1, 5, 12, 22, 35, ... ||
// || Hexagonal  || `P_{6,n}=n(2n-1)`   || 1, 6, 15, 28, 45, ... ||
// || Heptagonal || `P_{7,n}=n(5n-3)/2` || 1, 7, 18, 34, 55, ... ||
// || Octagonal  || `P_{8,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 (`P_{3,127}=8128`), square (`P_{4,91}=8281`), and pentagonal (`P_{5,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.
//
// # Solved by
// Stephan Brumme
// March 2017
//
// # Algorithm
// The container ''all'' contains a simple bitmask for each number ''x'':
// - if the 3rd bit is set, then ''x'' is a triangle number
// - if the 4th bit is set, then ''x'' is a square number
// - if the 5th bit is set, then ''x'' is a pentagonal number
// - if the 6th bit is set, then ''x'' is a hexagonal number
// - if the 7th bit is set, then ''x'' is a heptagonal number
// - if the 8th bit is set, then ''x'' is a octagonal number
//
// Function ''deeper'' recursively builds a ''sequence'' of number, where each number's highest two digits are equal to its predecessor's lowest two digits.
// Even more, all numbers represent differetn categories (triangle, square, pentagonal, ...).
//
// Some numbers belong to multiple categories. In such a case, all combinations have to be tried.
// A number must not occur twice in a sequence. And finally, the last number's lowest two digits have to match the first number's highest two digits, too.

#include <set>
#include <vector>
#include <iostream>

// all sums of valid sequences
std::set<unsigned int> results;

// 4 digits => all numbers must be below 10^4 = 10000
const unsigned int Limit = 10000;
// all number sets per number as a bitmask
std::vector<unsigned int> all(Limit, 0);

// bit mask of all categories (e.g. 1<<3 for triangle numbers, 1<<4 for square numbers, ...)
unsigned int finalMask = 0;

// add a category to a number
void add(unsigned int x, unsigned int category)
{
  // reject if not exactly 4 digits
  if (x < 1000 || x >= 10000)
    return;

  // set one bit
  auto bit = 1 << category;
  // adjust its bitmask
  all[x] |= bit & finalMask;
}

void deeper(std::vector<unsigned int>& sequence, unsigned int mask = 0)
{
  // all four digit-numbers
  unsigned int from =  1000;
  unsigned int to   = 10000;

  if (!sequence.empty())
  {
    // we only have to look at those numbers where the highest two digits match
    // the previous numbers lowest two digits
    auto lowerTwoDigits = sequence.back() % 100;
    from = lowerTwoDigits * 100;
    to   = from + 100;
  }

  // try all relevant numbers
  for (auto next = from; next < to; next++)
  {
    auto categories = all[next];
    // not a member of any relevant set ?
    if (categories == 0)
      continue;

    // must not use the same number twice
    bool isUnique = true;
    for (auto x : sequence)
      if (x == next)
      {
        isUnique = false;
        break;
      }
    if (!isUnique)
      continue;

    // extract all categories it belongs to
    for (auto j = 3; j <= 8; j++)
    {
      auto thisCategory = 1 << j;
      // not a member of that category ?
      if ((categories & thisCategory) == 0)
        continue;

      // must be a new category we haven't seen yet in the current sequence
      if ((mask & thisCategory) != 0)
        continue;

      // we have all categories ?
      auto nextMask = mask | thisCategory;
      if (nextMask == finalMask)
      {
        // must compare against first number, too
        auto first = sequence.front();

        auto lowerTwoDigits = next  % 100;
        auto upperTwoDigits = first / 100;

        if (lowerTwoDigits == upperTwoDigits)
        {
          // we found a result, store its sum
          auto sum = next;
          for (auto x : sequence)
            sum += x;
          results.insert(sum);
        }
      }
      else
      {
        // go deeper
        sequence.push_back(next);
        deeper(sequence, nextMask);
        sequence.pop_back();
      }
    }
  }
}

int main()
{
  // only some sets are relevant to current problem
  unsigned int numSets;
  std::cin >> numSets;
  for (unsigned int i = 0; i < numSets; i++)
  {
    unsigned int x;
    std::cin >> x;
    finalMask |= 1 << x;
  }

  // build sets
  unsigned int n = 1;
  while (true)
  {
    auto triangle = n * (n + 1) / 2;
    // triangle numbers grow the slowest, once we have all of those then we are done
    if (triangle >= 10000)
      break;

    // add a triangle number
    add(triangle, 3);

    // add a square number
    auto square   = n * n;
    add(square,   4);

    // add a pentagonal number
    auto pentagon = n * (3 * n - 1) / 2;
    add(pentagon, 5);

    // add a hexagonal number
    auto hexagon  = n * (2 * n - 1);
    add(hexagon,  6);

    // add a heptagonal number
    auto heptagon = n * (5 * n - 3) / 2;
    add(heptagon, 7);

    // add an octagonal number
    auto octagon  = n * (3 * n - 2);
    add(octagon,  8);

    n++;
  }

  // start search with an empty sequence
  std::vector<unsigned int> sequence;
  deeper(sequence);

  // print all results in ascending order
  for (auto x : results)
    std::cout << x << std::endl;

  return 0;
}