Oto plansza końcowa Settlers of Catan:

Tło:

Drogi (długie kije) i osady (i miasta) są renderowane przez małe chaty. Umieszczamy te elementy za pomocą następującego schematu: od góry mamy rząd poziomych wierzchołków i krawędzi, w których można umieścić drogę. Mamy kolumnę samych dróg i tak dalej. Używając R dla koloru czerwonego, O dla koloru pomarańczowego i B dla koloru niebieskiego i _ dla niczego, obrazowana tablica byłaby kodowana jako:

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

Tablica taka będzie twoim ciągiem wejściowym. Każda litera [A-Z]może oznaczać kolor gracza, ale będą maksymalnie cztery kolory (w tym puste). W przeciwnym razie gwarantuje się, że tablice będą ważne zgodnie z zasadami Osadników, co oznacza:

• Każdy kolor będzie miał co najwyżej dwie ciągłe sieci dróg, które mogą, ale nie muszą być rozdzielone przez osady / miasta innych graczy (budynki wierzchołków). Zobacz pomarańczową osadę rozbijającą czerwoną drogę po prawej stronie przykładowego obrazu.
  • Każda sieć dróg ma zagwarantowane co najmniej jedno osiedle.
• Wszystkie osady i miasta mają gwarancję, że znajdują się co najmniej dwie krawędzie od najbliższej innej osady / miasta (twojej lub innej)
• Jeden gracz może mieć tylko 15 dróg na planszy.
• Dla entuzjastów Catana: nie ma różnicy między osadami a miastami w celu rozwiązania tego problemu, więc nie rozróżniam ciągu wejściowego.

Wszystko to służy do specyfikacji ciągu „wejściowego”.

Najdłuższa droga:

W Osadnikach gracze otrzymują dwa punkty zwycięstwa za posiadanie „najdłuższej drogi”. Jest to zdefiniowane jako: Najdłuższa ciągła pojedyncza ścieżka (mierzona na drogach) od punktu początkowego do punktu końcowego, która nie jest dzielona przez osadę lub miasto przeciwnika . Cykle są w porządku, o ile można prześledzić ścieżkę od jednego określonego punktu początkowego do jednego określonego punktu końcowego. Tak więc pętla 6 dróg plus jedna rozgałęzienie drogi ma długość 7, ale jedna z dwoma rozgałęzieniami z pętli 6 po przeciwnych stronach jest nadal warta tylko 7.

Na przykładowej mapie Czerwona droga po prawej stronie jest warta tylko 4, ponieważ jest odcięta pomarańczową osadą po prawej stronie planszy (dlatego w ogóle uwzględniono osadę). Niebieski ma drogę o długości 13, a Pomarańczowy ma drogę o długości 12. Górna droga Czerwonego jest warta tylko 7, ponieważ nie łączy się z dwoma pojedynczymi drogami obok niego.

Wynik:

Wszyscy gracze, którzy mają najdłuższą drogę (może być więcej niż jedna, jeśli są remisy), po których następuje biała spacja i / lub znak podkreślenia liczą w podstawie 10 długości tej drogi.

Wyjście dla przykładowej płyty to:

B 13

Opis problemu:

Możesz napisać program lub funkcję , otrzymać tablicę wejściową przez STDIN lub jako argument ciągu do swojej funkcji, która zwraca wynik opisany powyżej jako ciąg lub wypisuje go do STDOUT (lub najbliższej alternatywy). Opcjonalnie możesz dołączyć jeden końcowy znak nowej linii do wyniku.

To jest golf golfowy , wygrywa najkrótszy program. Oczywiście standardowe luki są zabronione .

Python 2, 445 400 bajtów

Jestem fanem Osadników, więc to wyzwanie było fajne.

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

Wynik odzwierciedla zastąpienie każdego wystąpienia 4 spacjami tabulatorem.

Wyjaśnienie

Linie przed definicją funkcji odczytują dane wejściowe i budują znormalizowaną tablicę w jedną zmienną łańcuchową. Proces wstawia znaki „^” do krótkich linii reprezentujących pionowe odcinki drogi. Wypełnia również tablicę znakami „^”.

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

Po wywołaniu z parametrami domyślnymi funkcja zwraca długość drogi danego koloru. Pierwsza pętla jest aktywna tylko wtedy, gdy podano parametr position (p). Rekurencyjnie wyszukuje długość drogi na każdej prawidłowej pozycji drogi i śledzi najdłuższą. Gdy w parametrze pozycji znajduje się droga, funkcja rekurencyjnie dodaje długość sąsiednich dróg tego samego koloru. Droga jest zastąpiona przez „~” w roboczej kopii tablicy, aby upewnić się, że nie zlicza segmentów, które zostały już policzone.

Kod następujący po definicji funkcji wywołuje funkcję dla każdego koloru na planszy i drukuje kolor i długość o najwyższym wyniku.

Zrób to tutaj