Le défi

Votre programme doit prendre 3 entrées:

Un entier positif qui est le nombre de variables,
Un ensemble de paires non ordonnées d'entiers non négatifs, où chaque paire représente une égalité entre les variables, et
Un entier positif qui représente la variable de départ,

Il doit renvoyer un ensemble d'entiers non négatifs qui représentent toutes les variables qui peuvent être montrées transitoirement égales à la variable de départ (y compris la variable de départ elle-même).

En d' autres termes, les entrées données N, Eet S, renvoyer un jeu Qtel que:

S ∈ Q.
Si Z ∈ Qet (Y = Z) ∈ Ealors Y ∈ Q.
Si Z ∈ Qet (Z = Y) ∈ Ealors Y ∈ Q.

Cela peut également être exprimé comme un problème de théorie des graphes :

Étant donné un graphique non orienté et un sommet dans le graphique, répertoriez les sommets dans son composant connecté .

Caractéristiques

Vous pouvez choisir d'utiliser l'indexation basée sur 0 ou basée sur 1.
La première entrée compte le nombre de variables présentes, où les variables sont données sous forme de nombres. Alternativement, vous ne pouvez pas prendre cette entrée, auquel cas elle est supposée être égale à l'indice variable le plus élevé présent, ou à un de plus, selon votre schéma d'indexation.
Vous pouvez supposer que l'entrée est bien formée: vous ne recevrez pas de variables en dehors de la plage spécifiée par la première entrée. Par exemple, 3, [1 = 2, 2 = 0], 1est une entrée valide, tandis que ce 4, [1 = 719, 1 = 2, 3 = 2], -3n'est pas le cas.
Vous ne pouvez pas supposer qu'une variable sera associée à des égalités. Si une troisième entrée est "solitaire" (sans égalité), la sortie correcte est un ensemble singleton contenant uniquement cette entrée (car elle est égale à elle-même).
Vous pouvez supposer que les égalités ne contiendront pas une égalité d'une variable à elle-même, et que la même égalité ne sera pas donnée plusieurs fois (cela inclut des choses comme 1 = 2et 2 = 1).
Vous pouvez supposer que tous les entiers donnés seront dans la plage représentable de votre langue.
Vous pouvez prendre la deuxième entrée dans n'importe quel format raisonnable.

Voici quelques formats raisonnables:

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]

Vous pouvez produire dans n'importe quel format raisonnable (c.-à-d. Ensemble, liste, etc.). L'ordre n'est pas pertinent.

Notation

Il s'agit de code-golf , donc le programme valide le plus court (en octets) l'emporte.

Cas de test (indexés 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}

Cas de test (1 indexé)

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}

code-golf graph-theory equation Esolanging Fruit
la source

Sandbox

Esolanging Fruit

Pouvons-nous renoncer à prendre la première entrée si nous le désirons? Je pense qu'il n'est pas nécessaire d'obtenir la sortie correcte

dylnan

@dylnan "La première entrée compte le nombre de variables présentes, où les variables sont données sous forme de nombres. Alternativement, vous ne pouvez pas prendre cette entrée, auquel cas elle est supposée être égale à l'indice de variable le plus élevé présent, ou à un plus que cela, en fonction de votre schéma d'indexation. "(point 2 de la spécification)

Esolanging Fruit

Désolé parfois j'oublie de terminer la lecture

dylnan

La sortie peut-elle contenir des doublons? (Je peux affirmer que cela représente un ensemble ...)

Ton Hospel

7

Brachylog , 22 octets

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

Essayez-le en ligne!

Explication

{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
la source

5

Python 2 , 65 63 octets

^{-2 octets grâce aux ovs}

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

Essayez-le en ligne!

Barre
la source

2

Pyth , 12 octets

u|sf@TGQG.{E

Suite de tests.

Leaky Nun
la source

2

Nettoyer , 85 81 octets

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

Essayez-le en ligne!

Définit la fonction $ :: [[Int]] -> ([Int] -> [Int])

Οurous
la source

Intéressant. Comment ça limitmarche?

Esolanging Fruit

@EsolangingFruit prend une liste, supposée infinie, et retourne le premier élément qui se produit deux fois de suite.

Οurous

1

Oh, cela semble très utile!

Esolanging Fruit

1

Wolfram Language (Mathematica) , 32 octets

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

Format d' entrée: {2<->3, 3<->1}, 3. Il ne prend pas la première entrée.

Essayez-le en ligne!

alephalpha
la source

1

Langage de script Operation Flashpoint , 364 octets

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}

Appeler avec:

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
]

Production:

Déroulé:

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
la source

1

Python 2 , 53 octets

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

Essayez-le en ligne!

Même longueur que la fonction:

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

Essayez-le en ligne!

Ceci est basé sur la belle solution de Rod utilisant la mise à jour de court-circuit b|=b&p and p. Prendre le nombre de variables en entrée npermet de raccourcir le code de boucle.

xnor
la source

1

Gelée , 12 11 10 octets

-1 grâce à Erik l'Outgolfer (remplacez l'atome œ&par f)

⁹fÐfȯFµÐLQ

Un lien dyadique acceptant Eà gauche (comme une liste de deux listes de longueur) et Sà droite (comme un entier) renvoyant une liste [dédoublonnée].

Essayez-le en ligne! ou voir une suite de tests .

Comment?

⁹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
la source

œ&Les fvaleurs de retour de et ont toujours la même propriété booléenne.

Erik the Outgolfer

1

Perl 5 `-n0` , 49 39 octets

Donnez la valeur de départ sur une ligne sur STDIN suivie de lignes de paires de nombres équivalents (ou donnez la valeur de départ en dernier ou au milieu ou donnez plusieurs valeurs de départ, tout fonctionne)

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

Essayez-le en ligne!

Cela peut produire un élément dans le jeu de résultats plusieurs fois. Cette variation de 48 octets ne renvoie chaque élément équivalent qu'une seule fois:

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

Essayez-le en ligne!

Ton Hospel
la source

1

Rubis , 39 octets

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

Essayez-le en ligne!

GB
la source

1

K (ngn / k) , 37 36 35 octets

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

Essayez-le en ligne!

{ }fonction avec des arguments x, y, et zreprésentant N, EetS respectivement

!x est la liste 0 1 ... x-1

&2 est la liste 0 0

y,,&2nous ajoutons la paire 0 0pour yéviter le cas particulier d'un videy

+y,,&2 même chose transposée d'une liste de paires à une paire de listes

{ }[+y,,&2]est une projection, c'est-à-dire une fonction dans laquelle xsera la valeur de +y,,&2ety sera l'argument passé lors de l'appel de la projection

|y xest yaux indices x, inversé (| )

@[y;x;&;|y x]modifier les yindices xen prenant le minimum (& ) de l'élément existant et un élément de|y x

/ Continuez à appeler jusqu'à la convergence

a: assigner à un

a[z]=zmasque booléen des éléments aégaux au z-ième

& convertir le masque booléen en une liste d'indices

ngn
la source

1

Octave , 48 45 octets

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

Prend l'entrée comme "matrice d'adjacence", par exemple utilise [0 0 0; 0 0 1; 1 0 0]pour [2 = 3, 3 = 1], essayez-le en ligne!

Explication

Nous construisons d'abord la matrice d'adjacence complète pour le graphe transitif, en utilisant la somme de eye(size(A))(les éléments sont réflexifs), A(entrée) etA' (la relation est symétrique).

Nous calculons la fermeture transitive en calculant la puissance à nnz(A)laquelle suffit ( nnz(A)est la limite supérieure de la longueur d'un chemin), donc à partir de là, tout ce qui reste est d'obtenir la ligne de droite avec (u,:)et findtoutes les entrées non nulles.

ბიმო
la source

0

Python 2 , 87 octets

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

Essayez-le en ligne!

ovs
la source

0

Pari / GP , 80 octets

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

Essayez-le en ligne!

alephalpha
la source

0

JavaScript (ES6), 87 octets

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

La déduplication serait possible en utilisant &&[...new Set(d[n]||[n])]un coût de 14 octets.

Neil
la source

Égalité Transitive

Le défi

Caractéristiques

Notation

Cas de test (indexés 0)

Cas de test (1 indexé)

Réponses:

Brachylog , 22 octets

Explication

Python 2 , 65 63 octets

Pyth , 12 octets

Nettoyer , 85 81 octets

Wolfram Language (Mathematica) , 32 octets

Langage de script Operation Flashpoint , 364 octets

Python 2 , 53 octets

Gelée , 12 11 10 octets

Comment?

Perl 5 `-n0` , 49 39 octets

Rubis , 39 octets

K (ngn / k) , 37 36 35 octets

Octave , 48 45 octets

Explication

Python 2 , 87 octets

Pari / GP , 80 octets

JavaScript (ES6), 87 octets

Égalité Transitive

Le défi

Caractéristiques

Notation

Cas de test (indexés 0)

Cas de test (1 indexé)

Réponses:

Brachylog , 22 octets

Explication

Python 2 , 65 63 octets

Pyth , 12 octets

Nettoyer , 85 81 octets

Wolfram Language (Mathematica) , 32 octets

Langage de script Operation Flashpoint , 364 octets

Python 2 , 53 octets

Gelée , 12 11 10 octets

Comment?

Perl 5 -n0 , 49 39 octets

Rubis , 39 octets

K (ngn / k) , 37 36 35 octets

Octave , 48 45 octets

Explication

Python 2 , 87 octets

Pari / GP , 80 octets

JavaScript (ES6), 87 octets

Perl 5 `-n0` , 49 39 octets