HackerRank Brick Tiling Problem Solution

#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( "%d\n", ways[n][tm2-1] );
}

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

#include <initializer_list>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

uint32_t const mod = 1000000007;

void addmod(uint32_t& lhs, uint32_t rhs)
{
    if ((lhs += rhs) >= mod) lhs -= mod;
}
uint32_t mulmod(uint32_t lhs, uint32_t rhs)
{
    return (lhs * rhs) % mod;
}
template <class F>
void enum_sets(uint32_t lower, uint32_t upper, F process)
{
    if (lower == (lower & upper))
    {
        uint32_t delta = 0, total = upper - lower;
            do { process(lower + delta); }
        while ((delta = total & (delta - total)));
    }
}
uint32_t tilecode(uint32_t width,
    uint32_t a, uint32_t b)
{
    return (a << width) + b;
}
uint32_t tilecode(uint32_t width,
    uint32_t a, uint32_t b, uint32_t c)
{
    return (tilecode(width, a, b) << width) + c;
}
uint32_t pick()
{
    uint32_t x; cin >> x; return x;
}
uint32_t pickline(uint32_t width)
{
    uint32_t code = 0;
    for (istream::sentry _(cin); width--;)
        code += code + (cin.get() == '.');
    return code;
}
void picklayer(uint32_t width, uint32_t& layers)
{
    layers = tilecode(width, layers, pickline(width));
}
struct tileset : vector<uint32_t>
{
    tileset(
        uint32_t maxpos, uint32_t hitbit,
        initializer_list<uint32_t> tiles)
    {
        generate(maxpos, 0, tiles);
        sort(begin(), end());
        auto stop = begin();
        uint32_t last = 1;
        for (auto curr : *this)
        {
            if (curr != last)
                *(stop++) = last = curr;
            stop[-1] += hitbit;
        }
        erase(stop, end());
    }
private:
    void generate(
        uint32_t maxpos, uint32_t preset,
        initializer_list<uint32_t> tiles)
    {
        push_back(preset);
        for (uint32_t pos = 0; pos < maxpos; ++pos)
            for (auto tile : tiles)
        if (!(preset & (tile <<= pos)))
            generate(pos, preset + tile, tiles);
    }
};

int main()
{
    for (auto tests = pick(); tests; --tests)
    {
        auto height = pick(), width = pick();
        if (height < 2)
        {
            cout << (pickline(width) ? 0 : 1) << endl;
            continue;
        }
        if (width < 2)
        {
            uint32_t answer = 1; while (height--)
                if (pickline(width)) answer = 0;
            cout << answer << endl; continue;
        }
        uint32_t hitpos = width * 3,
            hitbit = 1 << hitpos,
            mask111 = hitbit - 1,
            mask011 = mask111 >> width,
            mask001 = mask011 >> width,
            mask100 = mask111 - mask011,
            mask110 = mask111 - mask001;
        tileset const horizontal(
            width - 2, hitbit,
            {
                tilecode(width, 1, 7),
                tilecode(width, 4, 7),
                tilecode(width, 7, 1),
                tilecode(width, 7, 4)
            });
        tileset const vertical(
            width - 1, hitbit,
            {
                tilecode(width, 1, 1, 3),
                tilecode(width, 2, 2, 3),
                tilecode(width, 3, 1, 1),
                tilecode(width, 3, 2, 2)
            });
        uint32_t size = 1u << (width + width);
        vector<uint32_t> counts(size), buffer(size);
        uint32_t layers = 0;
        picklayer(width, layers);
        picklayer(width, layers);
        buffer[layers] = 1;
        for (--height;; layers &= mask011)
        {
            fill(counts.begin(), counts.end(), 0);
            for (auto code : horizontal)
            {
                auto hits = code >> hitpos;
                enum_sets(code &= mask111, layers,
                    [&](uint32_t found) -> void
                    {
                        addmod(counts[found - code],
                            mulmod(hits, buffer[found]));
                    });
            }
            if (!--height) break;
            picklayer(width, layers);
            fill(buffer.begin(), buffer.end(), 0);
            for (auto code : vertical)
            {
                auto hits = code >> hitpos; code &= mask111;
                if (code == (code & layers)) enum_sets(
                    (code & mask110) + (layers & mask001),
                    (code & mask100) + (layers & mask011),
                    [&](uint32_t found) -> void
                    {
                        addmod(buffer[found - code], mulmod(
                            hits, counts[found >> width]));
                    });
            }
        }
        cout << counts.front() << endl;
    }
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
    const int MOD = 1000000007;
    static bool[,] board;
    static Dictionary<long, long> map;
    static int[] l1 = { 1, 2, 2 }, r1 = { 0, 0, 1 }, l2 = { 1, 1, 1 }, r2 = { 0, 1, 2 }, l3 = { 0, 1, 2 }, r3 = { 1, 0, 0 }, lr = { 1, -1 };
    static void Main(String[] args) {
        int _tc_ = int.Parse(Console.ReadLine());
        while (_tc_-- > 0) {
            map = new Dictionary<long, long>();
            Brick_Tiling();
        }
    }
    public static void Brick_Tiling() {
        var tmp = Console.ReadLine().Split(' ');
        int n = int.Parse(tmp[0]);
        int m = int.Parse(tmp[1]);
        int nm = n * m;

        board = new bool[n, m];
        for (int i = 0; i < n; i++) {
            var _l = Console.ReadLine();
            for (int j = 0; j < m; j++) {
                if (_l[j] == '#') {
                    board[i, j] = true;
                    nm--;
                }
            }
        }

        if (nm % 4 != 0) { Console.WriteLine(0); return; }

        long ans = Tile(n, m, nm);
        Console.WriteLine(ans);
    }

    static long Tile(int n, int m, int nm) {
        if (nm == 0) return 1;

        long key = getkey(n, m);
        if (map.ContainsKey(key)) return map[key];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i, j]) continue;

                long ans = 0;

                foreach (var item in range(i, j)) {
                    if (valid(item, n, m)) {
                        Fill(item);
                        ans += Tile(n, m, nm - 4);
                        ans %= MOD;
                        Fill(item, false);
                    }
                }

                map[key] = ans;
                return ans;
            }
        }

        map[key] = 0;
        return 0;
    }

    static long getkey(int n, int m) {
        long r = 17;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                r *= 17;
                if (board[i, j]) r += 31;
            }
        }
        return r;
    }

    static void Fill(piece[] L, bool assign = true) {
        L[0].fill(assign);
        L[1].fill(assign);
        L[2].fill(assign);
        L[3].fill(assign);
    }

    static bool valid(piece[] L, int n, int m) {
        foreach (var item in L) {
            if (!onAndOff(item.first, item.second, n, m)) return false;
        }
        return true;
    }

    static bool onAndOff(int x, int y, int n, int m) {
        if (x < 0 || y < 0) return false;
        if (x >= n || y >= m) return false;
        if (board[x, y]) return false;
        return true;
    }

    static IEnumerable<piece[]> range(int x, int y) {

        piece[] r = { new piece(0, 0), new piece(0, 0), new piece(0, 0), new piece(x, y) };
        foreach (var u in lr) {
            foreach (var v in lr) {

                // l1 , r1
                for (int i = 0; i < 3; i++) {
                    r[i] = new piece(x + l1[i] * u, y + r1[i] * v);
                }
                yield return r;

                // r1, l1
                for (int i = 0; i < 3; i++) {
                    r[i] = new piece(x + r1[i] * u, y + l1[i] * v);
                }
                yield return r;

                // l2, r2
                for (int i = 0; i < 3; i++) {
                    r[i] = new piece(x + l2[i] * u, y + r2[i] * v);
                }
                yield return r;

                // r2, l2
                for (int i = 0; i < 3; i++) {
                    r[i] = new piece(x + r2[i] * u, y + l2[i] * v);
                }
                yield return r;

            }
        }


        foreach (var u in lr) {
            foreach (var v in lr) {

                for (int i = 0; i < 3; i++) {
                    r[i] = new piece(x + l3[i] * u, y + r3[i] * v);
                }
                yield return r;

                for (int i = 0; i < 3; i++) {
                    r[i] = new piece(x + r3[i] * u, y + l3[i] * v);
                }
                yield return r;
            }
        }
    }
    class piece {
        public int first, second;
        public piece(int f, int s) { first = f; second = s; }

        public void fill(bool assign) {
            board[first, second] = assign;
        }
    }
}

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("(\r\n|[\n\r\u2028\u2029\u0085])*");

    for (int tItr = 0; tItr < t; tItr++) {
      String[] nm = scanner.nextLine().split(" ");
      scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

      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("(\r\n|[\n\r\u2028\u2029\u0085])*");
        grid[gridItr] = gridItem;
      }

      int result = brickTiling(grid);

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

    bufferedWriter.close();

    scanner.close();
  }
}

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

const MOD = 1000000007;

const 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]]
];


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

const setValue = (pattern, arr, x, y, cols, val) =>{
    for (let p of pattern) {
        let nx = x + p[0];
        let ny = y + p[1];
        if (val == 1) {
            arr[nx] = arr[nx] | (1 << (cols - ny - 1));
        } else {
            arr[nx] = arr[nx] & ~(1 << (cols - ny - 1));
        }
    }
}

const hashArr = (arr) =>{
    return arr.join("");
}

const is_same =(array1, array2) => {
    return (array1.length == array2.length) && array1.every((element, index) => element === array2[index]); 
}

const calc = (arr, rows, cols, memo, memo2) => {
    let hash = hashArr(arr);
    if (memo.has(hash) && is_same(arr, memo2.get(hash))) {
        return memo.get(hash);
    }

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

    memo.set(hash, 1);
    memo2.set(hash, [...arr]);
    return 1;
}

/*
 * Complete the 'brickTiling' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts STRING_ARRAY grid as parameter.
 */

function brickTiling(grid) {
    let rows = grid.length;
    let cols = grid[0].length;

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

    return calc(arr, rows, cols, new Map(), new Map());
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine().trim(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

        const n = parseInt(firstMultipleInput[0], 10);

        const m = parseInt(firstMultipleInput[1], 10);

        let grid = [];

        for (let i = 0; i < n; i++) {
            const gridItem = readLine();
            grid.push(gridItem);
        }

        const result = brickTiling(grid);

        ws.write(result + '\n');
    }

    ws.end();
}

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]))