Town Planning
Last Updated: 26 Apr, 2021
Difficulty: Hard
Town planner Ninja is assigned to build new houses in the ninja town for its citizens. The town is in the form of a rectangular grid ‘TOWN[][]’ of (‘M’ * ‘N’) dimensions where 'M' is the number of rows and 'N' is the number of columns. Each cell of the grid can be an 'empty location' (that can be used for house) denoted by '.' or 'Tree' denoted by 'T'.
Ninja wants to meet the demands of the citizens without cutting any of the trees.
Following are the conditions asked by citizens for their house locations :
House should not have a house on its left cell
House should not have a house on its right cell
House should not have a house on its upper-left cell
House should not have a house on its upper-right cell
Town planner Ninja needs your help. Return the maximum number of houses that can be built while meeting the citizens' demands and not cutting any of the trees.
For Example :
Input :
M = 3 , N = 5
Grid :
. . . T .
. T . . .
T . . T .
In the example above, the maximum number of houses that be built is 8.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then ‘T’ test cases follow:
The first line in each test case contains two space-separated positive integers ‘M’ and ‘N’, where 'M’ is the number of rows and ‘N’ is the number of columns in the grid.
The next ‘M’ lines contain a string of length ‘N’ containing ‘.’ or ‘T’ representing empty space or a Tree, respectively.
Output Format :
For each test case, print an integer denoting the maximum number of houses that can build following the conditions stated above.
Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 8
1 <= M <= 8
‘TOWN’ = { “.”,"T"}
Where 'TOWN’ denotes the 2-D grid represents whether a cell is empty or not.
Time limit: 1 sec
Approach 1
First of all, we should know why we are doing bitmasking? Below is the explanation:
- All the cells occupied by houses can be represented as ‘1’, and the remaining cells can be represented as ‘0’ by the user. Hence, a state of a row can be represented as a series of 0’s and 1’s (series of 0’s and 1’s is a binary number).
- Integers are stored as binary numbers in the memory but appear as decimal numbers to the user. Therefore, we tend to use a decimal number instead of a binary number to represent the state of a row.
Let’s now discuss the approach:
- The idea is to find all the valid combinations of houses of a row and call recursion on the next rows for each valid arrangement.
- To find if an arrangement of houses in a specific row is valid or not, we do the following checks for each cell (if we want to build a house in that cell):
- House should not have a house on its left cell
- House should not have a house on its right cell
- House should not have a house on its upper-left cell
- House should not have a house on its upper-right cell
- House should not be made if there is a tree in that specific cell.
- A possible arrangement of houses in a specific row is represented by a decimal number as discussed above.
- Hence, each of our recursive functions will generate all possible arrangements of houses and will check if each of the arrangements is valid. So, our recursive function will also have the previous row’s arrangement to check if the houses in the current row’s arrangement do not have any house to their upper-left cell and upper-right cell.
- If an arrangement in the current row is valid, recursion will be called for the next rows and the best answer will be returned.
- Let’s call the function that will return the best answer as ‘planTown()’ where the best answer is the maximum number of houses that can be built on the grid meeting all the demands.
- In addition to ‘planTown()’ function, we will need few additional functions as follows:
- ‘countSetBits()’ - count the number of set bits in a number (number of 1’s in binary representation of a number).
- ‘on()’ - check if a specific bit in a number is set or not (is 1 or not).
- ‘isArrangementValid()’ - checks if an arrangement of houses in a row is valid or not by checking if a cell is vacant or not and checking each cell if there are houses on its left, right and also using previous row arrangement to check if each cell has houses on their upper left and upper right cell.
- ‘getMaxHouses()’ - it's the recursive function which is called from ‘planTown()’ function to get the optimal answer.
Below are the functionality of each function:
countSetBits(‘mask’) :
This function takes an integer as an argument whose set bits are to be counted.
- Initialize a variable ‘count’ to 0, this will keep a count of the number of set bits.
- Run a for loop from 0 to (8 * size of integer) (say iterator = ‘i’) - Here, (8 * size of integer) is the limit because size of integer is (4 or 8 bytes) and 1 byte = 8 bits. Hence, total of (4 or 8) * (8 bits) are present which are to be checked.
- Check if (‘mask’ & (1 << ‘i’) is 1) - this will check if ‘ith’ bit is set
- ‘count’ = ‘count’ + 1.
- Else
- Continue.
- Check if (‘mask’ & (1 << ‘i’) is 1) - this will check if ‘ith’ bit is set
- Return ‘count’.
on(‘i’ , ‘mask’) :
This function takes two integers as arguments, ‘i’ and ‘mask’ where ‘mask’ is the integer whose ‘ith’ bit is to be checked if it is set or not.
- Check if ‘mask’ & (1 << ‘i’) is 1.
- Return true.
- Else
- Return false.
isArrangementValid(‘row’, ‘currRow’, ‘prevRow’) :
This function takes character arguments: array/list ‘row’ which is the current row, Integer ‘currRow’ which is the arrangement of houses for current row and Integer ‘prevRow’ which is the arrangement of houses in the previous row.
This function checks if ‘currRow’ is valid with respect to ‘prevRow’ an array/list ‘row’:
- Initialize a variable ‘n’ = size of array ‘row’.
- Run a for loop from 0 to ‘n’-1 (say iterator = ‘j’), to check for left and right houses:
- If on(‘j’ , ‘currRow’) == true:
- If (row[j] is equal to ‘T’), there is a tree at ‘jth’ cell in ‘row’:
- Return false.
- If (j is greater than 0 and on(‘j’-1,’currRow’)) is true, there is house on left of ‘jth’ cell :
- Return false.
- If (j is less then ‘n’-1 and on(‘j’+1,’currRow’)) is true, there is house on right of ‘jth’ cell :
- Return false.
- If (row[j] is equal to ‘T’), there is a tree at ‘jth’ cell in ‘row’:
- If on(‘j’ , ‘currRow’) == true:
- Run a for loop from 0 to ‘n’-1 (say iterator = ‘j’), to check for upper left and upper right houses:
- If (j is greater than 0 and on(‘j’, currRow) is true and on(‘j-1’, ‘prevRow’ is true), there is house on upper left cell:
- Return false.
- If (j is less than ‘n’-1 and on(‘j’, currRow) is true and on(‘j+1’, ‘prevRow’ is true), there is house on upper right cell:
- Return false.
- If (j is greater than 0 and on(‘j’, currRow) is true and on(‘j-1’, ‘prevRow’ is true), there is house on upper left cell:
- Return true.
getMaxHouses(‘Town’, ‘prevRow’, ‘i’):
This function takes arguments: array/list of array/list of characters ‘Town’ which is the original situation of town, Integer ‘prevRow’ which previous rows arrangement of houses, Integer ‘i’ which is index of current house, and returns the best answer for ‘ith’ row with respect to ‘prevRow’ and rows after ‘i’:
- Base condition: If i is equal to the size of ‘Town’ (equal to number of rows):
- Return 0.
- Initialize variable ‘and’ equal to 0, this will store the best answer for the current row.
- Initialize variable ‘m’ equal to number of rows, ‘n’ to number of columns.
- Run a for loop from 0 to 1 << ‘n’, (say iterator = ‘mask’), this is done to get all possible arrangement of houses in current row, where 1<<’n’ is equal to 2^’n’:
- If isArrangementValid(‘Town[i]’, ‘mask’, ‘prevRow’) is true, the current arrangement ‘mask’ is valid:
Call recursion on rows after ‘i’:
- temp = ‘getMaxHouses(‘Town’, ‘mask’, ‘i+1’) + countSetBits(‘mask’)’.
- Ans = maximum of ans and temp.
- Return ans.
planTown(‘Town’):
This function takes grid ‘Town’ as argument and calls recursive function ‘getMaxHouses’ to get the best answer, and then returns it.
- Initialize variable ‘prevRow’ = 0 (dummy row ‘prevRow’ which has all cells vacant).
- Initialize variable ‘i’ = 0, which stores the current row number in ‘Town’.
- 'and’ = ‘getMaxHouses(‘Town’, ‘prevRow’, ‘i’)’.
- Return ‘ans’.
Approach 2
The approach is very similar to approach 1. What we will do here is that we will not make repetitive recursive calls to the recursive functions if we have already calculated an answer for a specific value.
But how do we know that there will be repeated recursive calls?
Let’s understand :
Suppose we are at the ‘ith’ row of ‘Town’ and we make the following 2 recursive calls:
Recursive call 1 from ‘ith’ row:
- There can be 0 to 2^’n’ possible arrangements of houses on a specific row.
- So, suppose we are at the ‘ith’ row and recursion is called on the ‘xth’ arrangement of houses on row ‘i+1’ (0<=x<=2^’n’)’.
- Now, we reach the ‘i+1th’ row through a recursive call. Here also, there can be 0 to 2^’n’ possible arrangements of houses. So, from the ‘i+1th’ row, recursion is called on the ‘zth’ arrangement of houses on row ‘i+2’ (0<=z<=2^’n’).
Recursive call 2 from ‘jth’ row:
- There can be 0 to 2^’n’ possible arrangements of houses on a specific row.
- So, suppose we are at the ‘ith’ row and recursion is called on ‘yth’ arrangement of houses on row ‘i+1’ (0<=y<=2^’n’)’.
- Now, we reach the ‘i+1th’ row through a recursive call. Here also, there can be 0 to 2^’n’ possible arrangements of houses. So, from the ‘i+1th’ row, recursion is called on the ‘zth’ arrangement of houses on row ‘i+2’ (0<=z<=2^’n’).
From these 2 recursive calls from ‘ith’ row of ‘Town’ grid, we can see that both recursive calls were made from different arrangements (‘xth’ and ‘yth’ arrangement), but when we made recursive call from ‘i+1th’ row, arrangement ‘z’ is passed to ‘i+2th’ row. Hence, ‘zth’ arrangement from ‘i+1th’ row is passed 2 times this way but the same answer is returned from both calls. Hence, it is observed that repetitive recursive calls are made. So, to avoid these repetitive calls, we can store a previously calculated result in an array.
Below are the functionality of each function:
countSetBits(‘mask’) :
This function takes an integer as an argument whose set bits are to be counted.
- Initialize a variable ‘count’ to 0, this will keep a count of the number of set bits.
- Run a for loop from 0 to (8 * size of integer) (say iterator = ‘i’) - Here, (8 * size of integer) is the limit because size of integer is (4 or 8 bytes) and 1 byte = 8 bits. Hence, total of (4 or 8) * (8 bits) are present which are to be checked.
- Check if (‘mask’ & (1 << ‘i’) is 1) - this will check if ‘ith’ bit is set:
- ‘count’ = ‘count’ + 1.
- Else:
- Continue.
- Return ‘count’.
on(‘i’ , ‘mask’) :
This function takes two integers as arguments, ‘i’ and ‘mask’ where ‘mask’ is the integer whose ‘ith’ bit is to be checked if it is set or not.
- Check if ‘mask’ & (1 << ‘i’) is 1:
- Return true.
- Else:
- Return false.
isArrangementValid(‘row’, ‘currRow’, ‘prevRow’) :
This function takes character arguments: array ‘row’ which is the current row, Integer ‘currRow’ which is the arrangement of houses for current row and Integer ‘prevRow’ which is the arrangement of houses in the previous row.
This function checks if ‘currRow’ is valid with respect to ‘prevRow’ and array ‘row’:
- Initialize a variable ‘n’ = size of array ‘row’.
- Run a for loop from 0 to ‘n’-1 (say iterator = ‘j’), to check for left and right houses:
- If on(‘j’ , ‘currRow’) == true
- If (row[j] is equal to ‘T’), there is a tree at ‘jth’ cell in ‘row’:
- Return false.
- If (j is greater than 0 and on(‘j’-1,’currRow’)) is true, there is house on left of ‘jth’ cell :
- Return false.
- If (j is less then ‘n’-1 and on(‘j’+1,’currRow’)) is true, there is house on right of ‘jth’ cell :
- Return false.
- If (row[j] is equal to ‘T’), there is a tree at ‘jth’ cell in ‘row’:
3. Run a for loop from 0 to ‘n’-1 (say iterator = ‘j’), to check for upper left and upper right houses:
- If (j is greater than 0 and on(‘j’, currRow) is true and on(‘j-1’, ‘prevRow’ is true), there is a house on the upper left cell:
- Return false.
- If (j is less than ‘n’-1 and on(‘j’, currRow) is true and on(‘j+1’, ‘prevRow’ is true), there is house on upper right cell:
- Return false.
4. Return true.
getMaxHouses(‘Town’, ‘prevRow’, ‘i’, ‘dp’):
This function takes arguments: array of array of characters ‘Town’ which is the original situation of town, Integer ‘prevRow’ which previous rows arrangement of houses, Integer ‘i’ which is index of current house, and ‘dp’ array which is used to store the calculated results to avoid repetitive recursive calls(memoization). This function returns the best answer for ‘ith’ row with respect to ‘prevRow’ and rows after ‘i’:
- If i is equal to the size of ‘Town’ (equal to number of rows) (base condition):
- Return 0.
- If ‘dp[prevRow][i]’ is not equal to -1:
- return ‘dp[prevRow][i]’ because the value for the combination of ‘prevRow’ and ‘i’ is already calculated.
- Initialize variables ‘ans’ equal to 0, this will store the best answer for the current row.
- Initialize variable ‘m’ equal to number of rows, ‘n’ to number of columns.
- Run a for loop from 0 to 1 << ‘n’, (say iterator = ‘mask’), this is done to get all possible arrangement of houses in current row, where 1<<’n’ is equal to 2^’n’:
- If isArrangementValid(‘Town[i]’, ‘mask’, ‘prevRow’) is true, the current arrangement ‘mask’ is valid:
- Iteger temp = ‘getMaxHouses’(‘Town’, ‘mask’, ‘i+1’, ‘dp’) + countSetBits(‘mask’).
- Ans = maximum of ‘Ans’ and ‘temp’.
- If isArrangementValid(‘Town[i]’, ‘mask’, ‘prevRow’) is true, the current arrangement ‘mask’ is valid:
- Store value of ‘ans’ into ‘dp[prevRow][i]’ and return it.
planTown(‘Town’):
This function takes grid ‘Town’ as argument and calls recursive function ‘getMaxHouses’ to get the best answer, and then returns it.
- Initialize variable ‘prevRow’ = 0 (dummy row ‘prevRow’ which has all cells vacant).
- Initialize a 2D ‘dp’ array of dimensions (2^8)*(8) because maximum rows = 8 and range of arrangements is from (0 to 2^8).
- Assign value = -1 to every index of the ‘dp’ array to mark than none of the combinations is calculated yet.
- Initialize variable ‘i’ = 0, which stores the current row number in ‘Town’.
- Integer 'and’ = ‘getMaxHouses(‘Town’, ‘prevRow’, ‘i’, ‘dp’)’.
- Return ‘ans’.
Approach 3
This approach uses the same idea as the top-down DP approach, but instead of making recursive calls to calculate for previous rows, we use iteration in a bottom-up manner.
Now, let’s discuss the approach:
- We denote dp[i][mask] as the maximum number of houses for the first ‘i’ rows while the houses in the ‘i-th’ row follow the masking mask. There should be no adjacent valid states in the mask. The transition function is:
- ‘dp[i][mask]’ = max(‘dp[i][mask]’, ‘dp[i - 1][prevMask]’) + number of valid bits(‘mask’)
- where ‘prevMask’ is the masking for the (i-1)-th row. To meet the demands of citizens following conditions must hold:
- (‘mask’ & (‘prevMask’ >> 1)) == 0, there should be no houses in the upper left position for every house.
- ((‘mask’ >> 1) & ‘prevMask’) == 0, there should be no houses in the upper right position for every house.
- If these two equations hold and ‘dp[i - 1][prevMask]’ itself is valid, we could then transit from ‘dp[i - 1][prevMask]’ to ‘dp[i][mask]’ according to the transition function.
