Number of Ways to Paint N × 3 Grid - a short saga

Today's Leetcode problem was a bit of a wormhole but I feel like my notes and the process to find the answer make for a much more interesting post than just the winning algorithm, so this is the short saga of how I got to a top entry :-)

The Problem

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours while making sure that no two adjacent cells have the same colour.
You are given n the number of rows of the grid. Return the number of ways you can paint this grid modulo 10^9 + 7.

The naive solution

var numOfWays = n => {
    const allowedSets = ['RGB', 'RBG', 'RGR', 'RBR', 
                        'GBR', 'GRB', 'GRG', 'GBG', 
                        'BRG', 'BGR', 'BGB', 'BRB'];
    if (n == 1) return allowedSets.length;

    let collection = allowedSets;
    for (let i = 1; i < n; i++) {        
        let newCollection = [];
        collection.forEach(row => {
            let filtered = allowedSets.filter(e => 
                                 e[0] !== row[0] 
                                 && e[1] !== row[1] 
                                 && e[2] !== row[2]);
            newCollection = [...newCollection, ...filtered]; 
        })
        collection = newCollection;
    }
    return collection.length % (10**9 + 7);
}

The first step was to write down the most basic algorithm that could possibly work, aka the "naive solution". The time and space complexity are exponential but using dynamic programming techniques I believe it could be made faster and smarter.

On the other hand, I got to see the actual sets growing with each iteration over the collection and since I wasn't on time pressure I decided to investigate a bit deeper.

Finding patterns

//pairing table for n == 2
{
    RGB: [ 'GBR', 'GRG', 'GBG', 'BRG' ],
    RBG: [ 'GRB', 'BGR', 'BGB', 'BRB' ],
    RGR: [ 'GRB', 'GRG', 'GBG', 'BRG', 'BRB' ],
    RBR: [ 'GRB', 'GRG', 'BRG', 'BGB', 'BRB' ],
    GBR: [ 'RGB', 'BRG', 'BGB', 'BRB' ],
    GRB: [ 'RBG', 'RGR', 'RBR', 'BGR' ],
    GRG: [ 'RGB', 'RGR', 'RBR', 'BGR', 'BGB' ],
    GBG: [ 'RGB', 'RGR', 'BGR', 'BGB', 'BRB' ],
    BRG: [ 'RGB', 'RGR', 'RBR', 'GBR' ],
    BGR: [ 'RBG', 'GRB', 'GRG', 'GBG' ],
    BGB: [ 'RBG', 'RBR', 'GBR', 'GRG', 'GBG' ],
    BRB: [ 'RBG', 'RGR', 'RBR', 'GBR', 'GBG' ]
}

Initially I pre-calculated the twelve "allowed sets" by hand and then used Array.reduce to create pairing tables as each new row up to n was added.

Looking at the evolution of this table allowed me to make a few interesting observations, such as:

• when n == 1 result is 12, namely 6 two colour sets and 6 three colour sets.
• when n == 2 result is 54, because every two colour set from the previous round is repeated 5 times totalling 30 sets, while the three colour ones repeat 4, making for 24 sets.
• when n == 3 result is 246, with 108 three colours sets and 138 sets of two colours.

Trust your instincts but test exhaustively anyway
My first instinct was to calculate the growth in number of compatible pairs for each of the 12 distinct sets with a pen and paper. It looked something like this:

4*6 + 5*6 = 54          //pairs with 3 colour sets + pairs with 2 colour sets if n = 2
54 * (4/12) = 18      
54 * ceil(5/12) = 23 
18*6 + 23*6 = 246       //pairs with 3 colour sets + pairs with 2 colour sets if n = 3
246 * (18/54) = 82      
246 * ceil(23/54) = 105
82*6 + 105*6 = 1122     //pairs with 3 colour sets + pairs with 2 colour sets if n = 4

I didn't keep the code created for this one because it turned out to be a red herring. Somewhere between n == 15 and n == 25, depending on different rounding mechanisms implemented (...and I spent 1h plus on this), the result would be off.

There was something there... but I was trying to calculate how many pairs each of the 12 unique sets would have per row, and it took me a while to realise a much simpler pattern exists, one which allows directly calculating the total number of unique sets per row without fractions.

This is why a REPL is so useful :-)

> let twoC = 6, threeC = 6
> let next2C = (c2, c3) => 2 * c3 + 3 * c2
> let next3C = (c2, c3) => 2 * c3 + 2 * c2
> next2C(twoC, threeC)
30
> next3C(twoC, threeC)
24
> next3C(30, 24)
108
> next2C(30, 24)
138

Ok then! Let's give this one a try and let's see how it runs now....

var numOfWays = n => {
    let twoColours = 6;
    let threeColours = 6;
    const mod = (10**9 +7);

    for (let i = 1; i < n; i++) {
        let prevTwo = twoColours;
        let prevThree = threeColours;
        twoColours = (2 * prevThree + 3 * prevTwo) % mod;
        threeColours = (2 * prevThree + 2 * prevTwo) % mod;
    }
    return (twoColours + threeColours) % mod;
}
//64ms, better than 70.43%

Right. I'm about 2 hours into this problem and all I get is a top 70% result...

Persistence in the face of defeat
Once the feeling of utter failure gave way to the much more familiar impostor syndrome, I was able to make an honest evaluation of my code. Here it is:

• This solution starts with a pre-calculated result for n = 1, has two variables that can be removed without loss of functionality and I should be able to do away with the final modulo operation because I'm storing intermediate results using clock arithmetic anyway.
• Also, exponentiation is expensive so I could replace the 10**9 + 7 with 1000000007 to spare the CPU an instruction or two.

> numOfWays(4)
twoC: 15, threeC: 12
twoC: 69, threeC: 54
twoC: 315, threeC: 246
twoC: 1437, threeC: 1122
2559

What a rabbit hole! Now the sum of two and three colour sets is completely off... but the threeC variable holds the right result?? Before I worry too much about how this works, let me shave off one more CPU instruction and just return threeC instead of the sum of twoC + threeC!

var numOfWays = function(n) {
    let temp = 3;
    let res = 3;

    for (let i = 0; i < n; i++) {
        let prevRes = res;
        res = (2 * res + 2 * temp) % 1000000007;
        temp = (2 * prevRes + 3 * temp) % 1000000007;
    }
    return res;   
}
// Runtime: 60 ms, faster than 83.58% of JavaScript online submissions for Number of Ways to Paint N × 3 Grid.
// Memory Usage: 35.5 MB, less than 91.30% of JavaScript online submissions for Number of Ways to Paint N × 3 Grid.

Oh... top 83%... neat.

I suppose that means there is a solution that beats O(n) time and O(1) space but I can't imagine what it could be. I'm also not really sure of how to optimise for a JIT compiler, so perhaps I'm missing some of the nuances of modern Javascript... or maybe I should get a paid Leetcode account, because that's what the "speed up" link directs me to do?

My head hurts and I'm at my wits' end... I'm quite persistent but I've often felt like I had something to prove to my colleagues with CS degrees throughout my now 22 year career so I wasn't sure it wasn't hubris that was driving me madness. In other words, I wasn't ready to call it a day just yet ¯\(ツ)/¯

Convinced the exact same code would be blazingly fast in C, I gave it a go, and wouldn't you know it...

int numOfWays(int n){
    long int temp = 3;
    long int res = 3;

    for (int i = 0; i < n; i++) {
        long int prevRes = res;
        res = (2 * res + 2 * temp) % 1000000007;
        temp = (2 * prevRes + 3 * temp) % 1000000007;
    }
    return res;   
}
// Runtime: 0 ms, faster than 100.00% of C online submissions for Number of Ways to Paint N × 3 Grid.
// Memory Usage: 5.1 MB, less than 64.52% of C online submissions for Number of Ways to Paint N × 3 Grid.

Finally! It feels like my efforts paid off, and I'm only slightly annoyed because I don't fully understand why this variation works well in C but nowhere near the 95th percentile in JS. However, finding the patterns, pursuing my intuitions until finally discovering two working algorithms was definitely too much fun for me not to share!

Hope you've enjoyed this post, and if you know something I don't... please share too :-)