We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This question wrinkled my brain until I looked at Willis42's code. Here's some extra annotation in case it helps.
def legoBlocks(n, m):
# the ways to build a line of m from 0 up to 4 using legobricks from 1-4
# this takes the prev sums and adds one more way to it each time
permutations = [0, 1, 2, 4, 8]
mod = 10**9+7
# just keeps our numbers from getting too large - wraps if so
# for the rest, use dp to keep compiling the already set base cases. We dont need to add one more way here (like we did above) because we already compiled all the ways for bricks from 1-4 now if m is >=5 we just need to get the last 4 subproblems we already compiled and sum them. Remember, don't add "one more" bc we're not adding a "new way" bc we only consider lego bricks from 1-4. Permutations array already holds all the ways for 1-4, we just want to grab the already computed prev 4 ways each time.
for i in range(5, m+1):
permutations.append((permutations[i-1] + permutations[i-2] + permutations[i-3] + permutations[i-4])% mod)
# at this point we have all possible permutations of bricks from 1-4 up to m
# now we need to calculate n (height)
# we need to loop through all our permutations for each m, and raise them to the power of n to get all possible combinations up to n for each mth row.
for i in range(len(permutations)):
permutations[i] = (permutations[i] ** n) % mod
# now we have all possible but we need to introduce our condition to reduce by "bad" walls
# start with setting "good" permutations as 0 and 1 ( we dont have to worry about reducing till start stacking)
good_permutations = [0,1]
for i in range(2, m+1): # starting at 2 we are stacking rows
current = permutations[i] # grab the current one assuming all are "good"
for j in range(1, i): # now loop from each last known "good" section and subtract the right assuming all bad. as we move, we are only keeping known "good" sections and building on them
current -= (good_permutations[j] * permutations[i-j])
good_permutations.append(current % mod)
return good_permutations[m]
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lego Blocks
You are viewing a single comment's thread. Return to all comments →
This question wrinkled my brain until I looked at Willis42's code. Here's some extra annotation in case it helps.
def legoBlocks(n, m): # the ways to build a line of m from 0 up to 4 using legobricks from 1-4 # this takes the prev sums and adds one more way to it each time permutations = [0, 1, 2, 4, 8] mod = 10**9+7 # just keeps our numbers from getting too large - wraps if so