## 10904 - Structural Equivalence

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

Moderator: Board moderators

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

### 10904 - Structural Equivalence

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  )
--

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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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.

t-s-n
New poster
Posts: 1
Joined: Sat May 20, 2006 2:21 pm
Location: Germany, Nuremberg

### too crazy...

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

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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;

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: too crazy...

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.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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?
JongMan @ Yonsei

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
They are not equivalent - just draw them and take a look.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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!
JongMan @ Yonsei

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
The first types in structures: 'int' and 'B' are clearly not equivalent, so by definition, A and B are also not equivalent.