introduction

Dans ce défi, vous obtenez un graphique dirigé avec des boucles automatiques et votre tâche consiste à le convertir en un graphique non dirigé sans boucles automatiques.

Contribution

Votre entrée est un graphique dirigé avec un sommet défini {0, 1, ..., n-1}pour un certain nombre naturel n ≥ 0(ou {1, 2, ..., n}si vous utilisez une indexation basée sur 1). Le graphique est donné comme une nliste de longueurs Loù L[i]est une liste des voisins extérieurs du sommet i. Par exemple, la liste [[0,1],[0],[1,0,3],[]]représente le graphique

.-.
| v
'-0<--2-->3
  ^   |
  |   |
  v   |
  1<--'

Notez que les listes de voisins ne sont pas nécessairement ordonnées, mais elles sont garanties sans doublon.

Production

Votre sortie est un autre graphique au même format que l'entrée, obtenu à partir de celui-ci comme suit.

1. Supprimez toutes les boucles automatiques.
2. Pour chaque bord restant u -> v, ajoutez le bord inversé v -> us'il n'est pas déjà présent.

Comme pour l'entrée, les listes de voisins du graphique de sortie peuvent ne pas être triées, mais elles ne peuvent pas contenir de doublons. Pour le graphique ci-dessus, une sortie correcte serait [[1,2],[0,2],[0,1,3],[2]], qui représente le graphique

0<->2<->3
^   ^
|   |
v   |
1<--'

Règles

Vous pouvez utiliser l'indexation basée sur 0 ou basée sur 1 dans les graphiques. Les fonctions et les programmes complets sont acceptables. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites.

Cas de test

Ces cas de test utilisent une indexation basée sur 0; incrémenter chaque nombre dans le cas basé sur 1. Ces listes de voisins sont triées par ordre croissant, mais ce n'est pas obligatoire.

[] -> []
[[0]] -> [[]]
[[],[0,1]] -> [[1],[0]]
[[0,1],[]] -> [[1],[0]]
[[0,1],[0],[1,0,3],[]] -> [[1,2],[0,2],[0,1,3],[2]]
[[3],[],[5],[3],[1,3],[4]] -> [[3],[4],[5],[0,4],[1,3,5],[2,4]]
[[0,1],[6],[],[3],[3],[1],[4,2]] -> [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]]
[[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] -> [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]
[[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] -> [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
[[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] -> [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]

Pyth, 17 16 octets

.e-.|f}k@QTUQbkQ

Essayez-le en ligne: démonstration ou suite de tests

Explication

                   implicit: Q = input
.e             Q   enumerated mapping of Q (k index, b out-neighbors):
     f     UQ         filter [0, 1, ..., len(Q)-1] for elements T, which satisfy:
      }k@QT              k in Q[T]
                      # this are the in-neighbors
   .|        b        setwise union with b 
  -           k       remove k

CJam, 43 40 35 34 33 octets

2 octets enregistrés par Sp3000.

Cela a commencé comme une solution vraiment élégante, puis est devenu de plus en plus hideux alors que j'essayais de réparer certains trous que j'avais négligés. Je ne sais pas encore si l'idée originale est toujours récupérable, mais je ferai de mon mieux ...

q~_,,\ff{&W+0=)}_z..-{_,{;(},+}%`

Testez-le ici. Vous pouvez également exécuter l'intégralité du faisceau de test .

J'ajouterai une explication une fois que je suis sûr que le patient est mort.

Python 2, 107 octets

J'essaie toujours de savoir si je peux jouer au golf plus, mais pour l'instant, c'est le mieux que je puisse faire.

def u(g):e=enumerate;o=[set(_)-{i}for i,_ in e(g)];[o[j].add(i)for i,_ in e(o)for j in _];print map(list,o)

J'utilise des ensembles pour éviter les doublons; aussi, contrairement à list.remove(i), {S}-{i}ne génère pas d'erreur s'il in'est pas présent S.

Rubis, 78 octets

Enfin, certains utilisent les opérateurs de set de ruby ​​( [1,2]&[2]==[2]et [3,4,5]-[4]==[3,5]).

->k{n=k.size;n.times{|i|n.times{|j|(k[j]&[i])[0]&&k[i]=(k[i]<<j).uniq-[i]}};k}

ideone , y compris tous les cas de test, qu'il réussit.

CJam, 26 octets

l~_,,:T.-_T\ff&Tf.e&.|:e_p

Pas très court ...

Explication

l~                           e# Read the input.
  _,,:T                      e# Get the graph size and store in T.
       .-                    e# Remove self-loops from the original input.
         _T\ff&              e# Check if each vertex is in each list, and
                             e# return truthy if yes, or empty list if no.
               Tf.e&         e# Convert truthy to vertex numbers.
                    .|       e# Merge with the original graph.
                      :e_    e# Remove empty lists.
                         p   e# Format and print.

JavaScript (ES6), 96 110

Création d'ensembles d'adjacence à partir de la liste d'adjacence, ce qui permet d'éviter les doublons. Enfin, il reconstruit les listes à partir des ensembles.

//Golfed 
U=l=>
  l.map((m,n)=>m.map(a=>a-n?s[n][a]=s[a][n]=1:0),s=l.map(m=>[]))
  &&s.map(a=>[~~k for(k in a)])

// Ungolfed

undirect=(adList)=>(
  adSets=adList.map(_ => []),
  adList.forEach((curAdList,curNode)=>{
    curAdList.forEach(adNode=>{
      if (adNode!=curNode) {
        adSets[curNode][adNode]=1,
        adSets[adNode][curNode]=1
      }
    })  
  }),
  adSets.map(adSet=>[~~k for(k in adSet)])
)

// Test
out=s=>OUT.innerHTML+=s+'\n'

test=[
 [ [], [] ]
,[ [[0]], [[]] ]
,[ [[],[0,1]] , [[1],[0]] ]
,[ [[0,1],[]] , [[1],[0]] ]

,[ [[0,1],[0],[1,0,3],[]] , [[1,2],[0,2],[0,1,3],[2]] ]
,[ [[3],[],[5],[3],[1,3],[4]] , [[3],[4],[5],[0,4],[1,3,5],[2,4]] ]
,[ [[0,1],[6],[],[3],[3],[1],[4,2]] , [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]] ] 
,[ 
   [[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] ,
   [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]  
 ]
,[
  [[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] , 
  [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
 ]

,[
  [[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] ,
  [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],  [0,1,2,4,9],[0,3,5,6,7,8]]
 ]
] 

show=l=>'['+l.map(a=>'['+a+']').join(',')+']'

test.forEach(t => (
  r = U(t[0]),
  ck = show(r) == show(t[1]),           
  out('Test ' + (ck ? 'OK: ':'FAIL: ') + show(t[0])+' -> ' + 
      '\nResult: ' + show(r) + 
      '\nCheck : ' + show(t[1]) + '\n\n')
) )

<pre id=OUT></pre>

Java, 150

a->{int i=0,j,k=a.size();for(;i<k;a.get(i).remove((Object)i++))for(j=k;j-->0;)if(a.get(j).contains(i)&!a.get(i).contains(j))a.get(i).add(j);return a;}

Code étendu et exécutable:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function
public class C {
    static Function<List<List<Integer>>, List<List<Integer>>> f = a -> {
        int i = 0, j, k = a.size();
        for (; i < k; a.get(i).remove((Object) i++)) {
            for (j = k; j-- > 0;) {
                if (a.get(j).contains(i) & !a.get(i).contains(j)) {
                    a.get(i).add(j);
                }
            }
        }
        return a;
    };
    public static void main(String[] args) {
        System.out.println(f.apply(new ArrayList(Arrays.asList(
                new ArrayList(Arrays.asList(0, 1)),
                new ArrayList(Arrays.asList(1)),
                new ArrayList(Arrays.asList(1, 0, 3)),
                new ArrayList(Arrays.asList()))
        )));
    }
}

Groovy - 87

u={g->g.eachWithIndex{n,i->g[i]=n-i;g[i].each{g[it]<<i}};g.each{it=it.sort().unique()}}

Script complet pour exécuter les tests:

u={g->g.eachWithIndex{n,i->g[i]=n-i;g[i].each{g[it]<<i}};g.each{it=it.sort().unique()}}
assert u([]) == []
assert u([[0]]) == [[]]
assert u([[],[0,1]]) == [[1],[0]]
assert u([[0,1],[]]) == [[1],[0]]
assert u([[0,1],[0],[1,0,3],[]]) == [[1,2],[0,2],[0,1,3],[2]]
assert u([[3],[],[5],[3],[1,3],[4]]) == [[3],[4],[5],[0,4],[1,3,5],[2,4]]
assert u([[0,1],[6],[],[3],[3],[1],[4,2]]) == [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]]
assert u([[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]]) == [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]
assert u([[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]]) == [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
assert u([[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]]) == [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]

Mathematica, 84 66 64 octets

Utilisation de l'indexation basée sur 1.

MapIndexed[Union[#,First/@l~Position~Tr@#2]~Complement~#2&,l=#]&

Python 3, 127 octets

l=list;g=l(map(set,eval(input())))
for i in range(len(g)):
    for j in g[i]:g[j]=g[j]^g[j]&{j}|{i}
print(l(map(l,g)))

Essayez en ligne

Pas ma meilleure tentative ...