[Project Euler] Problem 92

원문: Problem 92

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?

숫자 체인은 숫자의 각 자리의 제곱을 연속해서 더한 것으로 만들어지고, 새로운 수는 전에 보였던 것이 나올 때까지 만든다. 예를 들면,

44 -> 32 -> 13 -> 10 -> 1 -> 1
85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89

그러므로 1 또는 89에 도달한 모든 체인은 무한 루프에 갇히게 된다. 매우 놀라운 것은 모든 시작하는 수는 결국 1 또는 89에 도달하게 된다. 얼마나 많은 천만 미만의 시작하는 수가 89에 도달하는가?

Brute force로, 모든 경우를 하나씩 테스트 하면 약 7분의 시간이 걸린다. 여기서 천만 미만의 수는 7자리의 수이기 때문에 최대 가능한 수는 81 * 7이다. 따라서 1 ~ 567까지의 chain만 미리 구한다면 그 이후의 수는 한 번의 chain 계산만으로 1 또는 89를 결정할 수 있다.

따라서 이를 적용하면 1분 정도로 줄게 되고, 0 ~ 9까지의 제곱을 미리 계산하면 20초 정도를 더 줄일 수 있다. 추가적으로 in 연산자를 사용하지 않고 1 ~ 567의 배열(리스트)을 만들어서 index를 사용하여 접근하면 20초 미만까지 줄일 수가 있다. 최종적으로 아래 코드는 15초까지 줄인 결과이다.

Python

l = [0] * 600                               # result cache
c = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]    # square cache

# initialize
l[1] = 1
l[89] = 89
count = 0

def nextNumber(number):
    s = 0
    while number > 0:
        s += c[number % 10]
        number //= 10
    return s

# create result cache
for start in range(1, 568):
    n = start
    while True:
        n = nextNumber(n)
        if l[n] == 1:
            l[start] = 1
            break
        elif l[n] == 89:
            count += 1
            l[start] = 89
            break

for start in range(568, 10000000):
    if l[nextNumber(start)] == 89:
        count += 1

print(count)

접기

추가적으로, 똑같은 알고리즘을 사용해서 C++로 구현하면 1초 이내로 시간을 줄일 수 있다! 이 문제를 풀면서, 파이썬의 경우 많은 횟수의 반복 연산에 대해서는 여전히 느린 것을 알 수 있었다. (혹은 파이썬을 아직도 제대로 못 짜는 것일 수도 있는데, 위에서 동일 알고리즘 내에서 더 개선이 가능한 지 모르겠다.)

C++

#include <iostream>

const int cache_number = 81 * 8 + 1;
int square_cache[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};   // square cache
int chain_cache[cache_number] = {0};                           // chain cache

int nextNumber(int number)
{
    int s = 0;
    while (number > 0) {
        s += square_cache[number % 10];
        number /= 10;
    }

    return s;
}

int main(void)
{
    int count = 0;

    // initialize
    chain_cache[89] = 89;
    chain_cache[1] = 1;

    // create chain_cache square_cache
    for (int i = 1; i < cache_number; i++) {
        int n = i;
        while (1) {
            n = nextNumber(n);

            if (chain_cache[n] == 1) {
                chain_cache[i] = 1;
                break;
            } else if (chain_cache[n] == 89) {
                chain_cache[i] = 89;
                count++;
                break;
            }
        }
    }

    for (int i = cache_number; i < 10000000; i++) {
        if (chain_cache[nextNumber(i)] == 89)
            count++;
    }

    std::cout<<count<<std::endl;

    return 0;
}

접기

참고로, 이 문제의 Thread에서 한 가지 힌트를 얻을 수 있었는데, 1234, 4321, 1423, 12340, 10234 등의 수의 경우 모두 같은 chain을 갖는다. 즉, 7자리의 숫자 내에서 같은 숫자를 가지는 조합은 같은 chain을 가지므로 1번만 계산을 할 수가 있다. 이를 이용하면 파이썬에서도 약 1초 이내로 계산이 가능하다.