Przejściowa równość

16

Wyzwanie

Twój program powinien przyjąć 3 dane wejściowe:

  • Dodatnia liczba całkowita, która jest liczbą zmiennych,
  • Zestaw nieuporządkowanych par nieujemnych liczb całkowitych, gdzie każda para reprezentuje równość między zmiennymi, i
  • Dodatnia liczba całkowita reprezentująca zmienną początkową,

Powinien zwrócić zestaw nieujemnych liczb całkowitych, które reprezentują wszystkie zmienne, które mogą być tranzytowo równe zmiennej początkowej (w tym samej zmiennej początkowej).

Innymi słowy, wprowadzone dane N, Eoraz S, zwraca zestaw Q, tak że:

  • S ∈ Q.
  • Jeśli Z ∈ Qi (Y = Z) ∈ Ewtedy Y ∈ Q.
  • Jeśli Z ∈ Qi (Z = Y) ∈ Ewtedy Y ∈ Q.

Można to również wyrazić jako problem :

Biorąc pod uwagę niekierowany wykres i wierzchołek na wykresie, wypisz listę wierzchołków w jego połączonym składniku .

Dane techniczne

  • Możesz wybrać indeksowanie oparte na 0 lub na podstawie 1.
  • Pierwsze wejście zlicza liczbę obecnych zmiennych, przy czym zmienne są podawane jako liczby. Alternatywnie, nie możesz wziąć tych danych wejściowych, w którym to przypadku zakłada się, że jest on równy albo najwyższemu obecnemu indeksowi zmiennych, albo o jeden większy, w zależności od twojego schematu indeksowania.
  • Możesz założyć, że dane wejściowe są dobrze sformułowane: nie otrzymasz zmiennych poza zakresem określonym przez pierwsze dane wejściowe. Na przykład 3, [1 = 2, 2 = 0], 1jest poprawnym wejściem, a 4, [1 = 719, 1 = 2, 3 = 2], -3nie jest.
  • Nie można zakładać, że dowolna zmienna będzie z nią powiązana. Jeśli podano trzecie wejście, które jest „samotne” (nie ma równości), poprawnym wyjściem jest zestaw singletonów zawierający tylko to wejście (ponieważ jest ono równe sobie).
  • Możesz założyć, że równości nie będą zawierały równości między zmienną a samą, i że ta sama równość nie zostanie podana wiele razy (obejmuje to takie jak 1 = 2i 2 = 1).
  • Możesz założyć, że wszystkie podane liczby całkowite będą w reprezentatywnym zakresie dla twojego języka.
  • Drugie wejście możesz pobrać w dowolnym rozsądnym formacie.

Oto kilka rozsądnych formatów:

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]
  • Możesz wyprowadzać dane w dowolnym rozsądnym formacie (np. Zestaw, lista itp.). Porządek jest nieistotny.

Punktacja

To jest , więc wygrywa najkrótszy prawidłowy program (w bajtach).

Przypadki testowe (indeksowane 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}

Przypadki testowe (indeksowane 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}
Esolanging Fruit
źródło
Piaskownica
Esolanging Fruit
Czy możemy zrezygnować z pierwszego wkładu, jeśli chcemy? Myślę, że nie jest konieczne uzyskanie prawidłowego wyniku
dylnan
@dylnan "Pierwsze wejście zlicza liczbę obecnych zmiennych, przy czym zmienne są podawane jako liczby. Alternatywnie, nie możesz wziąć tych danych wejściowych, w którym to przypadku zakłada się, że jest on równy albo najwyższemu obecnemu indeksowi zmiennych, albo jednemu więcej niż to, w zależności od schematu indeksowania. ”(punkt 2 specyfikacji)
Esolanging Fruit
Przepraszam, czasami zapominam zakończyć czytanie
dylnan
Czy dane wyjściowe mogą zawierać duplikaty? (Mogę twierdzić, że reprezentuje zestaw ...)
Ton Hospel

Odpowiedzi:

7

Brachylog , 22 bajty

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

Wypróbuj online!

Wyjaśnienie

{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.
Zgarb
źródło
5

Python 2 , 65 63 bajtów

-2 bajty dzięki ovs

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

Wypróbuj online!

Pręt
źródło
2

Czysty , 85 81 bajtów

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

Wypróbuj online!

Definiuje funkcję $ :: [[Int]] -> ([Int] -> [Int])

Obrzydliwe
źródło
Ciekawy. Jak limitdziała
Esolanging Fruit
@EsolangingFruit pobiera listę, przyjmując, że jest nieskończona, i zwraca pierwszy element, który występuje dwa razy z rzędu.
obrzydliwe
1
Och, to wydaje się bardzo przydatne!
Esolanging Fruit
1

Operacja Flashpoint język skryptowy , 364 bajty

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}

Zadzwoń z:

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
]

Wynik:

wprowadź opis zdjęcia tutaj

Rozwinięty:

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
}
Steadybox
źródło
1

Python 2 , 53 bajty

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

Wypróbuj online!

Ta sama długość co funkcja:

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

Wypróbuj online!

Jest to oparte na dobrym rozwiązaniu Rod wykorzystującym aktualizację zwarciową b|=b&p and p. Przyjmowanie liczby zmiennych jako danych wejściowych npomaga skrócić kod pętli.

xnor
źródło
1

Galaretka ,  12   11  10 bajtów

-1 dzięki Eryka Outgolfer (zamiast atomu œ&z f)

⁹fÐfȯFµÐLQ

Dyadyczny link akceptujący Epo lewej stronie (jako lista długości dwóch list) i Spo prawej stronie (jako liczba całkowita) zwraca listę [zduplikowaną].

Wypróbuj online! lub zobacz zestaw testowy .

W jaki sposób?

⁹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
Jonathan Allan
źródło
œ&„S f” s zwracane wartości zawsze mają tę samą właściwość logiczną.
Erik the Outgolfer
1

Perl 5 -n0 , 49 39 bajtów

Podaj wartość początkową w wierszu na STDIN, a następnie wiersze par równoważnych liczb (lub podaj wartość początkową na końcu lub w środku lub podaj wiele wartości początkowych, wszystko działa)

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

Wypróbuj online!

Może to wygenerować element w zestawie wyników wiele razy. Ta 48-bajtowa odmiana generuje każdy równoważny element tylko raz:

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

Wypróbuj online!

Ton Hospel
źródło
1

K (ngn / k) , 37 36 35 bajtów

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

Wypróbuj online!

{ }funkcja z argumentami x, yi zreprezentująca N, Eoraz Sodpowiednio

!x to lista 0 1 ... x-1

&2 jest lista 0 0

y,,&2dodajemy parę, 0 0aby yuniknąć specjalnego przypadku pustegoy

+y,,&2 to samo przeniesiono z listy par na parę list

{ }[+y,,&2]jest rzutowaniem, tj. funkcją, w której xbędzie wartością argumentu przekazanego podczas wywoływania +y,,&2i ybędzie nim

|y xjest yna indeksach x, odwrócony ( |)

@[y;x;&;|y x]zmienić yna indeksach x, biorąc minimum (& ) z istniejącego elementu i elementu z|y x

/ dzwonić do konwergencji

a: przypisać do

a[z]=zmaska ​​boolowska elementów arównychz -tym

& przekonwertować maskę logiczną na listę indeksów

ngn
źródło
1

Oktawa , 48 45 bajtów

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

Pobiera dane wejściowe jako „macierz przylegania”, na przykład używa [0 0 0; 0 0 1; 1 0 0]do [2 = 3, 3 = 1], spróbuj online!

Wyjaśnienie

Najpierw konstruujemy pełną macierz przylegania dla grafu przechodniego, używając sumy eye(size(A))(elementy są zwrotne), A(wejściowej) i A'(relacja jest symetryczna).

Obliczamy zamknięcie przechodnie obliczając moc, do nnz(A)której wystarcza ( nnz(A)jest górną granicą długości ścieżki), więc stamtąd pozostaje tylko uzyskanie odpowiedniego wiersza (u,:)i findwszystkich niezerowych wpisów.

ბიმო
źródło
0

Pari / GP , 80 bajtów

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

Wypróbuj online!

alephalpha
źródło
0

JavaScript (ES6), 87 bajtów

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

Deduplikacja byłaby możliwa przy użyciu &&[...new Set(d[n]||[n])]kosztu 14 bajtów.

Neil
źródło