253 - Cube painting

[sjaycohn]

I submitted for this problem 10 times and each time I get a wrong answer and I don't know why. My algorithm seems perfect. My roll functions work perfectly. For every roll on the x axis, I do 4 rolls on the y axis, and for every roll on the y axis, I do 4 rolls of the z axis. This should take care of every possible combination. My algorithm works for the test samples. What could I possibly be doing wrong?

My code is below.


#include <iostream>
#include <string>

using namespace std;

const int t=0, bo=5, l=2, r=3, f=1, ba = 4;

string roll_x(string cube1)
{
char top = cube1[f];
char front = cube1[bo];
char bottom = cube1[ba];
char back = cube1[t];
char left = cube1[l];
char right = cube1[r];
string cube2 = "";
cube2 = cube2+top+front+left+right+back+bottom;
return cube2;
}

string roll_y(string cube1)
{
char top = cube1[l];
char front = cube1[f];
char bottom = cube1[r];
char left = cube1[bo];
char right = cube1[t];
char back = cube1[ba];
string cube2 = "";
cube2 = cube2+top+front+left+right+back+bottom;
return cube2;
}

string roll_z(string cube1)
{
char top = cube1[t];
char front = cube1[l];
char bottom = cube1[bo];
char left = cube1[ba];
char right = cube1[f];
char back = cube1[r];
string cube2 = "";
cube2 = cube2+top+front+left+right+back+bottom;
return cube2;
}

void init(string cube1, string cube2)
{
int x = 0, y, z;
while(x < 4)
{
cube2 = roll_x(cube2);
if(cube1 == cube2)
{
cout << "TRUE\n";
return;
}
y = 0;
while(y < 4)
{
cube2 = roll_y(cube2);
if(cube1 == cube2)
{
cout << "TRUE\n";
return;
}
z = 0;
while(z < 4)
{
cube2 = roll_z(cube2);
if(cube1 == cube2)
{
cout << "TRUE\n";
return;
}
z++;
}
y++;
}
x++;
}
cout << "FALSE\n";
}

void main(void)
{
string cube, cube1, cube2;
while(cin.good())
{
cin >> cube;
cube1 = cube.substr(0,6);
cube2 = cube.substr(6,6);
init(cube1, cube2);
}
}

[temper_3243]

Hi,
This is regarding the problem 253 (painting cube ) on uva.http://acm.uva.es/p/v2/253.html
I have got this problem accepted from the below code. I have removed some variables and other things
to make sure this problem doesn't get accepted by copy paste method.

here are few questions. I think most of them are able to solve this problem by creating an array of
24 strings and then checking if it matches with any one of them.
This is really simple.

1) Are there any smarter ways of doing this problem.

2) What would one do if only reflections are to be accepted other than rotations. Again i don't
want to do it by generating arrays.

3) Are there any hashing or other smart ways or elegant ways to solve this problem . If you think like
posting code please mail it to niklaus@gmail.com

4) How would one solve the problem if it is extended to 4 or 5 dimensions. Is there any
math behind it.

Code: Select all

char *str[4] = { "123456",
  "135246",
  "154326",
  "142536"
};


char *other[5] = {
  "624351",
  "326154",
  "263415",
  "421653",
  "564312"
};

char *strarr[24];
char mystr[7];


void
gen (void)
{

  for (i = 0; i < 24; i++)
    strarr[i] = (char *) calloc (7, sizeof (char));

  for (i = 0; i < 4; i++)
    {
      strcpy (strarr[cnt], str[i]);
      cnt++;
    }

  for (i = 0; i < 5; i++)
    {
      strcpy (strarr[cnt], other[i]);
      cnt++;
    }

  for (i = 0; i < 5; i++)
    {
      m.clear ();
      for (j = 0; j < 6; j++)
	{
	  m[str[0][j]] = other[i][j];
	}


      for (k = 1; k < 4; k++)
	{


	  for (p = 0; p < 6; p++)
	    {

	      mystr[p] = m[str[k][p]];
	    }
	  mystr[p] = '\0';
	  strcpy (strarr[cnt], mystr);
	  cnt++;
	}
    }


  for (i = 0; i < cnt; i++)
    printf ("%s\n", strarr[i]);


  return;
}

int check(char *fstr,char *ostr)
{

	char *cons=(char *)calloc(7,sizeof(char));

	for(i=0;i<24;i++)
	{
		k=0;
		for(j=0;j<6;j++)
		{
			cons[k++]=fstr[strarr[i][j]-'0'-1];
		}
		if(strcmp(cons,ostr)==0)
			return 1;
	}
	if(i==24)
		return 0;

}

int
main ()
{

  gen ();
	while(scanf(" %s",bstr)!=EOF)
	{
		strncpy(bstr1,bstr,6);
		strncpy(bstr2,bstr+6,6);
		bstr1[6]='\0';
		bstr2[6]='\0';
		fl=check(bstr1,bstr2);
		if(fl==1)
			printf("TRUE\n");
		else
			printf("FALSE\n");
	}
  
  return 0;
}

[daveon]

Hi,

1) Yes, you can write a 10 line solution by hashing
2) Reflected how?
3) Yes, you can hash.
4) If it is extended to higher dimensions, rotations would be hard to comprehend, at least for me.

[temper_3243]

2) Relected along any of the axes.

Hashing , i am not clear on that.
Lets say you have a cube and the numbering is the same as given in the problem

1 (top) (zaxis)
2 (front) (yaxis)
3 (left side) (x axis)
4 (right side) (x axos_
5 (behind i.e opposite of 2) (y axis)
6 (bottom ) (zaxis)

Row if i relect along z axis the cube becomes

1 (top) (zaxis)
2 (front) (yaxis)
4 (left side) (x axis)
3 (right side) (x axis)
5 (behind i.e opposite of 2) (y axis)
6 (bottom ) (zaxis)




Now i find the neighbours of 4 and 3 unchanged. How are you going to hash it.

[daveon]

Hi,

There are 6 faces. Each face can be of 3 values. Create a hash function that is a function of 6 variables. I'm no expert at hashing, but my hashing only consists of the 4 basic operators. I used all 4 operations (-,+,/,*) in such a way that it gives a configuration(and all of its rotations) a unique value.

[temper_3243]

Hi,
Can you please explain what exactly you are doing. Pseudo code would be better. I am having a tough time figuring out how your algo works. seems like elegant but tough to understand.

Can you send the pseudo code or code to niklaus@gmail.com.

P.S. I have the problem already accepted.

[daveon]

You're better off figuring out this one on your own. My code doesn't reveal my thought process, so it is useless to look at it.

[temper_3243]

there are 24 rotations and you are doing 4*4*4 of them.


Your code looks pretty ok except for . Make it 4 rotations on x-axis , 4 rot on y axis, 4 rot on z axis. Now 4 rotations on x axis (but faces swapped on xaxis i.e faces on x axis swapped) similarly for other axis. So total of 24 and you will get accepted.

[mf]

there are 24 rotations and you are doing 4*4*4 of them.

Doesn't matter.

The problem is with this input reading code:

Code: Select all

while(cin.good())
{
cin >> cube;

Check state of cin.good() only after cin>>cube.
Or use "while (cin >> cube) { ... }".

[anderson101866]

Could anyone plz give some test cases?

[kamiloj]

I dont now every body want to rotate the cube.

it is a easy way to solve it, a very easy way.

we have a cube, that is a great facilitator, for the problem.

only see a ordinary cubic dice, the sum of your oposites sides is always seven, so if you are constructing one, and randomly generate the sides, with the rule of seven, you are going to obtain the same dice.

and example

supose the dice
side - oposite
1 - 6
3 - 4
2 - 5

is the same dice if we have any permutation of this
side - oposite
4 - 3
2 - 5
1 - 6

we can reorganize the second into the fist, if we put the 3 side (1,6) in the first place, the second in the third and the fist, in the second place, and we now that is the same cube.

it is because the oposites have to be equals in any equals cube, and it's the only rule, that is the same rule of the painting cube.

if we select a side and its oposite, for the 3 sides, of each cube, they have to be the same if we can reorganize one in the other way.

it's simple.

[forthright48]

The Judge data is weak. I wrote 2 solutions. One uses BFS and another simple pairwise calculation. I tried the following input in both code:

rgrgbbbbgrgr

In the bfs code, I got "FALSE" output and in the other code I got "TRUE". Yet, I got AC by submitting both codes. One of them got to be wrong right?

I think this one is the wrong one:

Code: Select all

/***********Template Starts Here***********/
#pragma comment (linker,"/STACK:16777216")
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <functional>
#include <string>
#include <iostream>
#include <cctype>

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define all(c) (c).begin(),(c).end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())

typedef long long vlong;
typedef unsigned long long uvlong;

const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;
const vlong maxint = 2147483647;
const vlong minint = -2147483648;

using namespace std;

/***********Template Ends Here***********/

char buf[100];

struct combo {
    char a, b;
}v[3], v2[3];

int main ()
{
    //freopen ( "input.txt", "r", stdin );
    //freopen ( "output.txt", "w", stdout );

    while ( scanf ( "%s", buf ) != EOF ) {
        v[0].a = buf[0];
        v[0].b = buf[5];
        v[1].a = buf[1];
        v[1].b = buf[4];
        v[2].a = buf[2];
        v[2].b = buf[3];

        v2[0].a = buf[0+6];
        v2[0].b = buf[5+6];
        v2[1].a = buf[1+6];
        v2[1].b = buf[4+6];
        v2[2].a = buf[2+6];
        v2[2].b = buf[3+6];

        //Find if the pairs match
        int i, j;
        int res = 0;
        for ( i = 0; i < 3; i++ ) {
            for ( j = 0; j < 3; j++ ) {
                if ( ( v2[j].a == v[i].a && v2[j].b == v[i].b )
                    || ( v2[j].a == v[i].b && v2[j].b == v[i].a ) ) {
                    res++;
                    v2[j].a = 0;
                    v2[j].b = 0;
                    break;
                }
            }
        }

        if ( res == 3 ) printf ( "TRUE\n" );
        else printf ( "FALSE\n" );
    }
    return 0;
}

Somebody contact the problem setter :p

[brianfry713]

For input rgrgbbbbgrgr output should be FALSE

[ashiq2446]

i am not finding way out.getting WA.
here is my code-

Code: Select all

#include<cstdio>
using namespace std;
int cop(char a1[6],char a2[6][7])
{
     int a,b,c,d,e,f;
     e=-1;
     for(a=0;a<6;a++)
     {
          if(a1[0]==a2[a][0])
          {
               if(a1[1]==a2[a][1])
               {
                    c=-1;
                    for(b=2;b<6;b++)
                    {
                         if(a1[2]==a2[a][b])
                         {
                              c=b;
                              d=2;
                              f=1;
                         while(d<6)
                         {

                              if(a1[d]!=a2[a][c])
                              {
                                   f=0;
                                 // printf("3");
                                   break;
                              }
                              //printf("%d-%d-%d ",d,c,b);
                              d=d+1;
                              c=c+1;
                              if(c==6) c=2;
                         }
                         if(f==1)
                         {
                              e=1;
                              break;
                         }

                         }
                    }
               }
          }
          if(e==1) break;
     }
     return e;
}

int main()
{
     char c1,c2,c3,c4,c5,c6,c11,c12,c13,c14,c15,c16;
     while((scanf("%c%c%c%c%c%c%c%c%c%c%c%c",&c1,&c2,&c3,&c4,&c5,&c6,&c11,&c12,&c13,&c14,&c15,&c16))==12)
     {
          char ara[6][7],ara1[6][6];
          int a,b,c,d,e;
          for(a=0;a<6;a++) ara[a][6]='1';
        //
          ara[0][0]=c1;
          ara[0][1]=c6;
          ara[0][2]=c2;
          ara[0][3]=c4;
          ara[0][4]=c5;
          ara[0][5]=c3;
          ara[1][0]=c2;
          ara[1][1]=c5;
          ara[1][2]=c4;
          ara[1][3]=c1;
          ara[1][4]=c3;
          ara[1][5]=c6;
          ara[2][0]=c3;
          ara[2][1]=c4;
          ara[2][2]=c1;
          ara[2][3]=c5;
          ara[2][4]=c6;
          ara[2][5]=c2;
          ara[3][0]=c4;
          ara[3][1]=c3;
          ara[3][2]=c1;
          ara[3][3]=c2;
          ara[3][4]=c6;
          ara[3][5]=c5;
          ara[4][0]=c5;
          ara[4][1]=c2;
          ara[4][2]=c1;
          ara[4][3]=c4;
          ara[4][4]=c6;
          ara[4][5]=c3;
          ara[5][0]=c6;
          ara[5][1]=c1;
          ara[5][2]=c2;
          ara[5][3]=c3;
          ara[5][4]=c5;
          ara[5][5]=c4;
          ara1[0][0]=c11;
          ara1[0][1]=c16;
          ara1[0][2]=c12;
          ara1[0][3]=c14;
          ara1[0][4]=c15;
          ara1[0][5]=c13;
          ara1[1][0]=c12;
          ara1[1][1]=c15;
          ara1[1][2]=c14;
          ara1[1][3]=c11;
          ara1[1][4]=c13;
          ara1[1][5]=c16;
          ara1[2][0]=c13;
          ara1[2][1]=c14;
          ara1[2][2]=c11;
          ara1[2][3]=c15;
          ara1[2][4]=c16;
          ara1[2][5]=c12;
          ara1[3][0]=c14;
          ara1[3][1]=c13;
          ara1[3][2]=c11;
          ara1[3][3]=c12;
          ara1[3][4]=c16;
          ara1[3][5]=c15;
          ara1[4][0]=c15;
          ara1[4][1]=c12;
          ara1[4][2]=c11;
          ara1[4][3]=c14;
          ara1[4][4]=c16;
          ara1[4][5]=c13;
          ara1[5][0]=c16;
          ara1[5][1]=c11;
          ara1[5][2]=c12;
          ara1[5][3]=c13;
          ara1[5][4]=c15;
          ara1[5][5]=c14;
          b=1;
          for(c=0;c<1;c++)
          {
               if(cop(ara1[c],ara)!=-1) ara[cop(ara1[c],ara)][6]='0';
               else
               {
                    b=0;
                    break;
                    // printf("3");
               }
          }
          if(b==1) printf("TRUE\n");
          else printf("FALSE\n");
     }
     return 0;
}