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):
d h w
1 1 1
1 1 2
1 1 3
1 1 4
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
3
7
9
3375
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)