Discussion on The Grid Search Challenge

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