USACO TRAINING - Section 1.2 - PROB Transformations

Question

I'm trying to improve my coding skills by going through the USACO TRAINING PROGRAM. I would like a review of my code for solving the transform problem.

Here is the problem statement:

A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:

• 1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.
• 2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.
• 3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.
• 4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).
• 5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).
• 6: No Change: The original pattern was not changed.
• 7: Invalid Transformation: The new pattern was not obtained by any of the above methods.

In the case that more than one transform could have been used, choose the one with the minimum number above.

INPUT FORMAT

Line 1: A single integer, N Line 2..N+1: N lines of N characters (each either '@' or '-'); this is the square before transformation Line N+2..2*N+1: N lines of N characters (each either '@' or '-'); this is the square after transformation

OUTPUT FORMAT

A single line containing the the number from 1 through 7 (described above) that categorizes the transformation required to change from the 'before' representation to the 'after' representation.

Here is my code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char *rotation( const char *square, char *transformed, int N, int quartersOfCircle );
char *reflection( const char *square, char *transformed, int N );
char *combination( const char *square, char *transformed, int N, int quartersOfCirle );

int main(void){

    FILE *fin = fopen("transform.in", "r");
    FILE *fout = fopen("transform.out", "w");
    char *square, *transformed, *memSpace;
    int N, transfId, i;

    fscanf(fin, "%d", &N);
    square = malloc( N*N * sizeof(char) );
    transformed = malloc( N*N * sizeof(char) );
    memSpace = malloc( N*N * sizeof(char) );

    for( i=0; i<N; i++ ){
        fscanf(fin, "%s", square+N*i);
    }
    for( i=0; i<N; i++ ){
        fscanf(fin, "%s", transformed+N*i);
    }

    if( strncmp( rotation(square, memSpace, N, 1), transformed, N*N) == 0 ) 
        transfId=1;
    else if( strncmp( rotation(square, memSpace, N, 2), transformed, N*N) == 0 ) 
        transfId=2;
    else if( strncmp( rotation(square, memSpace, N, 3), transformed, N*N) == 0 ) 
        transfId=3;
    else if( strncmp( reflection(square, memSpace, N ), transformed, N*N) == 0 ) 
        transfId=4;
    else if( strncmp( combination(square, memSpace, N, 1 ), transformed, N*N) == 0 
          || strncmp( combination(square, memSpace, N, 2 ), transformed, N*N) == 0 
          || strncmp( combination(square, memSpace, N, 3 ), transformed, N*N) == 0 ) 
        transfId=5;
    else if( strncmp(square, transformed, N*N) == 0 ) 
        transfId=6;
    else 
        transfId=7;

    fprintf(fout, "%d\n", transfId);

    return 0; 
}


char *rotation( const char *square, char *memSpace, int N, int quartersOfCircle ){
    int i, j;   
    switch( quartersOfCircle ){
        case 1:
            for(i=0; i<N; i++){
                for(j=0; j<N; j++){
                    *(memSpace + (N - 1 - i) + j*N ) = *(square + i*N + j);
                }
            }
            break;
        case 2:
            for(i=0; i<N; i++){
                for(j=0; j<N; j++){
                    *(memSpace + (N - 1 - i)*N + (N - 1 - j) ) = *(square + i*N + j);
                }
            }
            break;
        case 3:
            for(i=0; i<N; i++){
                for(j=0; j<N; j++){
                    *(memSpace + i + (N - 1 - j)*N ) = *(square + i*N + j);
                }
            }
            break;
        default:
            return NULL;
    }
    return memSpace;
}


char *reflection( const char *square, char *memSpace, int N ){
    int i, j;
    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            *(memSpace + i*N + (N - 1 - j) ) = *(square + i*N + j);
        }
    }
    return memSpace;
}


char *combination( const char *square, char *memSpace, int N, int quartersOfCirle ){

    char *memSpace2 = malloc( N*N * sizeof(char) );
    memSpace2 = rotation( square, memSpace2, N, quartersOfCirle );
    memSpace = reflection( memSpace2, memSpace, N );
    free(memSpace2);

    return memSpace;
}

From an algorithmic point of view, my solution is equivalent to the official one, but I didn't notice that an upper bound on \$N\$ was assumed, so I didn't use arrays.

Answer 1

1. scanf will automatically append a null termination character when using %s so your last read will go over the end of the buffer by 1 causing undefined behaviour. Given how the input is provided the easiest would be to simply allocate one additional byte at the end of each input buffer.

2. sizeof(char) is guaranteed by the C standard to always be 1. However to make the code more robust against type changes you should reference the variable you want to allocate like this:

   square = malloc(N * N + 1, sizeof(*square)); // +1 for the trailing '\0'
   

   Now should the element type of square ever change you don't have to remember to also update all the malloc calls. This SO answer has the details of why this works.

3. You do no free the memory allocated for square, transform and memSpace. Technically this is not a problem since the program is very straight forward and the memory will be released automatically when the process ends but it is a good habit to always clean up after yourself.

4. Since it's not explicitly mentioned I would by default read from stdin and write to stdout. This is way more flexible and much more in the spirit of the unix tools than to require files on the filesystem for input and output.

5. C traditionally uses snake_case naming convention. So mem_space instead of memSpace and transf_id instead of transfId.

6. memSpace is not named very descriptively. scratch_memory or scratch_pad makes the purpose immediately clear.

7. Instead of transfId I would name it transform_category - this matches the terminology in the problem description and as such makes it easier to relate increasing readability.

8. You should use braces even for single line statements (like in the main if-else cascade).

9. Since the input N denotes only the side length of the square you have N * N scattered around all over the place. This is essentially an instance of copy-n-paste code (on a small scale) and should be avoided. It's easy to forget to do this which can lead to weird bugs. Plus should it ever change in some form or shape you have to change it in a lot of places. Store it in a local variable like num_elements and use that instead. You won't loose anything, gain readability and make the code a bit more DRY.

10. While i and j are perfectly acceptable as for loop indices in your particular problem domain column and row would be more appropriate and make the logic easier to follow.

11. It's often advisable to run tools like valgrind on your code to check if you have any out-of-bounds problems or memory leaks. This implies that you do clean up after yourself properly (like releasing all memory you have allocated) because otherwise you may miss the important stuff among the "expected" memory leaks.