Tribonacci
Tags: kata, challenge, codewars, javascript
Published: 2019-12-01 21:47:17

## Task description

> As the challenge name may already reveal, it works basically like a Fibonacci, but summing the last 3 (instead of 2) numbers of the sequence to generate the next.
> 
> So, if we are to start our Tribonacci sequence with `[1, 1, 1]` as a starting input, we have this sequence:
> 
> `[1, 1 ,1, 3, 5, 9, 17, 31, ...]`
> 
> But what if we started with `[0, 0, 1]` as a signature? As starting with `[0, 1]` instead of `[1, 1]` basically shifts the common Fibonacci sequence by once place, you may be tempted to think that we would get the same sequence shifted by 2 places, but that is not the case and we would get:
> 
> `[0, 0, 1, 1, 2, 4, 7, 13, 24, ...]`
>
> The input `signature` will always contain 3 numbers; `n` will always be a non-negative number; if `n` equals `0`, then return an empty array and be ready for anything else which is not clearly specified.

## Task solution

### Tests

Tribonacci is basically `fibonacci++` if you'll excuse the pun and so we merely need to test if the inputs are valid and if so, what the returns should be. Accounting for this and the fact this implementation will be in JavaScript, we can use [the Jest testing framework](https://jestjs.io/) to assert the following cases:

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

  it("Should calculate the correct tribonacci values", () => {
    expect(tribonacci([1,1,1], 10)).toEqual([1,1,1,3,5,9,17,31,57,105]);
    expect(tribonacci([0,1,1], 10)).toEqual([0,1,1,2,4,7,13,24,44,81]);
    expect(tribonacci([1,0,0], 10)).toEqual([1,0,0,1,1,2,4,7,13,24]);
    expect(tribonacci([0,0,0], 10)).toEqual([0,0,0,0,0,0,0,0,0,0]);
    expect(tribonacci([1,1,1], 1)).toEqual([1]);
    expect(tribonacci([300,200,100], 0)).toEqual([]);
  });
});
```

### Implementation

```javascript
function tribonacci(signature, n) {
  if(!Array.isArray(signature)) {
    throw new Error(`InvalidArgumentException: Parameter 1 must be an array, received: ${typeof signature}`);
  } else if(signature.length !== 3) {
    throw new Error(`InvalidArgumentException: Parameter 1 must be an array of length 3. Received: an array of length ${signature.length}`);
  } 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}`);
  }

  const trib = [...signature];
  for (var i = 3; i < n; i++) {
    trib[i] = trib[i-1] + trib[i-2] + trib[i-3];
  }
  return n < 3 ? trib.slice(0, n) : trib;
};
```

We begin as ever with our defensive checks, testing the known issues that could arise with our inputs. 

From there we copy the `signature` array so as to not mutate the input data. Then we run a loop begining at index `3` since our copied array already has indexes `0`, `1` and `2` filled in from the copied `signature` array and loop up to `n`. On each iteration we add up the previous 3 items in the `trib` array. For example:

```text
signature = [0,1,1]
n = 5
tribonacci(signature, n)
loop
-> First iteration: trib = 0 + 1 + 1 = [0, 1, 1, 2]
-> Second iteration: trib = 1 + 1 + 2 = [0, 1, 1, 2, 4]
-> exit loop since the required `n` elements exist in the trib array
```

Finally we check if `n < 3`, if it is we just copy the array elements `0` to `n` and return an array of those, otherwise we return `trib` and thus completed the initial implementation of our tribonacci function.

Now, I personally like [recursive implementations](https://en.wikipedia.org/wiki/Recursion) of tasks like this and so let's refactor this implementation into a recursive alternative like so:

```javascript
function tribonacci(signature, n, trib = [...signature]) {
  if(!Array.isArray(signature)) {
    throw new Error(`InvalidArgumentException: Parameter 1 must be an array, received: ${typeof signature}`);
  } else if(signature.length !== 3) {
    throw new Error(`InvalidArgumentException: Parameter 1 must be an array of length 3. Received: an array of length ${signature.length}`);
  } 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}`);
  }

  if(trib.length >= n) return trib.slice(0, n);
  trib.push(
    [...trib.slice(-3)].reduce((accumulator, value) => accumulator + value, 0)
  );
  return tribonacci(signature, n, trib);
};
```

In this second implementation we rely solely on the inputs and the function definition itself. Our conditionals from the first implementation remain the same. After those however we have replaced our loop with some new logic, in short we do the following:

1. If `trib` has not been initialised with items, copy into it the items from the `signature`
2. If `trib` has more or the same items as `n` requires, return `0` to `n` items from `trib`
3. Push the sum of the last 3 items in the `trib` array to `trib`
4. Recursively call `tribonacci` until the `trib.length >= n` case is met

I like how recursive implementations look and work and so this was a fun little refactor to do.

## Conclusions

Overall, I enjoyed the quirkiness of this tribonacci challenge and especially implementing the recursive version. In a future post we will cover the related "Xibonacci" challenge which was another fun implementation to challenge yourself but that is for another time. See you in the next one!