This is an endgame board of Settlers of Catan:
The roads (the long stick pieces) and the settlements (and cities) are rendered by the little huts. We encode the placement of these pieces by using the following scheme: From the top, we have a row horizontal vertices and edges where a road can be placed. Then we have a column of only roads, and so forth. Using R for Red, O for Orange, and B for Blue, and _ for nothing, the pictured board would be encoded as:
________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_____
A board like this will be your input string. Any letter
[A-Z] may indicate a player color, but there will at most four colors (including empty). Boards are otherwise guaranteed to be valid according to the rules of Settlers, which means:
- Each color will have at most two contiguous road networks, which may or may not be broken apart by other players settlements / cities (vertex buildings). See the orange settlement breaking apart the red road on the right side of the sample image.
- Each road network is guaranteed to have at least one settlement.
- All settlements and cities are guaranteed to be at least two edges from the nearest other settlement / city (yours or otherwise)
- One player may only have 15 roads on the game board.
- For Catan enthusiasts: there is no distinction between settlements and cities for the purpose of this problem, so I don't distinguish in the input string.
All this is for the specification of the "input" string.
In Settlers, players get two victory points for having the "longest road". This is defined to be: The longest contiguous single path (measured in roads) from start point to end point, that is not broken up by an opponents settlement or city. Cycles are okay, as long as you can trace the path from one particular start point to one particular end point. So, a loop of 6 roads plus one road branching off is length 7, but one with two branching off the 6 road loop on opposite sides is still only worth 7.
In the example map, the Red road on the right side is only worth 4, because he is cut off by an Orange settlement on the right side of the board (that's why settlements are included at all). Blue has a road of length 13, and Orange has a road of length 12. Red's top road is only worth 7, because it doesn't connect to the two single roads next to it.
All players that have a road of the longest length (it could be more than one if there are ties), followed by a whitespace and/or underscore delimited count in base 10 of how long that road is.
So the output for the example board would be:
The Problem statement:
You may write a program or function, receives the input board via STDIN or as a string argument to your function, which returns the output described above as a string or prints it to STDOUT (or closest alternative). You may optionally include a single trailing newline in the output.