DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Roger has posted 34 posts at DZone. View Full User Profile

USACO Transform Puzzle

11.10.2008
| 1435 views |
  • submit to reddit
        // Solution to the USACO Tranform Algorithmic puzzle. Apologies to anyone who objects to my posting
// entire solutions -- I need a record of the techniques I used, and chopping the solution parts 
// out of the solution is too tedious. TopCoder routinely offers users' past solutions. And 
// anyone who needs to use my code to cheat their way through USACO should really get a life.
// 

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

#define NUM_TRANSFORMS      6
#define NO_MATCH            0
#define ROTATE_NINETY       1
#define ROTATE_ONE_EIGHTY   2
#define ROTATE_TWO_SEVENTY  3
#define REFLECTION          4
#define COMBINATION         5
#define UNCHANGED           6
#define INVALID_TRANSFORM   7


int rotateNinety(int nSize, char inTiles[nSize][nSize+1], 
        char outTiles[nSize][nSize+1]) {
    int x, y, j, i, retval = ROTATE_NINETY;
    char test[nSize][nSize+1]; 
    memset(test, 0, sizeof test);
    for (x=nSize, i=0; x > 0; --x, ++i) {
        for (y=0, j=nSize; y < nSize; ++y, --j) {
            test[i][y] = inTiles[j-1][i]; 
        }
    }
    
    for (x=0; x < nSize; ++x) {
        if (strcmp(test[x], outTiles[x]) != 0) {
            retval = NO_MATCH;
            break;
        }
    }
    
    return retval;    
}

int rotateOneEighty(int nSize, char inTiles[nSize][nSize+1], 
        char outTiles[nSize][nSize+1]) {
    int x, y, i, j, retval = ROTATE_ONE_EIGHTY;
    char test[nSize][nSize+1]; 
    memset(test, 0, sizeof test);
    for (x=nSize, j=0; x > 0; --x, ++j) {
        for (y=nSize, i=0; y > 0; --y, ++i) {
            test[j][i] = inTiles[x-1][y-1]; 
        }
    }
    
    for (x=0; x < nSize; ++x) {
        if (strcmp(test[x], outTiles[x]) != 0) {
            retval = NO_MATCH;
            break;
        }
    }
    
    return retval;
}

int rotateTwoSeventy(int nSize, char inTiles[nSize][nSize+1], 
        char outTiles[nSize][nSize+1]) {
    int x, y, j, retval = ROTATE_TWO_SEVENTY;
    char test[nSize][nSize+1]; 
    memset(test, 0, sizeof test);
    for (x=nSize, j=0; x > 0; --x,++j) {
        for (y=0; y < nSize; ++y) {
            test[j][y] = inTiles[y][x-1]; 
        }
    }
    
    for (x=0; x < nSize; ++x) {
        if (strcmp(test[x], outTiles[x]) != 0) {
            retval = NO_MATCH;
            break;
        }
    }
    
    return retval;
}

int reflect(int nSize, char inTiles[nSize][nSize+1], 
        char outTiles[nSize][nSize+1]) {
    int x, y, i, retval = REFLECTION;
    char test[nSize][nSize+1]; 
    memset(test, 0, sizeof test);
    for (x=0; x < nSize; ++x) {
        for (y=nSize, i=0; y > 0; --y, ++i) {
            test[x][i] = inTiles[x][y-1]; 
        }
    }
    
    for (x=0; x < nSize; ++x) {
        if (strcmp(test[x], outTiles[x]) != 0) {
            retval = NO_MATCH;
            break;
        }
    }
    
    return retval;
}

/* The pattern was reflected horizontally and then
 * subjected to one of the rotations (90, 180, 270) 
 */
int combination(int nSize, char inTiles[nSize][nSize+1], 
        char outTiles[nSize][nSize+1]) {
    int x, y, i, retval = COMBINATION;
    char test[nSize][nSize+1]; 
    memset(test, 0, sizeof test);
    for (x=0; x < nSize; ++x) {
        for (y=nSize, i=0; y > 0; --y, ++i) {
            test[x][i] = inTiles[x][y-1]; 
        }
    }
    
    if (rotateNinety(nSize, test, outTiles) == ROTATE_NINETY) return retval;
    if (rotateOneEighty(nSize, test, outTiles) == ROTATE_ONE_EIGHTY) return retval;
    if (rotateTwoSeventy(nSize, test, outTiles) == ROTATE_TWO_SEVENTY) return retval;

    return NO_MATCH;
}

int noChange(int nSize, char inTiles[nSize][nSize+1], 
        char outTiles[nSize][nSize+1]) {
    int x, retval = UNCHANGED;
    for (x=0; x < nSize; ++x) {
        if (strcmp(inTiles[x], outTiles[x]) != 0) {
            retval = NO_MATCH;
            break;
        }
    }

    return retval;
}

int main(void) {
    FILE *fin, *fout;
    int nSize, x, result = NO_MATCH;
    
    fin = fopen("transform.in", "r");
    fout = fopen("transform.out", "w");
    fscanf(fin, "%d", &nSize);
    
    char inTiles[nSize][nSize+1], outTiles[nSize][nSize+1];
    for (x=0; x < nSize; ++x) {
        fscanf(fin, "%s", inTiles[x]);
    }
    for (x=0; x < nSize; ++x) {
        fscanf(fin, "%s", outTiles[x]);
    }
    
    /* There's a much cooler way to do the following with function pointers.
     * but alas, the USACO implementation of gcc refused to compile them. 
     * Here's the pointer-function way to do the following lines:
     */
    
    /*
    functptr transforms[NUM_TRANSFORMS];
    memset(transforms, 0, sizeof transforms);
    transforms[0] = &noChange;
    transforms[1] = &rotateNinety;
    transforms[2] = &rotateOneEighty;
    transforms[3] = &rotateTwoSeventy;
    transforms[4] = &reflect;
    transforms[5] = &combination;
    
    int z = 0;
    while (result == NO_MATCH) {
        result = (*transforms[z++])(nSize, inTiles, outTiles);
    }
    */
    
    if ((result = rotateNinety(nSize, inTiles, outTiles)) != NO_MATCH) {
        fprintf(fout, "%d\n", result);
        return EXIT_SUCCESS;
    }
    if ((result = rotateOneEighty(nSize, inTiles, outTiles)) != NO_MATCH) {
        fprintf(fout, "%d\n", result);
        return EXIT_SUCCESS;
    }
    if ((result = rotateTwoSeventy(nSize, inTiles, outTiles)) != NO_MATCH) {
        fprintf(fout, "%d\n", result);
        return EXIT_SUCCESS;
    }
    if ((result = reflect(nSize, inTiles, outTiles)) != NO_MATCH) {
        fprintf(fout, "%d\n", result);
        return EXIT_SUCCESS;
    }
    if ((result = combination(nSize, inTiles, outTiles)) != NO_MATCH) {
        fprintf(fout, "%d\n", result);
        return EXIT_SUCCESS;
    }
    if ((result = noChange(nSize, inTiles, outTiles)) != NO_MATCH) {
        fprintf(fout, "%d\n", result);
        return EXIT_SUCCESS;
    }
    if (result == NO_MATCH) {
        result = INVALID_TRANSFORM;
        fprintf(fout, "%d\n", result);
    }
    

	return EXIT_SUCCESS;
}