Lego Blocks

Sort by

recency

|

15 Discussions

|

  • + 0 comments

    Here is Hackerrank Lego Blocks problem solution in Python, Java, C++, C and javascript

  • + 1 comment
    def legoBlocks(n, m):
        # If only one column or one row, there's only one way to build the wall
        if m == 1:
            return 1
        if n == 1:
            return 1 if 1 <= m <= 4 else 0
            
        MOD = pow(10, 9) + 7
        
        # Number of layouts to build a 1 x k wall for k = 1 to m
        p = [0, 1, 2, 4, 8]  # Base cases for widths 1 to 4
        for k in range(5, m + 1):
            # For width k, sum the previous four widths
            p.append(sum(p[-i] % MOD for i in range(1, 5)))
        
        # Number of layouts to build an n x k wall for k = 1 to m
        p = [pow(val, n, MOD) for val in p]
        
        # Number of good layouts (without any complete row gaps) to build n x k wall for k = 1 to m
        g = [0, 1]
        for k in range(2, m + 1):
            # Calculate the number of bad layouts for width k
            bad_layouts_num = sum(g[j] * p[k - j] for j in range(1, k)) % MOD
            # Explanation:
            # g[j] * p[k - j] represents the number of ways to build an n x k wall with a vertical division
            # at position j, resulting in a good layout on the left (g[j]) and any layout on the right (p[k - j]).
            # Summing these products for all j from 1 to k-1 gives the total number of bad layouts where there
            # is at least one complete vertical division in the wall.
            
            # Subtract bad layouts from total layouts to get good layouts
            g.append((p[k] - bad_layouts_num) % MOD)
        
        return g[m]
    
  • + 1 comment

    My Java solution:

    /**
     * Raise a num to an exponent and mod the result
     * NOTE: don't use Math.pow() since it will give
     * incorrect results since it does not mod the
     * intermediate results
     */
    private static long pow(long num, int exp, long mod) {
        long res = num;
        while (exp-- > 1) {
            res = (res * num) % mod;
        }
    
        return res;
    }
    
    /**
     * Strategy using Dynamic Programming:
     * 1. Create an array where each index represents the width
     * and store the number of permuations for a single row.
     * 
     * 2. Create an array where each index represents the width
     * and store the number of valid and invalid permutations for
     * the total number of rows (height)
     * 
     * 3. Create an array where each index represents the width
     * and store the number of invalid permuations of each
     * total number of rows.
     * 
     * 4. The final result will be the substracion of (2) - (3):
     * result = (valid + invalid) - (invalid)
     * 
     */
    public static int legoBlocks(int h, int w) {
        long divisor = 1000000007; // every calculation must be mod by this number
    
        // STEP 1:
        // Permutations for a single row is:
        // when width=0; 0 valid permutation
        // when width=1; 1 valid permutation
        // when width=2; 2 valid permutations
        // when width=3; 4 valid permutations
        // when width=4; 8 valid permutations
        // when widht=N; the sum of the previous 4 widths: (N-1) + (N-2) + (N-3) + (N-4)
        List<Long> singleRow = new ArrayList<>(Arrays.asList(0L, 1L, 2L, 4L, 8L));
    
        // STEP 2:
        // Total permutations for all rows:
        // when width=0; singleRow[0]^h valid permutations (always 0)
        // when width=1; singleRow[1]^h valid permutations (always 1)
        // when width=2; singleRow[2]^h valid permutations
        // when width=3; singleRow[3]^h valid permutations
        // when width=4; singleRow[4]^h valid permutations
        // when width=N; singleRow[N]^h valid permutations
        List<Long> total = new ArrayList<>(
                Arrays.asList(0L, 1L,
                        pow(2, h, divisor),
                        pow(4, h, divisor),
                        pow(8, h, divisor)));
    
        // Completes the singleRow and total arrays dynamically from
        // the previous values according to the above rules
        for (int i = 5; i <= w; i++) {
            long val = (singleRow.get(i - 1) + singleRow.get(i - 2) +
                    singleRow.get(i - 3) + singleRow.get(i - 4)) % divisor;
            singleRow.add(val);
    
            total.add(pow(val, h, divisor));
        }
    
        // STEP 3 Invalid permutations:
        // Perform a vertical cut across all rows of bricks
        // when width=0; 0 invalid permutations
        // when width=1; 0 invalid permutations
        List<Long> invalid = new ArrayList<>(Arrays.asList(0L, 0L));
    
        // This is the tricky part:
        // Starting with a 2-width cut up to the width
        // For each cut, walk 1-width at a time up to the cut
        // and add the result of the left * right (invalid permutations)
        // the left part are the valid permutations
        // the right part are all possible permutations (valid and invalid)
        for (int cut = 2; cut <= w; cut++) {
            long anum = 0;
            for (int i = 1; i < cut; i++) {
                long l = total.get(i) - invalid.get(i);
                long r = total.get(cut - i);
                anum += ((l * r) % divisor);
            }
            invalid.add(anum % divisor);
        }
    
        // STEP 4
        // We have finally calculated all the valid and invalid permuations
        // we only substract the total permutations from the invalid permuations 
        long r = (total.get(w) - invalid.get(w)) % divisor;
    
        // In case the substraction is negative
        // add the divisor(mod) to the result to find out the real value
        while (r < 0)
            r += divisor;
    
        return (int) r;
    }
    
  • + 0 comments

    in javascript:

    function legoBlocks(n, m) {
        // Write your code here
        const A = 1000000007n;
        const r = new Array(m+1).fill(0n);
        const a = new Array(m+1).fill(0n);
        
        a[0] = 1n;
        for (let j = 1; j <= m; j++) {
            a[j] += (j-1>=0) ? a[j-1] : 0n;
            a[j] += (j-2>=0) ? a[j-2] : 0n;
            a[j] += (j-3>=0) ? a[j-3] : 0n;
            a[j] += (j-4>=0) ? a[j-4] : 0n;
        }
        
        for (let j = 1; j <= m; j++) {
            const n1 = a[j] % A;
            const sum = n1 ** BigInt(n);
            a[j] = sum % A;
        }
        
        r[1] = 1n;
        for (let j = 2; j <= m; j++) {
            r[j] = a[j];
            for (let k = 1; k < j; k++) {
                const n1 = r[k] * a[j-k];
                r[j] -= n1;
            }
            // ATTENTION! in javascript, when the left operand of bigint is negative
            // need to add  +A to be positive, different from python for example
            r[j] = r[j] % A + A; 
        }
    
        return r[m] % A;
    }
    
  • + 0 comments

    Link of the Lego blocks problem explanation (Hindi) and code in Python3: https://youtu.be/K7tpEtdUuqU