Это доска эндшпиля Поселенцев Катана:

Фон:

Дороги (длинные палки) и поселения (и города) представлены маленькими хижинами. Мы кодируем расположение этих частей, используя следующую схему: Сверху у нас есть ряд горизонтальных вершин и ребер, где можно разместить дорогу. Тогда у нас есть колонка только дорог, и так далее. Используя R для красного, O для оранжевого и B для синего и _ ни для чего, изображенная плата будет закодирована как:

________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-Z]может обозначать цвет игрока, но будет не более четырех цветов (включая пустой). В противном случае доски гарантированы в соответствии с правилами Поселенцев, что означает:

• Каждый цвет будет иметь не более двух смежных дорожных сетей, которые могут быть или не быть разделены на другие населенные пункты / города (здания вершин). Посмотрите на оранжевое поселение, разбивающее красную дорогу на правой стороне образца изображения.
  • Каждая дорожная сеть гарантированно имеет хотя бы один населенный пункт.
• Все населенные пункты и города гарантированно находятся как минимум в двух краях от ближайшего другого населенного пункта / города (вашего или другого)
• У одного игрока может быть только 15 дорог на игровом поле.
• Для энтузиастов Катана: для целей этой задачи не проводится различия между поселениями и городами, поэтому я не различаю во входной строке.

Все это для спецификации "входной" строки.

Самая длинная дорога:

В «Поселенцах» игроки получают два победных очка за «самую длинную дорогу». Это определяется следующим образом: самый длинный непрерывный одиночный путь (измеренный на дорогах) от начальной точки до конечной точки, который не разделен поселением или городом противника . Циклы в порядке, если вы можете проследить путь от одной конкретной начальной точки до одной конкретной конечной точки. Таким образом, петля из 6 дорог плюс одно ответвление от дороги имеет длину 7, но одна из них с двумя ответвлениями от 6 дорожной петли на противоположных сторонах все еще стоит только 7

На карте-примере Красная дорога с правой стороны стоит только 4, потому что он отрезан от оранжевого поселения с правой стороны доски (поэтому поселения вообще включены). Дорога Blue имеет длину 13, а Orange - дорогу 12. Главная дорога Red стоит всего 7, потому что она не соединяется с двумя соседними дорогами.

Выход:

Всем игрокам, у которых самая длинная дорога (их может быть больше одного, если есть связи), за которыми следует пробел и / или знак с разделителем подчеркивания в базе 10 того, какова длина этой дороги.

Таким образом, вывод для примера платы будет:

B 13

Постановка задачи:

Вы можете написать программу или функцию , получить плату ввода через STDIN или в качестве строкового аргумента вашей функции, которая возвращает вывод, описанный выше, в виде строки или печатает его в STDOUT (или ближайшую альтернативу). При желании вы можете включить один завершающий символ новой строки в вывод.

Это код-гольф , выигрывает самая короткая программа. Стандартные лазейки запрещены, конечно .

Python 2, 445 400 байт

Я фанат Settlers, так что этот вызов был веселым.

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

Оценка отражает замену каждого вхождения из 4 пробелов на табуляцию.

объяснение

Строки перед определением функции читают ввод и строят нормализованную доску в единственную строковую переменную. Процесс вставляет символы «^» в короткие строки, представляющие вертикальные сегменты дороги. Он также дополняет доску символами «^».

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

При вызове с параметрами по умолчанию функция возвращает длину дороги данного цвета. Первый цикл активен только тогда, когда задан параметр position (p). Он рекурсивно находит длину дороги в каждой действительной дорожной позиции и отслеживает самую длинную. Когда в параметре позиции есть дорога, функция рекурсивно добавляет длину смежных дорог одного цвета. Дорога заменена на «~» в рабочей копии платы, чтобы гарантировать, что она не пересчитывает уже подсчитанные сегменты.

Код, следующий за определением функции, вызывает функцию для каждого цвета на доске и печатает самый высокий цвет и длину оценки.

Демо это здесь