253 - Cube painting

[bigredteam2000]

What is meant by `The output is a file of boolean.'? You can't directly output booleans in c++, so I took this to mean print out TRUE or FALSE as characters. This produced the `wrong answer'. My program did produce the same results as the sample, but I'm guessing it's a formatting problem.

[ganza]

You are printing output file well so your program need more testing to solve this problem

GaNZa

[FlyDeath]

I've finished,thanks

<font size=-1>[ This Message was edited by: FlyDeath on 2002-01-04 16:25 ]</font>

[raysa]

For i keep getting WA when comparing those painted cubes, I think
I need TONS of input-output cases for 253 problem. Anybody can help?
And please tell me if there's any catch in this prob...
Thank's!

[epsilon0]

YEAH! JUST GOT ACCEPTED!

this problem was a real torture to my brain since i had to mental rotate this damn cube to get my rotation tables...
i got mixed up in the process and had to modify my code and rewrite the table from scratch.

my solution is a little better than naive table, since i only consider 3 basic rotations (around x,y,z) then i combine them to get all 24 rotations... so i have another table that is a "map" of rotations to apply... and the real final rotation table is built in an init function in the beginning of my program.

there is no trick. i wonder if there is a smart way to do it, without having to enter tables by hand. you need a way or another to tell your program how to perform a rotation... and how to generate all possible non redundant rotations (24 of them)... if there is such a program, i'd really like to see it

if you get WA all the time and it's not a formatting problem, rethink your code, how it works etc... does it really do what you expect it to do? is what you expect it to do what you have to do to solve the pb? etc...

good luck



good luck

[Betalord]

I don't understand what is wrong with this algorithm.
Can anybody check the rotations?

program p253(input, output);

var
R1, R2, G1, G2, B1, B2: Byte;
i, j: Integer;
line: string;
cube1, cube2: array[1..6] of char;

Const

Rotations: array[1..24] of array[1..6] of Byte =
(
(1, 2, 3, 4, 5, 6),
(1, 3, 5, 2, 4, 6),
(1, 4, 2, 5, 3, 6),
(1, 5, 4, 3, 2, 6),

(2, 1, 4, 3, 6, 5),
(2, 3, 1, 6, 4, 5),
(2, 4, 6, 1, 3, 5),
(2, 6, 3, 4, 1, 5),

(3, 1, 2, 5, 6, 4),
(3, 2, 6, 1, 5, 4),
(3, 5, 1, 6, 2, 4),
(3, 6, 5, 2, 1, 4),

(4, 1, 5, 2, 6, 3),
(4, 2, 1, 6, 5, 3),
(4, 5, 6, 1, 2, 3),
(4, 6, 2, 5, 1, 3),

(5, 1, 3, 4, 6, 2),
(5, 3, 6, 1, 4, 2),
(5, 4, 1, 6, 3, 2),
(5, 6, 4, 3, 1, 2),

(6, 2, 4, 3, 5, 1),
(6, 3, 2, 5, 4, 1),
(6, 4, 5, 2, 3, 1),
(6, 5, 3, 4, 2, 1)

);

function Analyse: Boolean;
begin
Analyse := False;

R1 := 0;
G1 := 0;
B1 := 0;
R2 := 0;
G2 := 0;
B2 := 0;

ReadLn(line);

for i := 1 to 6 do
begin
cube1 := line;

if line = 'r' then Inc(R1)
else if line = 'g' then Inc(G1)
else Inc(B1);
end;
for i := 1 to 6 do
begin
cube2 := line[i+6];

if line[i+6] = 'r' then Inc(R2)
else if line[i+6] = 'g' then Inc(G2)
else Inc(B2);
end;

if R1 <> R2 then
Exit
else if B1 <> B2 then
Exit
else if G1 <> G2 then
Exit;

for i := 1 to 24 do
begin
Analyse := True;
for j := 1 to 6 do if not (cube2[j] = cube1[Rotations[j]]) then begin Analyse := False; Break; end;
if not Analyse then Continue;
// else:
Exit;
end;
end;

begin
while not Eof(input) do Writeln(Analyse);
end.



Regards,
Betalord

[shamim]

epsilon0 wrote:

i wonder if there is a smart way to do it, without having to enter tables by hand. you need a way or another to tell your program how to perform a rotation... and how to generate all possible non redundant rotations (24 of them)... if there is such a program, i'd really like to see it

one way to make program run faster is to use a quick rejection.

That is in both the cubes,

the color of opposite side must come as pair in both cube.

[danielguo]

I think if you mark face 5 as 4 and face 4 as 5, then you can handle the rotation of face 2 to 5 automatically.
So only need to input 6 ways to rotate. (which face is on top)

[Runtime_Error]

i dont know why i got WA, im just checking if the first cube and the second cube are the same without any 'rotation' tables. is it possible that the cubes are the same but you cant rotate one to get the second one? here is my algorithm: i remember face 1 color on the first cube, search for that color on the second cube and if i find it, i check if its adjacent faces are the same color as the adjacent face colors of first cubes face 1(i.e. 2354), then i check if its opposite face has the same color as face 6 on the first cube. thats it.. whats wrong in this algorithm?
Here is my code:
[cpp]
#include <iostream.h>
#include <string.h>

bool rot (char a[5], char b[5])
{
char t;
int i, j;
if (strcmp(a, b) == 0)
return true;
for (i = 0; i < 3; i++) {
t = b[3];
for (j = 3; j > 0; j--)
b[j] = b[j - 1];
b[0] = t;
if (strcmp(a, b) == 0)
return true;
}
return false;
}

void main()
{
int i;
bool b;
char cube[15], c1[7], c2[7], x, y, cr[5], c2r[5];
cr[4] = '\0';
c2r[4] = '\0';
while (cin.getline(cube, 15)) {
strncpy(c1, cube, 6);
c1[6] = '\0';
strncpy(c2, cube + 6, 6);
c2[6] = '\0';
x = c1[0];
cr[0] = c1[1];
cr[1] = c1[2];
cr[2] = c1[4];
cr[3] = c1[3];
y = c1[5];
b = false;
for (i = 0; i < 6; i++) {
if (c2 == x) {
switch (i) {
case 0:
c2r[0] = c2[1];
c2r[1] = c2[2];
c2r[2] = c2[4];
c2r[3] = c2[3];
if (rot(cr, c2r) && y == c2[5])
b = true;
break;
case 1:
c2r[0] = c2[0];
c2r[1] = c2[3];
c2r[2] = c2[5];
c2r[3] = c2[2];
if (rot(cr, c2r) && y == c2[4])
b = true;
break;
case 2:
c2r[0] = c2[0];
c2r[1] = c2[4];
c2r[2] = c2[5];
c2r[3] = c2[1];
if (rot(cr, c2r) && y == c2[3])
b = true;
break;
case 3:
c2r[0] = c2[0];
c2r[1] = c2[4];
c2r[2] = c2[5];
c2r[3] = c2[1];
if (rot(cr, c2r) && y == c2[2])
b = true;
break;
case 4:
c2r[0] = c2[0];
c2r[1] = c2[3];
c2r[2] = c2[5];
c2r[3] = c2[2];
if (rot(cr, c2r) && y == c2[1])
b = true;
break;
case 5:
c2r[0] = c2[1];
c2r[1] = c2[2];
c2r[2] = c2[4];
c2r[3] = c2[3];
if (rot(cr, c2r) && y == c2[0])
b = true;
break;
}
if (b)
break;
}
}
if (b)
cout << "TRUE\n";
else
cout << "FALSE\n";
}
}
[/cpp]

[daveon]

epsilon0 wrote:

i wonder if there is a smart way to do it, without having to enter tables by hand. you need a way or another to tell your program how to perform a rotation... and how to generate all possible non redundant rotations (24 of them)... if there is such a program, i'd really like to see it

You don't have to worry about rotations at all!

My idea is giving each face a value, kind of like hashing.
For each of the 6 faces, give it a value that is a function of it's 4 adjacent faces.
You can increase the accuracy of this method by including prime numbers or random numbers that represent each colour.
Add up these six values and repeat for second cube.
If both sums are equal, then both representations are equal.

Well, hope you get the general idea.
Good luck.

[Jemerson]

Hi guys, i've read your ideas but coudn't convinced myself that my code for any reason is wrong.
All I do is rotate 4 times up and for each rotation UP rotate 4 time for the LEFT. Rotate means to reorganize the chars inside a char array that represents the cube. Rotate up would be something like this:

Code: Select all

		char temp = cube[0];
		cube[0] = cube[1];
		cube[1] = cube[5];
		cube[5] = cube[4];
		cube[4] = temp;

Any idea of what can be wrong? I still got WA on my last submission

[mf]

I used a very similar code in my accepted program, but I have three nested loops, which rotate the cube around OX, OY and OZ axes.
How many different rotations does you algorithm produce? There should be 24 of them.

[Kallol]

To Jemerson,
ya your process is almost the same one i used for my AC code.
But you have to use 3 types of rotations.
for each X-rotation , do 4 Y-rotation and for each Y-rotation do 4 Z rotation. SO, u need a 3rd order nested loop. Hope this hint will help you

[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);
}
}

[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);
}
}