Write a program or function that takes in a nonempty list of mathematical inequalities that use the less than operator (
<). Each line in the list will have the form
[variable] < [variable]
[variable] may be any nonempty string of lowercase a-z characters. As in normal math and programming, variables with the same name are identical.
If a positive integer can be assigned to each variable such that all the inequalities are satisfied, then print or return a list of the variables with such an assignment. Each line in this list should have the form
[variable] = [positive integer]
and all variables must occur exactly once in any order.
Note that there may be many possible positive integer solutions to the set of inequalities. Any one of them is valid output.
If there are no solutions to the inequalities, then either don't output anything or output a falsy value (it's up to you).
The shortest code in bytes wins.
If the input were
mouse < cat mouse < dog
then all of these would be valid outputs:
mouse = 1 cat = 2 dog = 2
mouse = 37 cat = 194 dog = 204
mouse = 2 cat = 2000000004 dog = 3
If the input were
rickon < bran bran < arya arya < sansa sansa < robb robb < rickon
then no assignment is possible because it boils down to
rickon < rickon, so there either is no output or a falsy output.
More examples with solutions:
x < y x = 90 y = 91 --- p < q p < q p = 1 q = 2 --- q < p q < p p = 2 q = 1 --- abcdefghijklmnopqrstuvwxyz < abcdefghijklmnopqrstuvwxyzz abcdefghijklmnopqrstuvwxyz = 123456789 abcdefghijklmnopqrstuvwxyzz = 1234567890 --- pot < spot pot < spot pot < spots pot = 5 spot = 7 spots = 6 --- d < a d < b d < c d < e d = 1 a = 4 b = 4 c = 5 e = 4 --- aa < aaaaa a < aa aaa < aaaa aa < aaaa a < aaa aaaa < aaaaa aaa < aaaaa a < aaaaa aaaa = 4 aa = 2 aaaaa = 5 a = 1 aaa = 3 --- frog < toad frog < toaster toad < llama llama < hippo raccoon < science science < toast toaster < toad tuna < salmon hippo < science toasted < toast raccoon = 1 frog = 2 toaster = 3 toasted = 4 toad = 5 llama = 6 hippo = 7 science = 8 toast = 9 tuna = 10 salmon = 11
More examples with no solutions: (separated by empty lines)
z < z ps < ps ps < ps q < p p < q p < q q < p a < b b < c c < a d < a d < b d < c d < d abcdefghijklmnopqrstuvwxyz < abcdefghijklmnopqrstuvwxyz bolero < minuet minuet < bolero aa < aaaaa a < aa aaa < aaaa aa < aaaa aaaaa < aaaa a < aaa aaaa < aaaaa aaa < aaaaa a < aaaaa g < c a < g b < a c < a g < b a < g b < a c < a g < b a < g b < a c < b g < c a < g b < a c < b geobits < geoborts geobrits < geoborts geology < geobits geoborts < geology