Determining the individual letters of Fibonacci strings?

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" o开发者_运维问答r "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?

---

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!

---

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 

---

I found this. I did not do a pre-check (get the size of the k-th fibo string to test p againt it) because if the check is successful you'll have to compute it anyway. Of course as soon as k becomes big, you may have an overflow issue (the length of the fibo string is an exponential function of the index n...).

#include <iostream>
#include <string>

using namespace std;

string fibo(unsigned int n)
{
    if (n == 0)
        return "a";
    else if (n == 1)
        return "bc";
    else
        return fibo(n - 2) + fibo(n - 1);

}

int main()
{
    unsigned int k, p;
    cin >> k >> p;
    --k;
    --p;
    string fiboK = fibo(k);
    if (p > fiboK.size())
        cout << "No solution" << endl;
    else
        cout << fiboK[p] << endl;
    return 0;
}

EDIT: ok, I now see your point, i.e. checking in which part of the k-th string p resides (i.e. in string k - 2 or k - 1, and updating p if needed). Of course this is the good way to do it, since as I was saying above my naive solution will explode quite too quickly.

Your way looks correct to me from an algorithm point of view (saves memory and complexity).

---

I would have computed the K-th Fibonacci String, and then retrieve the P-th character of it. Something like that:

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

std::string FibonacciString(unsigned int k)
{
    std::vector<char> buffer;
    buffer.push_back('a');
    buffer.push_back('b');
    buffer.push_back('c');

    unsigned int curr = 1;
    unsigned int next = 2;

    while (k --)
    {
        buffer.insert(
            buffer.end(),
            buffer.begin(),
            buffer.end());

        buffer.erase(
            buffer.begin(),
            buffer.begin() + curr);

        unsigned int prev = curr;
        curr = next;
        next = prev + next;
    }

    return std::string(
        buffer.begin(),
        buffer.begin() + curr);
}

int main(int argc, char** argv)
{
    unsigned int k, p;
    std::cin >> k >> p;

    -- p;
    -- k;

    std::string fiboK = FibonacciString(k);
    if (p > fiboK.size())
        std::cout << "No solution";
    else
        std::cout << fiboK[p];
    std::cout << std::endl;
    return 0;
}

It does use more memory than your version since it needs to store both the N-th and the (N+1)-th Fibonacci string at every instant. However, since it is really close to the definition, it does work for every value.

Your algorithm seems to have some issue when k is large while p is small. The test fib_num[k] < p will dereference an item outside of the range of the array with k = 30 and p = 1, won't it ?

---

I made another example where each corresponding number of Fibonnaci series corresponds to the letter in the alfabet. So for 1 is a, for 2 is b, for 3 is c, for 5 is e... etc:

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string a = "abcdefghijklmnopqrstuvwxyz"; //the alphabet
    string a1 = a.substr(0,0); string a2 = a.substr(1,1); string nexT = a.substr(0,0);

    nexT = a1 + a2;

   while(nexT.length() <= a.length())
    {
        //cout << nexT.length() << ", ";             //show me the Fibonacci numbers
        cout << a.substr(nexT.length()-1,1) << ", "; //show me the Fibonacci letters
        a1 = a2;
        a2 = nexT;
        nexT = a1 + a2;
    }
    return 0;
}

Output: a, b, c, e, h, m, u,

---

Quote from Wikipedia, Fibonacci_word:

The nth digit of the word is 2+[nφ]-[(n+1)φ] where φ is the golden ratio ...

(The only characters used in the Wikipedia page are 1 and 0.) But note that the strings in the Wikipedia page, and in Knuth s Fundamental Algorithms, are built up in the opposite order of the above shown strings; there it becomes clear when the strings are listed, with ever repeating leading part, that there is only one infinitely long Fibonacci string. It is less clear when generated in the above used order, for the ever repeating part is the string s trailing part, but it is no less true. Therefore the term "the word" in the quotation, and, except for the question "is n too great for this row?", the row is not important.

Unhappily, though, it is too hard to apply this formula to the poster s problem, because in this formula the original strings are of the same length, and poster began with "a" and "bc".

This J(ava)Script script generates the Fibonacci string over the characters the poster chose, but in the opposite order. (It contains the Microsoft object WScript used for fetching command-line argument and outputting to the standard output.)

var u, v /*Fibonacci numbers*/, g, i, k, R;
v = 2;
u = 1;
k = 0;
g = +WScript.arguments.item(0); /*command-line argument for desired length of string*/
/*Two consecutiv Fibonacci numbers, with the greater no less than the
  Fibonacci string s length*/
while (v < g)
{   v += u;
    u = v - u;
    k = 1 - k;
}
i = u - k;
while (g-- > 0)
{   /*In this operation, i += u with i -= v when i >= v (carry),
      since the Fibonacci numbers are relativly prime, i takes on
      every value from 0 up to v. Furthermore, there are u carries,
      and, therefore, u instances of character 'cb', and v-u instances
      of 'a' (no-carry). The characters are spread as evenly as can be.*/
    if ((i += u) < v)
    {   R = 'a'; // WScript.StdOut.write('a'); /* no-carry */
    } else
    {   i -= v; /* carry */
        R = 'cb'; // WScript.StdOut.write('cb')
    }
}
/*result is in R*/ // WScript.StdOut.writeLine()

I suggest it because actually outputting the string is not required. One can simply stop at the desired length, and show the last thing about to be outputted. (The code for output is commented out with '//'). Of course, using this to find the character at position n has cost proportional to n. The formula at the top costs much less.