HackerRank Brick Tiling problem solution

In this HackerRank Brick Tiling problem solution, we have given a grid having N rows and M columns. A grid square can either be blocked or empty. Blocked squares are represented by a ‘#’ and empty squares are represented by ‘.’. Find the number of ways to tile the grid using L-shaped bricks. An L brick has one side of length three units while the other of length 2 units. All empty squares in the grid should be covered by exactly one of the L-shaped tiles, and blocked squares should not be covered by any tile. The bricks can be used in any orientation (they can be rotated or flipped).

Problem solution in Python.

def memoize(func):
    pool = {}
    def wrapper(*arg):
        if arg not in pool:
            pool[arg] = func(*arg)
        return pool[arg]
    return wrapper

mod = 1000000007
shapes = (
    ((1,0),(2,0),(2,1)),
    ((0,1),(0,2),(-1,2)),
    ((0,1),(1,1),(2,1)),
    ((1,0),(0,1),(0,2)),
    ((0,1),(-1,1),(-2,1)),
    ((0,1),(0,2),(1,2)),
    ((1,0),(2,0),(0,1)),
    ((1,0),(1,1),(1,2)))

for case in range(int(input())):
    Y,X = map(int,input().split())
    mx = [int(''.join('0' if c =='.' else '1' for c in input().rstrip()), 2) for i in range(Y)]
    mx = mx + 3*[0]
    full = (1<<X)-1

    @memoize
    def rec(y,first,second,third):
        if y==Y:
            return 1 if first == second and second == third and third == 0 else 0
        if first == full:
            return rec(y+1,second,third,mx[y+3])

        def can_fit(rows,shape,x_offset):
            res = rows[:]
            for x,y in shape:
                x += x_offset
                if x < 0 or x >= X or y < 0 or y >= Y:
                    return None
                if res[y] & (1<<x) != 0:
                    return None
                res[y] |= (1<<x)
            return res

        free = 0
        while (first & (1<<free)) != 0:
            free += 1
        rows = [first | (1<<free),second,third]
        ans = 0
        for shape in shapes:
            nrows = can_fit(rows,shape,free)
            if nrows != None:
                ans = (ans + rec(y, *nrows)) % mod
        return ans

    print(rec(0,mx[0],mx[1],mx[2]))

Problem solution in Java.

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {

  static int MOD = 1000000007;

  static int[][][] patterns = {
      {{0, 0}, {0, 1}, {1, 0}, {2, 0}},
      {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
      {{0, 0}, {1, 0}, {2, 0}, {2, -1}},
      {{0, 0}, {1, 0}, {1, 1}, {1, 2}},
      {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
      {{0, 0}, {1, 0}, {1, -1}, {1, -2}},
      {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
      {{0, 0}, {1, 0}, {0, 1}, {0, 2}},
  };

  static boolean canApply(int[][] pattern, int[] arr, int x, int y, int rows, int cols) {
    for (int[] p : pattern) {
      int nx = x + p[0];
      int ny = y + p[1];
      if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || (arr[nx] & (1 << (cols - ny - 1))) > 0) {
        return false;
      }
    }
    return true;
  }

  static void setValue(int[][] pattern, int[] arr, int x, int y, int rows, int cols, int val) {
    for (int[] p : pattern) {
      int nx = x + p[0];
      int ny = y + p[1];
      if (val == 1) {
        arr[nx] = arr[nx] | (1 << (cols - ny - 1));
      } else {
        arr[nx] = arr[nx] & ~(1 << (cols - ny - 1));
      }
    }
  }

  static void printArr(int[] arr, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
      StringBuilder s = new StringBuilder();
      for (int j = 0; j < cols; j++) {
        s.append((arr[i] & (1 << (cols - j - 1))) > 0 ? '#' : '.');
      }
      System.out.println(s);
    }
    System.out.println();
  }
  
  static int[] copy(int[] arr) {
    int[] narr = new int[arr.length];
    System.arraycopy(arr, 0, narr, 0, arr.length);
    return narr;
  }

  static int calc(int[] arr, int rows, int cols, Map<Integer, Integer> memo, Map<Integer, int[]> memo2) {
    int hash = Arrays.hashCode(arr);
    if (memo.containsKey(hash) && Arrays.equals(arr, memo2.get(hash))) {
      return memo.get(hash);
    }

    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        int matched = arr[i] & 1 << (cols - j - 1);
        if (matched == 0) {
          int ans = 0;
          for (int[][] pattern : patterns) {
            if (canApply(pattern, arr, i, j, rows, cols)) {
              setValue(pattern, arr, i, j, rows, cols, 1);
              ans += calc(arr, rows, cols, memo, memo2);
              ans %= MOD;
              setValue(pattern, arr, i, j, rows, cols, 0);
            }
          }
          memo.put(hash, ans);
          memo2.put(hash, copy(arr));
          return ans;
        }
      }
    }

    memo.put(hash, 1);
    memo2.put(hash, copy(arr));
    return 1;
  }

  /*
   * Complete the brickTiling function below.
   */
  static int brickTiling(String[] grid) {
    /*
     * Write your code here.
     */
    int rows = grid.length;
    int cols = grid[0].length();

    int[] arr = new int[rows];
    for (int i = 0; i < rows; i++) {
      int val = 0;
      for (int k = 0; k < cols; k++) {
        if (grid[i].charAt(k) == '#') {
          val |= (1 << (cols - k - 1));
        }
      }
      arr[i] = val;
    }

    return calc(arr, rows, cols, new HashMap<>(), new HashMap<>());
  }

  private static final Scanner scanner = new Scanner(System.in);

  public static void main(String[] args) throws IOException {

    BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    int t = scanner.nextInt();
    scanner.skip("(rn|[nru2028u2029u0085])*");

    for (int tItr = 0; tItr < t; tItr++) {
      String[] nm = scanner.nextLine().split(" ");
      scanner.skip("(rn|[nru2028u2029u0085])*");

      int n = Integer.parseInt(nm[0]);

      int m = Integer.parseInt(nm[1]);

      String[] grid = new String[n];

      for (int gridItr = 0; gridItr < n; gridItr++) {
        String gridItem = scanner.nextLine();
        scanner.skip("(rn|[nru2028u2029u0085])*");
        grid[gridItr] = gridItem;
      }

      int result = brickTiling(grid);

      bufferedWriter.write(String.valueOf(result));
      bufferedWriter.newLine();
    }

    bufferedWriter.close();

    scanner.close();
  }
}

Problem solution in C++.

#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

ll ways[25][260][260];
ll mod = 1000000007;
vector<pair<int, int> > upWays[260][10];
bool computed[260][10];
int n, m;

int map[25];

vector<pair<int, int> >& getUpWays(int fill, int w){
    if(computed[fill][w]) return upWays[fill][w];
    // printf("up ways%dn", fill);
    computed[fill][w] = true;
    if(fill == 0){
        upWays[fill][w].push_back(make_pair(0, 0));
        return upWays[fill][w];
    }
    vector<pair<int, int> >& ways = upWays[fill][w];
    for(int i = 0; i < w; i++){
        if(fill & (1<<i)){
            int up = 1<<i, upup = 3<<i;
            vector<pair<int, int> >& prev = getUpWays(fill - (1<<i), w);
            if(i + 1 < w){
                for(auto p : prev){
                    if(p.first & upup) continue;
                    if(p.second & up) continue;
                    ways.push_back(make_pair(p.first | upup, p.second | up));
                }
            }
            if(i > 0){
                upup = 3<<(i - 1);
                for(auto p : prev){
                    if(p.first & upup) continue;
                    if(p.second & up) continue;
                    ways.push_back(make_pair(p.first | upup, p.second | up));
                }
            }
            if(i + 2 < w){
                for(auto p : prev){
                    if(p.second & 7<<i)continue;
                    ways.push_back(make_pair(p.first, p.second | (7<<i)));
                }
            }
            if(i > 1){
                up = 7<<(i - 2);
                for(auto p : prev){
                    if(p.second & up)continue;
                    ways.push_back(make_pair(p.first, p.second | up));
                }
            }
            if(i == w - 1 || (3<<i) - (fill & (3<<i)))  break;
            up = 1<<i;
            vector<pair<int, int> >& pprev = getUpWays(fill - (3<<i), w);
            for(auto p : pprev){
                if(!(p.first & (1<<i)) && !(p.second & (1<<i))){
                    ways.push_back(make_pair(p.first | (1<<i), p.second | (1<<i)));
                }
                if(!(p.first & (2<<i)) && !(p.second & (2<<i))){
                    ways.push_back(make_pair(p.first | (2<<i), p.second | (2<<i)));
                }
            }
            if(i == w - 2 || (7<<i) - (fill & (7<<i))) break;
            vector<pair<int, int> >& ppprev = getUpWays(fill - (7<<i), w);
            for(auto p : ppprev) {
                if(!(p.second & (1<<i))){
                    ways.push_back(make_pair(p.first, p.second | (1<<i)));
                }
                if(!(p.second & (4<<i))){
                    ways.push_back(make_pair(p.first, p.second | (4<<i)));
                }
            }
            break;
        }
    }
    return ways;
}

ll getWays(int row, int row1, int row2){
    // printf("call %d %d %dn", row, row1, row2);
    if(row < -2){
        return 0;
    }
    if(row == -2){
        return (row1 == (1<<m) - 1) && (row2 == (1<<m) - 1) ? 1 : 0;
    }
    if(row == -1){
        // printf("%d %d %dn", row, row1, row2);
        return (row1 == (1<<m) - 1) && (row2 == map[0]) ? 1 : 0;
    }
    if(ways[row][row1][row2] != -1) return ways[row][row1][row2];
    if(map[row] - (row1 & map[row]) ||
        map[row + 1] - (row2 & map[row + 1])) return ways[row][row1][row2] = 0;

    int fill1 = row1 - map[row],
        fill2 = row2 - map[row + 1];

    if(fill1 == 0 && fill2 == 0) return ways[row][row1][row2] = getWays(row - 2, (1<<m) - 1, (1<<m) - 1);
    if(fill2 == 0) return ways[row][row1][row2] = getWays(row - 1, (1<<m) - 1, fill1 + map[row]);
    if(fill1 == 0) return ways[row][row1][row2] = 0;

    ll r = 0;
    // printf("%d %d %dn", row, fill1, fill2);
    vector<pair<int, int> >& upWay = getUpWays(fill2, m);
    for(auto u : upWay){
        int r1 = u.first, r2 = u.second;
        // printf("fill %d %dn", r1, r2);
        if(r2 - (fill1 & r2)) continue;
        r += getWays(row - 1, (1<<m) - 1 - r1, fill1 - r2 + map[row]);
        r %= mod;
    }

    return ways[row][row1][row2] = r;
}

int main(){
    int t;
    scanf("%d", &t);
    char row[20];
    for(int i = 0; i < 260; i++)for(int j = 0; j < 10; j++){
        computed[i][j] = false;
    }
    while(t--){
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++){
            scanf("%s", row);
            int mm = 0;
            for(int j = 0; j < m; j++){
                if(row[j] == '#'){
                    mm |= 1<<j;
                }
            }
            map[i] = mm;
        }
        for(int i = 0; i < n; i++)for(int j = 0; j < (1<<m); j++)for(int k = 0; k < (1<<m); k++){
            ways[i][j][k] = -1;
        }
        printf("%lldn", getWays(n - 2, (1<<m) - 1, (1<<m) - 1));
    }
    return 0;
}

Problem solution in C.

#include "assert.h"
#include "stdio.h"

#define rep(i,n) for(i=0;i<(n);i++)

#define MOD 1000000007
#define N 25
#define M 8
#define B 8

int n, m, tm, tm2, grid[N], ways[N][1<<(2*M)], width[B] = { 1, 1, 1, 1, 2, 2, 3, 3 }, b[M][B];
char buf[M+1];

int make_brick( int a, int b, int c, int d )
{
	return ( tm2 * a + tm * b + c ) << d;
}

void rec( int x, int y, int s0, int s1 )
{
	if( y == m )
	{
		ways[x+1][s1] = ( ways[x+1][s1] + ways[x][s0] ) % MOD;
		return;
	}

	if( ( ( s0 / tm ) >> y ) & 1 )
	{
		rec( x, y + 1, s0, s1 );
		return;
	}

	int i;
	rep(i,B) if( b[y][i] && ( ( b[y][i] / tm ) & s0 ) == 0 && ( b[y][i] & s1 ) == 0 )
		rec( x, y + width[i], s0, s1 ^ ( b[y][i] % tm2 ) );
}

void run()
{
	int i, j;
	scanf( "%d%d", &n, &m );
	assert( 1 <= n && n <= 20 && 1 <= m && m <= 8 );
	tm = 1<<m, tm2 = 1<<(2*m);

	rep(i,m)
	{
		b[i][0] = i + 2 <= m ? make_brick( 1, 1, 3, i ) : 0;
		b[i][1] = i - 1 >= 0 ? make_brick( 2, 2, 3, i - 1 ) : 0;
		b[i][2] = i + 3 <= m ? make_brick( 1, 7, 0, i ) : 0;
		b[i][3] = i - 2 >= 0 ? make_brick( 4, 7, 0, i - 2 ) : 0;
		b[i][4] = i + 2 <= m ? make_brick( 3, 1, 1, i ) : 0;
		b[i][5] = i + 2 <= m ? make_brick( 3, 2, 2, i ) : 0;
		b[i][6] = i + 3 <= m ? make_brick( 7, 1, 0, i ) : 0;
		b[i][7] = i + 3 <= m ? make_brick( 7, 4, 0, i ) : 0;
	}

	rep(i,n)
	{
		grid[i] = 0;
		scanf( "%s", buf );
		rep(j,m) assert( buf[j] == '#' || buf[j] == '.' );
		rep(j,m) if( buf[j] == '#' ) grid[i] ^= 1<<j;
	}
	grid[n] = grid[n+1] = tm-1;

	rep(i,n+1) rep(j,tm2) ways[i][j] = 0;
	ways[0][ tm * grid[0] + grid[1] ] = 1;
	rep(i,n) rep(j,tm2) if( ways[i][j] ) rec( i, 0, j, ( j % tm ) * tm + grid[i+2] );

	printf( "%dn", ways[n][tm2-1] );
}

int main()
{
	int t;
	scanf( "%d", &t );
	assert( 1 <= t && t <= 50 );
	while( t-- ) run();
	return 0;
}