Honnêtement, je ne peux pas croire que cela n'ait pas déjà été demandé, mais ici c'est

Contexte

Étant donné un simple plan non orienté graphique (le graphique peut être dessiné dans le plan sans intersections), il est prouvé que le graphique est quadri-colorable, un terme que nous explorerons un peu. Cependant, il est beaucoup plus facile de tracer un graphique en 5 couleurs, sur lequel nous concentrerons notre défi aujourd'hui.

Une coloration k valide d'un graphe est une affectation de "couleurs" aux nœuds du graphe avec les propriétés suivantes

1. Si deux nœuds sont reliés par une arête, les nœuds sont colorés avec des couleurs différentes.
2. Sur le graphique, il y a un maximum de 5 couleurs.

Compte tenu de cela, je vais vous présenter un algorithme assez basique pour colorier n'importe quel graphe planaire simple non dirigé. Cet algorithme nécessite les définitions suivantes

Accessibilité : si le nœud 1 est accessible à partir du nœud 2, cela signifie qu'il existe une séquence de nœuds, chacun connecté au suivant par un bord, de sorte que le premier nœud est le nœud 2 et le dernier est le nœud 1. Notez que, puisque les graphiques non orientés sont symétriques, si le nœud 1 est accessible à partir du nœud 2, le nœud 2 est accessible à partir du nœud 1.

Sous-graphique -graphe: un sous-graphe d'un graphe d'un ensemble donné de nœuds N est un graphe où les nœuds du sous-graphe sont tous en N, et une arête du graphe d'origine est dans le sous-graphe si et seulement si les deux nœuds sont connectés par l'arête sont en N.

Soit Color (N) une fonction pour colorer des graphes planaires à N nœuds à 5 couleurs. Nous définissons la fonction ci-dessous

1. Trouvez le nœud avec le moins de nœuds connectés. Ce nœud aura au plus 5 nœuds connectés.
2. Supprimez ce nœud du graphique.
3. Appelez Couleur (N-1) sur ce nouveau graphique pour le colorer.
4. Ajoutez le nœud supprimé au graphique.
5. Si possible, coloriez le nœud ajouté d'une couleur qu'aucun de ses nœuds connectés n'a.
6. Si ce n'est pas possible, alors les 5 nœuds voisins du nœud ajouté ont 5 couleurs différentes, nous devons donc essayer le processus suivant.
7. Numéroter les nœuds entourant le nœud ajouté n1 ... n5
8. Considérez le sous-graphique de tous les nœuds du graphique d'origine coloré de la même couleur que n1 ou n3.
9. Si dans ce sous-graphique, n3 n'est pas accessible à partir de n1, dans l'ensemble de nœuds accessibles à partir de n1 (y compris n1), remplacez toutes les occurrences de la couleur de n1 par n3 et vice versa. Colorez maintenant la couleur d'origine du nœud ajouté n1.
10. Si n3 était accessible à partir de n1 dans ce nouveau graphique, effectuez le processus à partir de l'étape 9 sur les nœuds n2 et n4, plutôt que n1 et n3.

Défi

Étant donné l'entrée d'une liste edgelist (représentant un graphique), coloriez le graphique, en attribuant à chaque nœud une valeur.

Entrée : une liste des bords du graphique (c.-à-d. [('a','b'),('b','c')...])

Notez que la liste de bord d'entrée sera telle que si (a, b) se trouve dans la liste, (b, a) ne se trouve PAS dans la liste.

Sortie : un objet contenant des paires de valeurs, où le premier élément de chaque paire est un nœud et le second sa couleur, c'est-à-dire, [('a',1),('b',2)...]ou{'a':1,'b':2,...}

Vous pouvez utiliser n'importe quoi pour représenter les couleurs, des nombres aux caractères, en passant par autre chose.

L'entrée et la sortie sont assez flexibles, tant qu'il est assez clair quelles sont les entrées et les sorties.

Règles

• C'est un défi de code-golf
• Vous n'êtes pas obligé d'utiliser l'algorithme que j'ai décrit ci-dessus. Il est simplement là pour référence.
• Pour tout graphique, il existe souvent de nombreuses méthodes valides pour les colorer. Tant que la coloration produite par votre algorithme est valide, cela est acceptable.
• N'oubliez pas que le graphique doit être en 5 couleurs.

Cas de test

Utilisez le code suivant pour tester la validité de vos résultats de coloration. Comme il existe de nombreuses couleurs de graphique valides par graphique, cet algorithme vérifie simplement la validité de la coloration. Voir la docstring pour voir comment utiliser le code.

Quelques cas de test aléatoires (et plutôt stupides) :

Cas de test 2: Krackhardt Kite Graph [(0, 1), (0, 2), (0, 3), (0, 5), (1, 3), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6), (5, 7), (6, 7), (7, 8), (8, 9)]

Une sortie valide: {0: 4, 1: 3, 2: 3, 3: 2, 4: 4, 5: 1, 6: 0, 7: 4, 8: 3, 9: 4}

Remarque : Ces cas de test sont trop petits pour tester le comportement plus nuancé de l'algorithme de coloration, donc la construction de vos propres graphiques est probablement un bon test de la validité de votre travail.

Remarque 2 : je vais ajouter un autre morceau de code qui représentera bientôt votre solution de coloration.

Remarque 3 : Je n'ai pas prévu les algorithmes de coloration aléatoire qui ont été présentés, ce qui est si cool avec PPCG! Cependant, si quelqu'un pouvait jouer à un algorithme plus déterministe, ce serait très cool aussi.

Python 2 , 96 octets

i=0
g=input()
while 1:i+=1;c={k:i/4**k%4for k in sum(g,())};all(c[s]^c[t]for s,t in g)>0<exit(c)

Essayez-le en ligne!

$g$$i$$c$$c$$c$ est une coloration valide.

L'entrée est planaire, il est donc toujours possible de trouver une coloration 4.

(Ainsi: cela trouve la coloration lexicographiquement la plus ancienne dans un sens, et le fait de manière très inefficace.)

$k$$\Big\lfloor \frac{i}{4^k} \Big\rfloor \bmod 4$$k$$i$

JavaScript (ES7), 80 76 74 octets

Sauvegardé 2 octets grâce à @Neil

Même approche que Lynn . Résout en 4 couleurs, numérotées de 0 à 3 .

a=>{for(x=0;a.some(a=>a.map(n=>z=c[n]=x>>n*2&3)[0]==z,c={});x++);return c}

Essayez-le en ligne!

Brachylog , 38 octets

cd{∧4>ℕ}ᶻ.g;?z{tT&h⊇ĊzZhpT∧Zt≠}ᵐ∧.tᵐ≜∧

Essayez-le en ligne!

Explication

Example input: [["a","b"],["c","b"]]

cd                                       Concatenate and remove duplicates: ["a","b","c"]
  {∧4>ℕ}ᶻ.                               The output is this list zipped zith integers that
                                           are in [0..4]: [["a",I],["b",J],["c",K]]
         .g;?z                           Zip the output with the input:
                                           [[[["a",I],["b",J],["c",K]],["a","b"]],[["a",I],["b",J],["c",K]],["c","b"]]
              {               }ᵐ∧        Map for each element
               tT                        Call T the couple of nodes denoting an edge
                 &h⊇Ċ                    Take a subset of 2 elements in the head
                     zZ                  Zip and call it Z
                      ZhpT               The nodes in Z are T up to a permutation
                          ∧Zt≠           The integers in Z are all different color
                                 .tᵐ≜∧   Label the integers (i.e. colors) in the output so that
                                           it matches the set constraints

Python 2 , 211 octets

def f(g):
 g={k:[(a,b)[a==k]for a,b in g if k in(a,b)]for k in sum(g,())};c={k:0 for k in g}
 for a,b in sorted(g.iteritems(),key=lambda a:len(a[1])):c={k:(c[k],c[k]+1)[c[a]==c[k]and k in b]for k in c}
 return c

Essayez-le en ligne!

Déterministe! Échouerait probablement sur des cas de test plus compliqués, mais je suis trop épuisé pour trouver un graphique pour lequel il échoue. Plus de cas de test et. Ou critique bienvenus!

Nettoyer , 139 octets

import StdEnv,Data.List
$l#(a,b)=unzip l
#e=nub(a++b)
=hd[zip2 e c\\c<- ?e|all(\(a,b)=c!!a<>c!!b)l]
?[h:t]=[[n:m]\\n<-[0..4],m<- ?t]
?e=[e]

Essayez-le en ligne!

Génère toutes les colorations et renvoie la première valide.

Gelée , 23 octets

®iⱮⱮ³¤ịE€S
FQ©L4ṗÇÐḟḢ®ż

Essayez-le en ligne!

Force brute. Suppose que les nœuds sont étiquetés par des entiers.