Having some difficult with a valid JavaScript version. The values that are failing are when combinations get over MOD (10^9 +7) Has anybody got a JavaScript version working or can spot the error in this code? Thanks

*(legoBlocks(8,10) on my code is giving 634608018.

Hacker rank is giving 634597424*

function legoBlocks(h, w) {
    // Write your code here
    let mod = (Math.pow(10, 9) + 7)

    //different combinations for a width when height is 1
    let t = [0];
    if (w >= 1) t.push(1)
    if (w >= 2) t.push(2)
    if (w >= 3) t.push(4)
    if (w >= 4) t.push(8)
    while (w >= 5 && t.length <= w){
        let start = t.length -4
        let arr = t.slice(start, t.length)
        let sum = arr.reduce((partialSum, a) => partialSum + a, 0)
        t.push(sum)
    }

    //different combinations for width given height h
    //e.g. total[height=2] is t^2, total[height=3] is t^3
    let total = t.slice()
    for (let outer=2; outer<=h; outer++) {
        for (let i = 0; i <= w; i++) {
            total[i] = (t[i] * total[i])
        }
    }


    let solid = []
    solid.length = w+1;
    solid.fill(0)
    solid[1] = 1

    //s[x] = total[x] - (SUM (where i starts at 1 and ends at x-1)  s[i] * total[w-i]))
    if (w>1){
        for (let ww=2; ww<=w; ww++){
            let unsolid_sum = 0;
            for (let i=1; i<ww; i++){

                unsolid_sum += (((solid[i]) * (total[ww-i])))
            }
            solid[ww] = ((total[ww] - unsolid_sum))
        }
    }

return solid[w] % mod

}

This question wrinkled my brain until I looked at Willis42's code. Here's some extra annotation in case it helps.

def legoBlocks(n, m): # the ways to build a line of m from 0 up to 4 using legobricks from 1-4 # this takes the prev sums and adds one more way to it each time permutations = [0, 1, 2, 4, 8] mod = 10**9+7 # just keeps our numbers from getting too large - wraps if so

# for the rest, use dp to keep compiling the already set base cases. We dont need to add one more way here (like we did above) because we already compiled all the ways for bricks from 1-4 now if m is >=5 we just need to get the last 4 subproblems we already compiled and sum them. Remember, don't add "one more" bc we're not adding a "new way" bc we only consider lego bricks from 1-4. Permutations array already holds all the ways for 1-4, we just want to grab the already computed prev 4 ways each time. 

for i in range(5, m+1): 
    permutations.append((permutations[i-1]  + permutations[i-2] + permutations[i-3] + permutations[i-4])% mod)

# at this point we have all possible permutations of bricks from 1-4 up to m
# now we need to calculate n (height) 
# we need to loop through all our permutations for each m, and raise them to the power of n to get all possible combinations up to n for each mth row.

for i in range(len(permutations)): 
    permutations[i] = (permutations[i] ** n) % mod

# now we have all possible but we need to introduce our condition to reduce by "bad" walls 
# start with setting "good" permutations as 0 and 1 ( we dont have to worry about reducing till start stacking) 
good_permutations = [0,1]

for i in range(2, m+1): # starting at 2 we are stacking rows
    current = permutations[i] # grab the current one assuming all are "good"
    for j in range(1, i): # now loop from each last known "good" section and subtract the right assuming all bad. as we move, we are only keeping known "good" sections and building on them            
        current -= (good_permutations[j] * permutations[i-j])
    good_permutations.append(current % mod)
return good_permutations[m]

Main points to take care about are: 1) calculate total number of combination per row using dynamic programming 2) inclusion/exclusion concept by splitting the wall on 2 parts - use dynamic programming for better performance 3) Fast/binary exponentiation by squaring the base and halving the exponent

Java code

public static long[] combinations;
    public static long modulo = 1000000007;
    private static long [] totals;
    private static long [] goods;
    private static long [] bads;
    public static int legoBlocks(int n, int m) {
        totals = new long[m+1];
        goods = new long[m+1];
        bads = new long[m+1];
        totals[0] = totals[1] = goods[0] = goods[1] = 1L;
        combinations = new long[m+1];
        combinations[0]=1L;
        long good = calculateGood(n,m);
        return (int) (good%modulo);
    }
    
    public static Long calculateGood(int n, int m) {
        if(goods[m]!=0) {
            return goods[m];
        }
        Long total = calculateTotal(n,m);
        Long bad = calculateBad(n,m);
        Long good = (total - bad)%modulo;
        if(good<0){
            good+=modulo;
        }
        goods[m] = good;
        return goods[m];
    }
    
    private static Long calculateBad(int n, int m) {
        if(bads[m]!=0){
            return bads[m];
        }
        Long totalBad = 0L;
        for(int i =1; i< m;i++) {            
            Long currentBad = (calculateGood(n, i)*calculateTotal(n, m-i))%modulo;
            totalBad=(totalBad+currentBad)%modulo;
        }
        bads[m]=totalBad%modulo;
        return totalBad;
    }
    
    private static Long calculateTotal(int n, int m){
        if(totals[m]!=0){
            return totals[m];
        }
        Long perRow = calculateCombinationsPerRow(m);
        
        long total = modPow(perRow, n);
        totals[m] = total%modulo;
        return totals[m];
    }
    
    private static long modPow(long base, int exponent) {
        long result = 1L;
        base = base % modulo;
        while (exponent > 0) {
            if (exponent%2 == 1) {
                result = (result * base) % modulo;
            }
            base = (base * base) % modulo;
            exponent /=2;
        }
    
        return result;
    }
    
    private static Long calculateCombinationsPerRow(int width){
        
        if(combinations[width]!=0){
            return combinations[width];
        }
        long total = 0L;
        if(width-4>=0){
            total += calculateCombinationsPerRow(width-4);
        }
        if(width-3>=0){
            total += calculateCombinationsPerRow(width -3);
        }
        if(width-2>=0){
            total += calculateCombinationsPerRow(width -2);
        }
        if(width-1>=0){
            total += calculateCombinationsPerRow(width -1);
        }
        combinations[width] = total%modulo;
        return combinations[width];
    }

Anyone know how I can improve my score (83.33) to 100.00. I've done all the optimisations I could think of..

class Result {

/*
 * Complete the 'legoBlocks' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n (width)
 *  2. INTEGER m (height)
 */

// Cache previous C(n,m) calculations - All Combinations to build a wall with Brick sizes [1,4]
// Cache previous N(n,m) calculations - All Combinations to build a legitimate wall with no breaks

public static Map<String, BigInteger> C_n_m = new HashMap<>();
public static Map<String, BigInteger> N_n_m = new HashMap<>();
public static BigInteger modulo = BigInteger.valueOf(1_000_000_007);

public static BigInteger noBreakWalls(int n, int m) {
    String key = n + "," + m;
    if (N_n_m.containsKey(key)) return N_n_m.get(key);
    BigInteger sum = buildAnyWall(n, m);
    for (int i=1; i < n ; i++) {
        sum = sum.subtract(buildAnyWall(n-i, m).multiply(noBreakWalls(i, m))); 
    }
    sum = sum.mod(modulo);
    N_n_m.put(key, sum);
    return sum;
}

public static BigInteger buildAnyWall(int n, int m) {
    String key = n + "," + m;
    if (C_n_m.containsKey(key)) return C_n_m.get(key);
    if (n < 5) {
        BigInteger basecase = BigInteger.valueOf(2).modPow(BigInteger.valueOf(m*(n-1)), modulo);
        C_n_m.put(key, basecase);
        return basecase;
    } else {
        BigInteger row = buildAnyWall(n-1, 1)
                            .add(buildAnyWall(n-2, 1))
                                .add(buildAnyWall(n-3, 1))
                                    .add(buildAnyWall(n-4, 1))
                                        .modPow(BigInteger.valueOf(m), modulo);
        C_n_m.put(key, row);
        return row;
    }
}

public static int legoBlocks(int n, int m) {
    return noBreakWalls(n, m).intValue();
}

}

this question would be Hard Level in Leetcode