HackerRank Hexagonal Grid problem solution YASH PAL, 31 July 2024 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') {“mode”:”full”,”isActive”:false} 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; } } {“mode”:”full”,”isActive”:false} 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("Tryingn%dn%dn%dn", 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("%dn", &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("YESn"); } else { printf("NOn"); } } return 0; } {“mode”:”full”,”isActive”:false} 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("YESn"); else printf("NOn"); } return 0; } {“mode”:”full”,”isActive”:false} algorithm coding problems