El reto

Su programa debe tomar 3 entradas:

• Un entero positivo que es el número de variables,
• Un conjunto de pares no ordenados de enteros no negativos, donde cada par representa una igualdad entre variables, y
• Un entero positivo que representa la variable inicial,

Debería devolver un conjunto de enteros no negativos que representan todas las variables que pueden ser transitivamente iguales a la variable inicial (incluida la propia variable inicial).

En otras palabras, entradas dadas N, Ey S, devolver un conjunto Q, de tal manera que:

• S ∈ Q.
• Si Z ∈ Qy (Y = Z) ∈ E, entonces Y ∈ Q.
• Si Z ∈ Qy (Z = Y) ∈ E, entonces Y ∈ Q.

Esto también se puede expresar como un problema de teoría de grafos :

Dado un gráfico no dirigido y un vértice en el gráfico, enumere los vértices en su componente conectado .

Especificaciones

• Puede elegir usar indexación basada en 0 o en 1.
• La primera entrada cuenta el número de variables que están presentes, donde las variables se dan como números. Alternativamente, no puede tomar esta entrada, en cuyo caso se supone que es igual al índice variable más alto presente, o uno más, dependiendo de su esquema de indexación.
• Puede suponer que la entrada está bien formada: no se le darán variables fuera del rango especificado por la primera entrada. Por ejemplo, 3, [1 = 2, 2 = 0], 1es una entrada válida, mientras 4, [1 = 719, 1 = 2, 3 = 2], -3que no lo es.
• No puede suponer que ninguna variable tendrá ninguna igualdad asociada con ella. Si se le da una tercera entrada que es "solitaria" (no tiene igualdades), la salida correcta es un conjunto singleton que contiene solo esa entrada (ya que es igual a sí misma).
• Puede suponer que las igualdades no contendrán una igualdad de una variable a sí misma, y ​​que la misma igualdad no se dará varias veces (esto incluye cosas como 1 = 2y 2 = 1).
• Puede suponer que todos los enteros dados estarán dentro del rango representable de su idioma.
• Puede tomar la segunda entrada en cualquier formato razonable.

Aquí hay algunos formatos razonables:

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]

• Puede imprimir en cualquier formato razonable (es decir, conjunto, lista, etc.). El orden es irrelevante.

Puntuación

Este es el código de golf , por lo que gana el programa válido más corto (en bytes).

Casos de prueba (indexados 0)

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}

Casos de prueba (1 indexado)

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}

Brachylog , 22 bytes

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

Pruébalo en línea!

Explicación

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

Python 2 , 65 63 bytes

^{-2 bytes gracias a ovs}

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

Pruébalo en línea!

Pyth , 12 bytes

u|sf@TGQG.{E

Banco de pruebas.

Limpio , 85 81 bytes

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

Pruébalo en línea!

Define la función $ :: [[Int]] -> ([Int] -> [Int])

Wolfram Language (Mathematica) , 32 bytes

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

Formato de entrada: {2<->3, 3<->1}, 3. No toma la primera entrada.

Pruébalo en línea!

Lenguaje de script Operation Flashpoint , 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}

Llamar con:

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
]

Salida:

Desenrollado:

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
}

Python 2 , 53 bytes

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

Pruébalo en línea!

Misma longitud que la función:

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

Pruébalo en línea!

Esto se basa en la buena solución de Rod usando la actualización de cortocircuito b|=b&p and p. Tomar el número de variables como entrada nayuda a acortar el código del bucle.

Jalea ,  12   11  10 bytes

-1 gracias a Erik the Outgolfer (reemplaza el átomo œ&con f)

⁹fÐfȯFµÐLQ

Un enlace diádico que acepta Ea la izquierda (como una lista de dos listas de longitud) y Sa la derecha (como un entero) que devuelve una lista [deduplicada].

Pruébalo en línea! o ver un conjunto de pruebas .

¿Cómo?

⁹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

Perl 5 -n0 , 49 39 bytes

Dé el valor inicial en una línea en STDIN seguido de líneas de pares de números equivalentes (o dé el valor inicial al final o en el medio o dé varios valores iniciales, todo funciona)

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

Pruébalo en línea!

Esto puede generar un elemento en el conjunto de resultados varias veces. Esta variación de 48 bytes genera cada elemento equivalente solo una vez:

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

Pruébalo en línea!

Rubí , 39 bytes

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

Pruébalo en línea!

K (ngn / k) , 37 36 35 bytes

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

Pruébalo en línea!

{ }función con argumentos x, yy zque representa N, EyS respectivamente

!x es la lista 0 1 ... x-1

&2 es la lista 0 0

y,,&2agregamos el par 0 0ay evitar el caso especial de un vacíoy

+y,,&2 lo mismo transpuesto de una lista de pares a un par de listas

{ }[+y,,&2]es una proyección, es decir, una función en la que xserá el valor de +y,,&2yy será el argumento pasado al llamar a la proyección

|y xestá yen índices x, invertido (| )

@[y;x;&;|y x]enmendar yen los índicesx tomando el mínimo ( &) del elemento existente y un elemento de|y x

/ sigue llamando hasta la convergencia

a: asignar a un

a[z]=zmáscara booleana de los elementos de aigual a laz enésima

& convierte la máscara booleana en una lista de índices

Octava , 48 45 bytes

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

Toma la entrada como "matriz de adyacencia", por ejemplo utiliza [0 0 0; 0 0 1; 1 0 0]para [2 = 3, 3 = 1], pruébelo en línea!

Explicación

Primero construimos la matriz de adyacencia completa para el gráfico transitivo, usando la suma de eye(size(A))(los elementos son reflexivos), A(input) yA' (la relación es simétrica).

Calculamos la clausura transitiva mediante el cálculo de la potencia a nnz(A)la que basta ( nnz(A)es cota superior para la longitud de un camino), por lo que a partir de ahí todo lo que queda es conseguir la fila derecha con (u,:)y findtodas las entradas que no son cero.

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

Pruébalo en línea!

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

Pruébalo en línea!

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]

La desduplicación sería posible con &&[...new Set(d[n]||[n])]un costo de 14 bytes.