Соревнование

Ваша программа должна принимать 3 входа:

• Целое положительное число, которое является числом переменных,
• Набор неупорядоченных пар неотрицательных целых чисел, где каждая пара представляет равенство между переменными, и
• Положительное целое число, которое представляет начальную переменную,

Он должен возвращать набор неотрицательных целых чисел, которые представляют все переменные, которые могут быть показаны транзитивно равными начальной переменной (включая саму начальную переменную).

Другими словами, учитывая входные данные N, Eи S, возвращают набор Q, такой что:

• S ∈ Q,
• Если Z ∈ Qи (Y = Z) ∈ Eтогда Y ∈ Q.
• Если Z ∈ Qи (Z = Y) ∈ Eтогда Y ∈ Q.

Это также может быть выражено как проблема теории графов :

Учитывая неориентированный граф и вершину в графе, перечислите вершины в его связанном компоненте .

Характеристики

• Вы можете выбрать индексирование на основе 0 или 1.
• Первый вход подсчитывает количество присутствующих переменных, где переменные задаются в виде чисел. В качестве альтернативы, вы не можете принимать эти входные данные, и в этом случае предполагается, что они равны либо максимальному значению присутствующего индекса, либо еще одному, в зависимости от вашей схемы индексации.
• Вы можете предположить, что вход правильно сформирован: вам не будут заданы переменные вне диапазона, указанного в первом входе. Например, 3, [1 = 2, 2 = 0], 1является допустимым входом, а 4, [1 = 719, 1 = 2, 3 = 2], -3нет.
• Вы не можете предполагать, что любая переменная будет иметь какие-либо равенства, связанные с ней. Если дан третий вход, который является «одиноким» (не имеет равенств), правильным выходом будет одноэлементное множество, содержащее только этот вход (так как он равен самому себе).
• Вы можете предположить, что равенства не будут содержать равенства от переменной к себе, и что одно и то же равенство не будет дано несколько раз (это включает в себя такие вещи, как 1 = 2и 2 = 1).
• Вы можете предположить, что все заданные целые числа будут в пределах представимого диапазона вашего языка.
• Вы можете взять второй вход в любом разумном формате.

Вот несколько разумных форматов:

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]

• Вы можете выводить в любом разумном формате (например, набор, список и т. Д.). Заказ не имеет значения.

счет

Это код-гольф , поэтому выигрывает самая короткая действительная программа (в байтах).

Тестовые случаи (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}

Тестовые случаи (1-индексированные)

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}

Брахилог , 22 байта

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

Попробуйте онлайн!

объяснение

{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 байта

^{-2 байта благодаря овсу}

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

Попробуйте онлайн!

Pyth , 12 байт

u|sf@TGQG.{E

Тестирование.

Чистый , 85 81 байт

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

Попробуйте онлайн!

Определяет функцию $ :: [[Int]] -> ([Int] -> [Int])

Wolfram Language (Mathematica) , 32 байта

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

Формат ввода: {2<->3, 3<->1}, 3. Это не займет первый вход.

Попробуйте онлайн!

Язык сценариев работы Flashpoint , 364 байта

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}

Звоните с:

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
]

Выход:

раскатали:

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 байта

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

Попробуйте онлайн!

Та же самая длина как функция:

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

Попробуйте онлайн!

Это основано на хорошем решении Рода, использующем обновление с коротким замыканием b|=b&p and p. Взятие числа переменных в качестве входных данных nпомогает сократить код цикла.

Желе ,  12   11  10 байт

-1 благодаря Эрику Гольфисту (замените атом œ&на f)

⁹fÐfȯFµÐLQ

Двоичная ссылка принимает Eслева (в виде списка из списков длины два) и Sсправа (в виде целого числа), возвращая [дедуплицированный] список.

Попробуйте онлайн! или посмотрите набор тестов .

Как?

⁹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 байт

Задать начальное значение в строке на STDIN, за которой следуют строки пар эквивалентных чисел (или дать начальное значение последним или посередине, или дать несколько начальных значений, все это работает)

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

Попробуйте онлайн!

Это может вывести элемент в наборе результатов несколько раз. Это 48-байтовое изменение выводит каждый эквивалентный элемент только один раз:

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

Попробуйте онлайн!

Рубин , 39 байт

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

Попробуйте онлайн!

K (нгн / к) , 37 36 35 байт

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

Попробуйте онлайн!

{ }функция с аргументами x, yи zпредставляя N,E и Sсоответственно

!x список 0 1 ... х-1

&2 это список 0 0

y,,&2мы добавляем пару 0 0кy избежать особого случая пустогоy

+y,,&2 то же самое перенесено из списка пар в пару списков

{ }[+y,,&2]является проекцией, то есть функцией, в которой xбудет значение +y,,&2иy будет аргумент, переданный при вызове проекции

|y xнаходится yв индексах x, негативы (| )

@[y;x;&;|y x]изменить yпо индексам x, взяв минимум (& ) существующего элемента и элемента из|y x

/ продолжайте звонить до схождения

a: назначить на

a[z]=zлогическая маска элементов, aравных z-ому

& преобразовать логическую маску в список индексов

Октава , 48 45 байт

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

Принимает ввод как "матрицу смежности", например, использует [0 0 0; 0 0 1; 1 0 0]для [2 = 3, 3 = 1], попробуйте это онлайн!

объяснение

Сначала мы построим полную матрицу смежности для транзитивного графа, используя сумму eye(size(A))(элементы рефлексивны), A(входные) иA' (отношение симметрично).

Вычислит транзитивное замыкание путем вычисления силы nnz(A)которой хватает ( nnz(A)это верхняя границы для длины для пути), поэтому оттуда все , что осталось, чтобы получить нужную строку с (u,:)и findвсеми ненулевых элементами.

Python 2 , 87 байт

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

Попробуйте онлайн!

Пари / ГП , 80 байт

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

Попробуйте онлайн!

JavaScript (ES6), 87 байт

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

Дедупликация была бы возможна с использованием &&[...new Set(d[n]||[n])]14 байтов.