Perl Weekly Challenge 150: Fibonacci Words

    Input: $a = '1234' $b = '5678'
    Output: 7

    Fibonacci Words:

    '1234'
    '5678'
    '12345678'
    '567812345678'
    '12345678567812345678'
    '56781234567812345678567812345678'
    '1234567856781234567856781234567812345678567812345678'

    The 51st digit in the first term having at least 51 digits '1234567856781234567856781234567812345678567812345678' is 7.

I don't see how the given that the input strings having the same number of digits is going to buy us anything (except that having a lookup table becomes feasible). And the fact that the input strings only contain digits is useful for only one thing: it makes a bc solution possible.

This is fairly trivial. We'll just keep concatenating strings until we have reached the required length, then print the right character.

With the input in $_, we first split the input into two strings:

my ($fib_prev, $fib_last) = /[0-9]+/g;

Now we iterate:

my $LENGTH = 51;
while (length ($fib_last) < $LENGTH) {
    ($fib_prev, $fib_last) = ($fib_last, $fib_prev . $fib_last);
}

And we print the right character:

say substr $fib_last, $LENGTH - 1, 1;

Find the full program on GitHub.

In Bash, we cannot assign multiple variables at the same time, So we need an additional variable in the main loop.

LENGTH=51

while read fib_prev fib_last
do   while ((${#fib_last} < LENGTH))
     do  fib_tmp=$fib_last
         fib_last=$fib_prev$fib_last
         fib_prev=$fib_tmp
     done
     echo ${fib_last:$((LENGTH - 1)):1}
done

Find the full program on GitHub.

Bc doesn't do string operations (other than printing string literals). So, we have to work hard to "concatenate" strings consisting of numbers. We do this by repeatedly multiplying one of the strings by 10, until we have clear enough space for the other number to be added:

fib_prev = read ()
if (fib_prev == 0) {
    break
}
fib_last = read ()
if (fib_last == 0) {
    break
}

while (fib_last < 10 ^ 51) {
    fib_tmp = fib_last
    t = fib_last
    fib_last = fib_prev
    while (t > 0) {
        fib_last = fib_last * 10
        t = t / 10
    }
    fib_last = fib_last + fib_tmp
    fib_prev = fib_tmp
}

while (fib_last > 10 ^ 51) {
    fib_last = fib_last / 10
}

fib_last % 10

Find the full program on GitHub.

In Scheme, recursion is preferred over assignment. So, we define a recursive method to concatenate string until the required length, then print the right character:

(define (fib fib_prev fib_last)
    (if (>= (string-length fib_last) 51)
        (format #t "~c\n" (string-ref fib_last 50))
        (fib fib_last (string-concatenate (list fib_prev fib_last)))))

And a main program to read input, can call the method above:

(define (main)
    (define line (read-line))
    (if (not (eof-object? line))
        (begin
            (fib (list-ref (string-split line #\ ) 0)
                 (list-ref (string-split line #\ ) 1))
            (main))))

(main)

Find the full program on GitHub.