# Perl Weekly Challenge 150: Fibonacci Words

by Abigail

## Challenge

You are given two strings having same number of digits, $a and $b.

Write a script to generate Fibonacci Words by concatenation of the previous two strings. Finally print 51st digit of the first term having at least 51 digits.

### Example:

    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.


## Discussion

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.

## Solution

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

### Perl

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. ### Bash 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

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
}
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.

### Scheme

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)
(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.

### Other languages

We also have implementations in:

AWK, C, Go, Java, Lua, Node.js, Pascal, Python, R, Ruby, and Tcl.