# Challenge description

• a relation is a set of ordered pairs of elements (in this challenge, we'll be using integers)

For instance, [(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)] is a relation.

• a relation is called transitive if for any two pairs of elements (a, b) and (b, c) in this relation, a pair (a, c) is also present,

• [(1, 2), (2, 4), (6, 5), (1, 4)] is transitive, because it contains (1, 2) and (2, 4), but (1, 4) as well,

• [(7, 8), (9, 10), (15, -5)] is transitive, because there aren't any two pairs (a, b), (c, d) present such that b = c.

• [(5, 9), (9, 54), (0, 0)] is not transitive, because it contains (5, 9) and (9, 54), but not (5, 54)

Given a list of pairs of integers, determine if a relation is transitive or not.

# Input / output

You will be given a list of pairs of integers in any reasonable format. Consider a relation

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

The following formats are equivalent:

[(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


Output: a truthy value for a transitive relation, falsy otherwise. You may assume that the input will consist of at least one pair, and that the pairs are unique.

• Does the input have to be a list-like format, or can it be an adjacency--matrix-like format? – xnor Nov 21 '16 at 21:25
• You should have a test case that is only transitive because the pairs are ordered. E.g. (1,3) (2,1) (3,4) (1,4) (2,4). If the pairs weren't ordered, this wouldn't be transitive because (2,3) is missing. – Martin Ender Nov 21 '16 at 21:26
• @MartinEnder I think you misinterpreted "ordered pairs". I don't think it means the pairs in an order - I think it means each pair has an order, first then second. – isaacg Nov 22 '16 at 1:09
• @isaacg that's what I meant. In other words, my test case is only truthy because the relation isn't implicitly symmetric. – Martin Ender Nov 22 '16 at 5:49
• Should the third test case ([(7, 8), (9, 10), (15, -5)]) be not transitive? – wnnmaw Nov 22 '16 at 14:08

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


Usage example: f [(1,2), (2,4), (6,5), (1,4)]-> True.

(Outer)loop over all pairs (a,b) and (inner)loop over the same pairs, now called (c,d) and every time when b==c check if (a,d)is also an existent pair. Combine the results with logical and.

• Most readable answer so far! – Lynn Nov 22 '16 at 2:07
• @Lynn Check out the Prolog answer, then ;-) – coredump Nov 22 '16 at 16:00

## Prolog, 66 bytes

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


The relation is not transitive if we can find (A,B) and (B,C) such that (A,C) doesn't hold.

# MATL, 27 25 bytes

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


Input format is a matrix (using ; as row separator) where each pair of the relation is a column. For example, test cases

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


are respectively input as

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


Truthy output is a matrix formed by ones. Falsy is a matrix that contains at least one zero.

Try it online!

### Explanation

The code first reduces the input integers to unique, 1-based integer values. From those values it generates the adjacency matrix; matrix-multiplies it by itself; and converts nonzero values in the result matrix to ones. Finally, it checks that no entry in the latter matrix exceeds that in the adjacency matrix.

## JavaScript (ES6), 69 67 bytes

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


Saved 2 bytes thanks to an idea by @Cyoce. There were four previous 69-byte formulations:

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)))

• You might be able to shorten the second solution by making an abbreviation for .every – Cyoce Nov 21 '16 at 23:53
• @Cyoce Indeed, you save 3 bytes each time by writing [e], so even though it costs 8 bytes to assign e you still save a byte. However, I went a step further by making an abbreviation for a.every, which saved a second byte. – Neil Nov 22 '16 at 0:04

# Brachylog, 24 bytes

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


Try it online!

Explanation:

'{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


In other words, if the input contains pairs [A:B] and [B:C], we can permute the input to put [A:B] and [B:C] at the start, delete all other elements, and produce a list [A:B:B:C]. Then we return truthy from the inner predicate (falsey from the whole program) if [A:C] isn't there.

## CJam (22 bytes)

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


Online test suite. This is an anonymous block (function) which takes the elements as a two-level array, but the test suite does string manipulation to put the input into a suitable format first.

### 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 bytes

!-eMfqFhTCM*_M


Test suite

Input format is expected to be [[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 bytes

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


Pure function which takes a list of pairs. If the input list contains {a,b} and {b,c} but not {a,c} for some a, b, c, replaces it with 0. Truthy is the input list, falsy is 0.

# C++14, 140 bytes

As unnamed lambda returning via reference parameter. Requires its input to be a container of pair<int,int>. Taking the boring O(n^3) approach.

[](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;}}


Ungolfed and usage:

#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, 9167 55 bytes

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


Try it online!

-24 bytes thanks to Leaky Nun
-12 bytes thanks to Bubbler

• 67 bytes (and fixed your code by changing lambda x to lambda s. – Leaky Nun Jun 23 '17 at 18:29
• @LeakyNun Oh whoops, that was supid stupid of me. Thanks! – HyperNeutrino Jun 23 '17 at 18:36
• 55 bytes by unpacking at fors. – Bubbler Nov 6 '18 at 4:28
• @Bubbler oh cool thanks – HyperNeutrino Nov 6 '18 at 8:07

Axiom 103 bytes

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)


ungolfed:

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


the exercises

(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 bytes

.Am},hdedQfqFtPTsM^Q2


## Clojure, 56 53 bytes

Update: Instead of using :when I'll just check that for all pairs of [a b] [c d] either b != c or [a d] is found from the input set.

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


Original:

Wow, Clojure for loops are cool :D This checks that the for loop does not generate a falsy value, which occurs if [a d] is not found from the input set.

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


This input has to be a set of two-element vectors:

(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]]))


If input must be list-like then (%[a d]) has to be replaced by ((set %)[a d]) for extra 6 bytes.

Both these solutions are unnamed functions taking a list of ordered pairs as input and returning True or False.

# Mathematica, 65 bytes

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


#~Permutations~{2}] creates the list of all ordered pairs of ordered pairs from the input, and Join@@@ converts those to ordered quadruples. Those are then operated upon by the function If[#2==#3,{#,#4},Nothing]&@@@, which has a cool property: if the middle two elements are equal, it returns the ordered pair consisting of the first and last numbers; otherwise it returns Nothing, a special Mathematica token that automatically disappears from lists. So the result is the set of ordered pairs that needs to be in the input for it to be transitive; SubsetQ[#,...] detects that property.

# Mathematica, 70 bytes

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


Table[...,{i,#},{j,#}] creates a 2D array indexed by i and j, which are taken directly from the input (hence are both ordered pairs). The function of those two indices is Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}, which translates to "either the second element of i and the first element of j don't match, or else the input contains the ordered pair consisting of the first element of i and the last element of j". This creates a 2D array of booleans, which And@@And@@@ flattens into a single boolean.

# APL(NARS), 39 chars, 78 bytes

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


test:

  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


one second 'solution' follow goto ways:

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


## Common Lisp, 121 bytes

(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))))))))
`

Try it online!