Determining the individual letters of Fibonacci strings?

Question

The Fibonacci strings are defined as follows:

• The first Fibonacci string is "a"
• The second Fibonacci string is "bc"
• The (n + 2)nd Fibonacci string is the concatenation of the two previous Fibonacci strings.

For example, the first few Fibonacci strings are

a
bc
abc
bcabc
abcbcabc

The goal is, given a row and an offset, to determine what character is at that offset. More formally:

Input: Two integers separated by a space - K and P(0 < K ≤ 10⁹), ( < P ≤ 10⁹), where K is the line number of the Fibonacci string and P is the position number in a row.

Output: The desired character for the relevant test: "a", "b" or "c". If P is greater than the kth row (K ≤ 10⁹), it is necessary to derive «No solution»

Example:

input: 18 58

output: a

I wrote this code to solve the problem:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int k, p;
    string s1 = "a";
    string s2 = "bc";
    vector < int >fib_numb;
    fib_numb.push_back(1);
    fib_numb.push_back(2);
    cin >> k >> p;
    k -= 1;
    p -= 1;
    while (fib_numb.back() < p) {
        fib_numb.push_back(fib_numb[fib_numb.size() - 1] + fib_numb[fib_numb.size() - 2]);
    }
    if (fib_numb[k] <= p) {
        cout << "No solution";
        return 0;
    }
    if ((k - fib_numb.size()) % 2 == 1)
        k = fib_numb.size() + 1;
    else
        k = fib_numb.size();
    while (k > 1) {
        if (fib_numb[k - 2] > p)
            k -= 2;
        else {
            p -= fib_numb[k - 2];
            k -= 1;
        }
    }
    if (k == 1)
        cout << s2[p];
    else
        cout << s1[0];
    return 0;
}

Is it correct? How would you have done?

Answer 1

You can solve this problem without explicitly computing any of the strings, and this is probably the best way to solve the problem. After all, if you're asked to compute the 50th Fibonacci string, you're almost certain to run out of memory; F(50) is 12,586,269,025, so you'd need over 12Gb of memory just to hold it!

The intuition behind the solution is that because each line of the Fibonacci strings are composed of the characters of the previous lines, you can convert an (row, offset) pair into a different (row', offset') pair where the new row is always for a smaller Fibonacci string than the one you started with. If you repeat this enough times, eventually you will arrive back at the Fibonacci strings for either row 0 or row 1, in which case the answer can immediately be read off.

In order to make this algorithm work, we need to establish a few facts. First, let's define the Fibonacci series to be zero-indexed; that is, the sequence is

F(0)   = 0
F(1)   = 1
F(n+2) = F(n) + F(n + 1)

Given this, we know that the nth row (one-indexed) of the Fibonacci strings has a total of F(n + 1) characters in it. You can see this quickly by induction:

• Row 1 has length 1 = F(2) = F(1 + 1)
• Row 2 has length 2 = F(3) = F(2 + 1).
• For some row n + 2, the length of that row is given by Size(n) + Size(n + 1) = F(n + 1) + F(n + 2) = F(n + 3) = F((n + 2) + 1)

Using this knowledge, let's suppose that we want to find the seventh character of the seventh row of the Fibonacci strings. We know that row seven is composed of the concatenation of rows five and six, so the string looks like this:

  R(7) = R(5) R(6)

Row five has F(5 + 1) = F(6) = 8 characters in it, which means that the first eight characters of row seven come from R(5). Since we want the seventh character out of this row, and since 7 ≤ 8, we know that we now need to look at the seventh character of row 5 to get this value. Well, row 5 looks like the concatenation of rows 3 and 4:

  R(5) = R(3) R(4)

We want to find the seventh character of this row. Now, R(3) has F(4) = 3 characters in it, which means that if we are looking for the seventh character of R(5), it's going to be in the R(4) part, not the R(3) part. Since we're looking for the seventh character of this row, it means that we're looking for the the 7 - F(4) = 7 - 3 = 4th character of R(4), so now we look there. Again, R(4) is defined as

 R(4) = R(2) R(3)

R(2) has F(3) = 2 characters in it, so we don't want to look in it to find the fourth character of the row; that's going to be contained in R(3). The fourth character of the line must be the second character of R(3). Let's look there. R(3) is defined as

 R(3) = R(1) R(2)

R(1) has one character in it, so the second character of this line must be the first character of R(1), so we look there. We know, however, that

 R(2) = bc

So the first character of this string is b, which is our answer. Let's see if this is right. The first seven rows of the Fibonacci strings are

1 a
2 bc
3 abc
4 bcabc
5 abcbcabc
6 bcabcabcbcabc
7 abcbcabcbcabcabcbcabc

Sure enough, if you look at the seventh character of the seventh string, you'll see that it is indeed a b. Looks like this works!

More formally, the recurrence relation we are interested in looks like this:

char NthChar(int row, int index) {
    if (row == 1) return 'a';
    if (row == 2 && index == 1) return 'b';
    if (row == 2 && index == 2) return 'c';
    if (index < Fibonacci(row - 1)) return NthChar(row - 2, index);
    return NthChar(row - 1, index - Fibonacci(row - 1));
}

Now, of course, there's a problem with the implementation as written here. Because the row index can range up to 10⁹, we can't possibly compute Fibonacci(row) in all cases; the one billionth Fibonacci number is far too large to represent!

Fortunately, we can get around this. If you look at a table of Fibonacci numbers, you'll find that F(45) = 1,134,903,170, which is greater than 10⁹ (and no smaller Fibonacci number is greater than this). Moreover, since we know that the index we care about must also be no greater than one billion, if we're in row 46 or greater, we will always take the branch where we look in the first half of the Fibonacci string. This means that we can rewrite the code as

char NthChar(int row, int index) {
    if (row == 1) return 'a';
    if (row == 2 && index == 1) return 'b';
    if (row == 2 && index == 2) return 'c';

    /* Avoid integer overflow! */
    if (row >= 46) return NthChar(row - 2, index);

    if (index < Fibonacci(row - 1)) return NthChar(row - 2, index);
    return NthChar(row - 1, index - Fibonacci(row - 1));
}

At this point we're getting very close to a solution. There are still a few problems to address. First, the above code will almost certainly blow out the stack unless the compiler is good enough to use tail recursion to eliminate all the stack frames. While some compilers (gcc, for example) can detect this, it's probably not a good idea to rely on it, and so we probably should rewrite this recursive function iteratively. Here's one possible implementation:

char NthChar(int row, int index) {
    while (true) {
       if (row == 1) return 'a';
       if (row == 2 && index == 1) return 'b';
       if (row == 2 && index == 2) return 'c';

       /* Avoid integer overflow! */
       if (row >= 46 || index < Fibonacci(row - 1)) {
           row -= 2;
       } else {
           index -= Fibonacci(row - 1);
           row --;
       }
    }
}

But of course we can still do much better than this. In particular, if you're given a row number that's staggeringly huge (say, one billion), it's really silly to keep looping over and over again subtracting two from the row until it becomes less than 46. It makes a lot more sense to just determine what value it's ultimately going to become after we do all the subtraction. But we can do this quite easily. If we have an even row that's at least 46, we'll end up subtracting out 2 until it becomes 44. If we have an odd row that's at least 46, we'll end up subtracting out 2 until it becomes 45. Consequently, we can rewrite the above code to explicitly handle this case:

char NthChar(int row, int index) {
    /* Preprocess the row to make it a small value. */
    if (row >= 46) {
        if (row % 2 == 0)
            row = 45;
        else
            row = 44;
    }

    while (true) {
       if (row == 1) return 'a';
       if (row == 2 && index == 1) return 'b';
       if (row == 2 && index == 2) return 'c';

       if (index < Fibonacci(row - 1)) {
           row -= 2;
       } else {
           index -= Fibonacci(row - 1);
           row --;
       }
    }
}

There's one last thing to handle, which is what happens if there isn't a solution to the problem because the character is out of range. But we can easily fix this up:

string NthChar(int row, int index) {
    /* Preprocess the row to make it a small value. */
    if (row >= 46) {
        if (row % 2 == 0)
            row = 45;
        else
            row = 44;
    }

    while (true) {
       if (row == 1 && index == 1) return "a"
       if (row == 2 && index == 1) return "b";
       if (row == 2 && index == 2) return "c";

       /* Bounds-checking. */
       if (row == 1) return "no solution";
       if (row == 2) return "no solution";

       if (index < Fibonacci(row - 1)) {
           row -= 2;
       } else {
           index -= Fibonacci(row - 1);
           row --;
       }
    }
}

And we've got a working solution.

One further optimization you might do is precomputing all of the Fibonacci numbers that you'll need and storing them in a giant array. You only need Fibonacci values for F(2) through F(44), so you could do something like this:

const int kFibonacciNumbers[45] = {
    0, 1, 1, 2, 3, 5, 
    8, 13, 21, 34, 55, 89,
    144, 233, 377, 610,
    987, 1597, 2584, 4181,
    6765, 10946, 17711, 28657,
    46368, 75025, 121393, 196418,
    317811, 514229, 832040,
    1346269, 2178309, 3524578,
    5702887, 9227465, 14930352,
    24157817, 39088169, 63245986,
    102334155, 165580141, 267914296,
    433494437, 701408733
};

With this precomputed array, the final version of the code would look like this:

string NthChar(int row, int index) {
    /* Preprocess the row to make it a small value. */
    if (row >= 46) {
        if (row % 2 == 0)
            row = 45;
        else
            row = 44;
    }

    while (true) {
       if (row == 1 && index == 1) return "a"
       if (row == 2 && index == 1) return "b";
       if (row == 2 && index == 2) return "c";

       /* Bounds-checking. */
       if (row == 1) return "no solution";
       if (row == 2) return "no solution";

       if (index < kFibonacciNumbers[row - 1]) {
           row -= 2;
       } else {
           index -= kFibonacciNumbers[row - 1];
           row --;
       }
    }
}

I have not yet tested this; to paraphrase Don Knuth, I've merely proved it correct. :-) But I hope this helps answer your question. I really loved this problem!

Answer 2

I guess your general idea should be OK, but I don't see how your code is going to deal with larger values of K, because the numbers will get enormous quickly, and even with large integer libraries it might take virtually forever to compute fibonacci(10^9) exactly.

Fortunately, you are only asked about the first 10^9 characters. The string will reach that many characters already on the 44th line (f(44) = 1134903170).

And if I'm not mistaken, from there on the first 10^9 characters will be simply alternating between the prefixes of line 44 and 45, and therefore in pseudocode:

def solution(K, P):
   if K > 45:
       if K % 2 == 0:
           return solution(44, P)
       else:
           return solution(45, P)
   #solution for smaller values of K here