Header Ad

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. and 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


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



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("%lld\n",ColumnCombWithNoHoles[M]);
    	
}

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


Post a Comment

3 Comments

  1. Can someone pls explain the intuition behind developing the logic? I can understand how to generate all possible combination to fill up a single block of W width and 1unit height, lets say its n, then to fill up all the N blocks of W width we will have n^N ways(including cracks bw the walls combinations). How to remove these invalid combination that part is not clear to me.

    ReplyDelete
  2. This absolutely useless without any explanation of the logic behind it.

    ReplyDelete
  3. Hi, can anyone explain the logic behind the program. And if possible can sb explain the question with diagram?

    ReplyDelete