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

bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am

Post by bigredteam2000 » Sun Nov 18, 2001 12:28 am

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
New poster
Posts: 4
Joined: Wed Oct 17, 2001 2:00 am
Location: Portugal
Contact:

Post by ganza » Mon Nov 19, 2001 2:13 pm

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

GaNZa

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Fri Jan 04, 2002 3:30 pm

I've finished,thanks

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

raysa
New poster
Posts: 40
Joined: Wed Dec 18, 2002 4:23 pm
Location: Indonesia

253 - Cube painting

Post by raysa » Sun Jan 12, 2003 4:26 pm

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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Sun Jan 26, 2003 3:16 pm

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 :P

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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Betalord
New poster
Posts: 9
Joined: Sat May 03, 2003 11:36 pm
Location: Slovenia

Post by Betalord » Fri Jun 20, 2003 10:09 pm

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Jun 21, 2003 12:31 pm

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
New poster
Posts: 1
Joined: Mon May 12, 2003 2:18 pm
Location: Taiwan
Contact:

Post by danielguo » Wed Jun 25, 2003 6:35 am

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
New poster
Posts: 5
Joined: Sat Oct 05, 2002 8:01 pm
Location: Yerevan, Armenia
Contact:

253 Cube Painting WA :(

Post by Runtime_Error » Wed Jul 16, 2003 12:59 pm

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]
A Runtime Error Has Occured, Do You Wish To Debug?

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sat Jul 30, 2005 2:01 am

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. :wink:

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson » Tue Apr 11, 2006 5:11 am

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
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Apr 12, 2006 10:43 am

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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Fri Jul 07, 2006 7:22 pm

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 :)
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

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

Problem 253 WA

Post by sjaycohn » Mon Jul 10, 2006 4:53 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);
}
}

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

253 WA

Post by sjaycohn » Mon Jul 10, 2006 5:13 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);
}
}

Post Reply

Return to “Volume 2 (200-299)”