In this Lego Blocks HackerRank solution, we 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?
Lego Blocks HackerRank solution
I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.
Problem Solution in Python
def legoBlocks(n, m):
f = [1]
g = [1]
h = [1]
for i in range(1, m + 1):
sumhg = 0
for j in range(1, i):
sumhg += h[j] * g[i-j] % (10**9+7)
f.append(sum(f[-4:]) % (10**9+7))
g.append(f[i] ** n % (10**9+7))
h.append((g[i] - sumhg) % (10**9+7))
return h[-1] % (10**9+7)Problem Solution in TypeScript
function legoBlocks(height: number, width: number): number {
let all = Array.from<bigint>({ length: width + 1 });
all[0] = 1n; // f(w) = 1 when w = 0
for (let w = 1; w < width + 1; w++) {
all[w] = all.slice(Math.max(0, w - 4), w).reduce((s, w) => s + w, 0n);
}
all = all.map(item => {
let temp = 1n;
for (let i = 0; i < height; i++) {
temp *= item;
}
return temp;
}); // f(w) ** h
const valid = [...all]; // assume all are valid
for (let w = 0; w < valid.length; w++) {
for (let separator = 1; separator < w; separator++) { // left-most separator
valid[w] = (valid[w] - valid[separator] * all[w - separator]) // minus invalid from valid
}
}
const mod = BigInt(10 ** 9 + 7);
return Number(valid[width] % mod);
}Solve original Problem on HackerRank here. Checkout more HackerRank Problems