Description du défi

Commençons par quelques définitions:

• une relation est un ensemble de paires d'éléments ordonnées (dans ce défi, nous utiliserons des entiers)

Par exemple, [(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)]est une relation.

• une relation est appelée transitive si pour deux paires d'éléments quelconques (a, b)et (b, c)dans cette relation, une paire (a, c)est également présente,

• [(1, 2), (2, 4), (6, 5), (1, 4)]est transitif, car il contient (1, 2)et (2, 4), mais (1, 4)aussi,

• [(7, 8), (9, 10), (15, -5)]est transitive, car il n'y a pas deux paires (a, b), (c, d)présente telle que b= c.

• [(5, 9), (9, 54), (0, 0)]n'est pas transitif, car il contient (5, 9)et (9, 54), mais pas(5, 54)

Étant donné une liste de paires d'entiers, déterminez si une relation est transitive ou non.

Entrée sortie

Vous recevrez une liste de paires d'entiers dans n'importe quel format raisonnable. Considérons une relation

[(1, 6), (9, 1), (6, 5), (0, 0)]

Les formats suivants sont équivalents:

[(1, 6), (9, 1), (6, 5), (0, 0)] # list of pairs (2-tuples)
[1, 9, 6, 0], [6, 1, 5, 0] # two lists [x1, x2, ..., xn] [y1, y2, ..., yn]
[[1, 6], [9, 1], [6, 5], [0, 0] # two-dimentional int array
[4, 1, 6, 9, 1, 6, 5, 0, 0] # (n, x1, y1, ..., xn, yn)
[1+6i, 9+i, 6+5i, 0+0i] # list of complex numbers

... many others, whatever best suits golfing purposes

Sortie: une valeur véridique pour une relation transitive, fausse sinon. Vous pouvez supposer que l'entrée consistera en au moins une paire et que les paires sont uniques.

Haskell, 42 octets

f x=and[elem(a,d)x|(a,b)<-x,(c,d)<-x,b==c]

Exemple d'utilisation: f [(1,2), (2,4), (6,5), (1,4)]-> True.

Boucle (externe) sur toutes les paires (a,b)et boucle (interne) sur les mêmes paires, désormais appelées (c,d)et à chaque fois lorsque b==cvérifier s'il (a,d)existe également une paire existante. Combinez les résultats avec logique and.

 Prolog, 66 octets

t(L):-not((member((A,B),L),member((B,C),L),not(member((A,C),L)))).

La relation n'est pas transitive si nous pouvons trouver (A, B) et (B, C) tels que (A, C) ne tient pas.

MATL , 27 25 octets

7#u2e!l6MX>thl4$XQttY*g<~

Le format d'entrée est une matrice (utilisant ;comme séparateur de lignes) où chaque paire de la relation est une colonne. Par exemple, les cas de test

[(1, 2), (2, 4), (6, 5), (1, 4)]
[(7, 8), (9, 10), (15, -5)]
[(5, 9), (9, 54), (0, 0)]

sont respectivement saisies comme

[1 2 6 1; 2 4 5 4]
[7 9 15; 8 10 -5]
[5 9 0; 9 54 0]

La sortie véridique est une matrice formée de uns. La fausseté est une matrice qui contient au moins un zéro.

Essayez-le en ligne!

Explication

Le code réduit d'abord les entiers d'entrée à des valeurs entières uniques basées sur 1. À partir de ces valeurs, il génère la matrice d'adjacence; la matrice la multiplie par elle-même; et convertit les valeurs non nulles de la matrice de résultats en valeurs. Enfin, il vérifie qu'aucune entrée dans cette dernière matrice ne dépasse celle de la matrice d'adjacence.

JavaScript (ES6), 69 67 octets

a=>(g=f=>a.every(f))(([b,c])=>g(([d,e])=>c-d|!g(([d,c])=>b-d|c-e)))

Enregistré 2 octets grâce à une idée de @Cyoce. Il y avait quatre formulations précédentes de 69 octets:

a=>a.every(([b,c])=>a.every(([d,e])=>c-d|a.some(([d,c])=>b==d&c==e)))
a=>!a.some(([b,c])=>!a.some(([d,e])=>c==d&a.every(([d,c])=>b-d|c-e)))
a=>a.every(([b,c])=>a.every(([d,e])=>c-d|!a.every(([d,c])=>b-d|c-e)))
(a,g=f=>a.every(f))=>g(([b,c])=>g(([d,e])=>c-d|!g(([d,c])=>b-d|c-e)))

Brachylog , 24 octets

'{psc[A:B:B:C],?'e[A:C]}

Essayez-le en ligne!

Explication:

'{psc[A:B:B:C],?'e[A:C]}
'{                     } it is impossible to find
    c                    a flattened
   s                     subset of
  p                      a permutation of the input
     [A:B:B:C]           that has four elements, with the second and third equal
              ,?         and such that the input
                'e       does not contain
                  [A:C]  a list formed of the first and fourth element

En d'autres termes, si l'entrée contient des paires [A:B]et [B:C], nous pouvons permuter l'entrée à mettre [A:B]et [B:C]au début, supprimer tous les autres éléments et produire une liste [A:B:B:C]. Ensuite, nous retournons la vérité du prédicat intérieur (falsey de tout le programme) s'il [A:C]n'y en a pas.

CJam (22 octets)

{__Wf%m*{z~~=*}%\-e_!}

Suite de tests en ligne . Il s'agit d'un bloc (fonction) anonyme qui prend les éléments comme un tableau à deux niveaux, mais la suite de tests fait une manipulation de chaîne pour placer d'abord l'entrée dans un format approprié.

Dissection

{         e# Begin a block
  _       e#   Duplicate the argument
  _Wf%    e#   Duplicate again and reverse each pair in this copy
  m*      e#   Cartesian product
  {       e#   Map over arrays of the form [[a b][d c]] where [a b] and [c d]
          e#   are in the relation
    z~~=* e#     b==c ? [a d] : []
  }%
  \-      e#   Remove those transitive pairs which were in the original relation
  e_!     e#   Test that we're only left with empty arrays
}

Pyth, 14 octets

!-eMfqFhTCM*_M

Suite de tests

Le format d'entrée devrait être [[0, 0], [0, 1], ... ]

!-eMfqFhTCM*_M
!-eMfqFhTCM*_MQQQ    Variable introduction
            _MQ      Reverse all of the pairs
           *   Q     Cartesian product with all of the pairs
         CM          Transpose. We now have [[A2, B1], [A1, B2]] for each pair
                     [A1, A2], [B1, B2] in the input.
    f                Filter on
       hT            The first element (the middle two values)
     qF              Being equal
  eM                 Take the end of all remaining elements (other two values)
 -              Q    Remove the pairs that are in the input
!                    Negate. True if no transitive pairs were not in the input

Mathematica, 49 octets

#/.{x=___,{a_,b_},x,{b_,c_},x}/;#~FreeQ~{a,c}:>0&

Fonction pure qui prend une liste de paires. Si la liste d'entrée contient {a,b}et {b,c}mais pas {a,c}pour certains a, b, c, la remplace par 0. Truthy est la liste d'entrée, la fausse est 0.

C ++ 14, 140 octets

Comme lambda sans nom retournant via le paramètre de référence. Nécessite que son entrée soit un conteneur de pair<int,int>. Prenant l'approche ennuyeuse O (n ^ 3).

[](auto m,int&r){r=1;for(auto a:m)for(auto b:m)if (a.second==b.first){int i=0;for(auto c:m)i+=a.first==c.first&&b.second==c.second;r*=i>0;}}

Non golfé et utilisation:

#include<vector>
#include<iostream>

auto f=
[](auto m,int&r){
  r=1;                         //set return flag to true
  for(auto a:m)                //for each element
    for(auto b:m)              //check with second element
      if (a.second==b.first){  //do they chain?
        int i=0;               //flag for local transitivity
        for(auto c:m)          //search for a third element
          i+=a.first==c.first&&b.second==c.second;
        r*=i>0;                //multiply with flag>0, resulting in 0 forever if one was not found
      }
}
;

int main(){
 std::vector<std::pair<int,int>> m={
  {1, 2}, {2, 4}, {6, 5}, {1, 4}
 };

 int r;
 f(m,r);
 std::cout << r << std::endl;

 m.emplace_back(3,6);
 f(m,r);
 std::cout << r << std::endl;

 m.emplace_back(3,5);
 f(m,r);
 std::cout << r << std::endl;

}

Python 2 , 91 67 55 octets

lambda s:all(b-c or(a,d)in s for a,b in s for c,d in s)

Essayez-le en ligne!

-24 octets grâce à Leaky Nun
-12 octets grâce à Bubbler

Axiome 103 octets

c(x)==(for i in x repeat for j in x repeat if i.2=j.1 and ~member?([i.1, j.2],x)then return false;true)

non golfé:

c(x)==
  for i in x repeat
    for j in x repeat
       if i.2=j.1 and ~member?([i.1, j.2],x) then return false
  true

                                                                   Type: Void

les exercices

(2) -> c([[1,2],[2,4],[6,5],[1,4]])
   Compiling function c with type List List PositiveInteger -> Boolean
   (2)  true
                                                                Type: Boolean
(3) -> c([[7,8],[9,10],[15,-5]])
   Compiling function c with type List List Integer -> Boolean
   (3)  true
                                                            Type: Boolean
(4) -> c([[5,9],[9,54],[0,0]])
   Compiling function c with type List List NonNegativeInteger ->
      Boolean
   (4)  false

Pyth - 22 21 octets

.Am},hdedQfqFtPTsM^Q2

Suite de tests .

Clojure, 56 53 octets

Mise à jour: Au lieu d'utiliser :whenje vais vérifier que pour toutes les paires de [a b] [c d]deux b != cou [a d]se trouve de l'ensemble d'entrée.

#(every? not(for[[a b]%[c d]%](=[b nil][c(%[a d])])))

Original:

Wow, Clojure pour les boucles est cool: D Ceci vérifie que la forboucle ne génère pas de valeur falsifiée, qui se produit si elle [a d]n'est pas trouvée dans le jeu d'entrée.

#(not(some not(for[[a b]%[c d]% :when(= b c)](%[a d]))))

Cette entrée doit être un ensemble de vecteurs à deux éléments:

(f (set [[1, 2], [2, 4], [6, 5], [1, 4]]))
(f (set [[7, 8], [9, 10], [15, -5]]))
(f (set [[5, 9], [9, 54], [0, 0]]))

Si l'entrée doit être de type liste, elle (%[a d])doit être remplacée par ((set %)[a d])pour 6 octets supplémentaires.

Ces deux solutions sont des fonctions sans nom prenant une liste de paires ordonnées en entrée et retournant Trueou False.

Mathematica, 65 octets

SubsetQ[#,If[#2==#3,{#,#4},Nothing]&@@@Join@@@#~Permutations~{2}]&

#~Permutations~{2}]crée la liste de toutes les paires ordonnées de paires ordonnées à partir de l'entrée et les Join@@@convertit en quadruples ordonnés. Ceux-ci sont ensuite exploités par la fonction If[#2==#3,{#,#4},Nothing]&@@@, qui a une propriété cool: si les deux éléments du milieu sont égaux, elle renvoie la paire ordonnée composée du premier et du dernier nombre; sinon, il revient Nothing, un jeton Mathematica spécial qui disparaît automatiquement des listes. Le résultat est donc l'ensemble des paires ordonnées qui doit être en entrée pour qu'il soit transitif; SubsetQ[#,...]détecte cette propriété.

Mathematica, 70 octets

And@@And@@@Table[Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j},{i,#},{j,#}]&

Table[...,{i,#},{j,#}]crée un tableau 2D indexé par iet j, qui sont extraits directement de l'entrée (d'où les deux paires ordonnées). La fonction de ces deux indices est Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}, ce qui se traduit par "soit le deuxième élément de iet le premier élément de jne correspondent pas, soit l'entrée contient la paire ordonnée constituée du premier élément de iet du dernier élément de j". Cela crée un tableau 2D de booléens, qui And@@And@@@s'aplatit en un seul booléen.

APL (NARS), 39 caractères, 78 octets

{∼∨/{(=/⍵[2 3])∧∼(⊂⍵[1 4])∊w}¨,⍵∘.,w←⍵}

tester:

  f←{∼∨/{(=/⍵[2 3])∧∼(⊂⍵[1 4])∊w}¨,⍵∘.,w←⍵}
  f (1 2) (2 4) (6 5) (1 4)
1
  f (7 8) (9 10) (15 ¯5)
1
  f (5 9) (9 54) (0 0)
0

une seconde «solution» suit les étapes suivantes:

r←q w;i;j;t;v
r←1⋄i←0⋄k←↑⍴w⋄→3
r←0⋄→0
→0×⍳k<i+←1⋄t←i⊃w⋄j←0
→3×⍳k<j+←1⋄v←j⊃w⋄→4×⍳t[2]≠v[1]⋄→2×⍳∼(⊂t[1]v[2])∊w

Lisp commun, 121 octets

(lambda(x)(not(loop for(a b)in x thereis(loop for(c d)in x do(if(= b c)(return(not(member`(,a ,d) x :test #'equal))))))))

Essayez-le en ligne!