16
\$\begingroup\$

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]

where a [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.

Examples

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Very closely related \$\endgroup\$ – Peter Taylor Oct 24 '15 at 20:44
  • \$\begingroup\$ Any limits on runtime? \$\endgroup\$ – Downgoat Oct 24 '15 at 20:53
  • \$\begingroup\$ @Vɪʜᴀɴ No lmits. \$\endgroup\$ – Calvin's Hobbies Oct 24 '15 at 20:54
  • \$\begingroup\$ How do we know when input ends? Is there empty line or something? \$\endgroup\$ – Hannes Karppila Oct 24 '15 at 20:59
  • \$\begingroup\$ @Yes. You can assume there's a trailing newline. \$\endgroup\$ – Calvin's Hobbies Oct 24 '15 at 21:02
4
\$\begingroup\$

Pyth, 39 bytes

V>1f.A<MxMLTN.pS{s=Nm%2cd).zVNjd[H\==hZ

Try it online: Demonstration

Brute-forces through all possible permutations (and interpret them as sortings), check if they match the inequalities, and assign them the values 1, 2, ...., n.

Explanation

f.A<MxMLTN.pS{s=Nm%2cd).z  
                 m     .z  map each input line d to:
                    cd)       split d by spaces
                  %2          and remove the second element
               =N          save this list of pairs to N
              s            combine these pairs to a big list of variable names
             {             set (remove duplicates)
          .pS              generate all permutations
f                          filter for permutations T, which satisfy:
     xMLTN                    replace each variable in N by their index in T
 .A<M                         check if each pair is ascending

V>1...VNjd[H\==hZ          implicit: Z = 0
 >1                        remove all but the last filtered permutation (if any)
V                          for each permutation N in ^ (runs zero times or once):
      VN                      for each variable H in N:
          [                      generate a list containing:
           H                        H
            \=                      "="
              =hZ                   Z incremented by 1 (and update Z)
        jd                       join this list by spaces and print
\$\endgroup\$
3
\$\begingroup\$

CJam (53 52 49 bytes)

qS-N/'<f/:A:|e!{A{1$1$&=!},!*},:ee{()" = "\N}f%1<

Online demo

This brute-forces all permutations of the distinct tokens, filtering for those assignments of the numbers 0 to n-1 which obey all of the constraints, and then formats them, incrementing the numbers, and presents the first one. This is certain to find a solution if there is one, because it's essentially a topological sort.

Thanks to Reto Koradi for 3 chars and Martin Büttner for 1.

\$\endgroup\$
  • \$\begingroup\$ @RetoKoradi, doh! Indeed. \$\endgroup\$ – Peter Taylor Oct 24 '15 at 21:55
2
\$\begingroup\$

Mathematica, 83 bytes

Quiet@Check[Equal@@@FindInstance[Join[#,#>0&/@(v=Sequence@@@#)],v,Integers][[1]],]&

Takes input as a list of inequalities. Either outputs a list of assignments or Null if it is impossible.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.