Szczerze mówiąc, nie mogę uwierzyć, że nie zostało to już zadane, ale oto jest

tło

Biorąc pod uwagę prosty, nieukierunkowany planarny (wykres można narysować w płaszczyźnie bez przecięć), jest to udowodnione twierdzenie, że wykres można pokolorować na 4 kolory, termin ten zbadamy za chwilę. Znacznie łatwiej jest jednak 5-kolorowy wykres, na którym dziś skoncentrujemy nasze wyzwanie.

Prawidłowe k-kolorowanie wykresu to przypisanie „kolorów” do węzłów wykresu o następujących właściwościach

1. Jeśli dwa węzły są połączone krawędzią, węzły są kolorowe w różnych kolorach.
2. Na całym wykresie znajduje się maksymalnie 5 kolorów.

Biorąc to pod uwagę, przedstawię ci dość prosty algorytm do 5-kolorowego dowolnego prostego nieukierunkowanego wykresu płaskiego. Ten algorytm wymaga następujących definicji

Osiągalność : jeśli węzeł 1 jest osiągalny z węzła 2, oznacza to, że istnieje sekwencja węzłów, z których każdy jest połączony krawędzią, tak że pierwszy węzeł to węzeł 2, a ostatni to węzeł 1. Uwaga: ponieważ wykresy niekierowane są symetryczne, jeśli węzeł 1 jest osiągalny z węzła 2, węzeł 2 jest osiągalny z węzła 1.

Podgraf : Podgraf wykresu danego zestawu węzłów N jest wykresem, w którym wszystkie węzły podgrafatu znajdują się w N, a krawędź oryginalnego wykresu znajduje się w podgrafie tylko wtedy, gdy oba węzły są połączone krawędzią są w N.

Niech Kolor (N) będzie funkcją kolorowania płaskich wykresów za pomocą N węzłów o 5 kolorach. Definiujemy funkcję poniżej

1. Znajdź węzeł z najmniejszą liczbą podłączonych do niego węzłów. Ten węzeł będzie miał maksymalnie 5 połączonych z nim węzłów.
2. Usuń ten węzeł z wykresu.
3. Zadzwoń do Color (N-1) na tym nowym wykresie, aby go pokolorować.
4. Dodaj usunięty węzeł z powrotem do wykresu.
5. Jeśli to możliwe, pokoloruj dodany węzeł kolorem, którego nie ma żaden z połączonych węzłów.
6. Jeśli nie jest to możliwe, wszystkie 5 sąsiednich węzłów do dodanego węzła mają 5 różnych kolorów, dlatego musimy wypróbować następujący proces.
7. Numeruj węzły otaczające dodany węzeł n1 ... n5
8. Weź podgraph wszystkich węzłów na oryginalnym wykresie w kolorze tego samego koloru co n1 lub n3.
9. Jeśli w tym podrozdziale n3 nie jest osiągalne z n1, w zbiorze węzłów osiągalnych z n1 (w tym n1) zamień wszystkie wystąpienia koloru n1 na n3 i odwrotnie. Teraz pokoloruj oryginalny kolor dodanego węzła n1.
10. Jeśli n3 było osiągalne z n1 na tym nowym wykresie, wykonaj proces od kroku 9 na węzłach n2 i n4, zamiast n1 i n3.

Wyzwanie

Biorąc pod uwagę wejście listy edgelist (reprezentującej wykres), pokoloruj wykres, przypisując każdemu węzłu wartość.

Dane wejściowe : lista krawędzi na wykresie (tj. [('a','b'),('b','c')...])

Zauważ, że wejściowa lista edycji będzie taka, że ​​jeśli (a, b) znajduje się na liście, (b, a) NIE jest na liście.

Dane wyjściowe : obiekt zawierający pary wartości, gdzie pierwszym elementem każdej pary jest węzeł, a drugim jego kolor, tj. [('a',1),('b',2)...]Lub{'a':1,'b':2,...}

Możesz użyć czegokolwiek do przedstawienia kolorów, od liczb, przez znaki i cokolwiek innego.

Dane wejściowe i wyjściowe są dość elastyczne, o ile jasne jest, jakie są dane wejściowe i wyjściowe.

Zasady

• To jest golf golfowy wyzwanie dla
• Nie musisz używać algorytmu, który opisałem powyżej. Jest po prostu tam w celach informacyjnych.
• Dla każdego wykresu często istnieje wiele prawidłowych metod ich kolorowania. Dopóki kolorystyka wygenerowana przez algorytm jest poprawna, jest to dopuszczalne.
• Pamiętaj, że wykres musi mieć 5 kolorów.

Przypadki testowe

Użyj następującego kodu, aby sprawdzić poprawność wyników kolorowania. Ponieważ istnieje wiele prawidłowych kolorów na wykresie, ten algorytm po prostu sprawdza poprawność kolorowania. Zobacz dokumentację, aby zobaczyć, jak korzystać z kodu.

Niektóre losowe (i raczej głupie) przypadki testowe :

Przypadek testowy 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)]

Prawidłowe wyjście: {0: 4, 1: 3, 2: 3, 3: 2, 4: 4, 5: 1, 6: 0, 7: 4, 8: 3, 9: 4}

Uwaga : Te przypadki testowe są zbyt małe, aby przetestować bardziej szczegółowe zachowanie algorytmu kolorowania, więc tworzenie własnych wykresów jest prawdopodobnie dobrym testem poprawności twojej pracy.

Uwaga 2 : Dodam kolejny fragment kodu, który wkrótce zobrazuje twoje rozwiązanie do kolorowania.

Uwaga 3 : Nie widziałem przedstawionych algorytmów losowego kolorowania, co jest takie fajne w PPCG! Gdyby jednak ktoś mógł zastosować bardziej deterministyczny algorytm, byłoby to również bardzo fajne.

Python 2 , 96 bajtów

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)

Wypróbuj online!

$g$$i$$c$$c$$c$ będzie prawidłową kolorystyką.

Dane wejściowe są płaskie, więc znalezienie 4 kolorów jest zawsze możliwe.

(Tak więc: znajduje to w pewnym sensie najwcześniejsze leksykograficzne zabarwienie i robi to bardzo nieefektywnie).

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

JavaScript (ES7), 80 76 74 bajtów

Zaoszczędź 2 bajty dzięki @Neil

Takie samo podejście jak Lynn . Rozwiązuje 4 kolory, ponumerowane od 0 do 3 .

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

Wypróbuj online!

Brachylog , 38 bajtów

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

Wypróbuj online!

Wyjaśnienie

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 bajtów

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

Wypróbuj online!

Deterministyczny! Prawdopodobnie zawiódłby w bardziej skomplikowanych przypadkach testowych, ale jestem zbyt wypalony, by znaleźć wykres, dla którego zawodzi. Więcej przypadków testowych i. Lub krytyka mile widziane!

Czysty , 139 bajtów

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]

Wypróbuj online!

Generuje wszystkie kolory i zwraca pierwszy prawidłowy.

Galaretka , 23 bajty

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

Wypróbuj online!

Brutalna siła. Zakłada, że ​​węzły są oznaczone liczbami całkowitymi.