Lego Blocks (interview question): subtracting number of cases with clear vertical break(s)

user_10338539 0
Viewed 57

I have been trying to understand the question extensively discussed here:

You have 4 types of lego blocks, of sizes 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3 and 1 * 1 * 4. Assume you have infinite number of blocks of each type.

You want to make a wall of height H and width M out of these blocks. The wall should not have any holes in it. The wall you build should be one solid structure. A solid structure means that it should not be possible to separate the wall along any vertical line without cutting any lego block used to build the wall. The blocks can only be placed horizontally. In how many ways can the wall be built?

I think I understood most of the implementation of the algorithm except the following idea:

Branch on the leftmost place where the wall is not connected. The number of All W*H walls is the number of Solid X*H walls times the number of All {W-X}*H walls,
summed across all possible values of X, plus the number of Solid W*H walls:

Shouldn't the total # of possible W*H walls be the sum of the number of All W*H walls times the number of All {W-X}* walls plus the number of Solid W*H walls? (I think maybe there's double counting if we just take the sum of All W*H walls and the number of All {W-X}* walls though...)

This would ensure that there is one vertical break between X and W-X among other potential vertical breaks within {W-X}*H walls.

In contrast, the sum of the number of All W*H walls times the number of Solid X*H walls and the number of All {W-X}*H walls and the number of Solid W*H walls sounds much more restrictive as we are ensuring that there is no vertical break within Solid X*H walls.

I think my confusion may stem from the fact that I have a hard time wrapping my head around the way they count the number of cases based on the idea of Branch on the leftmost place where the wall is not connected. in order to arrive at the formula S(H,W) = A(H,W) - Sum(S(H, L) * A(H, W-L)) [L=1..W-1] (That the number of solid walls with no vertical breaks is the number of all possible cases minus the number of Solid X*H walls times the number of All {W-X}*H walls summed across all possible X values.

dynamic-programming algorithm
1 Answers

Let's say f(n) is the number of ways of building a height-1 wall of length n, obviously ignoring the vertical rule.

Let's say g(n, k) = f(n)^k is the number of ways of building a height-k wall of length n, still ignoring the vertical rule.

We want h(n, k): the number of ways of building a height-k wall of length n that follows the vertical rule.

h(n, k) = g(n, k) less the subset of walls in g(n,k) that violate the vertical rule. Let's count those.

h(1, k) = g(1, k)

h(2, k) = g(2, k) - h(1, k) * g(1, k)

h(3, k) = g(3, k) - h(1, k) * g(2, k) - h(2, k) * g(1, k)

h(r, k) = g(r, k) - h(1, k) * g(r-1, k) - h(2, k) * g(r-2, k) - ... - h(r-1, k) * g(1, k).

What we're subtracting at each stage is all the walls that have their first vertical break at each possible position in succession.

Ruby implementation

def h(n,k)
  f_answers = [1, 1, 2, 4, 8] # f(n) for index n
  g_answers = []              # g(n, k) for index n
  h_answers = []              # h(n, k) for index n
  
  # populate f & g
  0.upto(n) do |i|
    f_answers.append(2 * f_answers[i-1] - f_answers[i-5]) if i >=5
    g_answers[i] = f_answers[i] ** k
  end
  
  # populate h
  1.upto(n) do |r|
    h_r = g_answers[r]
    1.upto(r-1) do |i|
      h_r -= h_answers[i] * g_answers[r-i]
    end
    h_answers[r] = h_r
  end
  
  return h_answers[n]
end
user_20410770
Related