HackerRank Lego Blocks Problem Solution

In this post, we will solve HackerRank Lego Blocks Problem Solution. You have an infinite number of 4 types of lego blocks of sizes given as (depth x height x width):

Using these blocks, you want to make a wall of height and width . Features of the wall are:

– The wall should not have any holes in it.
– The wall you build should be one solid structure, so there should not be a straight vertical break across all rows of bricks.
– The bricks must be laid horizontally.

How many ways can the wall be built?

Example

n = 2

m = 3

The height is and the width is . Here are some configurations:

These are not all of the valid permutations. There are 9 valid permutations in all.

Function Description

Complete the legoBlocks function in the editor below.

legoBlocks has the following parameter(s):

int n: the height of the wall
int m: the width of the wall

Returns
– int: the number of valid wall formations modulo

Input Format

The first line contains the number of test cases (10 power 9 + 7).

Each of the next lines contains two space-separated integers n and m.

Sample Input

STDIN   Function
-----   --------
4       t = 4
2 2     n = 2, m = 2
3 2     n = 3, m = 2
2 3     n = 2, m = 3
4 4     n = 4, m = 4

Sample Output

Table of Contents

Lego Blocks C Solution

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
long long modPow(long long a,int x);

int main(){
  int i,j,k,T,N,M;
  long long*dp,*all,*no_line;
  dp=(long long*)malloc(1001*sizeof(long long));
  all=(long long*)malloc(1001*sizeof(long long));
  no_line=(long long*)malloc(1001*sizeof(long long));
  dp[0]=dp[1]=1;
  for(i=2;i<=1000;i++){
    dp[i]=0;
    for(j=1;i-j>=0&&j<5;j++)
      dp[i]+=dp[i-j];
    dp[i]%=MOD;
  }
  scanf("%d",&T);
  for(i=0;i<T;i++){
    scanf("%d%d",&N,&M);
    for(j=1;j<=M;j++)
      all[j]=modPow(dp[j],N);
    for(j=1;j<=M;j++){
      no_line[j]=all[j];
      for(k=1;k<j;k++){
        no_line[j]-=no_line[k]*all[j-k];
        no_line[j]%=MOD;
      }
      if(no_line[j]<0)
        no_line[j]+=MOD;
    }
    printf("%lld\n",no_line[M]);
  }
  return 0;
}
long long modPow(long long a,int x){
  long long res = 1;
  while(x>0){
    if(x%2)
      res=(res*a)%MOD;
    a=(a*a)%MOD;
    x>>=1;
  }
  return res;
}

Lego Blocks C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

constexpr int M = 1000000007;
using Vll = vector < long long >;
using Vvll = vector < Vll >;

template <typename T>
std::ostream& operator <<(std::ostream& o, const vector<T>& v)
{
  for(auto i : v)
    o << i << ' ';
  return o;
}

template <>
std::ostream& operator <<(std::ostream& o, const Vll& v)
{
  for(auto i : v) {
    o << i << ' ';
  }
  o << endl;
  return o;
}
template <>
std::ostream& operator <<(std::ostream& o, const Vvll & vii)
{
  for(auto i : vii) {
    o << i;
  }
  return o;
}

unsigned long long Power(unsigned long long n, int p) {

  if(p == 0) 
      return 1;
  if(p == 1) 
      return n;
  
  unsigned long long ll = n;
  for(int i=2;i<=p;i++) {
    n = (n*ll)%M;
  }
  return n;
}

int main(int argc, char ** argv) {
  int T;

  cin >> T;

  int Mmax = 10;
  Vll A(Mmax+1);
  A[0] = 1;
  A[1] = 1;
  A[2] = 2;
  A[3] = 4;
  A[4] = 8;
  for (int i = 5; i <= Mmax; ++i) {
    A[i] = (A[i-1] + A[i-2] + A[i-3] + A[i-4]) % M;
  }
//  cout << "A: " << A << endl;

  int Nh, Mw;

  for (int t = 0; t < T; ++t) {
    cin >> Nh >> Mw;
    if (Mw > Mmax) {
      A.resize(Mw+1);
      for (int i = Mmax; i <= Mw; ++i) {
    	A[i] = (A[i-1] + A[i-2] + A[i-3] + A[i-4]) % M;
      }
      Mmax = Mw;

    }

    Vvll F(2);
    for (int i = 0; i < 2; ++i) {
      Vll c(Mw+1);
      F[i] = c;
    }

    F[1][1] = F[0][1] = 1;
    for (int i = 2; i <= Mw; ++i) {
      F[1][i] = F[0][i] = Power(A[i], Nh);
      for (int j = 1; j < i; ++j) {
        F[1][i] -= F[0][j] * F[1][i-j];
	F[1][i] %= M;
	F[1][i] += M;
	F[1][i] %= M;
      }
    }
    cout << F[1][Mw] << endl;
  }
  return 0;
}

Lego Blocks C Sharp Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LegoBlocks
{
    class Program
    {
        static void Main(string[] args)
        {
            UInt64[,] totalSolutions = CreateWorkMatrix();

            Int32 t = Int32.Parse(Console.ReadLine());
            for (Int32 tt = 0; tt < t; tt++)
            {
                UInt32[] data = Console.ReadLine().Split(' ').Select(e => UInt32.Parse(e)).ToArray();

                Console.WriteLine(CalculateResultMatrix(totalSolutions, data[0], data[1]));
            }
        }

        static UInt64[,] CreateWorkMatrix()
        {
            UInt64[,] workMatrix = new UInt64[1001, 1001];

            for (Int32 i = 1; i <= 1000; i++)
            {
                workMatrix[i, 1] = 1;
            }

            workMatrix[1, 2] = 2;
            workMatrix[1, 3] = 4;
            workMatrix[1, 4] = 8;
            for (Int32 i = 5; i <= 1000; i++)
            {
                workMatrix[1, i] = (workMatrix[1, i - 1] + workMatrix[1, i - 2] + workMatrix[1, i - 3] + workMatrix[1, i - 4]) % 1000000007;
            }

            for (UInt32 x = 2; x <= 1000; x++)
            {
                UInt64 baseValue = workMatrix[1, x];
                UInt64 currentValue = workMatrix[1, x];
                for (UInt32 y = 2; y <= 1000; y++)
                {
                    currentValue = (currentValue * baseValue) % 1000000007;
                    workMatrix[y, x] = currentValue;
                }
            }

            return workMatrix;
        }

        static UInt64 CalculateResultMatrix(UInt64[,] totalSolutions, UInt64 n, UInt64 m)
        {
            UInt64[] resultingArray = new UInt64[1001];

            resultingArray[1] = 1;

            for (UInt32 i = 2; i <= m; i++)
            {
                UInt64 acum = 0;
                for (UInt32 j = 1; j < i; j++)
                {
                    acum = (acum + ((resultingArray[j] * totalSolutions[n, i - j]) % 1000000007)) % 1000000007;
                }

                resultingArray[i] = (totalSolutions[n, i] + 1000000007 - acum) % 1000000007;
            }

            return resultingArray[m];
        }
    }
}

Lego Blocks Java Solution

import java.util.*;
import java.io.*;

public class LegoBlock {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    public static long MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(reader.readLine().trim());
        long[][] mat = new long[3][1001];
        // mat[0] is the base row
        mat[0][1] = 1;
        mat[0][2] = 2;
        mat[0][3] = 4;
        mat[0][4] = 8;
        for (int i = 5; i <= 1000; i++) {
            mat[0][i] = LegoBlock.add(mat[0][i], mat[0][i - 1]);
            mat[0][i] = LegoBlock.add(mat[0][i], mat[0][i - 2]);
            mat[0][i] = LegoBlock.add(mat[0][i], mat[0][i - 3]);
            mat[0][i] = LegoBlock.add(mat[0][i], mat[0][i - 4]);
        }
        for (int tk = 1; tk <= t; tk++) {
            int[] split = Arrays.stream(reader.readLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();
            int n = split[0], m = split[1];
            
            if (n == 1) {
                if (m <= 4) {
                    System.out.printf("%d\n", 1);
                }  else {
                    System.out.printf("%d\n", 0);
                }
                continue;
            }
            
            // mat[1] is all combinations
            for (int nk = 1; nk <= n; nk++) {
                for (int i = 1; i <= m; i++) {
                    if (nk == 1) {
                        mat[1][i] = mat[0][i];
                        continue;
                    }
                    mat[1][i] = LegoBlock.mul(mat[1][i], mat[0][i]);
                }
            }
            // mat[2] is the solutions
            for (int i = 1; i <= m; i++) {
                mat[2][i] = LegoBlock.sub(mat[1][i], LegoBlock.sum(mat[2], mat[1], i));
            }
            System.out.printf("%d\n", mat[2][m]);
        }
    }

    public static long add(long a, long b) {
        return (a + b) % LegoBlock.MOD;
    }

    public static long mul(long a, long b) {
        return (a * b) % LegoBlock.MOD;
    }

    public static long sub(long a, long b) {
        if (a < b) {
            return (a + LegoBlock.MOD - b) % LegoBlock.MOD;
        }
        return (a - b) % LegoBlock.MOD;
    }

    public static long sum(long[] S, long[] A, int w) {
        if (w <= 1) {
            return 0;
        }
        long sum_bads = 0;
        for (int i = 1; i < w; i++) {
            sum_bads = LegoBlock.add(sum_bads, LegoBlock.mul(S[i], A[w - i]));
        }
        return sum_bads;
    }
}

Lego Blocks JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

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

function legoBlocks(n, m) {
    // Write your code here
    var mod = BigInt(Math.pow(10, 9) + 7);
    var oneFloor = [];
    var dirtyMultiFloor = [];
    var cleanMultiFloor = [];

    oneFloor = [0n, 1n, 2n, 4n, 8n];

    for (let width = 1; width <= m; width++) {
        if (width > 4) {
            oneFloor[width] =
                (oneFloor[width - 1] +
                    oneFloor[width - 2] +
                    oneFloor[width - 3] +
                    oneFloor[width - 4]) %
                mod;
        }

        dirtyMultiFloor[width] = 1n;
        for (let k = 0; k < n; k++) {
            dirtyMultiFloor[width] *= oneFloor[width];
            dirtyMultiFloor[width] %= mod;
        }
    }

    for (let width = 1; width <= m; width++) {
        cleanMultiFloor[width] = dirtyMultiFloor[width] + mod;
        for (let k = 1; k < width; k++) {
            cleanMultiFloor[width] -=
                (cleanMultiFloor[k] * dirtyMultiFloor[width - k]) % mod;
            cleanMultiFloor[width] += mod;
        }
    }

    return cleanMultiFloor[m] % mod;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine().trim(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

        const n = parseInt(firstMultipleInput[0], 10);

        const m = parseInt(firstMultipleInput[1], 10);

        const result = legoBlocks(n, m);

        ws.write(result + '\n');
    }

    ws.end();
}

Lego Blocks Python Solution

#!/usr/bin/env python

import sys

MOD = 1000000007

if __name__ == '__main__':
    T = int(sys.stdin.readline())
    
    for _ in range(T):
        N, M = list(map(int, sys.stdin.readline().split()))
            
        # The number of combinations to build a single row
        row_combinations = [1, 1, 2, 4]
        
        # Build row combinations up to this wall's width
        while len(row_combinations) <= M:
            row_combinations.append(sum(row_combinations[-4:]) % MOD)
                
        # Compute total combinations for constructing a wall of height N of varying widths
        total = [pow(c, N, MOD) for c in row_combinations]
              
        # Find the number of unstable wall configurations for a wall of height N of varying widths
        unstable = [0, 0]
        
        for i in range(2, M + 1):
            unstable.append(sum((total[j] - unstable[j]) * total[i - j] for j in range(1, i)) % MOD)     
        
        # Print the number of stable wall combinations
        print((total[M] - unstable[M]) % MOD)