Table of Contents
Brick Tiling – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Brick Tiling HackerRank Solution
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define PB push_back
#define MP make_pair
#define SZ(v) ((int)(v).size())
#define abs(x) ((x) > 0 ? (x) : -(x))
#define FOREACH(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
typedef long long LL;
const int MOD = 1000000007;
const int inf = 0x3f3f3f3f;
const int maxn = 25;
const int maxs = 1 << 8;
LL dp[maxn][maxs][maxs];
int state[maxn];
int cur, nxt;
int n, m, initJ, initK;
bool valid(int mask, int pos) {
return (mask & (1 << pos)) == 0;
}
void dfs(int dep, int s1, int s2, int s3, int current) {
if (current >= (1 << m)) return;
if (current == (1 << m) - 1) {
dp[nxt][s2][s3] = (dp[nxt][s2][s3] + dp[cur][initJ][initK]) % MOD;
return;
}
if (s1 & (1 << dep)) {
dfs(dep + 1, s1, s2, s3, current);
} else {
// ### <- dep
// #
if (dep + 1 < m && valid(s2, dep) && valid(s3, dep) && valid(s3, dep + 1)) {
dfs(dep + 1, s1, s2 | (1 << dep), s3 | (1 << dep) | (1 << (dep + 1)), current | (1 << dep));
}
// #
// ### <- dep
if (dep >= 1 && valid(s2, dep) && valid(s3, dep) && valid(s3, dep - 1)) {
dfs(dep + 1, s1, s2 | (1 << dep), s3 | (1 << dep) | (1 << (dep - 1)), current | (1 << dep));
}
// # <- dep
// ###
if (dep + 1 < m && valid(s1, dep + 1) && valid(s2, dep + 1) && valid(s3, dep + 1)) {
dfs(dep + 2, s1, s2 | (1 << (dep + 1)), s3 | (1 << (dep + 1)), current | (1 << dep) | (1 << (dep + 1)));
}
// ### <- dep
// #
if (dep + 1 < m && valid(s1, dep + 1) && valid(s2, dep) && valid(s3, dep)) {
dfs(dep + 2, s1, s2 | (1 << dep), s3 | (1 << dep), current | (1 << dep) | (1 << (dep + 1)));
}
// ## <- dep
// #
// #
if (dep + 2 < m && valid(s2, dep) && valid(s2, dep + 1) && valid(s2, dep + 2)) {
dfs(dep + 1, s1, s2 | (1 << dep) | (1 << (dep + 1)) | (1 << (dep + 2)), s3, current | (1 << dep));
}
// #
// #
// ## <- dep
if (dep >= 2 && valid(s2, dep) && valid(s2, dep - 1) && valid(s2, dep - 2)) {
dfs(dep + 1, s1, s2 | (1 << (dep - 2)) | (1 << (dep - 1)) | (1 << dep), s3, current | (1 << dep));
}
// ## <- dep
// #
// #
if (dep + 2 < m && valid(s2, dep) && valid(s1, dep + 1) && valid(s1, dep + 2)) {
dfs(dep + 3, s1, s2 | (1 << dep), s3, current | (1 << dep) | (1 << (dep + 1)) | (1 << (dep + 2)));
}
// # <- dep
// #
// ##
if (dep + 2 < m && valid(s1, dep + 1) && valid(s1, dep + 2) && valid(s2, dep + 2)) {
dfs(dep + 3, s1, s2 | (1 << (dep + 2)), s3, current | (1 << dep) | (1 << (dep + 1)) | (1 << (dep + 2)));
}
}
}
char str[10];
int main() {
int ts;
scanf("%d", &ts);
while (ts--) {
memset(state, 0, sizeof(state));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", str);
for (int j = 0; j < m; j++) {
if (str[j] == '#') {
state[i] |= (1 << j);
}
}
}
if (n == 1) {
if (state[1] == (1 << m) - 1) puts("1");
else puts("0");
continue;
}
memset(dp, 0, sizeof(dp));
dp[2][state[1]][state[2]] = 1;
for (int i = 2; i <= n; i++) {
cur = i, nxt = i + 1;
for (int j = 0; j < (1 << m); j++) {
for (int k = 0; k < (1 << m); k++) {
if (dp[cur][j][k] == 0) continue;
initJ = j; initK = k;
dfs(0, j, k, state[i + 1], j);
}
}
}
cout << dp[n + 1][(1 << m) - 1][0] << endl;
}
return 0;
}
Java Brick Tiling HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
// static String INPUT = "1 2 2 ## ##";
static String INPUT = "";
static int[] makeMaskArray(int mask, int h, int amask)
{
int[] ret = new int[h];
int p = 0;
for(int i = 0;i < h;i++){
if((i&mask) == 0 && (amask == -1 || (i&amask) != 0)){
ret[p++] = i;
}
}
return Arrays.copyOf(ret, p);
}
static void solve()
{
for(int T = ni();T >= 1;T--){
int n = ni(), m = ni();
char[][] map = nm(n,m);
int[] pre = new int[1<<m*2+1];
pre[(1<<m*2+1)-1] = 1;
int[] cur = new int[1<<m*2+1];
int mod = 1000000007;
int omask = (1<<m*2+1)-1;
int hmask = 1<<m*2;
int mask1 = 1<<m-1|1<<2*m-1|1<<2*m;
int mask2 = 1<<m-1|1<<2*m-1|1<<2*m-2;
int mask3 = 1<<m-1|1<<m|1<<m+1;
int mask4 = 1<<m-1|1<<m-2|1<<m-3;
int mask5 = 1<<0|1<<m|1<<2*m;
int mask6 = 1<<0|1<<m-1|1<<2*m-1;
int mask7 = 1<<0|1<<1|1<<m+1;
int mask8 = 1<<0|1<<1|1<<m-1;
int[] val1 = makeMaskArray(mask1, 1<<2*m+1, -1);
int[] val2 = makeMaskArray(mask2, 1<<2*m+1, hmask);
int[] val3 = makeMaskArray(mask3, 1<<2*m+1, hmask);
int[] val4 = makeMaskArray(mask4, 1<<2*m+1, hmask);
int[] val5 = makeMaskArray(mask5, 1<<2*m+1, -1);
int[] val6 = makeMaskArray(mask6, 1<<2*m+1, hmask);
int[] val7 = makeMaskArray(mask7, 1<<2*m+1, hmask);
int[] val8 = makeMaskArray(mask8, 1<<2*m+1, hmask);
int[] valn = makeMaskArray(0, 1<<2*m+1, hmask);
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
Arrays.fill(cur, 0);
if(map[i][j] == '.'){
// xx
// .x
// .x
if(i >= 2 && j >= 1){
for(int k : val1){
int nk = ((k|mask1)<<1|1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}
// x.
// x.
// xx
if(i >= 2 && j >= 1){
for(int k : val5){
int nk = ((k|mask5)<<1|1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}
// xx
// x.
// x.
if(i >= 2 && j+1 < m){
for(int k : val2){
int nk = ((k|mask2)<<1|1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}
// .x
// .x
// xx
if(i >= 2 && j >= 1){
for(int k : val6){
int nk = ((k|mask6)<<1|1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}
// xxx
// ..x
if(i >= 1 && j >= 2){
for(int k : val3){
int nk = ((k|mask3)<<1|1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}
// x..
// xxx
if(i >= 1 && j >= 2){
for(int k : val7){
int nk = ((k|mask7)<<1|1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}
// xxx
// x..
if(i >= 1 && j+2 < m){
for(int k : val4){
int nk = ((k|mask4)<<1|1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}
// ..x
// xxx
if(i >= 1 && j >= 2){
for(int k : val8){
int nk = ((k|mask8)<<1|1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}
// none
for(int k : valn){
int nk = (k<<1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}else{
for(int k : valn){
int nk = (k<<1|1)&omask;
cur[nk] += pre[k];
if(cur[nk] >= mod)cur[nk] -= mod;
}
}
int[] dum = cur; cur = pre; pre = dum;
}
}
out.println(pre[(1<<m*2+1)-1]);
}
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Brick Tiling HackerRank Solution
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]))
Python 2 Brick Tiling HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
#!/usr/bin/python
def memo(func):
save = {}
def f(*args):
if args not in save:
save[args] = func(*args)
return save[args]
return f
shapes = (
# x
# o
# o o
((0,0), (1,0), (2,0), (2,1)),
# x o o
# o
((0,0), (0,1), (0,2), (1,0)),
# x o
# o
# o
((0,0), (0,1), (1,1), (2,1)),
# x
# o o o
((0,0), (1,-2), (1,-1), (1,0)),
# x o
# o
# o
((0,0), (0,1), (1,0), (2,0)),
# x
# o o o
((0,0), (1,0), (1,1), (1,2)),
# x
# o
# o o
((0,0), (1,0), (2,-1), (2,0)),
# x o o
# o
((0,0), (0,1), (0,2), (1,2)),
)
def get(layout, n, m):
full = (1 << m) - 1
for x in xrange(3):
layout.append(full)
'''
def p(x):
s = bin(x)
a = len(s) - 2
return "0000000000"[:m-a] + s[2:]
'''
@memo
def f(row, fst, snd, thr):
'''
print 'row', row
print p(fst)
print p(snd)
print p(thr)
'''
if row == n: return 1
if fst == full: return f(row+1, snd, thr, layout[row+3])
pos = 0
while pos < m:
if (fst & (1 << (m-1-pos))) == 0:
break
pos += 1
def go(shape):
ret = [fst, snd, thr]
for x,y in shape:
r, c = row + x, pos + y
if r < 0 or c < 0 or r >= n or c >= m: return None
if ret[x] & (1<<(m-1-c)): return None
ret[x] |= 1 << (m-1-c)
return ret
ret = 0
for x in shapes:
g = go(x)
if g is not None:
ret += f(row, *g)
return ret % 1000000007
return f(0, layout[0], layout[1], layout[2])
t = input()
for x in xrange(t):
n, m = map(int, raw_input().strip().split())
layout = []
empty = 0
for y in xrange(n):
here = 0
row = raw_input()
for x in row:
if x == '.':
empty += 1
here = here * 2
else:
here = here * 2 + 1
layout.append(here)
if empty == 0:
print 1
elif empty % 4 != 0:
print 0
else:
print get(layout, n, m)
C Brick Tiling HackerRank 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;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
