Problem K
Dimensional Analysis
You are deriving some equations for physics homework and are worried you’ve made some mistakes. To debug them, you will apply dimensional analysis. In dimensional analysis, you remove all magnitudes and units from a set of equations until you are left only with strings representing physical quantities and the special dimensionless constant $1$. The following is an example set of such equations:
velocity * time = length frequency = 1 / time acceleration = velocity / time force = mass * acceleration force = mass * length / time / time
Your equations, like the ones above, involve only multiplication and division (no addition, exponentiation, etc.) As you can see, some quantities (like velocity) are defined in terms of other, more basic quantities (length, time). But you’re not sure what the correct relationships are between the quantities. You do know that none of the quantities in your equations are unitless: it should not be possible, through any set of algebraic manipulations, to prove that any quantity is equal to the dimensionless constant $1$. (You may assume that all physical quantities in your equations have positive real magnitudes. In particular, you may freely divide any equation by any quantity without worrying about division by zero; and you may take square or higher roots of any quantity.)
A set of equations violating this condition is invalid (and a set of equations is valid otherwise). The above example is a valid system. Here is an invalid one:
foo * bar = xyzzy foo = xyzzy * bar
By substituting the second equation into the first, and dividing both sides by xyzzy, you get $\texttt{bar * bar = 1}$. Taking a square root of both sides, you get $\texttt{bar = 1}$ and so bar is dimensionless.
Given the set of equations in your dimensional analysis, compute whether the equations are valid.
Input
The first line of the input is a single integer $N$, the number of equations $(1 \leq N \leq 100)$. Each of the $N$ subsequent lines of input contains one equation. An equation consists of two expressions, separated by an equal sign surrounded by spaces “ = ”. Each expression contains one or more atoms, separated by either “ * ” or “ / ”; each atom is either the character ‘1’ or a physical quantity, represented by a lowercase string (containing one or more ASCII characters between ‘a’ and ‘z’). At most $100$ unique physical quantities appear in total across all equations, each equation contains at most $100$ atoms, and the total number of characters in all atoms across all equations will not exceed $100\, 000$.
There will be exactly one space before and after each ‘=’, ‘*’, and ‘/’ and the equations will contain no other whitespace or other extraneous punctuation. See the sample input for examples of how equations are formatted.
The operator * represents multiplication and / represents division. Expressions follow the usual associativity rules: a / b * c is the same as a * c / b but different from a / b / c.
Output
Print invalid if it is possible to prove that at least one of the physical quantities in an equation in the input must be dimensionless. Print valid otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 velocity * time = length frequency = 1 / time acceleration = velocity / time force = mass * acceleration force = mass * length / time / time |
valid |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 foo * bar = xyzzy foo = xyzzy * bar |
invalid |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 time * power = energy energy = work work = force * distance distance = distance 1 / 1 = 1 * 1 / 1 |
valid |
