Fill 4xN wall with 4×1 and 1×4 bricks

There is a wall with 4 x N dimensions and we have a brick with 4 x 1 dimension. We have to fill the wall with given brick and find out how may ways possible to fill that wall.

For example, if there is wall with N = 3, we have only one way to fill the wall, with three brick laid horizontally.

Where as with N = 4, there are two ways, one with putting four bricks horizontally, or 4 bricks vertically.

fill wall with bricks Actually, examples themselves give away the answer to the our problem. Let’s start small and build on top of it. What if N = 1 , then wall dimensions are 4 x 1, and there is only one way to fill that wall with brick of 4 x 1, which is to lay the brick horizontally.

What if N = 2, i.e. wall  is 4 x 2, , again, there is only one way  possible, put two bricks horizontally,we cannot put bricks vertical. Why?

Take N  = 3, i.e. wall with 4 x 3, only way we can fill the wall is to put three bricks horizontally, can’t use vertical brick.

What if N = 4, wall with 4 x 4 dimensions, in this scenario, we have two options, put four bricks horizontally or four bricks vertically, so there are two ways to fill a wall of 4 x 4 with brick of 4 x 1.

Now,  if number of ways to fill a wall of dimension 4 x N is f(N) then f(N) for values 1, 2 and 3 is as follows.

f(1)=1, f(2)=1, f(3)=1

We have two choices for each brick for wall of size greater than 4 X 3.  Either to keep brick vertically or  to keep brick horizontally.

If we keep brick vertically, we cover four units out of N units height of wall with each brick, require four vertical bricks to cover horizontally, so problem reduces to N-4 units.

If we keep brick horizontally, then it covers only 1 unit height of wall, hence we need to cover N-1 units of height further.
So, for N we have relationship as

f(N) = f(N-1)  + f(N-4)

We have the recurrence relation and the base conditions, let’s implement it.

Fill wall with brick : recursive implementation

int findWays(int n){
        if(n == 0 || n == 1 || n == 2 || n == 3) return 1;
        return findWays(n-1) + findWays(n-4);
}

int main(void) {
	int N = 5;
	int ways = findWays(N);
	printf("%d", ways);
	return 0;
}

Do you think this solution is optimized? Why do you think, it can be optimized and how? If you closely look at the recursion tree of implementation, you will see the problem. Some of the subproblems are solved repeatedly. Can we avoid solving them again and again?  Yes, that’s called memoization.

Well, this problem can be solved using dynamic programming, because two properties hold : First, optimal solution to subproblem gives solution to original problem. Second, overlapping subproblems.

Dynamic programming approach would be to fill a table bottom up where table [N] will be the solution.  table[0] = table[1] = table[2] = table[3] = 1 as discussed above.

Now from N = 4, we can fill the table bottom up as

table[N] = table[N-1] + table[N-4]

Fill wall with brick : dynamic programming implementation

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

int main(void) {
	int N =5;
	int table[N+1];
	table[0] = 1;
	table[1] = 1;
	table[2] = 1;
	table[3] = 1;
	find_ways(N, table);
	printf("%d", table[N]);
	return 0;
}

Complexity of dynamic programming approach is O (N) with space complexity of O(N).

Please share if there is something wrong or missing. If you are willing to share your knowledge and help thousands of learners across the world, please reach out to us on communications@algorithmsandme.com