"""
Problem 92: https://projecteuler.net/problem=92

Square digit chains
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?
"""

DD = {str(i):i*i for i in range(10)}

Chain1 = {1}
Chain89 = {89}


def numberChain(n: int):
    global Chain1,Chain89

    if n in Chain1:
        return
    if n in Chain89:
        return

    ChainAppend = {n}
    while True:
        n = sum(map(lambda c:DD[c], str(n)))
        if n in Chain1:
            Chain1 |= ChainAppend
            break
        if n in Chain89:
            Chain89 |= ChainAppend
            break
        ChainAppend.add(n)


def solution(limit: int = 10000000) -> int:
    """
    How many starting numbers below ten million will arrive at 89?
    """
    for n in range(1,limit):
        numberChain(n)
    
    return len(Chain89)


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(solution())
    # 8581146