Dies ist ein Endspielbrett der Siedler von Catan:

Hintergrund:

Die Straßen (die langen Stockstücke) und die Siedlungen (und Städte) werden von den kleinen Hütten gerendert. Wir codieren die Platzierung dieser Teile mit dem folgenden Schema: Von oben haben wir eine Reihe horizontaler Eckpunkte und Kanten, an denen eine Straße platziert werden kann. Dann haben wir eine Kolonne von nur Straßen und so weiter. Wenn Sie R für Rot, O für Orange und B für Blau und _ für nichts verwenden, wird die abgebildete Tafel wie folgt codiert:

________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_____

Ein Brett wie dieses wird Ihre Eingabezeichenfolge sein. Jeder Buchstabe [A-Z]kann eine Spielerfarbe anzeigen, es gibt jedoch höchstens vier Farben (einschließlich Leerzeichen). Die Gültigkeit der Boards wird ansonsten nach den Regeln der Siedler garantiert , was bedeutet:

• Jede Farbe hat höchstens zwei zusammenhängende Straßennetze, die von den Siedlungen / Städten anderer Spieler (Eckgebäuden) getrennt werden können oder nicht. Sehen Sie die orangefarbene Siedlung, die die rote Straße auf der rechten Seite des Beispielbildes durchbricht.
  • Für jedes Straßennetz ist mindestens eine Siedlung garantiert.
• Es wird garantiert, dass alle Siedlungen und Städte mindestens zwei Kanten von der nächsten anderen Siedlung / Stadt (Ihrer oder einer anderen) entfernt sind.
• Ein Spieler darf nur 15 Straßen auf dem Spielplan haben.
• Für Catan-Enthusiasten: Für dieses Problem gibt es keine Unterscheidung zwischen Siedlungen und Städten, daher unterscheide ich nicht in der Eingabezeichenfolge.

All dies ist für die Spezifikation der "Eingabe" -String.

Längste Straße:

In Siedler erhalten die Spieler zwei Siegpunkte für die "längste Straße". Dies ist definiert als: Der längste zusammenhängende einzelne Pfad (gemessen in Straßen) vom Startpunkt zum Endpunkt, der nicht von einer gegnerischen Siedlung oder Stadt getrennt wird . Zyklen sind in Ordnung, solange Sie den Pfad von einem bestimmten Startpunkt zu einem bestimmten Endpunkt verfolgen können. Eine Schleife von 6 Straßen plus einer abzweigenden Straße ist also Länge 7, aber eine Schleife von zwei Abzweigungen der 6 Straßen auf gegenüberliegenden Seiten ist immer noch nur 7 wert.

In der Beispielkarte ist die rote Straße auf der rechten Seite nur 4 wert, da sie von einer orangefarbenen Siedlung auf der rechten Seite des Bretts abgeschnitten wird (daher sind Siedlungen überhaupt enthalten). Blau hat eine Straße der Länge 13 und Orange eine Straße der Länge 12. Die Hauptstraße von Rot ist nur 7 wert, da sie nicht mit den beiden Einzelstraßen daneben verbunden ist.

Ausgabe:

Alle Spieler, die eine Straße mit der längsten Länge haben (bei Gleichstand kann es auch mehr als eine geben), gefolgt von einem Leerzeichen und / oder einem durch einen Unterstrich begrenzten Punkt, zählen in Basis 10, wie lang diese Straße ist.

Die Ausgabe für die Beispielkarte wäre also:

B 13

Die Problemstellung:

Sie können ein Programm oder eine Funktion schreiben , die Eingangskarte über STDIN oder als Zeichenfolgenargument für Ihre Funktion empfangen, die die oben beschriebene Ausgabe als Zeichenfolge zurückgibt oder sie an STDOUT (oder die nächstgelegene Alternative) ausgibt. Optional können Sie eine einzelne nachgestellte Newline in die Ausgabe aufnehmen.

Dies ist Code-Golf , das kürzeste Programm gewinnt. Standardlücken sind natürlich verboten .

Python 2, 445 400 Bytes

Ich bin ein Fan von Siedlern, also hat diese Herausforderung Spaß gemacht.

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

Die Punktzahl gibt an, dass jedes Vorkommen von 4 Leerzeichen durch einen Tabulator ersetzt wird.

Erläuterung

Die Zeilen vor der Funktionsdefinition lesen die Eingabe und bauen eine normalisierte Karte in eine einzelne Zeichenfolgenvariable auf. Der Prozess fügt "^" Zeichen in die kurzen Zeilen ein, die die vertikalen Straßensegmente darstellen. Außerdem wird die Tafel mit "^" Zeichen aufgefüllt.

^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^________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_____^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^^^^^^^

Wenn die Funktion mit den Standardparametern aufgerufen wird, gibt sie die Länge einer Straße einer bestimmten Farbe zurück. Die erste Schleife ist nur aktiv, wenn der Parameter position (p) angegeben wurde. Es findet rekursiv die Länge der Straße an jeder gültigen Straßenposition und verfolgt die längste. Befindet sich am Positionsparameter eine Straße, addiert die Funktion rekursiv die Länge benachbarter Straßen derselben Farbe. Die Straße wird in der Arbeitskopie der Tafel durch ein "~" ersetzt, um sicherzustellen, dass bereits gezählte Segmente nicht erneut gezählt werden.

Der Code, der auf die Funktionsdefinition folgt, ruft die Funktion für jede Farbe in der Platine auf und druckt die Farbe und Länge mit der höchsten Bewertung.

Demo hier