Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# USACO Transform Puzzle

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```// 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

#include

#include

#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;
}

``````
Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.