Transitive Equality

Question

The Challenge

Your program should take 3 inputs:

• A positive integer which is the number of variables,
• A set of unordered pairs of nonnegative integers, where each pair represents an equality between variables, and
• A positive integer which represents the starting variable,

It should return a set of nonnegative integers which represent all variables which can be shown to be transitively equal to the starting variable (including the starting variable itself).

In other words, given inputs N, E, and S, return a set Q, such that:

• S ∈ Q.
• If Z ∈ Q and (Y = Z) ∈ E, then Y ∈ Q.
• If Z ∈ Q and (Z = Y) ∈ E, then Y ∈ Q.

This can also be expressed as a graph-theory problem:

Given an undirected graph and a vertex in the graph, list the vertices in its connected component.

Specifications

• You can choose to use 0-based or 1-based indexing.
• The first input counts the number of variables that are present, where variables are given as numbers. Alternatively, you can not take this input, in which case this is assumed to be equal to either the highest variable index present, or one more than this, depending on your indexing scheme.
• You can assume the input is well formed: you will not be given variables outside of the range specified by the first input. For example, 3, [1 = 2, 2 = 0], 1 is a valid input, while 4, [1 = 719, 1 = 2, 3 = 2], -3 is not.
• You cannot assume that any variable will have any equalities associated with with it. If given a third input that is "lonely" (has no equalities), the correct output is a singleton set containing only that input (since it is equal to itself).
• You can assume that the equalities will not contain an equality from a variable to itself, and that the same equality will not be given multiple times (this includes things like 1 = 2 and 2 = 1).
• You can assume that all integers given will be within your language's representable range.
• You can take the second input in any reasonable format.

Here are some reasonable formats:

0 = 2
0 = 3
1 = 0

{(0, 2), (0, 3), (1, 0)}

[0, 2, 0, 3, 1, 0]

0 2 0 3 1 0

Graph[{{0, 2}, {0, 3}, {1, 0}}]

[0 = 2, 0 = 3, 1 = 0]

• You can output in any reasonable format (i.e. set, list, etc.). Order is irrelevant.

Scoring

This is code-golf, so the shortest valid program (in bytes) wins.

Test Cases (0-indexed)

3, [1 = 2, 2 = 0], 1                      -> {0, 1, 2}
5, [0 = 2, 0 = 3, 1 = 2], 3               -> {0, 1, 2, 3}
6, [0 = 3, 1 = 3, 2 = 4, 5 = 1], 4        -> {2, 4}
6, [0 = 3, 1 = 3, 2 = 4, 5 = 1], 5        -> {0, 1, 3, 5}
5, [0 = 1, 2 = 0, 0 = 3, 4 = 0], 2        -> {0, 1, 2, 3, 4}
6, [0 = 1, 1 = 2, 2 = 3, 3 = 4, 4 = 5], 3 -> {0, 1, 2, 3, 4, 5}
4, [0 = 1, 1 = 2, 2 = 0], 3               -> {3}
5, [0 = 2, 2 = 4], 2                      -> {0, 2, 4}
8, [], 7                                  -> {7}

Test Cases (1-indexed)

3, [2 = 3, 3 = 1], 2                      -> {1, 2, 3}
5, [1 = 3, 1 = 4, 2 = 3], 4               -> {1, 2, 3, 4}
6, [1 = 4, 2 = 4, 3 = 5, 6 = 2], 5        -> {3, 5}
6, [1 = 4, 2 = 4, 3 = 5, 6 = 2], 6        -> {1, 2, 4, 6}
5, [1 = 2, 3 = 1, 1 = 4, 5 = 1], 3        -> {1, 2, 3, 4, 5}
6, [1 = 2, 2 = 3, 3 = 4, 4 = 5, 5 = 6], 4 -> {1, 2, 3, 4, 5, 6}
4, [1 = 2, 2 = 3, 3 = 1], 4               -> {4}
5, [1 = 3, 3 = 5], 3                      -> {1, 3, 5}
8, [], 8                                  -> {8}

Answer 1

Brachylog, 22 bytes

{tc⊇,?k.&¬(t∋;.xȮ)∧}ᶠt

Try it online!

Explanation

{tc⊇,?k.&¬(t∋;.xȮ)∧}ᶠt  Input is a pair, say [2,[[1,3],[2,4],[5,2]]]
{                   }ᶠ   Find all outputs of this predicate:
 t                        Tail: [[1,3],[2,4],[5,2]]
  c                       Concatenate: [1,3,2,4,5,2]
   ⊇                      Choose a subset: [4,5]
    ,?                    Append the input: [4,5,2,[[1,3],[2,4],[5,2]]]
      k                   Remove the last element: [4,5,2]
       .                  This list is the output.
        &¬(      )∧       Also, the following is not true:
           t∋              There is a pair P in the second part of the input.
             ;.x           If you remove from P those elements that occur in the output,
                Ȯ          the result is a one-element list.
                      t  Take the last one of these outputs, which is the shortest one.

Answer 2

Python 2, 65 63 bytes

^{-2 bytes thanks to ovs}

def f(e,s):b={s};exec"for p in e:b|=b&p and p\n"*len(e);print b

Try it online!

Answer 3

Pyth, 12 bytes

u|sf@TGQG.{E

Test suite.

Answer 4

Clean, 85 81 bytes

import StdEnv
$l=limit o iterate(\v=removeDup(flatten[v:filter(isAnyMember v)l]))

Try it online!

Defines the function $ :: [[Int]] -> ([Int] -> [Int])

Answer 5

Wolfram Language (Mathematica), 32 bytes

#~VertexComponent~#2~Check~{#2}&

Input format: {2<->3, 3<->1}, 3. It does not take the first input.

Try it online!

Answer 6

Jelly,  12   11  10 bytes

-1 thanks to Erik the Outgolfer (replace the atom œ& with f)

⁹fÐfȯFµÐLQ

A dyadic link accepting E on the left (as a list of length-two-lists) and S on the right (as an integer) returning a [de-duplicated] list.

Try it online! or see a test-suite.

How?

⁹fÐfȯFµÐLQ - Link: list of lists, E; integer S
      µÐL  - repeat the monadic chain to the left until a fixed point is reached:
  Ðf       -   (for each pair in E) filter keep if:
 f         -     filter discard if in
⁹          -     chain's right argument
           -     (originally [S], thereafter the previous result as monadic)
    ȯ      -   logical OR with implicit right
           -   (force first pass to become S if nothing was kept)
     F     -   flatten to a single list
           -   (S -> [S] / [[1,4],[1,0]]->[1,4,1,0] / etc...)
         Q - de-duplicate

Answer 7

Perl 5 -n0, 49 39 bytes

Give starting value on a line on STDIN followed by lines of pairs of equivalent numbers (or give the starting value last or in the middle or give multiple starting values, it all works)

#!/usr/bin/perl -n0
s/
$1? | $1/
/ while/^(\d+
)/msg;say//g

Try it online!

This can output an element in the result set multiple times. This 48 bytes variation outputs each equivalent element only once:

s/
$1? | $1/
/ while/^(\d+
)(?!.*^\1)/msg;say//g

Try it online!

Answer 8

Operation Flashpoint scripting language, 364 bytes

f={t=_this;r=t select 1;i=0;while{i<t select 0}do{call format["V%1=[%1]",i];i=i+1};i=0;while{i<count r}do{call format(["V%1=V%1+V%2;V%2=V%1"]+(r select i));i=i+1};l=call format["V%1",t select 2];g={i=0;c=count l;while{i<c}do{if(i<count l)then{e=l select i;call _this};i=i+1}};{l=l+call format["V%1",e]}call g;"l=l-[e]+[e];if(count l<c)then{c=count l;i=0}"call g;l}

Call with:

hint format
[
    "%1\n%2\n%3\n%4\n%5\n%6\n%7\n%8\n%9",
    [3, [[1, 2], [2, 0]], 1] call f,
    [5, [[0, 2], [0, 3], [1, 2]], 3] call f,
    [6, [[0, 3], [1, 3], [2, 4], [5, 1]], 4] call f,
    [6, [[0, 3], [1, 3], [2, 4], [5, 1]], 5] call f,
    [5, [[0, 1], [2, 0], [0, 3], [4, 0]], 2] call f,
    [6, [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]], 3] call f,
    [4, [[0, 1], [1, 2], [2, 0]], 3] call f,
    [5, [[0, 2], [2, 4]], 2] call f,
    [8, [], 7] call f
]

Output:

Unrolled:

f =
{
    t = _this;
    r = t select 1;
    i = 0;
    while {i < t select 0} do
    {
        call format["V%1=[%1]", i];
        i = i + 1
    };

    i = 0;
    while {i < count r} do
    {
        call format(["V%1=V%1+V%2;V%2=V%1"] + (r select i));
        i = i + 1
    };

    l = call format["V%1", t select 2];

    g =
    {
        i = 0;
        c = count l;
        while {i < c} do
        {
            if (i < count l) then
            {
                e = l select i;
                call _this
            };
            i = i + 1
        }
    };

    {l = l + call format["V%1", e]} call g;
    "l = l - [e] + [e];

    if (count l<c)then
    {
        c = count l;
        i = 0
    }" call g;

    l
}

Answer 9

Python 2, 53 bytes

e,s,n=input()
b={s}
for p in n*e:b|=b&p and p
print b

Try it online!

Same length as function:

lambda e,s,n:reduce(lambda b,p:b|(b&p and p),n*e,{s})

Try it online!

This is based off Rod's nice solution using the short-circuiting update b|=b&p and p. Taking the number of variables as an input n helps shorten the loop code.

Answer 10

K (ngn/k), 37 36 35 bytes

{&a[z]=a:{y[x]&:|y x;y}[+y,,&2]/!x}

Try it online!

{ } function with arguments x, y, and z representing N, E, and S respectively

!x is the list 0 1 ... x-1

&2 is the list 0 0

y,,&2 we add the pair 0 0 to y to avoid the special case of an empty y

+y,,&2 same thing transposed from a list of pairs to a pair of lists

{ }[+y,,&2] is a projection, i.e. a function in which x will be the value of +y,,&2 and y will be the argument passed in when calling the projection

|y x is y at indices x, reversed (|)

@[y;x;&;|y x] amend y at indices x by taking the minimum (&) of the existing element and an element from |y x

/ keep calling until convergence

a: assign to a

a[z]=z boolean mask of the elements of a equal to the z-th

& convert the boolean mask to a list of indices

Answer 11

Ruby, 39 bytes

->e,*s{e.map{e.map{|a|a-s!=a&&s|=a}};s}

Try it online!

Answer 12

Octave, 48 45 bytes

t=@(A,u)find(((eye(size(A))+A+A')^nnz(A))(u,:));

Takes input as "adjacency-matrix", for example uses [0 0 0; 0 0 1; 1 0 0] for [2 = 3, 3 = 1], try it online!

Explanation

First we construct the complete adjacency matrix for the transitive graph, using the sum of eye(size(A)) (elements are reflexive), A (input) and A' (the relation is symmetric).

We compute the transitive closure by computing the power to nnz(A) which suffices (nnz(A) is upper bound for a path's length), so from there all that's left is to get the right row with (u,:) and find all non-zero entries.

Answer 13

Python 2, 87 bytes

g,v=input();x={v};d=[v]
for c in d:x|={c};d+={k[k[0]==c]for k in g if c in k}-x
print x

Try it online!

Answer 14

Pari/GP, 80 bytes

f(g,p)=c=concat;if(p==q=c(c(p=Set(p),[e|e<-g,setintersect(Set(e),p)])),p,f(g,q))

Try it online!

Answer 15

JavaScript (ES6), 87 bytes

(a,n)=>a.map(([b,c])=>[...d[b]||[b],...d[c]||[c]].map((e,_,a)=>d[e]=a),d=[])&&d[n]||[n]

Deduplication would be possible using &&[...new Set(d[n]||[n])] at a cost of 14 bytes.