Codesignal Solution: fibonacciWord

Original Problem

The Fibonacci word sequence of bit strings is defined as:

F(0) = "0"
F(1) = "1"
F(n) = F(n − 1) + F(n − 2) if n >= 2

Where + is the string concatenation operation.

The first few elements are:

np
00
11
210
3101
410110
510110101
61011010110110

Given a number n and a bit pattern p, return the number of occurrences of the bit pattern p in F(n).

Example
For n = 6 and p = "10", the output should be
fibonacciWord(n, p) = 5.
The Fibonacci word for n = 6 is "1011010110110", and the string "10" occurs 5 times in the string "1011010110110".

Input/Output

Solution

The given recursive definition of the fibonacci word sequence has a complexity of \(O(2^n)\). However, a linearized dynamic programming algorithm can be derived. Taking the first two elements, every successive element concatenates the last two elements:

n0 = "0"
n1 = "1"
n2 = n1 + n0
n3 = n2 + n1
n4 = n3 + n2
n5 = ...

This algorithm can be implemented without recursion already:

function fib(n) {
	a = "0"
	b = "1"
	t = "" + n

	for (; n > 1; n--) {
		t = b + a
		a = b
		b = t
	}
	return t
}

With this function the given table can be reproduced. Now to the interesting part, the counting of the overlapping. Using the derived function above, we could simply loop over the string and count the occurrences of \(p\) at the current position. But with \(n=40\) 165580141 iterations are already needed. So we have a new limiting factor. A better way is to use the point only, where b and a get connected. Looking at the \(P\) last digits of the left string and the \(P\) first digits of the right string - with \(P\) being the length of \(p\) - also prevents double-countings. Using the function above as a template, we can implement this idea as:

function fibonacciWord(n, p) {
  a = "0"
  b = "1"
  c = p == a

  r = 0
  s = 0
  P = p.length - 1

  for (; n > 1; n--) {
    r = s + c
    if (P > 0)
      r+= (b.slice(-P) + a.slice(0, P)).indexOf(p) != -1
    c = s
    s = r

    t = b
    b = b + a
    a = t
  }
  return r
}

Which can be simplified a bit, but unfortunately JavaScript is quite expressive on string slicing and matching, so that the final solution isn't that much shorter:

fibonacciWord = (n, p) => {
  a = "0"
  b = "1"
  c = p == a

  r = 0
  P = p.length - 1

  while (--n) {
    t = r
    r+= c + !!P * (b.slice(-P) + a.slice(0, P)).includes(p)
    c = t

    t = b
    b+= a
    a = t
  }
  return r
}

« Back to problem overview