Hora de outro desafio de labirinto, mas não como você o conhece.
As regras para esse desafio são um pouco diferentes da maioria dos desafios do labirinto. Os tipos de bloco são definidos da seguinte maneira:
S: A localização no labirinto em que você começaE: O local que você está tentando acessar0: Muro que você não pode atravessar+: Piso que você pode atravessar
Você pode viajar em uma das seis direções: cima-esquerda, cima-direita, esquerda, direita, baixo-esquerda ou baixo-direita.
\ /
-S-
/ \
O labirinto não quebra. O objetivo é encontrar a seqüência de caminho mais curto para chegar a partir Sde E.
Entrada:
A entrada é linhas separadas por espaço, como os labirintos mostrados. Nenhum espaço à direita seguirá uma linha.
Saída:
Uma série de R, Le Fonde
Rgira você para a direita (sentido horário) 60 grausLgira você para a esquerda (sentido anti-horário) 60 grausFmove um espaço na direção que você está apontando
Você começa a apontar left-up
O caminho mais curto é contado pelo comprimento da sequência produzida, não pelo número de posições visitadas. Seu programa deve imprimir o caminho mais curto como a solução.
Se o labirinto é insolúvel, você deve produzir Invalid maze!.
( >>>é a saída)
0 0 0 0
0 + 0 + 0
0 0 0 + + 0
0 + 0 + 0 + 0
0 0 + + 0 0 + 0
0 0 + 0 + 0 0 + 0
E 0 + 0 0 + + 0
+ + 0 + 0 + 0
0 0 0 0 0 +
+ 0 + + +
0 S 0 0
>>>RFRFFLFLFRFFLFFFLFLFFRFLFLFRFRFRF
+ 0 0 0 0 0 0
0 0 0 0 0 + + 0
0 0 E 0 + 0 0 + 0
0 0 0 0 0 0 0 +
0 + 0 0 + + +
0 0 + + 0 0
S + 0 0 0
>>>Invalid maze!
0 E S
>>>LF
E + 0
0 + + +
0 0 S
+ +
>>>FFLF
E
0 +
0 + +
0 +
S
>>>RFFLFF
0 E + 0 0
0 + 0 0 + +
+ 0 + + + 0
+ 0 + 0 + 0
+ + + 0 S
>>>FFLFLFFRFRFFRFF
E 0 + + 0
0 + 0 + + 0
+ + + 0 + 0
+ 0 0 0 0 0
+ + + + 0
+ 0 S 0
>>>FLFFRFFRFLF
(Observe que alguns dos labirintos têm outras soluções que têm o mesmo comprimento, mas não estão listadas aqui)
fonte
Respostas:
Python 2, 291 bytes
Uma função,
ftomando o labirinto como uma lista de linhas e retornando uma solução, se houver.Explicação
Executa uma pesquisa de amplitude no gráfico dos pares de posição / direção para encontrar o caminho mais curto de
SatéE.O interessante é encontrar uma maneira compacta de representar posições e direções em uma grade hexagonal, que admita "passos" simples (isto é, movendo-se em uma determinada direção) e rotação. É tentador usar números complexos aqui, para representar coordenadas em uma grade hexagonal "real", mas essa não é uma idéia muito boa por vários motivos, o mais sério dos quais é o fato de que precisamos conectar um √3 um lugar para fazê-lo funcionar (sen 60 ° = √3 / 2), que, ao usar números de ponto flutuante, não é possível se precisarmos de precisão absoluta (por exemplo, para acompanhar os estados que já visitamos;) você pode tentar inicializar seu console JavaScript, digitar
Math.sqrt(3)*Math.sqrt(3) == 3e ver por si mesmo.Mas, podemos usar um pequeno truque! Em vez de usar números complexos, vamos definir números hexagonais de maneira similar, como um par de números reais a + bh , em que h desempenha um papel semelhante ao imaginário i ao lidar com números complexos. Assim como em números complexos, podemos associar o par ( a , b ) a um ponto no plano, onde o eixo real aponta para a direita, o eixo imaginário aponta 60 ° para cima e ambos cruzam o hexágono regular da unidade quando o real e as partes imaginárias são iguais a 1, respectivamente. Mapear esse sistema de coordenadas para as células do labirinto é trivial.
Diferentemente de i , a constante h é definida pela relação h 2 = h - 1 (a solução de h pode revelar algumas idéias.) E é isso! Número hexagonal pode ser adicionado e multiplicado, usando a relação acima, bem como os números complexos: ( a + BH ) + ( C + DH ) = ( a + c ) + ( b + d ) H ,
e ( a + bh ) · ( c + dh ) = ( ac - bd) + ( +ad + bc + bd ) h . Essas operações têm a mesma interpretação geométrica de suas contrapartes complexas: adição é adição vetorial e multiplicação é dimensionamento e rotação. Em particular, para girar um número hexagonal 60 ° no sentido anti-horário, multiplicamos por h :
( a + bh ) · h = - b + ( a + b ) h , e para rodar o mesmo número 60 ° no sentido horário, dividimos por h :
( a + bh ) / h = ( a bh) · (1 - h ) = (a + b) - ah . Por exemplo, podemos pegar o número hexagonal da unidade apontando para a direita, 1 = (1, 0), um círculo completo, no sentido anti-horário, multiplicando-o por h seis vezes:
(1, 0) · h = (0, 1 ); (0, 1) · h = (-1, 1); (-1, 1) · h = (-1, 0); (-1, 0) · h = (0, -1); (0, -1) · h = (1, -1);
(1, -1) · h = (1, 0).
O programa usa números hexagonais dessa maneira para representar a posição atual no labirinto e a direção atual, para avançar na direção especificada e girar a direção para a esquerda e para a direita.
fonte
Hexagonia , 2437 bytes
O tão esperado programa está aqui:
Experimente online!
Versão "legível":
Testado no IDE esotérico: o TIO pode atingir o tempo limite em alguns dos casos de teste maiores, mas todos verificados. Muito obrigado a Timwi, isso não teria sido possível sem o IDE.
Há um pouco de espaço vazio, então eu poderia ser capaz de encaixar isso em um hexágono 28 de comprimento lateral (em vez de 29), mas essa será uma tarefa enorme, por isso provavelmente não vou tentar.
Explicação básica
Clique nas imagens para obter uma versão maior e mais detalhada.
Funções
Nota: As divisões geralmente estão corretas, mas ocasionalmente podem ser um palpite aproximado.
Este código é bastante "funcional" - tanto quanto o Hexagony permite. Existem oito funções principais nesse código, rotuladas no diagrama acima, nomeadas pelos números com os quais são chamados (portanto, os números dos ponteiros de instruções são o número mod 6). Em ordem (aproximada) de chamada, eles são (nomes citados são locais na memória que serão explicados mais adiante):
F,ReLpronto para o processamento principal. O ponteiro de instrução 0 passa para a função 0 enquanto a execução passa para a função 1.+movimento dentro de 2 movimentos após o primeiro alcance. Retorna à função 1.F. Retorna à função 1.F,RouLanexado. Retorna à função 1.FFLF), depois finaliza o programa.Invalid maze!e termina.Memória
Nota: Obrigado novamente ao IDE Esotérico pelo diagrama
A memória consiste em três partes principais:
0ou um lugar válido que foi acessado mais jogadas atrás do que seria necessário para sair do lugar em qualquer direção.+que ainda não foi alcançado.-1s com um único-2à esquerda, permite que o ponteiro de memória retorne rapidamente à área de processamento do núcleo.F,R,Lcomo1,2,3respectivamente-1s à direita e valores de y acima (embora y = 0 seja processado como 1 de qualquer maneira para fins de separar o trilho dos dados de referência)Outros locais importantes de memória:
Eé armazenado aqui.fonte
Python 3, 466 bytes
Provavelmente teria ficado menor se eu usasse uma pesquisa profunda ou algo assim. Essa monstruosidade usa Dijkstra e é bastante rápida, mas muito longa.
O código define uma função
Sque pega uma cadeia de linhas múltiplas com o labirinto e retorna o resultado.Aqui está um teste do código.
Ungolfed
fonte
L,,R.Groovy, 624 bytes. Fore!
Com o tempo, a bola rola com uma grande. Leva uma sequência de linhas múltiplas como arg para
QVersão não destruída:
fonte
C #,
600574 bytesPrograma completo, aceita entrada de STDIN, saída para STDOUT.
Edit: houve um bug no manuseio do envoltório (não quebrou em nenhum dos casos de teste) que teria adicionado 1 byte, então eu fiz um pouco mais de golfe para compensar.
Começa lendo no mapa, anexando
(a cada linha para saber onde termina e pode voltar e adicionar uma carga de espaços para tornar o mapa retangular e com uma linha de espaços ao lado direito (isso economiza fazendo verificações de embrulho, como será explicado abaixo). Ele calcula a largura do retângulo em algum momento e determina o comprimento total do mapa.Em seguida, inicializa tudo para uma pesquisa de largura em primeiro lugar. Duas matrizes grandes são criadas, uma para armazenar todos os estados que precisamos explorar em nossa pesquisa e a outra para registrar a rota que seguimos para chegar a cada estado. O estado inicial é adicionado à matriz devido, com os ponteiros de cabeça e cauda predefinidos de alguma maneira acima. Tudo é indexado em 1.
Nós então iteramos até que a cauda colide com a cabeça, ou pelo menos pareça ter colidido com a cabeça. Para cada estado que visitamos, tentamos adicionar um novo estado na mesma posição em que somos rotacionados para a esquerda ou direita e depois para onde avançamos. As direções são indexadas, com a direção inicial (padrão
0) correspondente a "cima-esquerda".Quando tentamos enfileirar um estado, ele é marcado como checado, mas não checado, por causa das colunas de espaços no lado direito, que são captadas pelo "nós podemos estar aqui?" cheque (você não pode estar em espaços). Se o estado estiver na fila, verificaremos se está na
Ecélula e, se estiver, definiremos o início da fila como menos ele mesmo, o que faz com que o loop principal saia e informa a última linha do programa para imprimir a rota correspondente, em vez da mensagem de falha (que mostra se ficarmos sem estados para expandir (a cauda bate na cabeça)).Como a maioria das minhas pesquisas de gráficos neste site, estou fazendo bom uso de estruturas em C #, que são padrão para comparar por valor literal.
fonte
Python 2, 703 bytes
Não é tão bom quanto as outras duas versões, mas pelo menos funciona haha. Defina
Mpara o labirinto.Como não tenho experiência em resolver labirintos, ele segue uma abordagem de força bruta, onde encontra todas as soluções possíveis que não envolvem a passagem de si mesmas. Calcula as voltas a partir das mais curtas e depois escolhe o menor resultado.
Versão desarrumada desarrumada:
fonte
if heading != required_heading: while heading != required_heading:por apenaswhile heading != required_heading: