euler-0259.cpp

// ////////////////////////////////////////////////////////
// # Title
// Reachable Numbers
//
// # URL
// https://projecteuler.net/problem=259
// http://euler.stephan-brumme.com/259/
//
// # Problem
// A positive integer will be called reachable if it can result from an arithmetic expression obeying the following rules:
//
// - Uses the digits 1 through 9, in that order and exactly once each.
// - Any successive digits can be concatenated (for example, using the digits 2, 3 and 4 we obtain the number 234).
// - Only the four usual binary arithmetic operations (addition, subtraction, multiplication and division) are allowed.
// - Each operation can be used any number of times, or not at all.
// - Unary minus is not allowed.
// - Any number of (possibly nested) parentheses may be used to define the order of operations.
//
// For example, 42 is reachable, since (1/23) * ((4*5)-6) * (78-9) = 42.
//
// What is the sum of all positive reachable integers?
//
// # Solved by
// Stephan Brumme
// July 2017
//
// # Algorithm
// I wrote a very basic ''struct Fraction'' to represent a rational number. It supports addition, multiplication, division and comparison.
// It doesn't care about signs, division-by-zero and so on.
//
// My ''search'' function returns all fractions that can be generated by splitting its ''std::string'' parameter in any possible way
// and applying any allowed operation:
// - it splits its input into two parts
// - then calls itself recursively to get all fractions generated by the left part and by the right part
// - two nested loops add, subtract, multiply and divide all fractions from the left part with all fractions from the right part
// - invalid things, like division-by-zero, are rejected and subtraction is simulated by adding with a negated numerator
// - there might be several combinations that produce the same result, therefore the output is sorted and ''std::unique'' ensures only unique fractions are left
// - (I don't reduce fractions and so it's possible to have the same fraction multiple times if their numerators and denominators differ by a factor)
//
// ''main'' has to check whether these fractions are positive integers.
// And finally all duplicates are removed and the sum of all unique integers is displayed.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

// a rational number
// fractions are neither reduced nor is the sign kept consistent
// (both numerator and denominator might be negative)
struct Fraction
{
  // create a new number
  Fraction(unsigned int numerator_, unsigned int denominator_ = 1)
  : numerator(numerator_), denominator(denominator_)
  {}

  // add
  Fraction operator+(const Fraction& other) const
  {
    return Fraction(numerator   * other.denominator + other.numerator * denominator,
                    denominator * other.denominator);
  }
  // multiply
  Fraction operator*(const Fraction& other) const
  {
    return Fraction(numerator   * other.numerator,
                    denominator * other.denominator);
  }
  // divide
  Fraction operator/(const Fraction& other) const
  {
    return Fraction(numerator * other.denominator,
                    denominator * other.numerator);
    // note: I don't attempt to reduce the fraction
  }

  // for std::sort
  bool operator<(const Fraction& other) const
  {
    return numerator * other.denominator <  denominator * other.numerator;
  }
  // for std::unique
  bool operator==(const Fraction& other) const
  {
    return numerator * other.denominator == denominator * other.numerator;
  }

  // both might have a negative sign
  int numerator;
  int denominator;
};


// return all rational numbers that can be produced by the sequence of digits
std::vector<Fraction> search(const std::string& digits)
{
  // if no operations are applied, then all digits might be a single number
  std::vector<Fraction> result = { Fraction(std::stod(digits)) };

  // split digits into two parts and apply an operation on them
  for (size_t split = 1; split < digits.size(); split++)
  {
    auto left  = digits.substr(0, split);
    auto right = digits.substr(split);

    // recursively find all fractions that can be created with these parts
    auto leftFractions  = search(left);
    auto rightFractions = search(right);

    // merge both with + - * /
    for (auto x : leftFractions)
      for (auto y : rightFractions)
      {
        // add
        result.push_back(x + y);
        // subtract: not really implemented, just negate second number's numerator and then add
        result.push_back(x + Fraction(-y.numerator, y.denominator));
        // multiply
        result.push_back(x * y);
        // divide: disallow division by zero
        if (y.numerator != 0)
          result.push_back(x / y);
      }
  }

  // prune redundant values (makes the code about 10x faster !)
  if (result.size() > 1)
  {
    std::sort(result.begin(), result.end());
    auto last = std::unique(result.begin(), result.end());
    result.erase(last, result.end());
  }

  return result;
}

int main()
{
  unsigned int lastDigit = 9;
  std::cin >> lastDigit;

  // create a string with all digits in ascending order (from 1 to lastDigit)
  std::string digits = "123456789";
  digits = digits.substr(0, lastDigit);

  // find all possible fractions
  auto fractions = search(digits);

  // all found values
  std::vector<int> found;

  // extract all integers from these fractions
  for (auto current: fractions)
  {
    // remove negative sign from denominator
    if (current.denominator < 0)
    {
      current.numerator   *= -1;
      current.denominator *= -1;
    }
    // fraction must be positive
    if (current.numerator <= 0)
      continue;

    // numerator must be a multiple of its denominator (=> fraction must be an integer)
    if (current.numerator % current.denominator == 0)
      found.push_back(current.numerator / current.denominator);
  }

  // remove duplicates
  std::sort(found.begin(), found.end());
  auto last = std::unique(found.begin(), found.end());
  found.erase(last, found.end());

  // add all
  unsigned long long sum = 0;
  for (auto x : found)
    sum += x;

  // show result
  std::cout << sum << std::endl;
  return 0;
}