HackerRank Lego Blocks problem solution

In this HackerRank Lego Blocks problem solution, we have given an infinite number of 4 types of lego blocks of sizes given as (depth x height x width). and using these blocks we need to make a wall of height n and width m.

Remember that wall should not have any holes in it and should be one solid structure and bricks must be laid horizontally. all the permutations of the wall are not valid so we need to find and print the number of valid wall formations.

HackerRank Lego Blocks problem solution in Python.

#!/bin/python3

import os
import sys
import datetime
#
# Complete the legoBlocks function below.
#
def legoBlocks(n, m):
    A = 1000000000+7
    r = [0]*(m+1)
    a = [0]*(m+1)
    print(datetime.datetime.now())

    a[0] = 1
    for j in range(1, m+1):
        a[j] += a[j-1] if j-1>=0 else 0
        a[j] += a[j-2] if j-2>=0 else 0
        a[j] += a[j-3] if j-3>=0 else 0
        a[j] += a[j-4] if j-4>=0 else 0
    print(datetime.datetime.now())    
    for j in range(1, m+1):
        a[j] = a[j] % A
        a[j] = a[j] ** n
        a[j] = a[j] % A
    print(datetime.datetime.now())
    
    r[1] = 1
    for j in range(2, m+1):
        r[j] = a[j]
        for k in range(1, j):
            r[j] -= r[k]*a[j-k]
        r[j] = r[j] % A
    print(datetime.datetime.now())
    return r[m]%A

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        nm = input().split()

        n = int(nm[0])

        m = int(nm[1])

        result = legoBlocks(n, m)

        fptr.write(str(result) + 'n')

    fptr.close()

Lego Blocks problem solution in Java.

import java.util.*;

public class Solution {
	int md=1000000007;
	int[][] ways = new int[1001][1001];
	int[][] waysRestrict = new int[1001][1001];
	public Solution(){
		for(int[] w : ways) Arrays.fill(w, -1);
		for(int[] w : waysRestrict) Arrays.fill(w, -1);
	}
	public int solve(int n, int m)
	{
		if (ways[n][m] != -1) return ways[n][m];
		long ans;
		if (m==1) ans = 1;
		else if (n==1){
			if (m<=4) {
				ans = 2*solve(1,m-1);
			}
			else {
				ans = solve(1,m-1);
				ans = (ans + solve(1,m-2))%md;
				ans = (ans + solve(1,m-3))%md;
				ans = (ans + solve(1,m-4))%md;
			}
		}
		else{
			ans = 1; int one = solve(1,m);
			for (int i=0; i<n; i++) ans = (ans * one)%md;
		}
		ways[n][m] = (int)ans;
		return ways[n][m];
	}
	public int solveRestrict(int n, int m)
	{
		if (waysRestrict[n][m] != -1) return waysRestrict[n][m];
		long ans;
		if (m==1) ans = 1;

		else {
			ans = solve(n,m);
			for (int i=1; i<m; i++) {
				long a = solve(n,i);
				a = (a*solveRestrict(n,m-i))%md;
				ans -= a;
				if (ans<0) ans+=md;
			}
		}
		waysRestrict[n][m] = (int)ans;
		return waysRestrict[n][m];
	}
	public static void main (String[] args) {
		Solution o = new Solution();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i=0; i<n; i++) {
			int a, b;
			a = sc.nextInt(); b = sc.nextInt();
			System.out.println(o.solveRestrict(a,b));
		}
		sc.close();
	}
}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <stdio.h>

using namespace std;

const int M = 1000000007;
const int maxn = 1000;

long long T[maxn + 1][maxn + 1];
long long B[maxn + 1], G[maxn + 1];

void init()
{
	T[1][0] = 1;
	for (int j = 1; j <= maxn; j++)
	{
		T[1][j] = T[1][j - 1];
		if (j >= 2) T[1][j] += T[1][j - 2];
		if (j >= 3) T[1][j] += T[1][j - 3];
		if (j >= 4) T[1][j] += T[1][j - 4];
		T[1][j] %= M ;
	}
	for (int i = 2; i <= maxn; i++)
		for (int j = 1; j <= maxn; j++) 
		{
			T[i][j] = T[i - 1][j] * T[1][j];
			T[i][j] %= M ;
		}
}

int main()
{
	init();	
	int cs, n, m;
	cin >> cs ;
	while (cs--)
	{
		cin >> n >> m;
		B[1] = 0;
		G[1] = 1;
		for (int j = 2; j <= m; j++)
		{
			B[j] = 0;
			for (int k = 1; k < j; k++)
			{
				B[j] += T[n][j - k] * G[k];
				B[j] %= M ;
			}
			G[j] = (T[n][j] + M - B[j]) % M ;
		}
		cout << G[m] << endl;
	}	
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define MOD 1000000007
#define MAX 1001

 int N, M,i,j,nPieces = 4;
int pieces[] = {1, 2, 3, 4};
long long RowComb[MAX],ColumnComb[MAX],ColumnCombWithNoHoles[MAX];

void logic()
{
    scanf("%d %d",&N,&M);
    
    memset(RowComb, 0, sizeof(RowComb));
    RowComb[0] = 1;
    for (i = 1; i <= M; i++) {
        for (j = 0; j < nPieces; j++) {
            if (i - pieces[j] >= 0)
                RowComb[i] = (RowComb[i]+RowComb[i - pieces[j]]) % MOD;
        }
    }

    for (i = 1; i <= M; i++) {
        long long res = 1;
        for (j = 1; j <= N; j++) {
            res = (res *RowComb[i]) % MOD;
        }
        ColumnComb[i] = res;
    }
    ColumnCombWithNoHoles[1] = ColumnComb[1];
    for (i = 2; i <= M; i++) {
        ColumnCombWithNoHoles[i] = ColumnComb[i];
        for (j = 1; j < i; j++) {
            ColumnCombWithNoHoles[i] = (MOD + ColumnCombWithNoHoles[i]-(ColumnCombWithNoHoles[j] * ColumnComb[i - j]) % MOD) % MOD;
        }
    }

    printf("%lldn",ColumnCombWithNoHoles[M]);
    	
}

int main() {
    int T;
	scanf("%d",&T);	
	while(T--) logic();   
    return 0;
}