Town Planning

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:

1. 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.
2. 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.
3. A possible arrangement of houses in a specific row is represented by a decimal number as discussed above.
4. 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.
5. If an arrangement in the current row is valid, recursion will be called for the next rows and the best answer will be returned.
6. 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.
7. 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.

1. Initialize a variable ‘count’ to 0, this will keep a count of the number of set bits.
2. 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.
3. 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.

1. Check if ‘mask’ & (1 << ‘i’) is 1.
   • Return true.
2. 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’:

1. Initialize a variable ‘n’ = size of array ‘row’.
2. 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.
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 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.
4. 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’:

1. Base condition: If i is equal to the size of ‘Town’ (equal to number of rows):
   • Return 0.
2. Initialize variable ‘and’ equal to 0, this will store the best answer for the current row.
3. Initialize variable ‘m’ equal to number of rows, ‘n’ to number of columns.
4. 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.

1. 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.

1. Initialize variable ‘prevRow’ = 0 (dummy row ‘prevRow’ which has all cells vacant).
2. Initialize variable ‘i’ = 0, which stores the current row number in ‘Town’.
3. 'and’ = ‘getMaxHouses(‘Town’, ‘prevRow’, ‘i’)’.
4. Return ‘ans’.

O(2^M * 2^N * 2^N * N), where ‘M’ is the number of rows and ‘N’ is the number of columns.

Total number of recursive calls can be 2^’M’ * 2^’N’, and in each recursive call, 2^N arrangements are checked, where each arrangement’s validity is checked using ‘N’ iterations. Hence, total time complexity is O(2^M * 2^N * 2^N * N)

O(2^M * 2^N), where ‘M’ is the number of rows and ‘N’ is the number of columns.

Total number of recursive calls can be 2^’M’ * 2^’N’. Hence, total space taken on recursion stack is O(2^M * 2^N)