Spatial Concepts Test

From Progteam

Revision as of 22:12, 7 March 2008 by Kerry (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


Spatial Concepts Test
Problem Number 0000
Sorter: Uncategorized
Source: GNYR ICPC 2007
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=0000



This is problem I from the GNYR programming contest at Kean University. This problem is not yet on the Peking site See problem specs here [[1]]

You can submit this here:[[2]].

Current Method, probably stupid: 24 cases- 1 for each possible corner view. Each case gives the translation of each faces' numbering system from the input numbering to the corner view numbering.

Translate input into flat square numbers. ex B3C1A2B4A3E1: B3-> 1,3; C1->2,1...E1->6,1.

Read corner views, and check for a given corner existing without regard to orientation. Check all possibilites (redundant use of symbols). If no corner, then N. If yes corner, then check orientation.

Check orientation by translating the input orientation number to corner number. Just hard code each translation. (I think this translation is the weak point of the algorithm. If you can think a better method, please comment here)

I'll try to get some code up on Mon or Tues.

Here's my code at last. Still gets Wrong Answer, so help appreciated. I know the style is poor, but it was my first C project in a long time.

-Kerry

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

struct face {
	char symbol;
	int flat_orientation;
};

char *transform_faces(struct face *cube, char corners[24][7]);


int main() {

struct face cube[8];
char corners[24][7];
int a, b, i, j, k, tot;
char *answer;
int possible[5]={0};

	answer=(char *)malloc(sizeof(char)*8);
	scanf("%d\n", &a);
	i = 0;
	while (i < a) {
		tot=0;
		for(j=1;j<7;j++) {
			scanf("%c%d", &cube[j].symbol, &cube[j].flat_orientation);
		}
		transform_faces(cube, corners);
		for(j=0;j<5;j++){
			possible[j]=0;
			scanf("%s", answer);
			for(k=0;k<24;k++) {
				for(b=1;b<7;b+=2)
					if (corners[k][b] == '0')
						corners[k][b]='4';
				if (!strncmp(answer, &corners[k][0], 5)) {
					possible[j] = 1;
					tot++;
				}
			}
		}
		printf("%d %d", i+1, tot);
		for(j=0;j<5;j++) {
			if(possible[j]) {
				printf(" Y");
			}
			else {
				printf(" N");
			}
		}
		printf("\n");
		i++;
		while(getchar()!='\n');
		
	}
return;
}


char *transform_faces(struct face *old_cube, char corners[24][7]) {
int i,j;	
struct face cube[8];

	for(j=1;j<7;j++)
		cube[j].symbol=old_cube[j].symbol;

	for(i=0;i<24;i++) {
		for (j=1;j<7;j++)
			cube[j].flat_orientation=old_cube[j].flat_orientation;
		switch(i) {
			case 0:
			cube[1].flat_orientation = cube[1].flat_orientation + 5;
                        cube[3].flat_orientation = cube[3].flat_orientation + 0;
                        cube[2].flat_orientation = cube[2].flat_orientation + 7;
			corners[0][0] = cube[1].symbol;
			corners[0][1] = (char)(cube[1].flat_orientation % 4 + 48);
			corners[0][2] = cube[3].symbol;
			corners[0][3] = (char)(cube[3].flat_orientation % 4 + 48);
			corners[0][4] = cube[2].symbol;
			corners[0][5] = (char)(cube[2].flat_orientation % 4 + 48);
			corners[0][6] = '\0';
			break;
                        case 1:
                        cube[1].flat_orientation = cube[1].flat_orientation + 0;
                        cube[2].flat_orientation = cube[2].flat_orientation + 0;
                        cube[5].flat_orientation = cube[5].flat_orientation + 7;
                        corners[1][0] = cube[1].symbol;
                        corners[1][1] = (char)(cube[1].flat_orientation % 4 + 48);
                        corners[1][2] = cube[2].symbol;
                        corners[1][3] = (char)(cube[2].flat_orientation % 4 + 48);
                        corners[1][4] = cube[5].symbol;
                        corners[1][5] = (char)(cube[5].flat_orientation % 4 + 48);
                        corners[1][6] = '\0';
                        break;
                        case 2:
                        cube[1].flat_orientation = cube[1].flat_orientation + 7;
                        cube[5].flat_orientation = cube[5].flat_orientation + 0;
                        cube[4].flat_orientation = cube[4].flat_orientation + 7;
                        corners[2][0] = cube[1].symbol;
                        corners[2][1] = (char)(cube[1].flat_orientation % 4 + 48);
                        corners[2][2] = cube[5].symbol;
                        corners[2][3] = (char)(cube[5].flat_orientation % 4 + 48);
                        corners[2][4] = cube[4].symbol;
                        corners[2][5] = (char)(cube[4].flat_orientation % 4 + 48);
                        corners[2][6] = '\0';
                        break;
                        case 3:
                        cube[1].flat_orientation = cube[1].flat_orientation + 6;
                        cube[4].flat_orientation = cube[4].flat_orientation + 0;
                        cube[3].flat_orientation = cube[3].flat_orientation + 7;
                        corners[3][0] = cube[1].symbol;
                        corners[3][1] = (char)(cube[1].flat_orientation % 4 + 48);
                        corners[3][2] = cube[4].symbol;
                        corners[3][3] = (char)(cube[4].flat_orientation % 4 + 48);
                        corners[3][4] = cube[3].symbol;
                        corners[3][5] = (char)(cube[3].flat_orientation % 4 + 48);
                        corners[3][6] = '\0';
                        break; 

                        case 4:
                        cube[2].flat_orientation = cube[2].flat_orientation + 0;
                        cube[5].flat_orientation = cube[5].flat_orientation + 7;
                        cube[1].flat_orientation = cube[1].flat_orientation + 0;
                        corners[4][0] = cube[2].symbol;
                        corners[4][1] = (char)(cube[2].flat_orientation % 4 + 48);
                        corners[4][2] = cube[5].symbol;
                        corners[4][3] = (char)(cube[5].flat_orientation % 4 + 48);
                        corners[4][4] = cube[1].symbol;
                        corners[4][5] = (char)(cube[1].flat_orientation % 4 + 48);
                        corners[4][6] = '\0';
                        break;
                        case 5:
                        cube[2].flat_orientation = cube[2].flat_orientation + 7;
                        cube[1].flat_orientation = cube[1].flat_orientation + 5;
                        cube[3].flat_orientation = cube[3].flat_orientation + 0;
                        corners[5][0] = cube[2].symbol;
                        corners[5][1]= (char)(cube[2].flat_orientation % 4 + 48);
                        corners[5][2]= cube[1].symbol;
                        corners[5][3]= (char)(cube[1].flat_orientation % 4 + 48);
                        corners[5][4]= cube[3].symbol;
                        corners[5][5]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[5][6]= '\0';
                        break;
                        case 6:
                        cube[2].flat_orientation = cube[2].flat_orientation + 6;
                        cube[3].flat_orientation = cube[3].flat_orientation + 5;
                        cube[6].flat_orientation = cube[6].flat_orientation + 0;
                        corners[6][0] = cube[2].symbol;
                        corners[6][1]= (char)(cube[2].flat_orientation % 4 + 48);
                        corners[6][2]= cube[3].symbol;
                        corners[6][3]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[6][4]= cube[6].symbol;
                        corners[6][5]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[6][6]= '\0';
                        break;
                        case 7:
                        cube[2].flat_orientation = cube[2].flat_orientation + 5;
                        cube[6].flat_orientation = cube[6].flat_orientation + 5;
                        cube[5].flat_orientation = cube[5].flat_orientation + 6;
                        corners[7][0] = cube[2].symbol;
                        corners[7][1]= (char)(cube[2].flat_orientation % 4 + 48);
                        corners[7][2]= cube[6].symbol;
                        corners[7][3]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[7][4]= cube[5].symbol;
                        corners[7][5]= (char)(cube[5].flat_orientation % 4 + 48);
                        corners[7][6]= '\0';
                        break;
                        case 8:
                        cube[3].flat_orientation = cube[3].flat_orientation + 0;
                        cube[2].flat_orientation = cube[2].flat_orientation + 7;
                        cube[1].flat_orientation = cube[1].flat_orientation + 5;
                        corners[8][0] = cube[3].symbol;
                        corners[8][1]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[8][2]= cube[2].symbol;
                        corners[8][3]= (char)(cube[2].flat_orientation % 4 + 48);
                        corners[8][4]= cube[1].symbol;
                        corners[8][5]= (char)(cube[1].flat_orientation % 4 + 48);
                        corners[8][6]= '\0';
                        break;
                        case 9:
                        cube[3].flat_orientation = cube[3].flat_orientation + 7;
                        cube[1].flat_orientation = cube[1].flat_orientation + 6;
                        cube[4].flat_orientation = cube[4].flat_orientation + 0;
                        corners[9][0] = cube[3].symbol;
                        corners[9][1]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[9][2]= cube[1].symbol;
                        corners[9][3]= (char)(cube[1].flat_orientation % 4 + 48);
                        corners[9][4]= cube[4].symbol;
                        corners[9][5]= (char)(cube[4].flat_orientation % 4 + 48);
                        corners[9][6]= '\0';
                        break;
                        case 10:
                        cube[3].flat_orientation = cube[3].flat_orientation + 6;
                        cube[4].flat_orientation = cube[4].flat_orientation + 5;
                        cube[6].flat_orientation = cube[6].flat_orientation + 7;
                        corners[10][0] = cube[3].symbol;
                        corners[10][1]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[10][2]= cube[4].symbol;
                        corners[10][3]= (char)(cube[4].flat_orientation % 4 + 48);
                        corners[10][4]= cube[6].symbol;
                        corners[10][5]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[10][6]= '\0';
                        break;
                        case 11:
                        cube[3].flat_orientation = cube[3].flat_orientation + 5;
                        cube[6].flat_orientation = cube[6].flat_orientation + 0;
                        cube[2].flat_orientation = cube[2].flat_orientation + 6;
                        corners[11][0]= cube[3].symbol;
                        corners[11][1]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[11][2]= cube[6].symbol;
                        corners[11][3]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[11][4]= cube[2].symbol;
                        corners[11][5]= (char)(cube[2].flat_orientation % 4 + 48);
                        corners[11][6]= '\0';
                        break;
                        case 12:
                        cube[4].flat_orientation = cube[4].flat_orientation + 0;
                        cube[3].flat_orientation = cube[3].flat_orientation + 7;
                        cube[1].flat_orientation = cube[1].flat_orientation + 6;
                        corners[12][0] = cube[4].symbol;
                        corners[12][1]= (char)(cube[4].flat_orientation % 4 + 48);
                        corners[12][2]= cube[3].symbol;
                        corners[12][3]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[12][4]= cube[1].symbol;
                        corners[12][5]= (char)(cube[1].flat_orientation % 4 + 48);
                        corners[12][6]= '\0';
                        break;
                        case 13:
                        cube[4].flat_orientation = cube[4].flat_orientation + 7;
                        cube[1].flat_orientation = cube[1].flat_orientation + 7;
                        cube[5].flat_orientation = cube[5].flat_orientation + 0;
                        corners[13][0] = cube[4].symbol;
                        corners[13][1]  = (char)(cube[4].flat_orientation % 4 + 48);
                        corners[13][2] = cube[1].symbol;
                        corners[13][3] = (char)(cube[1].flat_orientation % 4 + 48);
                        corners[13][4] = cube[5].symbol;
                        corners[13][5] = (char)(cube[5].flat_orientation % 4 + 48);
                        corners[13][6] = '\0';
                        break;
                        case 14:
                        cube[4].flat_orientation = cube[4].flat_orientation + 6;
                        cube[5].flat_orientation = cube[5].flat_orientation + 5;
                        cube[6].flat_orientation = cube[6].flat_orientation + 6;
                        corners[14][0] = cube[4].symbol;
                        corners[14][1] = (char)(cube[4].flat_orientation % 4 + 48);
                        corners[14][2] = cube[5].symbol;
                        corners[14][3] = (char)(cube[5].flat_orientation % 4 + 48);
                        corners[14][4] = cube[6].symbol;
                        corners[14][5] = (char)(cube[6].flat_orientation % 4 + 48);
                        corners[14][6] = '\0';
                        break;
                        case 15:
                        cube[4].flat_orientation = cube[4].flat_orientation + 5;
                        cube[6].flat_orientation = cube[6].flat_orientation + 7;
                        cube[3].flat_orientation = cube[3].flat_orientation + 6;
                        corners[15][0] = cube[4].symbol;
                        corners[15][1] = (char)(cube[4].flat_orientation % 4 + 48);
                        corners[15][2] = cube[6].symbol;
                        corners[15][3] = (char)(cube[6].flat_orientation % 4 + 48);
                        corners[15][4]= cube[3].symbol;
                        corners[15][5]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[15][6]= '\0';
                        break;
                        case 16:
                        cube[5].flat_orientation = cube[5].flat_orientation + 0;
                        cube[4].flat_orientation = cube[4].flat_orientation + 7;
                        cube[1].flat_orientation = cube[1].flat_orientation + 7;
                        corners[16][0] = cube[5].symbol;
                        corners[16][1]= (char)(cube[5].flat_orientation % 4 + 48);
                        corners[16][2]= cube[4].symbol;
                        corners[16][3]= (char)(cube[4].flat_orientation % 4 + 48);
                        corners[16][4]= cube[1].symbol;
                        corners[16][5]= (char)(cube[1].flat_orientation % 4 + 48);
                        corners[16][6]= '\0';
                        break;
                        case 17:
                        cube[5].flat_orientation = cube[5].flat_orientation + 7;
                        cube[1].flat_orientation = cube[1].flat_orientation + 0;
                        cube[2].flat_orientation = cube[2].flat_orientation + 0;
                        corners[17][0] = cube[5].symbol;
                        corners[17][1]= (char)(cube[5].flat_orientation % 4 + 48);
                        corners[17][2]= cube[1].symbol;
                        corners[17][3]= (char)(cube[1].flat_orientation % 4 + 48);
                        corners[17][4]= cube[2].symbol;
                        corners[17][5]= (char)(cube[2].flat_orientation % 4 + 48);
                        corners[17][6]= '\0';
                        break;
                        case 18:
                        cube[5].flat_orientation = cube[5].flat_orientation + 6;
                        cube[2].flat_orientation = cube[2].flat_orientation + 5;
                        cube[6].flat_orientation = cube[6].flat_orientation + 5;
                        corners[18][0] = cube[5].symbol;
                        corners[18][1]= (char)(cube[5].flat_orientation % 4 + 48);
                        corners[18][2]= cube[2].symbol;
                        corners[18][3]= (char)(cube[2].flat_orientation % 4 + 48);
                        corners[18][4]= cube[6].symbol;
                        corners[18][5]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[18][6]= '\0';
                        break;
                        case 19:
                        cube[5].flat_orientation = cube[5].flat_orientation + 5;
                        cube[6].flat_orientation = cube[6].flat_orientation + 6;
                        cube[4].flat_orientation = cube[4].flat_orientation + 6;
                        corners[19][0] = cube[5].symbol;
                        corners[19][1]= (char)(cube[5].flat_orientation % 4 + 48);
                        corners[19][2]= cube[6].symbol;
                        corners[19][3]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[19][4]= cube[4].symbol;
                        corners[19][5]= (char)(cube[4].flat_orientation % 4 + 48);
                        corners[19][6]= '\0';
                        break;
                        case 20:
                        cube[6].flat_orientation = cube[6].flat_orientation + 0;
                        cube[2].flat_orientation = cube[2].flat_orientation + 6;
                        cube[3].flat_orientation = cube[3].flat_orientation + 5;
                        corners[20][0] = cube[6].symbol;
                        corners[20][1]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[20][2]= cube[2].symbol;
                        corners[20][3]= (char)(cube[2].flat_orientation % 4 + 48);
                        corners[20][4]= cube[3].symbol;
                        corners[20][5]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[20][6]= '\0';
                        break;
                        case 21:
                        cube[6].flat_orientation = cube[6].flat_orientation + 7;
                        cube[3].flat_orientation = cube[3].flat_orientation + 6;
                        cube[4].flat_orientation = cube[4].flat_orientation + 5;
                        corners[21][0] = cube[6].symbol;
                        corners[21][1]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[21][2]= cube[3].symbol;
                        corners[21][3]= (char)(cube[3].flat_orientation % 4 + 48);
                        corners[21][4]= cube[4].symbol;
                        corners[21][5]= (char)(cube[4].flat_orientation % 4 + 48);
                        corners[21][6]= '\0';
                        break;
                        case 22:
                        cube[6].flat_orientation = cube[6].flat_orientation + 6;
                        cube[4].flat_orientation = cube[4].flat_orientation + 6;
                        cube[5].flat_orientation = cube[5].flat_orientation + 5;
                        corners[22][0] = cube[6].symbol;
                        corners[22][1]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[22][2]= cube[4].symbol;
                        corners[22][3]= (char)(cube[4].flat_orientation % 4 + 48);
                        corners[22][4]= cube[5].symbol;
                        corners[22][5]= (char)(cube[5].flat_orientation % 4 + 48);
                        corners[22][6]= '\0';
                        break;
                        case 23:
                        cube[6].flat_orientation = cube[6].flat_orientation + 5;
                        cube[5].flat_orientation = cube[5].flat_orientation + 6;
                        cube[2].flat_orientation = cube[2].flat_orientation + 5;
                        corners[23][0] = cube[6].symbol;
                        corners[23][1]= (char)(cube[6].flat_orientation % 4 + 48);
                        corners[23][2]= cube[5].symbol;
                        corners[23][3]= (char)(cube[5].flat_orientation % 4 + 48);
                        corners[23][4]= cube[2].symbol;
                        corners[23][5]= (char)(cube[2].flat_orientation % 4 + 48);
                        corners[23][6] = '\0';
                        break; 

		}
	}
return corners;
}


Personal tools