Under construction

Still being built. Things may change

Structural Equivalence

Time limit1sMemory limit128 MB

Summary
Given recursive type definitions with aliases and structs, group type names into the smallest set of lines where each line holds names that are structurally equivalent after full unfolding.
Level

Hard8 of 10

Topics
Union-find, Graph, DFS, Implementation
Solved
No attempts yet

Problem

In programming-language design there is a long-running debate between structural equivalence and name equivalence for deciding when two types match. Algol 68 uses pure structural equivalence, and this problem asks you to compute it.

A simplified Algol 68 type definition has the following grammar:

type_def   -> type T = type_expr
type_expr  -> T | int | real | char | struct ( field_defs )
field_defs -> T | field_defs T

Here T is a programmer-defined type name, which for this problem is a single uppercase letter. The words type, int, real, char, and struct, together with =, (, and ), appear literally. Wherever the grammar shows a space, the input may contain zero or more spaces.

Two types are structurally equivalent when either:

  • they are the same primitive type (int, real, or char), or
  • they are both structs that have the same number of fields and whose fields are pairwise structurally equivalent in the same order.

A type name may be defined as another type name (an alias), as a primitive, or as a struct. Definitions may refer to names that are defined later, and a type may refer to itself, so the definitions can be (mutually) recursive; equivalence is taken over the fully unfolded types.

Input

The input contains several test cases. Each test case is a list of type definitions as described above, one definition per line. A line containing a single - separates consecutive test cases. A line containing -- marks the end of the input, following the last test case.

Output

For each test case, print the type names grouped so that all names in one group are structurally equivalent to one another. Print one group per line, with the names on a line separated by single spaces. Within each line the names must be in alphabetical order, and the lines themselves must also be in alphabetical order. Each type name appears on exactly one line, and the number of lines must be as small as possible (group every set of mutually equivalent names together). Print one blank line between the outputs of consecutive test cases.

Examples3

  1. Example 1

    Input
    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)
--
    Expected output
    A B C
R S W Z
X Y

  2. Example 2

    Input
    type A = int
type B = real
type C = int
-
type D = char
type E = char
--
    Expected output
    A C
B

D E

  3. Example 3

    Input
    type A = int
type B = real
type P = struct(A B)
type Q = struct(B A)
type M = struct(A A)
--
    Expected output
    A
B
M
P
Q