Voici un tableau final de Settlers of Catan:

Contexte:

Les routes (les longs morceaux de bâton) et les colonies (et les villes) sont rendues par les petites cabanes. Nous encodons le placement de ces pièces en utilisant le schéma suivant: Du haut, nous avons une rangée de sommets et d'arêtes horizontaux où une route peut être placée. Ensuite, nous avons une colonne de routes seulement, et ainsi de suite. En utilisant R pour Rouge, O pour Orange et B pour Bleu et _ pour rien, la carte illustrée serait codée comme suit:

________RR_R_
__R_
__RR_R_RRR_____R_
B___R
_B_________B__OO_OOR_
B__B_R
BB_BBB_____B____RR_R_
OBB_O
OO__BB_BB__OOO_OO
O_O_
_O_OOO_O_____

Un tableau comme celui-ci sera votre chaîne d'entrée. Toute lettre [A-Z]peut indiquer une couleur de joueur, mais il y aura au plus quatre couleurs (y compris vide). Les conseils sont par ailleurs garantis pour être valides selon les règles des colons, ce qui signifie:

• Chaque couleur aura au plus deux réseaux routiers contigus, qui peuvent ou non être séparés par les autres colonies / villes des joueurs (bâtiments de sommet). Voir la colonie orange briser la route rouge sur le côté droit de l'image échantillon.
  • Chaque réseau routier est garanti d'avoir au moins un règlement.
• Tous les établissements et villes sont garantis à au moins deux bords de l'autre établissement / ville le plus proche (le vôtre ou non)
• Un joueur ne peut avoir que 15 routes sur le plateau de jeu.
• Pour les amateurs de Catan: il n'y a pas de distinction entre les colonies et les villes aux fins de ce problème, donc je ne fais pas de distinction dans la chaîne d'entrée.

Tout cela est pour la spécification de la chaîne "d'entrée".

Route la plus longue:

Dans Settlers, les joueurs obtiennent deux points de victoire pour avoir "la plus longue route". Ceci est défini comme étant: Le chemin unique contigu le plus long (mesuré en routes) du point de départ au point d'arrivée, qui n'est pas interrompu par une colonie ou une ville adverse . Les cycles sont corrects, tant que vous pouvez tracer le chemin d'un point de départ particulier à un point final particulier. Ainsi, une boucle de 6 routes plus une dérivation de route est de longueur 7, mais une avec deux branches de la boucle de route 6 sur les côtés opposés ne vaut toujours que 7.

Dans l'exemple de carte, la route rouge sur le côté droit ne vaut que 4, car il est coupé par une colonie orange sur le côté droit du plateau (c'est pourquoi les colonies sont incluses). Bleu a une route de longueur 13 et Orange a une route de longueur 12. La route supérieure de Rouge ne vaut que 7, car elle ne se connecte pas aux deux routes à côté d'elle.

Production:

Tous les joueurs qui ont une route de la plus longue longueur (il pourrait y en avoir plusieurs s'il y a des égalités), suivis d'un espace délimité par des espaces et / ou des soulignements dans la base 10 de la longueur de cette route.

Ainsi, la sortie de l'exemple de carte serait:

B 13

L'énoncé du problème:

Vous pouvez écrire un programme ou une fonction , recevoir la carte d'entrée via STDIN ou comme argument de chaîne dans votre fonction, qui renvoie la sortie décrite ci-dessus sous forme de chaîne ou l'imprime dans STDOUT (ou l'alternative la plus proche). Vous pouvez éventuellement inclure une seule nouvelle ligne de fin dans la sortie.

Il s'agit du code-golf , le programme le plus court qui gagne. Les failles standard sont bien sûr interdites .

Python 2, 445 400 octets

Je suis un fan de Settlers, donc ce défi était amusant.

T="^"
Z=26
A=T*52
for i in range(11):A+=(T*(i%2)*3).join(x for x in raw_input()).center(Z,T)
A+=T*52
def f(c,p=0,l=0,B=A):
 b=l;C=B[0:p]+T+B[p+1:];n=(Z,1)[p%2]
 for i in(p<1)*range(390):
    if(i/Z%2<1&i%2>0)|(i/Z%2>0&i%2<1):b=max(b,f(c,i))
 for i in(p-n,p+n)*(B[p]==c):
    for j in(i-Z,i-1,i+1,i+Z)*(B[i]in c+"_"):b=max(b,f(c,j,l+1,C))
 return b
i=l=0
for x in A:
 if x<T:i=f(x)
 if i>l:c=x;l=i
print c,l

Le score reflète le remplacement de chaque occurrence de 4 espaces par une tabulation.

Explication

Les lignes avant la définition de la fonction lisent l'entrée et construisent une carte normalisée en une seule variable de chaîne. Le processus insère des caractères "^" dans les lignes courtes représentant les segments de route verticaux. Il remplit également la carte avec des caractères "^".

^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^________RR_R_^^^^^^^
^^^^^^_^^^_^^^R^^^_^^^^^^^
^^^^__RR_R_RRR_____R_^^^^^
^^^^B^^^_^^^_^^^_^^^R^^^^^
^^_B_________B__OO_OOR_^^^
^^B^^^_^^^_^^^B^^^_^^^R^^^
^^BB_BBB_____B____RR_R_^^^
^^^^O^^^B^^^B^^^_^^^O^^^^^
^^^^OO__BB_BB__OOO_OO^^^^^
^^^^^^O^^^_^^^O^^^_^^^^^^^
^^^^^^_O_OOO_O_____^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^

Lorsqu'elle est appelée avec les paramètres par défaut, la fonction renvoie la longueur d'une route d'une couleur donnée. La première boucle n'est active que lorsque le paramètre position (p) a été fourni. Il trouve récursivement la longueur de la route à chaque position de route valide et garde la trace de la plus longue. Lorsqu'il y a une route au paramètre de position, la fonction ajoute récursivement la longueur des routes adjacentes de la même couleur. La route est remplacée par un "~" dans la copie de travail du tableau pour garantir qu'elle ne recomptera pas les segments qui ont déjà été comptés.

Le code suivant la définition de la fonction appelle la fonction pour chaque couleur de la carte et imprime la couleur et la longueur les plus élevées.

Démonstration ici