Discussion on The Grid Search Challenge

Sort 645 Discussions, By:

vangoor_bharath 5 years ago+ 0 comments

May be authors should add following testcase:

Because my code fails for this but for all the available testcases it passes.

bantic 5 years ago+ 0 comments

Some of the test cases have CR+LF (i.e. "\r\n") line endings, and the JavaScript boilerplate solution does not properly strip these off; it assumes all lines end with "\n" only. That means some of the grids and patterns for the test cases will be arrays like grid=["123\r","456\r","789\r"] and pattern = ["12\r","45\r"]. The boilerplate needs to update its processing of stdin to split on "\n" and then strip "\r" from each line as well.

JedJulliard 2 years ago+ 0 comments

Python code

check if first line of pattern fits into grid.

if it does, check for every other line of the pattern.

for every other line of pattern that checks off, add 1 to lineChecks

once lineChecks == len(pattern) -1, return YES

once a line of pattern does not check off, lineChecks return to zero.

def gridSearch(G, P):
    lineChecks = 0
    for i in range(len(G[0])-len(P[0])+1):
        for j in range(len(G)-len(P)+1):
            if G[j][i:i+len(P[0])] == P[0]:
                for x in range(1,len(P)):
                    if G[j+x][i:i+len(P[0])] == P[x]:
                        lineChecks +=1
                        if lineChecks == len(P) - 1:
                            return "YES"
                    else:
                        lineChecks = 0
    return "NO"

JsFoxy 4 years ago+ 0 comments

Here is my solution in Javascript using RegEx. I pass all test cases and times range from 0.06s up to 0.15s

function main() {
    var t = parseInt(readLine());
    for(var a0 = 0; a0 < t; a0++){
        var R_temp = readLine().split(' ');
        var R = parseInt(R_temp[0]);
        var C = parseInt(R_temp[1]);
        var G = [];
        for(var G_i = 0; G_i < R; G_i++){
           G[G_i] = readLine();
        }
        var r_temp = readLine().split(' ');
        var r = parseInt(r_temp[0]);
        var c = parseInt(r_temp[1]);
        var P = [];
        for(var P_i = 0; P_i < r; P_i++){
           P[P_i] = readLine();
        }
    	
        
        // -------------- Code below this point -----------
        var patt_len = P.length;
        var offset   = (G[0].length - P[0].length)+1;
        var pattern  = '';
        var regex;
        var result;
        var i;
        var str = '';

     	// Simply concatenate grid using . as separaor
        // make sure u use some kind of separator or
        // it won't work, you can use anything but
        // numbers here as separator
        str = G.join('.');

        // Here I build RegEx pattern
        for(i = 0; i < patt_len; i++)
        {
            if(i !== (patt_len - 1)){
                pattern += '(' + P[i] + ').{' + offset + '}';
            } else {
                pattern += '(' + P[i] + ')';
            }
        }
		
        // And in end we run it on our strig 
        // and see if we have match or not
        regex = new RegExp(pattern);
        result = str.match(regex);
        console.log(result !== null ? 'YES' : 'NO');
    }

}

So idea was to get grid array in one string, and then use pattern array to build RegEx expression and run it on string. So for example let's let's take one of default inputs:

After we concatenate our grid will look like:

// note that u can use any simbol to concatenate string
// just make sure it's not a number :)
7283455864.6731158619.8988242643.3830589324.2229505813.5633845374.6473530293.7053106601.0834282956.4607924137

And our pattern will look like this:

//note that "." in this regex it's not actual dot we used
// to concatenate string. The {7} part we got by calculating
// how much apart our patten needs to be in a string, we simply
// use our (grid length - pattern length) + 1, we need this +1
// to count in our concatenate simbol, in my case dot.
/(9505).{7}(3845).{7}(3530)/g

Kuriocity 1 year ago+ 0 comments

Java

static String gridSearch(String[] g, String[] p) 
    {
        for(int i=0;i<=(g.length-p.length);i++)
        {
            for(int j=0;j<=(g[0].length()-p[0].length());j++)
            {
                int a=i;
                int c=0;
                if(g[i].substring(j,j+p[0].length()).equals(p[0]))
                {
                    c++;
                    for(int k=1;k<p.length;k++)
                    {
                        i++;   
                        if(g[i].substring(j,j+p[0].length()).equals(p[k]))c++;
                        else break;
                         
                    }
                    if(c==p.length)return "YES";
                }
                i=a;
            }
        }
        return "NO";
    }

Load more conversations