Ini adalah papan endgame dari Pemukim Catan:

Latar Belakang:

Jalan-jalan (potongan-potongan tongkat panjang) dan pemukiman (dan kota-kota) diberikan oleh pondok-pondok kecil. Kami menyandikan penempatan potongan-potongan ini dengan menggunakan skema berikut: Dari atas, kami memiliki garis horizontal dan tepi di mana jalan dapat ditempatkan. Kemudian kita memiliki kolom jalan saja, dan sebagainya. Menggunakan R untuk Merah, O untuk Oranye, dan B untuk Biru, dan _ untuk apa-apa, papan gambar akan dikodekan sebagai:

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

Papan seperti ini akan menjadi string masukan Anda. Huruf apa pun [A-Z]dapat menunjukkan warna pemain, tetapi paling banyak ada empat warna (termasuk kosong). Papan dijamin tidak sah menurut aturan Pemukim, yang berarti:

• Setiap warna akan memiliki paling banyak dua jaringan jalan yang berdekatan, yang mungkin atau mungkin tidak terpecah oleh pemukiman / kota pemain lain (bangunan vertex). Lihat penyelesaian oranye yang memecah jalan merah di sisi kanan gambar sampel.
  • Setiap jaringan jalan dijamin memiliki setidaknya satu pemukiman.
• Semua pemukiman dan kota dijamin setidaknya dua sisi dari pemukiman / kota terdekat lainnya (milik Anda atau lainnya)
• Satu pemain mungkin hanya memiliki 15 jalan di papan permainan.
• Untuk para penggemar Catan: tidak ada perbedaan antara pemukiman dan kota untuk tujuan masalah ini, jadi saya tidak membedakan dalam string input.

Semua ini untuk spesifikasi string "input".

Jalan Terpanjang:

Di Settlers, pemain mendapatkan dua poin kemenangan karena memiliki "jalan terpanjang". Ini didefinisikan sebagai: Jalur tunggal berdekatan terpanjang (diukur di jalan) dari titik awal ke titik akhir, yang tidak dipecah oleh pemukiman atau kota lawan . Siklus boleh saja, selama Anda dapat melacak jalur dari satu titik awal tertentu ke satu titik akhir tertentu. Jadi, satu loop dari 6 jalan ditambah satu jalan bercabang adalah panjang 7, tetapi satu dengan dua percabangan dari 6 jalan loop di sisi yang berlawanan masih hanya bernilai 7.

Dalam contoh peta, jalan Merah di sisi kanan hanya bernilai 4, karena ia terputus oleh pemukiman Oranye di sisi kanan papan (itulah sebabnya pemukiman dimasukkan sama sekali). Biru memiliki jalan dengan panjang 13, dan Orange memiliki jalan dengan panjang 12. Jalan atas Red hanya bernilai 7, karena tidak terhubung ke dua jalan tunggal di sebelahnya.

Keluaran:

Semua pemain yang memiliki jalan dengan panjang terpanjang (bisa lebih dari satu jika ada ikatan), diikuti oleh spasi putih dan / atau garis bawah dihitung jumlah di pangkalan 10 dari berapa lama jalan itu.

Jadi output untuk papan contoh adalah:

B 13

Pernyataan Masalah:

Anda dapat menulis program atau fungsi , menerima papan input melalui STDIN atau sebagai argumen string ke fungsi Anda, yang mengembalikan output yang dijelaskan di atas sebagai string atau mencetaknya ke STDOUT (atau alternatif terdekat).Anda dapat secara opsional memasukkan satu baris baru dalam output.

Ini adalah kode-golf , kemenangan program terpendek. Tentu saja celah standar dilarang .

Python 2, 445 400 byte

Saya penggemar Settler, jadi tantangan ini menyenangkan.

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

Skor mencerminkan mengganti setiap kemunculan 4 spasi dengan tab.

Penjelasan

Baris sebelum definisi fungsi membaca input, dan membuat papan yang dinormalisasi menjadi variabel string tunggal. Proses memasukkan "^" karakter ke dalam garis pendek yang mewakili segmen jalan vertikal. Itu juga melapisi papan dengan karakter "^".

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

Ketika dipanggil dengan parameter default, fungsi mengembalikan panjang jalan warna yang diberikan. Loop pertama hanya aktif ketika parameter posisi (p) diberikan. Secara rekursif menemukan panjang jalan di setiap posisi jalan yang valid, dan melacak yang terpanjang. Ketika ada jalan di parameter posisi, fungsi tersebut secara rekursif menambah panjang jalan yang berdekatan dengan warna yang sama. Jalan diganti dengan "~" di copy papan kerja untuk memastikannya tidak menceritakan kembali segmen yang sudah dihitung.

Kode yang mengikuti definisi fungsi memanggil fungsi untuk setiap warna di papan, dan mencetak warna dan panjang skor tertinggi.

Demo di sini