Challenge 03: Searching the Matrix Solution

Abi and Maddy are now in kindergarten at ECDC on Notre Dame's campus. Although they are quite the animal experts1, they are still novices at math and most numerical things2. 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 Despacito3 to help them with their sadness.

Because their father disapproves of the digital assistant4, 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.


Just ask them about ham-hams or the naked mole rat. ↩
Not really, they are good at this stuff too; must have gotten it from their mom. ↩
Heard the accordion version everyday in Rome. Amazing. ↩
Finally some truth. ↩