Écrivez un programme ou une fonction qui prend dans une liste non vide des inégalités mathématiques qui utilisent l'opérateur inférieur à ( <). Chaque ligne de la liste aura le formulaire

[variable] < [variable]

où a [variable]peut être n'importe quelle chaîne non vide de caractères az minuscules. Comme dans les mathématiques et la programmation normales, les variables du même nom sont identiques.

Si un entier positif peut être affecté à chaque variable de sorte que toutes les inégalités soient satisfaites, imprimez ou renvoyez une liste des variables avec une telle affectation. Chaque ligne de cette liste doit avoir le formulaire

[variable] = [positive integer]

et toutes les variables doivent apparaître exactement une fois dans n'importe quel ordre.

Notez qu'il peut y avoir de nombreuses solutions entières positives possibles à l'ensemble des inégalités. L'un d'eux est une sortie valide.

S'il n'y a pas de solution aux inégalités, alors ne produisez rien ou ne produisez pas de valeur fausse (c'est à vous de décider ).

Le code le plus court en octets gagne.

Exemples

Si l'entrée était

mouse < cat
mouse < dog

alors tout cela serait des sorties valides:

mouse = 1
cat = 2
dog = 2

mouse = 37
cat = 194
dog = 204

mouse = 2
cat = 2000000004
dog = 3

Si l'entrée était

rickon < bran
bran < arya
arya < sansa
sansa < robb
robb < rickon

alors aucune affectation n'est possible car elle se résume à rickon < rickon, donc il n'y a pas de sortie ou une sortie fausse.

Plus d'exemples avec des 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

Plus d'exemples sans solutions: (séparés par des lignes vides)

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

Pyth, 39 octets

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

Essayez-le en ligne: Démonstration

Brute-force à travers toutes les permutations possibles (et interprétez-les comme des triages), vérifiez si elles correspondent aux inégalités et attribuez-leur les valeurs 1, 2, ...., n.

Explication

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

CJam ( 53 52 49 octets)

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

Démo en ligne

Cette forces brutalise toutes les permutations des jetons distincts, de filtrage pour les affectations des numéros 0à n-1qui obéissent à toutes les contraintes et les formate, incrémenter les numéros, et présente le premier. Il est certain de trouver une solution s'il y en a une, car il s'agit essentiellement d'une sorte topologique.

Merci à Reto Koradi pour 3 caractères et Martin Büttner pour 1.

Mathematica, 83 octets

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

Prend la contribution comme une liste des inégalités. Soit sort une liste de devoirs ou Nullsi c'est impossible.