Checking for 2D Array Rotations + Reflections

[Hyerim Yoon]

(This is an unofficial USACO Bronze problem that I have been working on for a few days--it is not a homework problem.)

I have created a code that will classify a 2D array rotation / reflection into one of these categories ->

#1: The arrangement is rotated 90 degrees clockwise.

#2: The arrangement is rotated 180 degrees clockwise.

#3: The arrangement is rotated 270 degrees clockwise.

#4: The arrangement is reflected horizontally (see the sample input).

#5: The arrangement is reflected horizontally and then one of actions #1 to #3 is performed.

#6: No change.

#7: None of the above.

Unfortunately, some of the test cases I have inputted are giving me the wrong answers. Will anyone please help me understand what I did wrong in my code?

The first line of any input contains a single integer 'N'. The next N lines contain a string of N characters that represent the original arrangement of the array. The final N lines each contain a string of N characters that represent the rearrangement of the array.

For example, the input below is supposed to give me '5' ->

5
-@@@-
-@@--
-@---
-----
-----
-----
----@
---@@
--@@@
-----
but my current code is giving me '3'.

The input below is supposed to give me '1' ->

6
-@-@-@
@-@-@-
-@-@-@
@-@-@-
-@-@-@
@-@-@-
@-@-@-
-@-@-@
@-@-@-
-@-@-@
@-@-@-
-@-@-@
but my code is currently giving me 5.

Here is my full code, annotated with some of the comments I have made ->

# include <iostream>
using namespace std;

// Strategy -> 
// 1. Go over all the possible solutions IN ORDER + stop at the one that corresponds to the current input 
// 2. Print out the number of the solution 

int main() {
    char a[10][10]; 
    char b[10][10];

    char input; 
    int N, output = 7; 
    cin >> N; 

    // Take in the inputs for the original grid 
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            cin >> input; 
            a[i][j] = input; 
        }
    }

    // Take in the inputs for the changed grid 
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            cin >> input; 
            b[i][j] = input; 
        }
    }

    // The output variable is originally set to "none of the above" (number 7)
    // Go through all of the "if" statements below to see if the grids match any of the other cases 

    // 1. 90 degrees clockwise 
    bool trueCase = true; 
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
           if(b[i][j] != a[N - j - 1][i]) {
               trueCase = false; 
           }
        }
    }

    if(trueCase) {
        output = 1; 
    }

    // 2. 180 degrees clockwise 
    trueCase = true; 
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            if(b[i][j] != a[N - 1 - i][N - 1 - j]) {
                trueCase = false; 
            }
        }
    }

    if(trueCase) {
        output = 2; 
    }

    // 3. 270 degrees clockwise
    trueCase = true; 
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            if(b[i][j] != a[N - j - 1][N - i - 1]) {
                trueCase = false; 
            }
        }
    }

    if(trueCase) {
        output = 3; 
    } 

    // 4. Reflected horizontally
    trueCase = true; 
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            if(b[i][j] != a[i][N - j - 1]) {
                trueCase = false; 
            }
        }
    }

    // If there is horizontal reflection + one of the actions #1 to #3 is performed, set "output" to 5 
    // If there is just a horizontal reflection and nothing more, set "output" to 4 

    if(trueCase && (output == 1 || output == 2 || output == 3)) {
        output = 5; 
    } else if (trueCase) {
        output = 4; 
    }

    // 6. No change
    trueCase = true; 
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            if(b[i][j] != a[i][j]) {
                trueCase = false; 
            }
        }
    }

    if(trueCase) {
        output = 6; 
    }

    cout << output << endl; 

    return 0; 
}

[salem c]

Well the problem is your code bumbles through all the cases, and doesn't stop (as it should) after the first matching case.

You'd do a lot better if you had half a dozen functions called things like
- inputGrid (you'd call this twice)
- check90
- check180
- check270
etc

Your main would end up being about 10 lines long, and a lot easier to see where your logic breaks.

[seeplus]

There may be an issue with case 4 - reflected horizontally. What testing has been done for each of the cases 1 - 4?

What debugging of the program has been done? Where does the execution of the program deviate from that expected from the program design?

[lastchance]

Your test for case 3 is wrong.

Your test for case 5 is disastrous.

Your model answer for the second case could in principle be 4 (reflection). Depends on the order of testing. In fact, you could answer any of 1-6 for the following input:

2
@@
@@
@@
@@

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

using matrix = vector<string>;

//==========================================================

matrix quarterTurn( const matrix &M )
{
   int N = M.size();
   matrix R( N, string( N, ' ' ) );
   for ( int i = 0; i < N; i++ )
      for ( int j = 0; j < N; j++ ) R[i][j] = M[N-1-j][i];
   return R;
}

//==========================================================

matrix reflect( const matrix &M )
{
   matrix R = M;
   for ( string &s : R ) reverse( s.begin(), s.end() );
   return R;
}

//==========================================================

ostream & operator << ( ostream &out, const matrix &M )
{
   for ( string s : M ) out << s << '\n';
   return out;
}

//==========================================================

int test( const matrix &M, const matrix &R )
{
   // Taken in order (1-6). In some cases, multiple answers are possible

   matrix Q = quarterTurn( M );   if ( R == Q ) return 1;
          Q = quarterTurn( Q );   if ( R == Q ) return 2;
          Q = quarterTurn( Q );   if ( R == Q ) return 3;

   matrix H = reflect( M );       if ( R == H ) return 4;

          Q = quarterTurn( H );   if ( R == Q ) return 5;
          Q = quarterTurn( Q );   if ( R == Q ) return 5;
          Q = quarterTurn( Q );   if ( R == Q ) return 5;

                                  if ( R == M ) return 6;

   return 7;
}

//==========================================================

int main()
{
// istream &in = cin;
   istringstream in( "5    \n"
                     "-@@@-\n"
                     "-@@--\n"
                     "-@---\n"
                     "-----\n"
                     "-----\n"
                     "-----\n"
                     "----@\n"
                     "---@@\n"
                     "--@@@\n"
                     "-----\n" );

   int N;
   in >> N;
   matrix M( N ), R( N );
   for ( int i = 0; i < N; i++ ) in >> M[i];
   for ( int i = 0; i < N; i++ ) in >> R[i];

// cout << M << "\n\n" << R << "\n\n" << quarterTurn( reflect( M ) ) << '\n';

   cout << test( M, R ) << '\n';
}