4
\$\begingroup\$

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example:

44 → 32 → 13 → 10 → 1 → 1

85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

My solution doesn't finish in under a minute. I'm already caching the results of arrivesAt89, including all permutations. Any help is welcomed.

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>

int sumOfDigitsSquared(int n) {
    auto digits = std::to_string(n);
    int sum = 0;

    for (auto c : digits) {
        sum = (c - '0') * (c - '0');
    }

    return sum;
}

std::vector<int> permutations(int n) {
    auto digits = std::to_string(n);
    std::vector<int> res;
    res.push_back(n);

    do {
        res.push_back(stoi(digits));
    } while (std::next_permutation(digits.begin(), digits.end()));

    return res;
}

bool arrivesAt89(int n) {
    static auto cache = std::unordered_map<int,bool>();

    int m = n;
    while (m != 1) {
        if(cache.find(m) != cache.end()) {
            return cache.find(m)->second;
        }
        if (m == 89) {
            auto perms = permutations(m);
            for (auto p : perms) {
                cache.insert({p, true});
            }
            return true;
        }
        m = sumOfDigitsSquared(m);
    }

    auto perms = permutations(n);
    for (auto p : perms) {
        cache.insert({p, false});
    }
    return false;
}

int main() {
    int numberOf89s = 0;

    for (int i = 1; i< 10000000; i++) {
        if (arrivesAt89(i)) numberOf89s++;
    }

    std::cout << numberOf89s << std::endl;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Although I've answered it now... This code simply doesn't work. It will quickly enter an infinite loop. Code that doesn't work is off-topic for codereview, and on-topic for stackoverflow. \$\endgroup\$ – user673679 Dec 9 '18 at 10:46
  • \$\begingroup\$ As an aside, it would be more logical to use the smallest number in the circle as the canonical example, rather than the second-largest. But that's for Project Euler themselves. \$\endgroup\$ – Deduplicator Dec 9 '18 at 23:11
  • \$\begingroup\$ Project Euler asks people not to share solution code for obvious reasons. \$\endgroup\$ – Micha Wiedenmann Dec 9 '18 at 23:26
  • 5
    \$\begingroup\$ @MichaWiedenmann Consensus is that the goal of this site (code review) is more important than PE's request to keep solutions secret (which has obviously been ignored many times over on other sites including personal blogs, so the existence of solutions on SE isn't going to have any great effect). \$\endgroup\$ – Bob Dec 10 '18 at 0:06
  • \$\begingroup\$ @user673679 Problem statements without MCVE are not often on-topic for Stack Overflow, so please doublecheck that. \$\endgroup\$ – Mast Dec 10 '18 at 8:41
10
\$\begingroup\$
  • I guess the idea behind using permutations is that any permutation of the same digits will result in the same squared sum. However... in that case, shouldn't we simply calculate the squared sum and cache that?
  • It appears that we're only caching the permutations of the digits at the end of the chain. i.e. we'll only ever end up with 1, 89 and 98 in the map! We should probably be caching all the values in the chain up to the final result.
  • #include <string> for std::to_string.
  • Converting to and from std::string is probably quite slow. We can use simple integer arithmetic to extract the individual digits.
  • The implementation of sumOfDigitsSquared is clearly incorrect with basic testing.
\$\endgroup\$
  • \$\begingroup\$ The % can also be slow. Don't assume your method is faster without measuring. (I don't say it's slower, but you have to measure before making assumptions). \$\endgroup\$ – Calak Dec 9 '18 at 12:14
  • \$\begingroup\$ "The implementation of sumOfDigitsSquared is clearly incorrect with basic testing" can you explain why it's incorrect? \$\endgroup\$ – Calak Dec 9 '18 at 12:15
  • 2
    \$\begingroup\$ @Calak only the last iteration of the loop matters, it continuously overwrites sum. += is probably needed. \$\endgroup\$ – Wes Toleman Dec 9 '18 at 14:48
  • 1
    \$\begingroup\$ @WesTolemanWe I know, but I asked him to try to be more precise about why it doesn't work. Just telling "it's broken" without explaining why is almost pointless. \$\endgroup\$ – Calak Dec 9 '18 at 15:32
  • 1
    \$\begingroup\$ @Calak I think it's much better for OP to find the exact problem themselves. It's not hard to find, and doing so helps more with the actual issue (OP needs to learn to debug and test code). The point of that statement is "do basic testing", not "it's broken". \$\endgroup\$ – user673679 Dec 9 '18 at 16:33
3
\$\begingroup\$

Obviously, the algorithm provided will set up a number of equivalence classes of numbers containing the same ciphers. E. g. 1012, 1210, and all other permutations of are equivalent.

So you might want to sort the numbers by their digits (skipping all zeros), so you'd only have to store 112 for above numbers, or the other way round, only generate the sorted numbers by some appropriate algorithm.

Finally, you can easily generate the number of permutations from these numbers. Example above:

00 000 112

There are 8! but we need to divide by the number of equivalent permutations (due to the five zeros and the two ones), so we get:

8! / 5! / 2!

A mentioned number generator might look like this one:

std::vector<unsigned int> current({1, 2, 3, 4, 5, 6, 7, 8, 9 });
std::vector<unsigned int> previous;

for(unsigned int i = 0; i < 7; ++i)
{
    using std::swap;
    for(auto n : current)
        std::cout << n << ' ';
    std::cout << std::endl;
    swap(current, previous);
    current.clear();
    for(auto n : previous)
    {
        for(unsigned int m = 1; m <= n % 10; ++m)
        {
            current.push_back(n * 10 + m);
        }
    }
}

producing all sorted numbers up to 7 digits (OK, within numbers, sorting order is invers, but that's not of relevance...).

\$\endgroup\$
3
\$\begingroup\$

Plenty of good answers have been given I'll just point out that 10 million is actually not a lot.

The square sum of digits of 9999999 is 7*81=567 and this is the largest sum you can get. So to determine if any up to 7 digit number ends up as 1 or 89 cannot require more than 567 iterations of computing the sum of squared digits.

Meaning that brute force 567*10M=5.67 G iterations of computing sum of digits squared will solve it. Sum of digits squared using the trivial integer division approach is 7 divisions with remainder, 6 additions and 7 multiples, plus loop overhead call it 30 instructions, so in total you'd need 5.67*30~=16G instructions.

For a typical desktop computer with 4 GHz one core turbo and IPC of 2 (which is pessimistic for modern x86 CPUs) that amounts to 8 G instructions per second, which means brute force should take around two seconds if my math isn't completely of the charts wrong.

So you can do a bunch of clever stuff but it won't save you more than two seconds of CPU time over just brute forcing it. And you can do much worse than brute force as OPs solution doesn't complete after a whole minute by computing ineffective sums, allocating a bunch of memory left right and center, generating permutations and what not.

Edit: To prove my point:

I implemented the brute force soloution:

pe.cpp

#include <iostream>

int ssd(int n){
  int ans = 0;
  while(n){
    int d = n%10;
    n = n/10;
    ans += d*d;
  }
  return ans;
}

int main(int, char**){
  int n89 = 0;
  for(int n = 2; n < 10000000; n++){
    int s = ssd(n);
    while(s != 1 && s != 89){
      s = ssd(s);
    }
    if(s==89){
      n89++;
    }
  }
  std::cout<<n89<<std::endl;
}

And ran it, producing the correct solution in under half a second:

$ g++ -O3 pe.cpp -o pe && time ./pe
8581146

real    0m0.423s
user    0m0.423s
sys     0m0.000s

On my machine:

$ cat /proc/cpuinfo | grep "model name" | tail -n 1
model name  : Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz
\$\endgroup\$
  • \$\begingroup\$ Completing a challenge from the Euler Project should ask for more than mere brute force. The criterium stated on the home page is that the algorithm shouldn't take more than one minute on an average machine to complete. Your machine isn't what I'd call average, and using C++ over other slower languages is already a boost. Even if the original poster devised a rather clumsy solution, I believe he's right in trying to beat brute force. \$\endgroup\$ – papagaga Dec 11 '18 at 13:02
  • \$\begingroup\$ I disagree, some of the early questions can be solved with just pen and paper. While my machine is quite strong, it also computed the solution in less than 0.5 s on one core. So a machine with 1/120 the single core performance of mine should still make the 1 minute mark. So even something that has only a fifth of the performance of a VIA Eden 1 GHz low power CPU should still be able to compute it in under a minute... I bet even a Pentium 200 would make it under one minute (cpubenchmark.net/singleThread.html). I think that's below average, yes? \$\endgroup\$ – Emily L. Dec 11 '18 at 22:30
  • 1
    \$\begingroup\$ @papagaga what I'm trying to say is that sometimes the brute force solution is the best one, or at least good enough. For example shaker sort (two sided bubble sort) of faster than quicksort on almost sorted arrays (codereview.stackexchange.com/a/159974/36120). Knowing when you can and should use an "inefficient" solution is an important skill for a software engineer. \$\endgroup\$ – Emily L. Dec 11 '18 at 22:38
  • \$\begingroup\$ @EmiliL: ... I'm not sure how it happened, but I was mixing up minutes and seconds. You're absolutely right. \$\endgroup\$ – papagaga Dec 12 '18 at 7:52
3
\$\begingroup\$
int sumOfDigitsSquared(int n) {
    auto digits = std::to_string(n);
    int sum = 0;

    for (auto c : digits) {
        sum += (c - '0') * (c - '0'); // I corrected the = into +=
    }

    return sum;
}

Conversions come with a performance hit, especially when the conversion implies memory allocation and copy, as here with std::to_string. It would make perfect sense if you had some use for the string, but you don't, since you return another int. And the math behind it is really basic:

constexpr int sum_of_squared_digits(int n) {
    int res = 0;
    while (n) {
        const int digit = n % 10;
        res += digit * digit;
        n /= 10;
    }
    return res;
}

I've marked it constexpr, only to hint that the whole algorithm could be performed at compile-time, but it wouldn't really be fair, so it won't.

bool arrivesAt89(int n) {
    static auto cache = std::unordered_map<int,bool>();

unordered_map might not be necessary in this case. A simple array would suffice, with 0 meaning unexplored, 1 ending with 1 and 89 ending with 89: it's even faster and all the memory allocation is done upfront.

    int m = n;
    while (m != 1) {
        if(cache.find(m) != cache.end()) {
            return cache.find(m)->second;
        }
        if (m == 89) {
            auto perms = permutations(m);
            for (auto p : perms) {
                cache.insert({p, true});
            }
            return true;
        }
        m = sumOfDigitsSquared(m);

Here is I think the main weakness of your algorithm: you only cache the result for the number n and its permutations; all intermediary values are ignored, although they belong on the same path as n and would populate the map much faster.

    }

    auto perms = permutations(n);
    for (auto p : perms) {
        cache.insert({p, false});
    }
    return false;
}

Computing the permutations come with another heavy conversion, with memory allocation and copy (std::to_string) and a std::vector you won't use beyond feeding it to the static std::unordered_map inside your master function.

std::vector<int> permutations(int n) {
    auto digits = std::to_string(n);
    std::vector<int> res;
    res.push_back(n);

    do {
        res.push_back(stoi(digits));
    } while (std::next_permutation(digits.begin(), digits.end()));

Besides, it won't give you every permutation: if you want to go through all permutations with std::next_permutation, you need to start with a sorted std::string.

    return res;
}

Anyway, I don't think that permutations are the best way of testing the numbers equivalence: you don't need it if you keep track of intermediary values, because permutations will result in the same squared digits' sum.

Here what I'd find correctly optimized:

auto precompute_results(int n) {
    std::vector<int> results(n, 0); 
    // a vector instead of a map, 
    // elements can be:
    // 0 = unexplored, 1 = ending in 1, 89 = ending in 89
    // n = on the same path as n
    for (int i = 1; i < n; ++i) {
        auto cur = results[i] ? results[i] : i;
        while (true) {
            if (cur == 1 || cur == 89) break;
            if (cur < n && results[cur]) {
                cur = results[cur];
                continue; // we go down the path to either 1 or 89
            }
            if (cur < n) results[cur] = i; // we memorize that cur in on the same path as i
            cur = sum_of_squared_digits(cur);
        }
        results[i] = cur;
    }
    return results;
}
\$\endgroup\$
1
\$\begingroup\$

Sometimes it's good to remember the KISS principle.

With this in mind, first the squares of each digit is constant therefore a constant int[] to store those values will eliminate constantly multiplying them.

Integer math is much faster than string conversions.

One solution taking this in to account could look like this:

const int squares[] = { 0,1,4,9,16,25,36,49,64,81 };
bool IsSquareSum89(int num)
{
    int sum = 0;
    while (num != 89 && num != 1)
    {
        sum = 0;
        while (num > 0)
        {
            int digit = num % 10;
            sum += squares[digit];
            num /= 10;
        }
        num = sum;
    }
    return num == 89;
}
int GetAnswer(int target)
{
    int answer = 0;
    for (int i = target - 1; i > 0; --i)
    {
        if (IsSquareSum89(i))
        {
            ++answer;
        }
    }
    return answer;
}

On my machine this finds the answer in about 2 seconds.

\$\endgroup\$
  • \$\begingroup\$ So you optimize out a measly integer multiplication, that is right next to a division... that is wasted optimization effort. Plus: to fetch a value from an array requires an integer multiplication! \$\endgroup\$ – Cris Luengo Dec 11 '18 at 1:43
  • \$\begingroup\$ @CrisLuengo "to fetch a value from an array requires an integer multiplication" - Not always. For byte arrays, no operation is required. For an int array like this, rather than multiplication, you shift the index left by two, which is pretty cheap. \$\endgroup\$ – Reinderien Dec 11 '18 at 1:50
  • \$\begingroup\$ I'm pretty sure that the array access is more expensive than a multiplication: there is the memory access (maybe 100 × longer than a multiplication) and the offset calculation \$\endgroup\$ – papagaga Dec 11 '18 at 8:02
  • \$\begingroup\$ @papagaga - when I compare this code with EmilyL's , which uses the same basic algorithm, this code is slightly faster. The difference is probably close enough to say that they're even. \$\endgroup\$ – tinstaafl Dec 11 '18 at 12:17
  • \$\begingroup\$ You're right: in this case, since your array is small enough to hold in a cache line, access won't cost more than a multiplication -but still not much less either, whereas it makes the program a little more complicated. \$\endgroup\$ – papagaga Dec 11 '18 at 13:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.