寻找数字河流的交汇点

Question

我遇到了以下问题：

A digital river is a sequence of numbers where every number is followed by the same number plus the sum of its digits. In such a sequence 123 is followed by 129 (since 1 + 2 + 3 = 6), which again is followed by 141.

We call a digital river river K, if it starts with the value K. For example:
river 7 is the sequence beginning with {7, 14, 19, 29, 40, 44, 52, ... } and
river 471 is the sequence beginning with {471, 483, 498, 519, ... }.

Digital rivers can meet. This happens when two digital rivers share the same values. River 32 meets river 47 at 47, while river 471 meets river 480 at 519.

Given two meeting digital rivers, print out the meeting point.

为了解决这个问题，我编写了以下代码（r_1和r_2是河流的起点）：

r_1 = [int(input())]
r_2 = [int(input())]

while True:
    r_1.append(r_1[-1] +  sum([int(d) for d in str(r_1[-1])]))
    r_2.append(r_2[-1] +  sum([int(d) for d in str(r_2[-1])]))
    if r_2[-1] in r_1:
        print(r_2[-1]),
        break
    elif r_1[-1] in r_2:
        print(r_1[-1])
        break

这段代码可以工作，但是当r_1或r_2很大，并且集合点远离河流时，计算时间太长。我使用了一个while循环和两个if语句，所以我看不出如何改进这段代码

我怎样才能减少时间

Answer 1

您正在向两个列表中添加新项目，而不管它们相距有多远。尝试只计算河流中具有较低值的下一步，而不是同时计算这两步，这可能会导致不需要的额外计算

while True:
    # if its found, break
    if r_1[-1] == r_2[-1]:
        print(r_1[-1])
        break
    else:
        # if r_1 is larger, only increment r_2
        if r_1[-1] > r_2[-1]:
            r_2.append(r_2[-1] + sum([int(d) for d in str(r_2[-1])]))
        # if r_2 is larger, only increment r_1
        elif r_1[-1] < r_2[-1]:
            r_1.append(r_1[-1] + sum([int(d) for d in str(r_1[-1])]))

注意：这也没有指定上限，因此如果河流永远不匹配，可能会永远运行

Answer 2

很明显，数字河流是一个不断增加的序列，它从不减少。因此，要找到两条河流的汇合点，只需跟踪两条河流的当前值，并只更新值最小的河流。如果它超过了另一个，那么向前推进另一个…等等，直到你得到相同的值

同样，您只需要以这种方式保持更新的值。没有理由建立一个列表

例如：

a = 471
b = 480

while a != b:
    if a < b:
        a += sum([int(d) for d in str(a)])
    else:
        b += sum([int(d) for d in str(b)])

print(a) # 519