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.
  1. Lego Blocks
  2. Discussions

Lego Blocks

Sort by

recency

|

79 Discussions

|

  • knee982
     + 0 comments

    this question would be Hard Level in Leetcode

  • enadream
     + 1 comment

    One of the dumbest question I have ever seen. This is mathematical problem not algorithm or data structure.

  • joseespejo
     + 1 comment

    ┌──┬─┐
    ┼──┼─┼
    ┼──┴─┼
    └────┘

    Is this a valid wall? There are 2 rows with the same breaks but the total break doesnt reach the full height.

  • lijiapeng1412
     + 0 comments

    Q1: why {n:1 m:5} would be 0, and {n:1 m:3} would be want 1

    A1: m > 4, and the widest wall is 4, so the wall must has at least two block, and that cause a vertical break, and is invalid

    Q2: how to understand the calculation of invalid wall? (valid left part) * (all right part)

    A2:

    1. left part is valid, that is said left part does not have vertical break

    2. at least one vertical break is between left part and right part

    3. [ left part | right part ] the two part combined together is a wall that has at least one vertical break wall, and that is invalid

  • willis42
     + 0 comments

    My solution, with comments in case it helps:

    def legoBlocks(n, m):
  modulo = 10 ** 9 + 7
  # calculate num_permutations for one line
	# base cases:
	# (1, 1): (1,)
	# (1, 2): ((1, 1), (2,))
	# (1, 3): ((1, 1, 1), (1, 2), (2, 1), (3,))
	# (1, 4): ((1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2), (1, 3), (3, 1), (4,))
  num_permutations = [0, 1, 2, 4, 8]
  # iterate out further with dynamic programming expanding on prior subproblems:
  # each iteration, include 1-width block after all the i-1-width ways,
  # plus 2-width block after all the i-2-width ways, etc. up to the 4-width block
  for i in range(5, m+1):
    num_permutations.append((num_permutations[i - 1] + num_permutations[i - 2] + num_permutations[i - 3] + num_permutations[i - 4]) % modulo)
  
  num_permutations_for_n = [((i ** n) % modulo) for i in num_permutations]
  # intuitively, 0 ways to make a width-0 "good" wall, and only 1 way to make a width-1 "good" wall
  good_permutations = [0, 1]
  # any "good" wall permutation of width < w is essentially one of the "invalid" left portions of a "bad" wall, so we subtract those out, multiplied by the permutations_for_n 
  for i in range(2, m+1):
    gp_for_i = num_permutations_for_n[i]
    for j in range(1, i):
      gp_for_i -= (good_permutations[j] * num_permutations_for_n[i-j])
    good_permutations.append(gp_for_i % modulo)
  return good_permutations[m]