In this HackerRank Hexagonal Grid problem solution, we have given a hexagonal grid consisting of two rows, each row consisting of N cells. your goal is to tile the whole grid such that every cell is covered by a tile, and no two tiles occupy the same cell. To add to the woes, certain cells of the hexagonal grid are blackened. No tile must occupy a blackened cell.
Problem solution in Python.
def solve(problem):
if not problem:
return True
if len(problem) == 1 and not problem[0]:
return False
elif len(problem) == 1 and problem[0]:
return True
if problem[0]:
return solve(problem[1:])
if not problem[0] and not problem[1]:
return solve(problem[2:])
if not problem[0] and len(problem) > 2 and not problem[2]:
return solve(problem[3:])
return False
for i in range(int(input())):
int(input()) # Pass, not interesting
first_row = [int(i) for i in str(input())]
second_row = [int(i) for i in str(input())]
row = [i for tupl in zip(first_row, second_row) for i in tupl]
if solve(row):
print('YES')
else:
print('NO')
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T>0){
int n = sc.nextInt();
List<Integer> cells = new ArrayList<>();
fillArr(cells, sc.next());
fillArr(cells, sc.next());
if(tile(cells)){
System.out.println("YES");
} else {
System.out.println("NO");
}
T--;
}
}
private static void fillArr(List<Integer> arr, String data) {
for (int i = 0; i < data.length(); i++) {
arr.add(data.charAt(i) - '0');
}
}
public static boolean tile(List<Integer> list) {
// set i+n, i+n-1, i+1 cells
int cSize = list.size() / 2;
Deque<List<Integer>> deque = new ArrayDeque<>();
deque.addFirst(list);
while (!deque.isEmpty()) {
List<Integer> cells = deque.removeLast();
int index = getFreeCellIndex(cells);
if (index < 0) return true;
if (index != cSize - 1)
tilePossibleCells(deque, cells, index, index + 1);
if (index != 0 && index != cSize)
tilePossibleCells(deque, cells, index, index + cSize - 1);
tilePossibleCells(deque, cells, index, index + cSize);
}
return false;
}
private static void tilePossibleCells(Deque<List<Integer>> deque, List<Integer> cells, int index, int next) {
if (next < cells.size()) {
if (cells.get(next) == 0) {
ArrayList<Integer> newCell = new ArrayList<>(cells);
newCell.set(next, 5);
newCell.set(index, 5);
// System.out.println("added: " + newCell);
deque.addFirst(newCell);
}
}
}
private static int getFreeCellIndex(List<Integer> cells) {
for (int i = 0; i < cells.size(); i++) {
if (cells.get(i) == 0) return i;
}
return -1;
}
}Problem solution in C++.
#include <cstdio>
#include <map>
using namespace std;
map<int,bool> cache;
bool possible(int bot, int top, int length) {
if (length == 0) {
return true;
}
map<int,bool>::iterator it = cache.find(top * 1024 + bot);
if (it != cache.end()) {
return it->second;
}
//printf("Trying\n%d\n%d\n%d\n", top, bot, length);
bool can = false;
// Special case if bot is blacked out
if (bot & 1) {
if (top & 1) {
can = possible(bot >> 1, top >> 1, length - 1);
} else if (length > 1 && !(top & 2)) {
can = possible (bot >> 1, (top >> 1) | 1, length - 1);
}
cache[top*1024 + bot] = can;
return can;
}
// Try left slant
if (!(top & 1)) {
can = possible(bot >> 1, top >> 1, length - 1);
} else {
//Try right slant
if (!(top & 2) && length > 1) {
can = possible(bot >> 1, (top >> 1) | 1, length - 1);
} else if (length > 1 && !(bot & 2)) {
// Try the single horizontal
can = possible(bot >> 2, top >> 2, length - 2);
}
}
cache[top*1024 + bot] = can;
return can;
}
int main() {
int T;
scanf("%d", &T);
for (int i = 0; i < T; ++i) {
int N;
scanf("%d\n", &N);
int top = 0;
for (int j = 0; j < N; ++j) {
char temp;
scanf("%c", &temp);
if (temp == '1') {
top |= 1 << j;
}
}
getchar();
int bot = 0;
for (int j = 0; j < N; ++j) {
char temp;
scanf("%c", &temp);
if (temp == '1') {
bot |= 1 << j;
}
}
cache.clear();
if (possible(bot, top, N)) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int T;
int N;
int a[2][12];
int dp[11][12];
int solve(int u, int d)
{
int retval = 0;
if(u>=N && d>= N)
return 1;
if((u-d)>=2)
{
if(a[1][d] == 1)
return retval |= solve(u, d+1);
else if(a[1][d+1] == 0)
return retval |= solve(u, d+2);
else
return 0;
}
else if((d-u)>=2)
{
if(a[0][u] == 1)
return retval |= solve(u+1, d);
else if(a[0][u+1] == 0)
return retval |= solve(u+2, d);
else
return 0;
}
else if(u<d)
{
// only one
// u 0 0
// 0 d d
if(a[0][u] == 1)
return retval |= solve(u+1, d);
else if(a[0][u+1] == 0)
return retval |= solve(u+2, d);
else
return 0;
}
else if(u>d)
{
if(a[1][d] == 1)
return retval |= solve(u, d+1);
else if((u-d) == 2)
{
if(a[1][d+1] == 0)
return retval |= solve(u+1, d);
else
return 0;
}
else
{
if(a[0][u] == 0)
retval |= solve(u+1, d+1);
if(a[1][d+1] == 0)
retval |= solve(u, d+2);
return retval;
}
}
else
{
if(a[0][u] == 1)
return retval |= solve(u+1, d);
else
{
if(a[1][d] == 0)
retval|= solve(u+1, d+1);
if(a[0][u+1] == 0)
retval |= solve(u+2, d);
return retval;
}
}
return retval;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
scanf("%d", &T);
for(int t=0; t<T; t++)
{
scanf("%d", &N);
for(int i=0; i<N; i++)
scanf("%1d", a[0]+i);
for(int i=0; i<N; i++)
scanf("%1d", a[1]+i);
a[0][N]=1;
a[1][N]=1;
#if 0
printf("----\n");
for(int i=0; i<N; i++)
printf("%d ", a[0][i]);
printf("\n");
for(int i=0; i<N; i++)
printf("%d ", a[1][i]);
printf("\n");
#endif
int retval = solve(0, 0);
if(retval)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
0 Comments