253 - Cube painting

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sjaycohn
New poster
Posts: 3
Joined: Mon Jul 10, 2006 4:45 am

Post by sjaycohn » Mon Jul 10, 2006 5:16 am

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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

painting cubes --extending to n dimension :)

Post by temper_3243 » Tue Jul 11, 2006 11:45 pm

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Thu Jul 13, 2006 4:52 am

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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Thu Jul 13, 2006 11:33 am

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sat Jul 15, 2006 3:45 am

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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sat Jul 15, 2006 12:50 pm

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sat Jul 15, 2006 4:08 pm

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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sat Jul 15, 2006 10:58 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Jul 16, 2006 12:06 am

temper_3243 wrote: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
New poster
Posts: 5
Joined: Sat Jul 28, 2007 6:33 am
Location: Taiwan

Post by anderson101866 » Sat Jan 26, 2008 11:35 am

Could anyone plz give some test cases? :-?

kamiloj
New poster
Posts: 9
Joined: Fri Dec 29, 2006 3:34 pm

253 - easy solution

Post by kamiloj » Tue Jun 15, 2010 11:55 pm

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
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Location: Bangladesh
Contact:

Re: 253 Cube Painting - WA

Post by forthright48 » Mon Apr 01, 2013 7:09 pm

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
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 253 Cube Painting - WA

Post by brianfry713 » Mon Apr 01, 2013 9:34 pm

For input rgrgbbbbgrgr output should be FALSE
Check input and AC output for thousands of problems on uDebug!

ashiq2446
New poster
Posts: 1
Joined: Tue Aug 18, 2015 1:29 pm

Re: 253 - Cube painting

Post by ashiq2446 » Thu Oct 08, 2015 10:03 pm

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;
}
Last edited by brianfry713 on Sat Oct 10, 2015 5:20 am, edited 1 time in total.
Reason: Added code block

Post Reply

Return to “Volume 2 (200-299)”