Fibonacci, Tribonacci and friends

Task description

If you have completed the Tribonacci sequence kata, you would know by now that mister Fibonacci has at least a bigger brother. If not, give it a quick look to get how things work.

Well, time to expand the family a little more: think of a Quadribonacci starting with a signature of 4 elements and each following element is the sum of the 4 previous, a Pentabonacci (well Cinquebonacci would probably sound a bit more italian, but it would also sound really awful) with a signature of 5 elements and each following element is the sum of the 5 previous, and so on.

Well, guess what? You have to build a Xbonacci function that takes a signature of X elements - and remember each next element is the sum of the last X elements - and returns the first n elements of the so seeded sequence.

xbonacci([1,1,1,1}, 10) = [1,1,1,1,4,7,13,25,49,94]
xbonacci([0,0,0,0,1], 10) = [0,0,0,0,1,1,2,4,8,16]
xbonacci([1,0,0,0,0,0,1], 10) = [1,0,0,0,0,0,1,2,3,6]
xbonacci([1,1]) produces the Fibonacci sequence

Task solution

This challenge will extend the 5th post in this series where we tackled the Tribonacci Kata. The tests are basically the same except we now have some extra requirements on the function signature to test for in the invalid input tests and further to that, we need to now allow variable length of both the first and second inputs for the happy path tests.

Tests

describe("Xibonacci tests", () => {
  it("Should throw if invalid inputs provided", () => {
    expect(() => Xibonacci(0, 0)).toThrow(/InvalidArgumentException/);
    expect(() => Xibonacci(["test"], 5)).toThrow(/InvalidArgumentException/);
    expect(() => Xibonacci([], "")).toThrow(/InvalidArgumentException/);
    expect(() => Xibonacci([1, 1, 1], -1)).toThrow(/InvalidArgumentException/);
    expect(() => Xibonacci([0,1], 10, "test")).toThrow(/InvalidArgumentException/);
  });

  it("Should calculate the correct Xibonacci sequences", () => {
    expect(Xibonacci([0,1], 10)).toEqual([0,1,1,2,3,5,8,13,21,34]);
    expect(Xibonacci([1,1], 10)).toEqual([1,1,2,3,5,8,13,21,34,55]);
    expect(Xibonacci([0,0,0,0,1], 10)).toEqual([0,0,0,0,1,1,2,4,8,16]);
    expect(Xibonacci([1,0,0,0,0,0,1], 10)).toEqual([1,0,0,0,0,0,1,2,3,6]);
    expect(Xibonacci([1,0,0,0,0,0,0,0,0,0], 20)).toEqual([1,0,0,0,0,0,0,0,0,0,1,1,2,4,8,16,32,64,128,256]);
  });
});

Implementation

function Xbonacci(signature, n, currentIndex = 0){
  if(!Array.isArray(signature)) {
    throw new Error(`InvalidArgumentException: Parameter 1 must be an array, received: ${typeof signature}`);
  } else if(!signature.every(value => Number.isInteger(value))) {
    throw new Error(`InvalidArgumentException: Parameter 1 must be an array of integers. Atleast one element in the array does not conform to this, received: ${signature}`);
  } else if(!Number.isInteger(n)) {
    throw new Error(`InvalidArgumentException: Parameter 2 must be an integer, received: ${typeof n}`);
  } else if(n < 0) {
    throw new Error(`InvalidArgumentException: Parameter 2 should be a non-negative integer equal to 0 or greater. Received: ${n}`);
  } else if(!Number.isInteger(currentIndex)) {
    throw new Error(`InvalidArgumentException: Parameter 3 must be an integer, received: ${typeof currentIndex}`);
  }

  const next = signature.slice(currentIndex, signature.length);
  const summed = next.reduce((a, b) => a + b, 0);
  if(signature.length !== n) return Xbonacci([...signature, summed], n, currentIndex + 1);
  return signature.slice(0, n)
}

As ever we run our input validation checks to make the invalid input tests pass. From here we slice the elements from the currentIndex up to the end element of the signature array, add the values in the sliced array up and then push the result of the addition into the original array.

Our return conditions are also simple in action, if we have enough or more elements in signature to satiate the requirement of n, we return signature sliced from 0 to n elements. Otherwise, if this requirement is not met, we recurse to run the next iteration and add another element to the signature. This keeps happening until the requirement of n is satiated and the expected return value is able to be provided.

Let's look at an example of this in action:

signature = [1, 2, 3]
n = 5
currentIndex = 0
Xbonacci(signature, n, currentIndex)
  -> next = signature.slice(0, 3) = [1, 2, 3]
  -> summed = 1 + 2 + 3 = 6
  -> signature = [1, 2, 3, 6]
  -> signature.length !== n = true
    -> Xbonacci(signature, n, currentIndex + 1)
      -> next = signature.slice(1, 4) = [2, 3, 6]
      -> summed = 2 + 3 + 6 = 11
      -> signature = [1, 2, 3, 6, 11]
      -> signature.length !== n = false
        -> return signature

output: [1, 2, 3, 6, 11]

Conclusions

Xibonacci can basically do anything with number sequence operations related to Fibonacci, case in hand, we could write a test for fibonacci and some variants like so:

const fibonacci = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
expect(Xibonacci([0, 1], 10)).toEqual(fibonacci);

const tribonacci = [0, 1, 1, 2, 4, 7, 13, 24, 44, 81];
expect(Xibonacci([0, 1, 1], 10)).toEqual(tribonacci);

const quadranacci = [0, 1, 1, 2, 4, 8, 15, 29, 56, 108];
expect(Xibonacci([0, 1, 1, 2], 10)).toEqual(quadranacci);

const quintinacci = [0, 1, 1, 2, 3, 7, 14, 27, 53, 104];
expect(Xibonacci([0, 1, 1, 2, 3], 10)).toEqual(quintinacci);

Overall this was a fun little challenge to complete and I like that we managed to build on top of the Tribonacci article from previously to come up with this solution.

See you in the next one!