Remarque: Dans cet article, les termes «caractère» et «couleur» signifient essentiellement la même chose
Cette image:
peut être représenté comme
....'''333
.eeee'''3e
..dddd33ee
%%%dd####e
(mappage des couleurs aux caractères ascii)
Le théorème des quatre couleurs stipule que "compte tenu de la séparation d'un plan en régions contiguës, produisant une figure appelée carte, pas plus de quatre couleurs ne sont nécessaires pour colorer les régions de la carte afin qu'aucune région adjacente n'ait la même couleur. Deux les régions sont appelées adjacentes si elles partagent une frontière commune qui n'est pas un coin, où les coins sont les points partagés par trois régions ou plus. " - Wikipedia ( lien )
Cela signifie qu'il devrait être possible de colorier une carte à l'aide de quatre couleurs afin qu'aucune des deux parties qui partagent un bord partagent une couleur.
L'algorithme pour colorier une carte en utilisant seulement quatre couleurs est compliqué, donc dans ce défi, votre programme n'a besoin que de colorier la carte en utilisant cinq couleurs ou moins.
La carte précédente recolorée pourrait ressembler à ceci:
qui pourrait être représenté comme
....'''333
.eeee'''3e
..dddd33ee
333dd....e
ou équivalent
@@@@$$$!!!
@^^^^$$$!^
@@<<<<!!^^
!!!<<@@@@^
Défi:
Étant donné une "carte" composée de caractères ascii (où chaque caractère représente une couleur différente), "recolorez" la carte (représentez la carte en utilisant différents caractères ascii) afin qu'elle n'utilise que cinq couleurs ou moins.
Exemple:
Contribution:
%%%%%%%%%%%%##########$$$$$$$$%%
*****%%%####!!!!!!!%%%%%%%%%#^^^
(((((((***>>>>??????????%%%%%%%%
&&&&&&&&$$$$$$$^^^^^^^))@@@%%%%%
^^^^^^%%%%%%%%%%%%##############
Sortie possible:
11111111111122222222223333333311
44444111222255555551111111112444
22222224441111444444444411111111
55555555222222255555553355511111
22222211111111111122222222222222
Précisions:
- La carte d'entrée utilisera toujours six caractères ou plus
- Vous pouvez utiliser cinq caractères différents dans la sortie
- Vous pouvez utiliser moins de cinq caractères différents dans la sortie
- Vous pouvez prendre l'entrée dans n'importe quel format raisonnable (y compris un tableau de tableaux ou un tableau de chaînes)
- Il s'agit de code-golf, donc la réponse la plus courte l'emporte.
121
comme 3 régions distinctes pour éviter ce problème, même si l'exemple implique le contraire, ou devons-nous la traiter comme 2, et supposer qu'aucune carte ne sera donnée qui nécessite plus de 5 couleurs?Réponses:
Python 2 ,
375361359357355353350347 octetsEssayez-le en ligne!
Prend l'entrée comme une liste de chaînes et retourne une liste de listes
f
prend l'entrée de la carte et la colore,g
renvoie tous les personnages connectés et l'ensemble de leurs voisins, la zone peut être colorée avec une couleur distincte.la source
if~-(n!={c}or(i,j)in m):
pour -2 octets