1
$\begingroup$

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

$\endgroup$
17
  • 2
    $\begingroup$ 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? $\endgroup$ Commented Jun 27, 2016 at 6:53
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 27, 2016 at 7:16
  • 1
    $\begingroup$ @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$. $\endgroup$ Commented Jun 27, 2016 at 7:32
  • 1
    $\begingroup$ You should check/use the forum by clicking Discussion. Also check the Editorial Tab. It sees that you can find a solution there. $\endgroup$ Commented Jun 27, 2016 at 13:12
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Jun 27, 2016 at 17:16

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks miracle173 for the patience to reply, mark your reply as answer. $\endgroup$ Commented Jun 29, 2016 at 19:03

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.