15
\$\begingroup\$

Challenge description

Let's start with some definitions:

  • 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.

\$\endgroup\$
  • \$\begingroup\$ Does the input have to be a list-like format, or can it be an adjacency--matrix-like format? \$\endgroup\$ – xnor Nov 21 '16 at 21:25
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Nov 21 '16 at 21:26
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – isaacg Nov 22 '16 at 1:09
  • \$\begingroup\$ @isaacg that's what I meant. In other words, my test case is only truthy because the relation isn't implicitly symmetric. \$\endgroup\$ – Martin Ender Nov 22 '16 at 5:49
  • \$\begingroup\$ Should the third test case ([(7, 8), (9, 10), (15, -5)]) be not transitive? \$\endgroup\$ – wnnmaw Nov 22 '16 at 14:08

16 Answers 16

8
\$\begingroup\$

Haskell, 42 bytes

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.

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

 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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)))
\$\endgroup\$
  • 1
    \$\begingroup\$ You might be able to shorten the second solution by making an abbreviation for .every \$\endgroup\$ – Cyoce Nov 21 '16 at 23:53
  • \$\begingroup\$ @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. \$\endgroup\$ – Neil Nov 22 '16 at 0:04
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;

}
\$\endgroup\$
1
\$\begingroup\$

Python 2, 91 67 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

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

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
\$\endgroup\$
0
\$\begingroup\$

Pyth - 22 21 bytes

.Am},hdedQfqFtPTsM^Q2

Test Suite.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\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.