Nik wrote:
> 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 [EMAIL PROTECTED]
>
> 4) How would one solve the problem if it is extended to 4 or 5
> dimensions. Is there any
> math behind it.
> [code elided]
This is a graph isomorphism problem. For 3d the graph is planar, so it
can be solved in O(n) time where n is the number of vertices of the
polytope.
For n=8, enumeration is fine. You don't need to generate tables. It
seems a little more elegant to compute a canonical variant of both the
input colorings and compare these for equality. You can use string min
to pick the variant from the 24 possible rotations. You worked very
hard to get the rotations. Instead you can define two rotations of 90
degrees and compose these to get all the rest.
Perhaps there is a way to exploit the fact that there are only 3 colors
and 6 faces, but I don't see one.
Here's a quick hack. I have not tried submitting it, so apologize in
advance if there are silly errors. But I believe this is correct.
#define I(X) X-1
/* from: 1 2 3 4 5 6 */
int r16[] = { I(1),I(4),I(2),I(5),I(3),I(6) };
int r43[] = { I(2),I(6),I(3),I(4),I(1),I(5) };
void rot(char *cube, int *r)
{
char t[6]; int i;
for (i = 0; i < 6; i++) t[r[i]] = cube[i];
strncpy(cube, t, 6);
}
char *cvnt(char *v, char *cube)
{
char t[6]; int i, j, k;
strncpy(v, cube, 6);
strncpy(t, cube, 6);
for (i = 0; i < 2; i++) {
for (j = 0; j < 4; j++) {
for (k = 0; k < 3; k++) {
if (strncmp(t, v, 6) < 0) strncpy(v, t, 6);
rot(t, r16); rot(t, r43);
}
rot(t, r16);
}
rot(t, r43); rot(t, r43);
}
return v;
}
int main(void)
{
char a[6], b[6], buf[100];
while (scanf(" %s", buf) != EOF)
printf("%s\n", strncmp(cvnt(a, buf), cvnt(b, buf + 6), 6) == 0 ?
"TRUE" : "FALSE");
return 0;
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
