Page 1 of 1

10904 - Structural Equivalence

Posted: Thu Nov 03, 2005 10:48 pm
by Krzysztof Duleba
Any hints? I'm out of luck here. Are cases like the following allowed?

Code: Select all

type A = Z
type B = Z
--
What should I return for

Code: Select all

type A =   int
type B = A
type C = int
type X  = struct(A B)
type Y = struct(B   A)
type Z = struct(A Z)
type   S = struct(A S)
type W = struct(B R)
type R = struct(C W)
-
 type A = int
type B = char
type C = B
     type D = C
type E = D
type F = E
type G = F
type H = struct(B B C C D)
type J = struct(C G F A B)
-
type A = B
type B = A
type C = B
type D = int
type E = char
-
type A = struct(A A)
type B = struct(B B)
type C = struct(A A)
type D = struct(C A)
type E = struct(I A)
type F = struct(A I)
type G = struct(Z C)
type I = int
type Z = char
-
type A = Z
type B = Z
-
type A = C
type B = D
type D = C
type C = int
-
type A = B
type B = A
type C = D
type D = int
-
type A = Z
type B = Z
-
type A = A
type B = B
type C = D
type D = C
type E = F
type F = G
type G = int
type H = I
type I = char
type J = K
type K = L
type L = M
type M = N
type N = O
type O = L
type S = T
type U = V
type P = struct (P P)
type Q = struct (Q   Q)
type X = struct(Z Z)
type Y = struct (Z Z  )
--
My answers are

Code: Select all

A B C
R S W Z
X Y

A
B C D E F G
H
J

A B C
D
E

A B C D
E
F
G
I
Z

A B

A B C D

A B
C D

A B

A B C D J K L M N O
E F G
H I
P Q
S U
X Y

Posted: Sat Dec 10, 2005 9:58 pm
by Martin Macko
Krzysztof Duleba wrote:Any hints? I'm out of luck here. Are cases like the following allowed?

Code: Select all

type A = Z
type B = Z
--
No, it's not allowed, because Z is not defined. My AC would abort() in such case.

Posted: Sat Dec 10, 2005 11:57 pm
by Krzysztof Duleba
Thanks. Then what's the right answer for the following test?

Code: Select all

type A =   int

type B = A
type C = int
type X  = struct(A B)
type Y = struct(B   A)
type Z = struct(A Z)
type   S = struct(A S)
type W = struct(B R)
type R = struct(C W)
-
type A = int
type B = char
type C = B
type D = C
type E = D
type F = E
type G = F
type H = struct(B B C C D)
type J = struct(C G F A B)
-
type A = B
type B = A
type C = B
type D = int
type E = char
-
type A = struct(A A)
type B = struct(B B)
type C = struct(A A)
type D = struct(C A)
type E = struct(I A)
type F = struct(A I)
type G = struct(Z C)
type I = int
type Z = char
-
type A = C
type B = D
type D = C
type C = int
-
type A = B
type B = A
type C = D
type D = int
-
type A = B
type B = A
type C = D
type D = E
type E = C
I have

Code: Select all

A B C
R S W Z
X Y

A
B C D E F G
H
J

A B C
D
E

A B C D
E
F
G
I
Z

A B C D

A B
C D

A B C D E

Posted: Sun Dec 11, 2005 12:23 am
by Martin Macko
Krzysztof Duleba wrote:Thanks. Then what's the right answer for the following test?
Hard to say. My AC's output for the 3rd case is

Code: Select all

A B C D E
and for the 6th

Code: Select all

A B C D
But your answers give me more sence. Thus, there are probably no such cyclical cases in the tests. My solution just greedily expands the variables into at most a certain depth and then compares the structure.

Posted: Sun Dec 11, 2005 12:40 am
by Krzysztof Duleba
Are you sure about your output? In case 3, D = int, E = char. How come they are equivalent? You also missed E in case 6.

In my solution I treat types as trees (possibly infinite, but that's not a problem) with labelled leaves. I say that types are equivalent iff their trees are identical. I tested several modifications and different implementations of this approach and still WA :-(

Posted: Sun Dec 11, 2005 12:58 am
by Martin Macko
Krzysztof Duleba wrote:Are you sure about your output? In case 3, D = int, E = char. How come they are equivalent? You also missed E in case 6.
Well, I'm not... actually I'm sure my answer is wrong, but that's what my AC outputs. D=E happend by comparing them to A. As A has not fully defined type my solution after a few iterations gave comparing A with D up and said it couldn't find a difference between them, thus A=D. The same happend for A=E. I don't know if there are such not fully defined types in the test cases. Probably not, because I wouldn't have got AC if there were such cases.

Posted: Sun Dec 11, 2005 1:08 am
by Krzysztof Duleba
Thanks for help. Now I know what was wrong. There are commas in the input! My solution was ok (or, at least, acceptable ;-) ) all the time. This is very disappointing.

Anyway, the problem would be much nicer if the test cases were harder and included infinite cases.

too crazy...

Posted: Sat May 20, 2006 2:25 pm
by t-s-n
Hi,
as this is the one and only post for problem #10904, I'll ask here:

do you have some more test-cases for this problem ?

What's the output for:
type A = int
type B = char
type C = A
-
type A = B
type B = A
-
type A = int
type B = char
type C = struct(A B)
type D = struct(A A)
type E = struct(B A)
type F = struct(B B)
-
type A = int
type B = int
type C = struct(A B)
type D = struct(A A)
type E = struct(B A)
type F = struct(B B)
--
My output says:
A C
B

A B

A
B
C
D
E
F

A B
C D E F

Thanx for your help,
Thomas

Posted: Sat May 20, 2006 2:36 pm
by Krzysztof Duleba
Same here.

Make sure to handle those damn commas correctly. I'm not sure, but there may be some tabs too (I have this line in my code, it could be important):

Code: Select all

while(str[n] == ' ' || str[n] == '\t' || str[n] == ',')++n; 

Re: too crazy...

Posted: Sat May 20, 2006 10:35 pm
by Martin Macko
t-s-n wrote:Hi,
as this is the one and only post for problem #10904, I'll ask here:

do you have some more test-cases for this problem ?
My AC's output is the same, too. Post your outputs to some more test cases so I can compare them to mine.

Posted: Sun Jun 04, 2006 6:27 pm
by Whinii F.
Infinite things make me sick..
A = struct (int A int)
B = struct (int B)
Are these two equivalent? A will only have even number of ints but it's not true for B.

Mmm.. Am I missing something?

Posted: Mon Jun 05, 2006 8:05 am
by Krzysztof Duleba
They are not equivalent - just draw them and take a look.

Posted: Mon Jun 05, 2006 8:40 am
by Whinii F.
Thanks for the answer.

However, the problem statement is still confusing. The only definition of "equivalence" it gives is "if they are both structures containing equivalent types in the same order".

Then, are these two equivalent?
type A = struct(int A)
type B = struct(B int)
If we have to merely compare the parsed trees, these should not be equivalent.. however they fit in the above definition... So I don't know. Someone please clarify!

Posted: Mon Jun 05, 2006 9:03 am
by mf
The first types in structures: 'int' and 'B' are clearly not equivalent, so by definition, A and B are also not equivalent.