It is Saturday morning and I am in my second block of the day. I typically do a couple 2-hour blocks on weekend days. As usual I got up at 05:00 AM and got breakfast ready. During breakfast my wife mentioned that she was not feeling well. Apparently she caught a cold or flu.
We had invited for lunch a couple of her brothers and spouses. One of her brother’s birthday was yesterday. We decided to change the menu and postpone lunch with family for next Saturday. We had planned a couple of Italian dishes and I was already savoring them. We both enjoy cooking but decided on a single simpler course for lunch.
After my first 2-hour block I prepared some tea. We sat in the living room
and continued discussing an alternate menu for the day. We decided that she would watch while I cooked a red sauce and pasta dish. Will use some grocery store bought egg noodles. I will just make the red sauce.
I cleaned some beef we had in the fridge and started the searing process in a pot with some olive oil. While the beef seared, I chopped a couple onions. I added the onions to the pot with some salt, spices and herbs.
I then opened a large (2 lbs) can of Italian tomato puree and poured it into the pot. Added some red wine and dried mushrooms. Lowered the temperature in the stove and covered the pot.
Turned on the oven and set the temperature to 350 degrees F. As soon as the oven reached temperature, tuned off the stove and placed the pot in the oven. Lunch should be ready by 01:00 PM.
After checking all was well came down to my office for the second and last 2-hour block of the day.
Early this morning I selected the challenge The Grid Search from HackerRank. The problem is rated with a medium difficulty. I got the code completed before the first break of the day. I decided to take care of some additional testing, submission and posting this entry in my blog during the second 2-hour block of the day.
If interested, take a look at the description of the description of the problem in HackerRank.
It seems that we are provided two arrays of numbers. The first array, which I will refer to the grid, contains a set of characters. Note that the testing scaffolding represents the grid as an array of strings.
The second array, which I will refer to as the pattern, contains an array of strings which we need to match exactly on the grid.
In general when matching patterns I like to approach the problem with a sliding window. We could place the pattern in the top left corner of the grid and start checking if the corresponding characters match. If they not, we can move to the next position in the grid and repeat the process. Sounds like a reasonable approach.
Note that since the pattern has a size, we do not need to start a match on every single character in the grid.
We also note that if we are matching characters and a few match, we could move the starting point to the location in which the match failed. There is no need to try matching on a grid in which we know the match will fail.
2 10 10 7283455864 6731158619 8988242643 3830589324 2229505813 5633845374 6473530293 7053106601 0834282956 4607924137 3 4 9505 3845 3530 15 15 400453592126560 114213133098692 474386082879648 522356951189169 887109450487496 252802633388782 502771484966748 075975207693780 511799789562806 404007454272504 549043809916080 962410809534811 445893523733475 768705303214174 650629270887160 2 2 99 99 YES NO
I decided to use Java and the Visual Studio Code IDE. The output of the sample case seems to match the expected results. We are given two tests. The first uses a grid of 10 x 10 characters and a pattern of 3 x 4 characters. The pattern is found so the code prints “YES”. On the second grid of 15 x 15 characters the 2 x 2 pattern is not found so we need to print “NO”.
/*
* Test scaffolding.
*/
public static void main(String[] args) throws IOException {
// **** ****
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// **** read the number of test cases ****
int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// // ???? ????
// System.out.println("main <<< t: " + t);
// **** loop once per test case ****
for (int tItr = 0; tItr < t; tItr++) {
// **** read and extract the number or rows and columns for the grid ****
String[] RC = scanner.nextLine().split(" ");
int R = Integer.parseInt(RC[0]);
int C = Integer.parseInt(RC[1]);
// // ???? ????
// System.out.println("main <<< R: " + R + " C: " + C);
// **** read the grid ****
String[] G = new String[R];
for (int i = 0; i < R; i++) {
String GItem = scanner.nextLine();
G[i] = GItem;
}
// **** read and extract the number or rows and columns for the pattern ****
String[] rc = scanner.nextLine().split(" ");
int r = Integer.parseInt(rc[0]);
int c = Integer.parseInt(rc[1]);
// // ???? ????
// System.out.println("main <<< r: " + r + " c: " + c);
// **** read the pattern ****
String[] P = new String[r];
for (int i = 0; i < r; i++) {
String PItem = scanner.nextLine();
P[i] = PItem;
}
// **** search for the pattern in the grid ****
String result = gridSearch(G, P);
// **** ****
bufferedWriter.write(result);
bufferedWriter.newLine();
}
// **** close the output stream ****
bufferedWriter.close();
// **** close the scanner ****
scanner.close();
}
I like to solve challenges using my computer systems. The first task is to create a project and copy the test scaffolding to my IDE. Like to first explore the provided code and understand how the data is provided. While doing so I add some comments and run some tests (which they all fail) until a solution is completed. I like to use a TDD approach at work and when solving challenges.
Once we have collected the data for the two arrays we call the function gridSearch() to address the problem.
/*
* Complete the gridSearch function below.
*/
static String gridSearch(String[] G, String[] P) {
// **** ****
int R = G.length;
int C = G[0].length();
// // ???? ????
// System.out.println("gridSearch <<< R: " + R + " C: " + C);
// **** ****
int r = P.length;
int c = P[0].length();
// // ???? ????
// System.out.println("gridSearch <<< r: " + r + " c: " + c);
// **** loop searching for the pattern in the grid ****
for (int row = 0; row <= R - r; row++) {
for (int col = 0; col <= C - c; col++) {
// **** search for the pattern at this location ****
int[] lastCoords = patternSearch(G, P, row, col);
// // ???? ????
// System.out.println("gridSearch <<< lastCoords: [" + lastCoords[0] + ", " +
// lastCoords[1] + "]");
// **** check if pattern was found ****
if ((row + r == lastCoords[0]) && (col + c == lastCoords[1])) {
return "YES";
}
}
}
// **** pattern NOT found ****
return "NO";
}
The idea is to position the pattern over the grid stating at the top left corner and moving it from left to right and top to bottom looking for a match. The actual match if checked by calling the patternSearch() function. Note that that function returns an array of two integers. These values are used to determine if a pattern is matched or not. I could as well have returned the strings “YES” or “NO” but I did not (more on this latter in this post).
/*
*
*/
static int[] patternSearch(String[] G, String[] P, int startRow, int startCol) {
// **** ****
int[] lastCoords = new int[2];
// // ???? ????
// System.out.println("patternSearch <<< startRow: " + startRow + " startCol: "
// + startCol);
// **** ****
int r = P.length;
int c = P[0].length();
// // ???? ????
// System.out.println("patternSearch <<< r: " + r + " c: " + c);
// ***** traverse the pattern matching the grid ****
int row = 0;
int col = 0;
for (row = 0; row < r; row++) {
for (col = 0; col < c; col++) {
// // ???? ????
// System.out.println("<<< P[" + row + "].charAt(" + col + "): " +
// P[row].charAt(col) + " G[" + (startRow + row)
// + "].charAt(" + (startCol + col) + "): " + G[startRow + row].charAt(startCol
// + col));
// **** check if we encountered a mismatch ****
if (P[row].charAt(col) != G[startRow + row].charAt(startCol + col)) {
// **** set last graphic coordinates ****
lastCoords[0] = startRow + row;
lastCoords[1] = startCol + col;
// **** return last graphic coordinates ****
return lastCoords;
}
}
}
// **** set last graphic coordinates ****
lastCoords[0] = startRow + row;
lastCoords[1] = startCol + col;
// **** return last graphic coordinates ****
return lastCoords;
}
This function performs a pattern search by attempting to traverse the entire pattern. If a mismatch occurs, it returns the values of the row and column where that match failed. The idea for this is to be able to start the next search and skip a few characters in the grid. If the solution as I have it here would have timed out, I will then have applied the technique I just described to speed up the search process. I did not implement it because the code was fast enough as is to pass all the tests.
he entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a message using the following address: john.canessa@gmail.com. All messages will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Twitter: @john_canessa