1

Working on some interesting combination problems related to Lego blocks. For example, this one. Confusion is, I often see two dimensions (e.g. height and width in below problem) mentioned to calculate the number of combinations, so length needed to mention in such problems?

https://www.hackerrank.com/challenges/lego-blocks

You have 4 types of lego blocks, of sizes (1 x 1 x 1), (1 x 1 x 2), (1 x 1 x 3), and (1 x 1 x 4). Assume that you have an infinite number of blocks of each type.

Using these blocks, you want to make a wall of height N and width M. The wall should not have any holes in it. The wall you build should be one solid structure. A solid structure can be interpreted in one of the following ways:

  1. It should not be possible to separate the wall along any vertical line without cutting any lego block used to build the wall.
  2. You cannot make a vertical cut from top to bottom without cutting one or more lego blocks.

The blocks can only be placed horizontally. In how many ways can the wall be built?

regards, Lin

miracle173
  • 11,049
Lin Ma
  • 183
  • 2
    What is the difference between "to separate the wall along any vertical line " and "make a vertical cut from top to bottom"? Doesn't both mean: A vertical line intersects the interior of at least one block? – miracle173 Jun 27 '16 at 06:53
  • @miracle173, agree with what you said. If you could comment on my original question, it will be great. Vote up. :) – Lin Ma Jun 27 '16 at 07:14
  • 1
    You can derive a recurrence using inclusion-exclusion: First ignore the solidity constraint; find the number of ways of tiling a row of width $M$ with blocks of lengths $1$ through $4$; take that to the $N$-th power to get the number of unconstrained configurations for an $N\times M$ wall; and then implement the solidity constraints using inclusion-exclusion over all possible positions of fissures that violate them. I don't think this will yield a closed form, but it would allow you to calculate the numbers with a computer. – joriki Jun 27 '16 at 07:16
  • Thanks @joriki, vote up. How do you comment on my original question, which is why only width/height mentioned, and no length? I think to calculate the combination, need all of the information. Please feel free to correct me. – Lin Ma Jun 27 '16 at 07:20
  • 1
    @LinMa: I guess I misspoke when I wrote "length"; read "width" instead. I was ignoring the third dimension since the blocks all have third dimension $1$. – joriki Jun 27 '16 at 07:32
  • 1
    You should check/use the forum by clicking Discussion. Also check the Editorial Tab. It sees that you can find a solution there. – miracle173 Jun 27 '16 at 13:12
  • @joriki, thanks. I think for a wall, it should have 3 dimension, when talking about width M and height N (or no matter if we call them length or width), what is your 3 dimension in your mind -- M * N * 1, correct? – Lin Ma Jun 27 '16 at 17:04
  • 1
    @LinMa: Yes, that's what I thought you meant by "a wall of height $N$ and width $M$". I assumed that if it was meant to have a third dimension other than the common dimension $1$ of all the blocks, you'd have stated it in the question. – joriki Jun 27 '16 at 17:16
  • @joriki, thanks and vote up. For the dimension of value 1, how do you call it, length? :) – Lin Ma Jun 27 '16 at 17:18
  • 1
    @LinMa: How about "thickness"? – joriki Jun 27 '16 at 17:21
  • @joriki, nice name, vote up. If you could add a reply, I will mark it as answer to benefit other people who has confusion as well for describe a 3 dimension object, like Lego block. :) – Lin Ma Jun 27 '16 at 17:46
  • 1
    @LinMa: Thanks, but I feel my suggestion answers the question only in a rather impracticable manner. Someone might come up with something better. – joriki Jun 27 '16 at 17:52
  • @joriki, thanks and vote up. :) – Lin Ma Jun 27 '16 at 17:55
  • 1
    https://www.hackerrank.com/challenges/lego-blocks/forum/comments/149085 – miracle173 Jun 29 '16 at 01:12
  • @miracle173, thanks and vote up. But how it is related to my question? :) – Lin Ma Jun 29 '16 at 01:31
  • 1
    it gives a hint how the number of walls can be calculated. Isn't this your question? – miracle173 Jun 29 '16 at 07:27
  • @miracle173, thanks for the info and vote up. Actually my question is, for a wall, it should be 3 dimension (width * height * length), in the problem statement, I only see height N and width M, it seems missing one dimension? I just want to ask in such problem, how should we get what is the 3rd dimension? If you have any further thoughts, it will be great. – Lin Ma Jun 29 '16 at 07:49

1 Answers1

1

I made some changes (marked boldface) and I hope the text is now clearer.

You have 4 types of lego blocks, of sizes given in (length x width x height) as (1 x 1 x 1), (2 x 1 x 1), (3 x 1 x 1), and (4 x 1 x 1). Assume that you have an infinite number of blocks of each type.

Using these blocks, you want to make a wall that is rectangular parallelepiped of height N and length M and width 1 without any holes and notches. The wall you build should be one solid structure. A solid structure can be interpreted in one of the following ways:

  1. It should not be possible to separate the wall along any vertical cut without cutting any lego block used to build the wall.
  2. You cannot make a vertical cut from top to bottom without cutting one or more lego blocks.

The blocks can only be placed in such a way that the lenght, width and height of a block are parallel to the length, width and height of the wall. In how many ways can the wall be built?

From this follows that the third dimension of the wall is 1 because it is explicitly mentioned. I think one cannot get this from the original text if one does not make some assumptions based on the experience with building lego walls in the childhood.

Because the problem is not affected by the width it can be view as a two dimensional tiling problem, And because height dimension of the blocks also does not affect the problem, it can be viewed as one dimensional problem.

miracle173
  • 11,049