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.

HackerRank Hexagonal Grid problem solution


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("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;
}

{"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("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

{"mode":"full","isActive":false}