Tribonacci

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 to assert the following cases:

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

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:

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 of tasks like this and so let's refactor this implementation into a recursive alternative like so:

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!

Comments

[Amin]

Hi there, great article. Thanks for sharing your solution for the tribonacci.

Personally I like to go further in the error handling by creating my own error classes just like custom exception classes in PHP.

"use strict";

class LogInvalidIntegerError extends Error {
    constructor(...parameters) {
        super(...parameters);

        this.name = "LogInvalidIntegerError";
    }
}

function logInteger(x) {
    if (!Number.isInteger(x)) {
        throw new LogInvalidIntegerError("First argument must be an integer");
    }

    console.log(`Integer: ${x}`);
}

try {
    logInteger(1);
    // Integer: 1

    logInteger(1.2);
    // LogInvalidIntegerError: First argument must be an integer
} catch (error) {
    if (error instanceof LogInvalidIntegerError) {
        console.error("Nope, integers only.");
    } else {
        console.error(`Unhandled error: ${error.toString()}`);
    }
}

Just a suggestion for those that don't know that this kind of behavior exists in JavaScript as well.

This also works in chai with the expect helper.

"use strict";

import "mocha";
import { expect } from "chai";
import { logInteger, LogInvalidIntegerError } from "../src/log.js";

describe("log.js", function() {
    describe("logInteger", function() {
        it("should throw an exception on non-integer", function() {
            expect(log(1.2)).to.throw(LogInvalidIntegerError);
        });
    });
});

Which is kind of cool IMO!

[James Robb]

Hi Amin! I agree, it is a nice thing to do but usually I wouldn't implement my own custom error because if I did that in every project I would have inconsistencies all over the place. Instead I would normally use something like the custom-error npm package to generate custom error types if required. Usually though, even that is something I tend to avoid unless there is a clear requirement to do so.

I also didn't include such an implementation in this post since it is out of scope generally speaking and I wanted the focus to be on the challenge and not surrounding elements or constructs.

Thanks for the input though, it's a good point and I hope this answer was well received.

[Amin]

Yay! I didn't know about this package. Looks really interesting. Will dig the source-code when I got some time and... It is added to my todo list. Haha!

[James Robb]

Sure, could perhaps be a good open source project to contribute to and tidy up since it is been a while since it was updated although it works perfectly as is for it's usecase now anyway without issues and according to the Snyk vulnerability database when I search for custom-error under npm there are no security vulnerabilities either which is a great thing for any 3rd party package.