Problem involves a grid of N x N, and has a certain number of thieves and robbers. Count how many thieves are caught

Question

The question is to have Cops and Robbers on a grid N x N. One cop can catch only 1 robber, and only if he is within the same row, and the distance between them should be less than s. My idea was to take each row, and check if a cop can catch. Once that happens I'll break, and move on to the next row. I don't know what is going wrong.

Edit : I realized I had not considered the existence of multiple police officers and thieves in the same row. I also should add that I did not get any compile errors. Only the output is wrong. And I don't know any other language except C. I have been coding only for a few months.

#include <stdio.h>

    int main ()
        {
            int test, n, s ;

            printf ("Type the number of test cases, size, and separation limit of Cop and Robber, separated by space.\n") ;
            scanf ("%d %d %d", &test, &n, &s) ;

            char grid [n][n] ;

            for (int i = 0 ; i < test ; i ++)
                {
                    printf ("Start filling the grid. Type P for Cop and T for Robber.\n") ;

                    for (int j = 0 ; j < n ; j ++)
                        for (int k = 0 ; k < n ; k ++)
                            scanf ("%1c", &grid [j][k]) ;

                    int check = 0, result = 0 ;

                    for (int j = 0 ; j < n ; j ++)
                        for (int k = 0 ; k < n ; k ++)
                            {
                                for (int l = k + 1 ; (l - k <= s) && (l < n) ; l ++)
                                    {
                                        if ((grid [j][k] == 'p' && grid [j][l] == 't') || (grid [j][k] == 't' && grid [j][l] == 'p'))
                                            {
                                                result ++ ;
                                                check ++ ;
                                                break ;
                                            }
                                    }

                                check = 0 ;
                                break ;
                            }

                    printf ("The number of robbers caught is : %d\n", result) ;
                }
        }

The problem is not clearly expressed. In light of the limitation that no cop can catch more than one robber, the question of "how many thieves *are* caught" requires an additional specification of how cops choose which robber to catch. That affects the answer for some board layouts. But perhaps the question is really more like "what is the *maximum* number of robbers that can be caught?" — John Bollinger, Dec 13 '20 at 14:45

score 1 · Answer 1 · answered Dec 13 '20 at 12:47

Here is how I seem to have worked out the problem, i could have helped you specifically if you could have mentioned the error you got while executing the code, anyways , here's the algorithm I used:

Get the lowest index of policeman p and thief t. Make an allotment if |p-t| <= k and increment to the next p and t found.
Otherwise increment min(p, t) to the next p or t found.
Repeat above two steps until next p and t are found.
Return the number of allotments made.

It uses vectors to store the indices of police and thief in the array and processes them.

As far as the code goes:

#include <iostream> 
#include <vector> 
#include <cmath> 
  
using namespace std; 
  
// Returns maximum number of thieves that can 
// be caught. 
int policeThief(char arr[], int n, int k) 
{ 
    int res = 0; 
    vector<int> thi; 
    vector<int> pol; 
  
    // store indices in the vector 
    for (int i = 0; i < n; i++) { 
        if (arr[i] == 'P') 
            pol.push_back(i); 
        else if (arr[i] == 'T') 
            thi.push_back(i); 
    }    
  
    // track lowest current indices of 
    // thief: thi[l], police: pol[r] 
    int l = 0, r = 0; 
    while (l < thi.size() && r < pol.size()) { 
  
        // can be caught 
        if (abs(thi[l] - pol[r]) <= k) { 
            res++; 
            l++; 
            r++; 
        } 
  
        // increment the minimum index 
        else if (thi[l] < pol[r]) 
            l++; 
        else
            r++; 
    } 
  
    return res; 
}

Above is the implementation of the algorithm.

Below is the code used to test:

int main() 
{ 
    int k, n; 
  
    char arr1[] = { 'P', 'T', 'T', 'P', 'T' }; 
    k = 2; 
    n = sizeof(arr1) / sizeof(arr1[0]); 
    cout << "Maximum thieves caught: "
         << policeThief(arr1, n, k) << endl; 
  
    char arr2[] = { 'T', 'T', 'P', 'P', 'T', 'P' }; 
    k = 2; 
    n = sizeof(arr2) / sizeof(arr2[0]); 
    cout << "Maximum thieves caught: "
         << policeThief(arr2, n, k) << endl; 
  
  
    return 0; 
}

I get the following output based on the above test cases:

Upvote if it helped!

That's a very long and in-depth C++ answer...unfortunately to a C question. — tadman, Dec 13 '20 at 13:04
It was best for me to keep the spirit of the problem solved alive. The algorithm remains the same irrespective of the language used and one could be encouraged enough to solve it again in their preferred language referring the answer here rather than directly copy-pasting the code if I had written in C :) — aryashah2k, Dec 13 '20 at 13:08

anotherOne · Answer 2 · 2020-12-13T14:34:42.990

I've run the code only in my head, so I am not granting to solve your problems.

The first thing I noticed is this small thing of putting spaces between %d in scanf. You can safely do

scanf ("%d%d%d", &test, &n, &s) ;

What is the effect of trailing white space in a scanf() format string?

Now coming to your problems, there was a logic error in your loops. Fixed by: grid[j][l] = 'x';. I also added some improvement

for (int j = 0; j < n; j++) {

    for (int k = 0; k < n; k++) {
        
        if ( grid[j][k] == 'p' || grid[j][k] == 't' ) {
            
            for (int l = k +1; (l <= k + s) && (l < n); l++) {
                
                if ( (grid[j][l] == 'p' || grid[j][l] == 't') && grid[j][l] != grid[j][k] ) {
                    
                    ++result;
                    grid[j][l] = 'x';
                    break;
                }
              /*else if( l == n - 1 ) {
                    
                    k = n;*/
                }
            }
        }
    }
}

The else if() breaks the loop for(int k... when you already know that there are no more cops and robbers to match in the current row. I guess it is an improvement only if s is at least one third of n or even a bit less than that.

John Bollinger · Accepted Answer · 2020-12-13T15:45:31.337

I realized I had not considered the existence of multiple police officers and thieves in the same row.

Before talking about the algorithm, some comments about code style:

It's hard for me to overemphasize the importance of choosing meaningful names for your variables. The few extra moments it takes to type longer names pays off time and again in clarifying the meaning of the code and avoiding mixups.
I urge you to make a practice of always using code blocks for the bodies of of for, while, do, if, and else statements, even when the block contains only one statement, except else statements whose bodies are single if statements. It is very easy to introduce errors into code that does otherwise, and such mistakes have led to high-profile bugs, such as the goto fail in Apple's SSL library.
Although it is a common convention to put spaces around operators, it is very uncommon to extend that to separating indexing operators ([x]) from the expressions to which they apply. Doing so makes your code harder for most people to read. Similar applies to array declarations.

Additionally, do note that the number of thieves caught depends on the strategy the cops employ to choose which thief to catch. For example, consider this board with N = 5 and s = 2:

t_ptp
_____
_____
_____
_____

If each police officer chooses to catch the closest uncaught thief, and they make their choices from left to right, then the officer in the third column will choose first, selecting the thief next to him on his right. The officer in the last column then cannot catch any thief, because the one in the first column is too far away.

On the other hand, if the police are considered from left to right, and each one catches the left-most uncaught thief within range (who may be on either side of the officer), then the first officer will catch the first thief, and the second officer will catch the second thief.

It turns out that the latter approach in fact maximizes the number of thieves caught (proof omitted).

If your approach accounted both for thieves being caught at most once and police catching at most one thief, then it would be equivalent to the second algorithm. One pretty simple way to introduce that accounting into your code would be to remove both the police officer and the thief from the board when one captures the other (by overwriting their positions with some other character):

                                                result ++ ;
                                                grid[j][k] = ' ';
                                                grid[j][l] = ' ';
                                                break ;

Note: you never use the value of your check variable, so I omit incrementing it.

Personally, I would be inclined to write code that implements the optimal algorithm in the form I first described it, as I find that clearer, but you shouldn't need to modify your current code that much.

Okay, thanks a lot for pointing out the mistakes in the code style. And thank you very much for the algorithm too. — Espeon, Dec 13 '20 at 18:08

Problem involves a grid of N x N, and has a certain number of thieves and robbers. Count how many thieves are caught

3 Answers3