What is the total number of ways in which the bricks can be arranged on the wall?

5
votes

There is a wall of size 4xN. We have infinite number of bricks of size 4x1 and 1x4. What is the total number of ways in which the bricks can be arranged on the wall so that a new configuration arises every time?

For N = 1, the brick can be laid in 1 format only. For N = 7, one of the ways in which we can lay the bricks is

enter image description here

There are 5 ways of arranging the bricks for N = 7

I solve this problem using dynamic programming:

static int computeBricks(int n)
{
    if(n <= 3) { return 1; }

    int[] table = new int[n+1];

    table[0] = 1;
    table[1] = 1;
    table[2] = 1;
    table[3] = 1;

    for(int i = 4; i <= n; ++i)
    {
        table[i] = table[i-1] + table[i-4];
    }

    return table[n];
}

But it's just a combination: a guess + intuition. I don't understand this solution completely. Why table[i] = table[i-1] + table[i-4]?

Doesn't it look like the coin change problem?

The number of ways to change amount a using n kinds of coins equals: the number of ways to change amount a using all but the first kind of coin, plus the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.

But I also don't understand how we can use this idea to solve the original problem

3
c#algorithm
First create set n1 - which is number of possible long breaks. Values from 0 to int(N/4). Foreach n1 you'll get set of n2=N-n1*(4-1). Calculate possible variant for n2. Repeat for all n1... - Leonid Malyshev
This is very similar to the coin change problem. Look only at the bottom row: it consists of units of size 1and 4. There is only one way to build the wall from each bottom row pattern. So the solution is counting possible ways of summing N with only 1 and 4. However, here order matters. - rici
@rici Can you help me please to create a full solution using coin change problem ideas? That's how we can solve coins problem f(N, coins, m - 1) + f(n - coins[m - 1], coins, m); How to transform this solution to compute the original problem about bricks? - user6611771
You already have the solution: f(i) = f(i-1) + f(i-4). That's simpler than the coin change problem because there are only two "coins". The multiple coin equivalent would be F(N, coins, m, i) = f(N, coins, m, i-1) + f(N - coins[i-1], coins, m, m): in other words, either don't use "this coin" (index i) or use "this coin" and restart the scan. - rici

3 Answers

5
votes

Just to be complete, you can do that using simple counting techniques, no algorithm needed.

You have N spots. You have two ways to fill the spots: either one at a time (vertical bricks), or filling 4 consecutive spots in one go (horizontal bricks). You can reformulate that: this is the number of ways you can place K piles of 4 horizontal bricks (K is between 0 and N/4) among N-(3*K) vertical bricks (for each pile of 4 horizontal bricks, you lose 3 spots compared to 1 vertical brick - this is kind of where your [n-4] comes from in your original algorithm).

Let's illustrate that with an example. First of all, the notation choose(n, k) that I use below is the mathematical combination "n choose k", i.e.

combination

Now let's dive in the example. What can you do with N = 15 spots?

  • You have either K = 0 pile of horizontal bricks (H) and 15 vertical bricks (V): VVVVVVVVVVVVVVV. The number of ways to do that is choose(15, 0) = 1

  • Or you can place K = 1 H somewhere (you lose three spots by replacing 4 V by 1 H): VVVVHVVVVVVV. The number of ways to do that is choose(15-3, 1) = choose(12, 1) = 12

  • Or you can place K = 2 H (you lose six spots by replacing 8 V by 2 H): VVHVVVVVH. The number of ways to do that is choose(15-6, 2) = choose(9, 2) = 36

  • Or you can place K = 3 H (you lose nine spots by replacing 12 V by 3 H): HVVHHV. The number of ways to do that is choose(15-9, 3) = choose(6, 3) = 20

That's it, you have reached the maximum number of horizontal piles (max K = 15/4 = 3). Then you just sum all of these to get the total number of ways you can fill the spots: 1+ 12 + 36 + 20 = 69.

Here is the general formula that directly follows up from this explanation:

formula1

Which finally leads to:

formula2

2
votes

There is obviously only one way to arrange the bricks if you have less than 4 columns:

1, 12, 123
1, 12, 123
1, 12, 123
1, 12, 123

However, there are two ways to arrange bricks for the 4-th column.
Way 1 - simply add a column to a correct solution of 3 columns:

1234
1234
1234
1234

Way 2 - remove existing three columns and place four horizontal bricks:

1111
2222
3333
4444

The same logic applies to all consequent columns - you may either take all proper arranges for N-1 and add a column to each of them or take all correct arranges for N-4 and place four bricks horizontally.
The solution is that simple because of one derivation from the problem - you can either place 4 horizontal bricks or 4 vertical bricks, because putting 1 horizontal brick will make placing vertical impossible, and vice versa.
This task would be much more difficult if wall still was 4xN, but bricks were 2x1 and 1x2.

0
votes
  f(n) = f(n-1) + f(n-4)  if n >= 4 <p>
  f(n) = 1 if 0  <= n < 4