Project Euler #230: Fibonacci Words Discussions |

3 years ago+ 7 comments

Here's another python version that is (hopefully?) reasonably well-commented to make it clear what's happening.

BTW I have to admit that I really find it astonishing how much cleaner the Python solutions to many of these problems look compared to other languages! To me, it's really much closer to the pseudocode I'd write. Or is it just me?

import os

def find_digit(A, B, n):
    lengths = [len(A)]
    if n <= len(A):
        return A[n-1]
    lengths.append(len(B))
    if n <= len(B):
        return B[n-1]

    idx = 1
    # Building up until we hit total digit length n.
    # Only count length though, do not build the actual string!
    while True:
        idx = idx + 1
        lengths.append(lengths[idx-2] + lengths[idx-1])
        if lengths[idx]  >= n:
            break

    # Going back recursively until we know where exactly to 
    # find digit n. Use the fact that 
    # sequence[i] = [sequence[i-2], sequence[i-1]].
    len_diff = n
    while idx > 1:
        if lengths[idx-2] < len_diff:
            # Digit n is in the second part of the sequence  
            # section currently considered.
            len_diff = len_diff - lengths[idx-2]
            idx = idx - 1
        else:
            # Digit n is in first part of the sequence section 
            # currently considered.
            idx = idx - 2

    if idx == 0:
        return A[len_diff-1]
    else:
        return B[len_diff-1]


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    num_tests = int(input().strip())
    tests = []
    for i in range(num_tests):
        A, B, n_str = input().rstrip().split()
        num = find_digit(A, B, int(n_str))
        fptr.write(str(num) + '\n')

    fptr.close()