Opis wyzwania

Zacznijmy od kilku definicji:

• relacja jest zbiorem uporządkowanych par elementów (w tym wyzwaniem, będziemy używać liczb całkowitych)

Na przykład [(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)]jest relacją.

• relacja jest nazywana przechodnią, jeśli dla dowolnych dwóch par elementów (a, b)iw (b, c)tej relacji (a, c)występuje również para ,

• [(1, 2), (2, 4), (6, 5), (1, 4)]jest przechodnie, ponieważ zawiera (1, 2)i (2, 4), ale (1, 4)także

• [(7, 8), (9, 10), (15, -5)]jest przechodnie, ponieważ nie ma żadnych dwóch par (a, b), (c, d)obecnych tak, że b= c.

• [(5, 9), (9, 54), (0, 0)]nie jest przechodnie, ponieważ zawiera (5, 9)i (9, 54), ale nie zawiera(5, 54)

Biorąc pod uwagę listę par liczb całkowitych, określ, czy relacja jest przechodnia, czy nie.

Wejście wyjście

Otrzymasz listę par liczb całkowitych w dowolnym rozsądnym formacie. Rozważ relację

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

Następujące formaty są równoważne:

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

Wyjście: prawdziwa wartość dla relacji przechodniej, w przeciwnym razie fałsz. Możesz założyć, że dane wejściowe będą się składać z co najmniej jednej pary i że pary są unikalne.

Haskell, 42 bajty

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

Przykład użycia: f [(1,2), (2,4), (6,5), (1,4)]-> True.

Pętla (zewnętrzna) nad wszystkimi parami (a,b)i (wewnętrzna) pętla nad tymi samymi parami, teraz wywoływanymi (c,d)i za każdym razem, gdy b==csprawdzane (a,d)jest, czy istnieje również para. Połącz wyniki z logiką and.

 Prolog, 66 bajtów

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

Relacja nie jest przechodnia, jeśli możemy znaleźć (A, B) i (B, C) w taki sposób, że (A, C) nie zachowuje się.

MATL , 27 25 bajtów

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

Format wejściowy to macierz (używana ;jako separator wierszy), w której każda para relacji jest kolumną. Na przykład przypadki testowe

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

są odpowiednio wprowadzane jako

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

Wyjściowa prawda to macierz utworzona przez jedynki.Falsy to matryca zawierająca co najmniej jedno zero.

Wypróbuj online!

Wyjaśnienie

Kod najpierw redukuje wejściowe liczby całkowite do unikalnych wartości całkowitych opartych na 1. Z tych wartości generuje macierz przyległości; matryca mnoży ją sama; i konwertuje wartości niezerowe w macierzy wyników na te. Na koniec sprawdza, czy żaden wpis w drugiej macierzy nie przekracza wpisu w macierzy przylegania.

JavaScript (ES6), 69 67 bajtów

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

Zaoszczędzono 2 bajty dzięki pomysłowi @Cyoce. Były cztery poprzednie 69-bajtowe formuły:

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 bajty

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

Wypróbuj online!

Wyjaśnienie:

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

Innymi słowy, jeśli dane wejściowe zawierają pary [A:B] i [B:C], możemy zezwolić, aby dane wejściowe wstawiały [A:B]i [B:C]na początku usuwały wszystkie inne elementy i tworzyły listę [A:B:B:C]. Następnie zwracamy prawdę z wewnętrznego orzecznika (falsey z całego programu), jeśli go [A:C]nie ma.

CJam (22 bajty)

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

Zestaw testów online . Jest to anonimowy blok (funkcja), który przyjmuje elementy jako tablicę dwupoziomową, ale pakiet testowy dokonuje manipulacji ciągiem znaków, aby najpierw wprowadzić dane wejściowe do odpowiedniego formatu.

Sekcja

{         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 bajtów

!-eMfqFhTCM*_M

Zestaw testowy

Format wejściowy ma być [[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 bajtów

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

Czysta funkcja, która pobiera listę par. Jeśli lista zawiera wejście {a,b}i {b,c}ale nie {a,c}dla niektórych a, b, c, zastępuje go 0. Prawda jest listą wejściową, fałsz jest 0.

C ++ 14, 140 bajtów

Jako nienazwana lambda powraca poprzez parametr referencyjny. Wymaga, aby jego dane wejściowe były pojemnikiem pair<int,int>. Przyjmując nudne podejście 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;}}

Niegolfowane i użytkowanie:

#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 bajtów

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

Wypróbuj online!

-24 bajty dzięki Dziurawej Zakonnicy
-12 bajtów dzięki Bubblerowi

Axiom 103 bajty

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)

bez golfa:

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

ćwiczenia

(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 bajtów

.Am},hdedQfqFtPTsM^Q2

Pakiet testowy .

Clojure, 56 53 bajtów

Aktualizacja: Zamiast używać :whenpo prostu sprawdzę, czy dla wszystkich par [a b] [c d]jednego z nich b != club [a d]znajduje się w zestawie wejściowym.

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

Oryginalny:

Wow, Clojure dla pętli są fajne: D Sprawdza, czy forpętla nie generuje wartości fałszowania, która pojawia się, jeśli [a d]nie zostanie znaleziona w zestawie wejściowym.

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

Wejście to musi być zbiorem wektorów dwuelementowych:

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

Jeśli dane wejściowe muszą być podobne do list, to (%[a d])należy je zastąpić ((set %)[a d])dodatkowymi 6 bajtami.

Oba te rozwiązania są nienazwanymi funkcjami przyjmującymi listę uporządkowanych par jako dane wejściowe i zwracające Truelub False.

Mathematica, 65 bajtów

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

#~Permutations~{2}]tworzy listę wszystkich uporządkowanych par uporządkowanych par z danych wejściowych i Join@@@konwertuje je na uporządkowane poczwórne. Są one następnie obsługiwane przez funkcję If[#2==#3,{#,#4},Nothing]&@@@, która ma fajną właściwość: jeśli środkowe dwa elementy są równe, zwraca uporządkowaną parę składającą się z pierwszej i ostatniej liczby; w przeciwnym razie powróciNothing specjalny token Mathematica, który automatycznie znika z list. Tak więc wynikiem jest zestaw uporządkowanych par, który musi znajdować się na wejściu, aby był przechodni; SubsetQ[#,...]wykrywa tę właściwość.

Mathematica, 70 bajtów

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

Table[...,{i,#},{j,#}]tworzy tablicę 2D indeksowaną przez ii j, które są pobierane bezpośrednio z danych wejściowych (stąd obie pary uporządkowane). Funkcją tych dwóch indeksów jest Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}, co przekłada się na „albo drugi element ii pierwszy element jnie pasują, albo dane wejściowe zawierają uporządkowaną parę składającą się z pierwszego elementu ii ostatniego elementu j”. Tworzy to tablicę 2D booleanów, która And@@And@@@spłaszcza się w jedną wartość logiczną.

APL (NARS), 39 znaków, 78 bajtów

{∼∨/{(=/⍵[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

jedna sekunda „rozwiązania” jest gotowa:

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 bajtów

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

Wypróbuj online!