Fibonacci words
and round numbers
Weekly challenge 150 — 31 January 2022
Week 150: 31 Jan 2022
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.
This is a good example of a task where efficiency isn't an issue. You can probably generate a Fibonacci series up to the point where you run out of memory in milliseconds, and for the example above we only need 4 more terms to reach the 51 character length requested.
Even giving my vanilla algorithm with two starting strings which are 1 character long, and asking for the first term with 1000 characters you only need 14 terms beyond the two given ones.
And I could do the task as stated on paper in under 20 seconds!
#!/usr/bin/perl # Peter Campbell Smith - 2022-01-31 # PWC 150 task 1 use v5.28; use strict; use warnings; use utf8; my ($a, $b, $index, $j, $test, @fib, @tests, $big, $length); # sets of inputs to test ($a, $b, character index of interest) @tests = (['1234', '5678', 51], ['12345678', '98765432', 159], ['1234567890', '1234567890', 1000]); # loop over tests for $test (@tests) { # get parameters ($fib[0], $fib[1], $index) = @$test; # create successive ternms of series until one is long enough $j = 1; while (1) { $j ++; $fib[$j] = $fib[$j - 2] . $fib[$j - 1]; last if length($fib[$j]) >= $index; } # format the answer say qq[\nInput: $fib[0], $fib[1]]; $length = length($fib[$j]); $big = ''; $big .= qq[$1\n] while $fib[$j] =~ m|(.{50})|g; $big .= substr($fib[$j], int($length / 50) * 50); say qq[Character $index is ] . substr($fib[$j], $index - 1, 1) . qq[, term $j is $length characters long:\n$big]; }
Input: 1234, 5678 Character 51 is 7, term 6 is 52 characters long: 12345678567812345678567812345678123456785678123456 78 Input: 12345678, 98765432 Character 159 is 7, term 7 is 168 characters long: 98765432123456789876543212345678987654329876543212 34567898765432123456789876543298765432123456789876 54329876543212345678987654321234567898765432987654 321234567898765432 Input: 1234567890, 1234567890 Character 1000 is 0, term 11 is 1440 characters long: 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 1234567890123456789012345678901234567890
Any content of this website which has been created by Peter Campbell Smith is in the public domain