Este é o segundo de uma série de desafios no Island Golf. Desafio anterior
Dois eremitas chegaram a uma ilha deserta. Como vieram buscar a solidão, desejam viver o mais longe possível um do outro. Onde eles deveriam construir suas cabanas para maximizar a distância a pé entre eles?
Entrada
Sua entrada será uma grade retangular composta por dois caracteres, representando terra e água. Nos exemplos abaixo, a terra é #
e a água é .
, mas você pode substituir quaisquer dois caracteres distintos que desejar.
...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........
Sempre haverá pelo menos duas peças de terra. Os ladrilhos terrestres serão todos contíguos (ou seja, há apenas uma ilha). Os ladrilhos de água também serão contíguos (ou seja, não há lagos). A borda externa da grade será todos os ladrilhos de água. Ladrilhos de terra não serão conectados na diagonal: ou seja, você nunca verá algo como
....
.#..
..#.
....
Resultado
Seu código deve gerar a mesma grade, com dois locais de cabana marcados. Nos exemplos abaixo, os locais das cabanas estão marcados com X, mas você pode substituir qualquer caractere, desde que seja distinto dos caracteres terrestres e aquáticos.
Os locais das cabanas devem ser dois terrenos, escolhidos de forma a maximizar a distância a pé entre eles. Definimos distância a pé como o comprimento do caminho mais curto, inteiramente em terra, entre os dois pontos. Os ladrilhos terrestres são considerados adjacentes na horizontal ou na vertical, mas não na diagonal.
Uma possível solução para a ilha acima:
...........
...X#......
..#####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........
A distância a pé entre esses dois pontos é 11, que é a maior distância entre dois pontos nesta ilha. Há outra solução à distância 11:
...........
...##......
..X####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........
Detalhes
Sua solução pode ser um programa completo ou uma função . Qualquer um dos métodos padrão de entrada e saída é aceitável.
Sua entrada e saída podem ser uma cadeia de linhas múltiplas, uma lista de cadeias ou uma matriz 2D / lista aninhada de caracteres / cadeias de caracteres únicos. Sua saída pode (opcionalmente) ter uma única nova linha à direita. Como mencionado acima, você pode usar três caracteres distintos no lugar de #.X
(especifique em seu envio quais caracteres você está usando).
Casos de teste
A. Ilhas com canais de cabana exclusivos:
....
.##.
....
....
.XX.
....
......
......
..##..
...#..
......
......
......
......
..X#..
...X..
......
......
........
.#####..
.##..##.
.#..###.
.##..##.
........
........
.#####..
.##..##.
.#..###.
.#X..#X.
........
.........
.#####.#.
.#...#.#.
.#.###.#.
.#.....#.
.#######.
.........
.........
.#####.X.
.#...#.#.
.#.X##.#.
.#.....#.
.#######.
.........
B. Exemplo de uma ilha com várias soluções possíveis:
........
....##..
...####.
..###...
.#####..
.#####..
..##....
........
Saídas possíveis:
........
....#X..
...####.
..###...
.#####..
.X####..
..##....
........
........
....#X..
...####.
..###...
.#####..
.#####..
..X#....
........
........
....##..
...###X.
..###...
.#####..
.X####..
..##....
........
........
....##..
...###X.
..###...
.#####..
.#####..
..X#....
........
C. Caso de teste grande como um Gist
Este é o código-golfe : o código mais curto em cada idioma vence.
Respostas:
Python 3,
249246 bytesRaspou 3 bytes, graças ao DLosc.
Entrada e saída são cadeias simples, com '.', '@' E 'X' representando água, cabanas e terra, respectivamente.
Versão anterior:
Entrada é uma única sequência, com '.' e '#' representando água e terra, respectivamente. 'X' representa as cabanas na saída.
Explicação:
É basicamente fazer uma primeira pesquisa abrangente de todos os pontos de partida possíveis ao mesmo tempo. Mantenha um dicionário, d, de comprimentos de caminho digitados pelo início e fim do caminho, por exemplo, d [(k, i)] é a distância de k a i. Em seguida, itere sobre as teclas no dicionário, d, e crie um novo dicionário, u, com caminhos com 1 unidade a mais, movendo a unidade do ponto final 1 para N, S, E, W, por exemplo, u [(k, i + 1)] = d [(k, i)] + 1. Não inclua caminhos que já estão em d. Se u não estiver vazio, adicione os novos caminhos mais longos ae repita. Quando u está vazio, isso significa que não há mais caminhos a serem feitos. Agora d contém todos os caminhos possíveis e seus comprimentos. Portanto, é apenas uma questão de obter a chave com o caminho mais longo.
Versão menos comentada e comentada:
fonte
C #, 387 bytes
Vamos fazer a bola rolar ...
Experimente Online
O programa completo, lê STDIN, grava em STDOUT. Ele simplesmente passa por cada célula e executa um BFS para calcular a célula mais distante, registrando as duas se for a mais distante já registrada. Nada realmente, e frustrantemente pouco eu posso encontrar para jogar golfe.
Código formatado e comentado:
fonte