16
\$\begingroup\$

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 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 , 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}
\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – Esolanging Fruit Mar 15 '18 at 15:59
  • \$\begingroup\$ Can we forgo taking the first input if we desire? I think it's not necessary to get the correct output \$\endgroup\$ – dylnan Mar 15 '18 at 16:06
  • \$\begingroup\$ @dylnan "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." (point 2 of the spec) \$\endgroup\$ – Esolanging Fruit Mar 15 '18 at 16:07
  • \$\begingroup\$ Sorry sometimes I forget to finish reading \$\endgroup\$ – dylnan Mar 15 '18 at 16:28
  • \$\begingroup\$ May the output contain duplicates ? (I can claim it represents a set...) \$\endgroup\$ – Ton Hospel Mar 15 '18 at 22:36

15 Answers 15

7
\$\begingroup\$

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

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!

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

Pyth, 12 bytes

u|sf@TGQG.{E

Test suite.

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

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

\$\endgroup\$
  • \$\begingroup\$ Interesting. How does limit work? \$\endgroup\$ – Esolanging Fruit Mar 16 '18 at 23:18
  • \$\begingroup\$ @EsolangingFruit it takes a list, assumed to be infinite, and returns the first element that occurs twice in a row. \$\endgroup\$ – Οurous Mar 16 '18 at 23:46
  • 1
    \$\begingroup\$ Oh, that seems very useful! \$\endgroup\$ – Esolanging Fruit Mar 16 '18 at 23:59
1
\$\begingroup\$

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!

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

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:

enter image description here

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

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ œ&'s and f's return values always have the same boolean property. \$\endgroup\$ – Erik the Outgolfer Mar 15 '18 at 21:21
1
\$\begingroup\$

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!

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

Ruby, 39 bytes

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

Try it online!

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

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

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

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.

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

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!

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

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!

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

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.

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