fundo
Você é aprendiz de um poderoso mago, e seu mestre está desenvolvendo um feitiço para criar um labirinto interdimensional para prender seus inimigos. Ele quer que você programe seu computador a vapor para analisar os possíveis layouts. A programação desta máquina diabólica é altamente perigosa, portanto, você deve manter o código o mais curto possível.
Entrada
Sua entrada é uma grade bidimensional de pontos .
e hashes #
, significando espaço e paredes vazios, dados como uma sequência delimitada por nova linha. Sempre haverá pelo menos um .
e um #
, e você pode decidir se há uma nova linha à direita ou não.
Essa grade é o modelo de um labirinto infinito, que é feito alinhando infinitamente muitas cópias da grade uma da outra. O labirinto é dividido em cavidades , que são componentes conectados de espaços vazios (espaços adjacentes na diagonal não são conectados). Por exemplo, a grade
##.####
...##..
#..#..#
####..#
##...##
resulta no seguinte labirinto (continuado infinitamente em todas as direções):
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
Este labirinto em particular contém uma cavidade de área infinita. Por outro lado, esse projeto resulta em um labirinto com apenas cavidades finitas:
##.####
##..###
####...
..####.
#..####
Saída
Sua saída será um valor verdadeiro se o labirinto contiver uma cavidade infinita e um valor falso se não. Observe que o labirinto pode conter cavidades finitas e infinitas; nesse caso, a saída deve ser verdadeira.
Regras
Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas.
Casos de teste adicionais
Cavidades infinitas:
.#
#.#
...
#.#
#.###.#.###.#
#.#...#...#.#
#.#.#####.#.#
..#.#...#.#..
###.#.#.#.###
#...#.#.#...#
#.###.#.###.#
##.###
#..###
..##..
###..#
##..##
..#..#..#..#..#..#
.#..#..#..#..#..#.
#..#..#..#..#..#..
#.####.###.###.####
#...#..#...###..###
###.#..#.######..##
....####.#######...
###..###...########
##########.##....##
..###......##.##...
#.........##..#####
###########..###..#
#...........####..#
#.###########.##..#
#.##....##.....####
#.####.###.###.####
Cavidades finitas:
###
#.#
###
.#
#.
####
.#..
####
#.#.#
..#..
#####
..#..
#.#.#
#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#
##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####
###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##
###########
........#..
#########.#
..........#
.##########
.#.........
##.########
...#.......
.
e um#
na entrada.Respostas:
JavaScript (ES6),
235253O mesmo método usado pelo @mac. Para cada célula livre, tento um preenchimento recursivo, marcando as células usadas com a coordenada que estou usando (que pode estar fora do modelo original). Se durante o preenchimento eu chegar a uma célula já marcada com uma coordenada diferente, estou em um caminho infinito.
A maneira peculiar de lidar com o módulo em JS é bastante irritante.
Teste no console Firefox / FireBug
Infinito
Saída
Finito
Saída
fonte
(j%4-1)%2
fornece um bom padrão de repetição.L=
contagem de bytes.C # -
423375 bytesO programa C # completo, aceita entrada via STDIN, gera "True" ou "False" para STDOUT conforme apropriado.
Eu não podia deixar esse Linq lá ... felizmente, sua remoção valeu a pena! Agora, ele controla as células visitadas e visitadas em uma matriz (já que, de qualquer maneira, apenas olha para um número finito delas). Também reescrevi o código direcional, removendo a necessidade de um Lambda e geralmente tornando o código mais impossível de entender (mas com economia substancial de bytes).
Trata-se de uma pesquisa de amplitude (não que isso importe) que continue até ficar presa em uma caverna finita ou decidir que a caverna é grande o suficiente para ser infinitamente grande (quando tiver tantas células quanto a célula). Retângulo original, isso significa que deve haver um caminho de uma célula para outra em algum outro lugar, que possamos seguir sempre).
Código não cortado:
fonte
C#
resposta como a melhor forma de obter votos aqui.Python 2 -
258210244 bytesVerifique recursivamente os caminhos, se o estouro da pilha retornar 1 (verdade) senão retornar None (falsey).
fonte
;
para as linhasp
, pois você os obterá na mesma linha que oif
.Python 2 -
297286275 bytesSeleciona uma célula "aberta" arbitrária para iniciar um preenchimento de inundação. O labirinto é infinito se, durante o preenchimento, visitarmos novamente uma célula que já visitamos, mas ela tem uma coordenada diferente da visita anterior. Se o preenchimento de inundação preencher toda a região sem encontrar uma célula, tente uma região diferente. Se não for possível encontrar uma região, o labirinto é finito.
Leva o arquivo para processar na linha de comando, retorna o código de saída
1
para infinito e0
finito.Retorna resultados corretos para todos os casos de teste.
fonte