Challenge 03: Searching the Matrix

Abi and Maddy are now in kindergarten at ECDC on Notre Dame's campus. Although they are quite the animal experts¹, they are still novices at math and most numerical things². To help them improve their math skills, they play a game where they put numbers in a grid in ascending order such as below:

1 3 5
7 9 11
13 15 17

Then they take turns coming up with numbers and checking if it is in the grid. For instance, the number 7 is in the matrix above, but the number 12 is not.

They are pretty good at this game if the board is small. Unfortunately, as the matrix grows and the amount of numbers to search within the grid increases, the time required to search for their targets takes too long and they get frustrated and ask Alexa to play Despacito³ to help them with their sadness.

Because their father disapproves of the digital assistant⁴, he asks that you help his daughters come up with a faster way to search the matrices for different numbers.

Input

You will be given a series of matrices and search targets in the following format:

ROWS COLS
R1C1 R1C2 R1C3 ...
R2C1 R1C2 R1C3 ...
...
NTARGETS
TARGET1
TARGET2
...

First you will get the number of ROWS and COLS in the matrix (where 0 < ROWS, COLS <= 250), followed by the data in the matrix. The values will be integers in the range 0 <= VALUE <= 1,000,0000 and will be in ascending order across each row and down the columns. Next, you will be given a number, NTARGETS, indicating the number of targets you need to search the matrix for, followed by those targets.

Here is an example input:

3 3
1 3 5
7 9 11
13 15 17
2
7
12

The final matrix will begin with ROWS and COLS values of 0 0 and should not be processed.

Output

You are to read in each matrix and then check if each of the NTARGETS is contained in the matrix. If found, you should report the coordinates of the target: {TARGET} is at row={ROW}, col={COL}. Otherwise, you should report {TARGET} is not in grid.

Here is the output for the example input above:

7 is at row=1, col=0
12 is not in the grid

Note: The ROW and COL numbers start with 0.

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa18-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge03               # Create and checkout challenge03 branch

$ $EDITOR challenge03/program.cpp           # Edit your code

$ git add challenge03/program.cpp           # Stage your changes
$ git commit -m "challenge03: done"         # Commit your changes

$ git push -u origin challenge03            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge03 assignment ...
Submitting challenge03 code ...
  Result Success
   Score 6.00

$ curl -F source=@challenge03/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa18/challenge03
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, remember to create a merge request. Refer to the Reading 02 TA List to determine your corresponding TA for the merge request.