Colonos de Catan - a estrada mais longa!

16

Este é um tabuleiro final de Colonos de Catan:

Catan board

Fundo:

As estradas (os longos pedaços de pau) e os assentamentos (e cidades) são processados ​​pelas pequenas cabanas. Codificamos a colocação dessas peças usando o seguinte esquema: No topo, temos uma linha de vértices e arestas horizontais onde uma estrada pode ser colocada. Então nós temos uma coluna de apenas estradas, e assim por diante. Usando R para vermelho, O para laranja e B para azul e _ para nada, o quadro na foto seria codificado como:

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

Uma placa como essa será sua string de entrada. Qualquer letra [A-Z]pode indicar a cor de um jogador, mas haverá no máximo quatro cores (incluindo vazio). Placas são outra forma garantida para ser válido de acordo com as regras de colonos, o que significa:

  • Cada cor terá no máximo duas redes de estradas contíguas, que podem ou não ser separadas por outros assentamentos / cidades dos jogadores (edifícios de vértices). Veja o assentamento laranja rompendo a estrada vermelha no lado direito da imagem de amostra.
    • É garantido que cada rede rodoviária tenha pelo menos um assentamento.
  • Todos os assentamentos e cidades estão garantidos a pelo menos duas margens do outro assentamento / cidade mais próximo (seu ou não)
  • Um jogador pode ter apenas 15 estradas no tabuleiro do jogo.
  • Para os entusiastas de Catan: não há distinção entre assentamentos e cidades para o propósito deste problema, portanto não distingo na sequência de entrada.

Tudo isso é para a especificação da string "input".

Estrada mais longa:

Nos colonos, os jogadores ganham dois pontos de vitória por terem o "caminho mais longo". Isso é definido como: O caminho único contíguo mais longo (medido nas estradas) do ponto inicial ao ponto final, que não é dividido por uma cidade ou povoado adversário . Os ciclos estão corretos, desde que você possa rastrear o caminho de um ponto inicial específico para um ponto final específico. Portanto, um trecho de 6 estradas mais uma estrada se ramifica é o comprimento 7, mas uma com duas ramificações fora da estrada 6 em lados opostos ainda vale apenas 7.

No mapa de exemplo, a estrada Vermelha no lado direito vale apenas 4, porque ele é cortado por um assentamento Orange no lado direito do tabuleiro (é por isso que os assentamentos são incluídos). O azul tem uma estrada de comprimento 13 e a laranja tem uma estrada de 12. A estrada superior do vermelho vale apenas 7, porque não se conecta às duas estradas isoladas ao lado.

Resultado:

Todos os jogadores que têm uma estrada com o maior comprimento (pode ser mais de uma se houver empates), seguidos por um espaço em branco e / ou sublinhado contam na base 10 o tempo que essa estrada tem.

Portanto, a saída para o quadro de exemplo seria:

B 13

A declaração do problema:

Você pode escrever um programa ou função , receber a placa de entrada via STDIN ou como um argumento de string para sua função, que retorna a saída descrita acima como uma string ou imprime em STDOUT (ou alternativa mais próxima). Opcionalmente, você pode incluir uma única nova linha à direita na saída.

Este é o , o programa mais curto vence. As brechas padrão são proibidas, é claro .

durron597
fonte
2
A verdadeira declaração do problema: o jogador laranja é um idiota.
CorsiKa 28/05
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. Levei alguns minutos para descobrir o que isso significava. Você deve explicar mais claramente que as linhas horizontais também incluem os assentamentos e locais de assentamento.
DLosc 28/05
@corsiKa Já tive alguém que fez isso comigo antes!
Jerry Jeremiah
1
O laranja e o vermelho na imagem são realmente semelhantes. Você deveria ter escolhido outra cor.
mbomb007

Respostas:

3

Python 2, 445 400 bytes

Sou fã de colonos, então esse desafio foi divertido.

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

A pontuação reflete a substituição de cada ocorrência de 4 espaços por uma guia.

Explicação

As linhas antes da definição da função leem a entrada e constroem uma placa normalizada em uma única variável de cadeia. O processo insere caracteres "^" nas linhas curtas que representam os segmentos de estrada verticais. Ele também preenche o quadro com caracteres "^".

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

Quando chamada com os parâmetros padrão, a função retorna o comprimento de uma estrada de uma determinada cor. O primeiro loop está ativo apenas quando o parâmetro position (p) foi fornecido. Encontra recursivamente o comprimento da estrada em cada posição válida e mantém o controle da estrada mais longa. Quando há uma estrada no parâmetro position, a função adiciona recursivamente o comprimento de estradas adjacentes da mesma cor. A estrada é substituída por um "~" na cópia de trabalho do quadro para garantir que ele não conte os segmentos que já foram contados.

O código após a definição da função chama a função para cada cor no quadro e imprime a cor e o comprimento com a pontuação mais alta.

Demonstre aqui

Chuck Morris
fonte