Lego Blocks

  • + 0 comments

    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();
    }
    

    }