Um labirinto em uma grade N por N de células quadradas é definido especificando se cada aresta é uma parede ou não. Todas as arestas externas são paredes. Uma célula é definida como o início , e uma célula é definida como a saída , e a saída é alcançável desde o início. O início e a saída nunca são a mesma célula.
Observe que nem o início nem a saída precisam estar na borda externa do labirinto, portanto, este é um labirinto válido:
Uma sequência de 'N', 'E', 'S' e 'W' indica a tentativa de mover para o norte, leste, sul e oeste, respectivamente. Um movimento bloqueado por uma parede é pulado sem movimento. Uma string sai de um labirinto se a aplicação dessa string desde o início resultar no alcance da saída (independentemente de a string continuar depois de chegar à saída).
Inspirada por essa pergunta intrigante.SE para a qual o xnor forneceu um método comprovável de solução de uma string muito longa, escreva um código que possa encontrar uma única string que saia de qualquer labirinto de 3 por 3.
Excluindo labirintos inválidos (iniciar e sair na mesma célula ou saída inacessível desde o início), existem 138.172 labirintos válidos e a string deve sair de cada um deles.
Validade
A cadeia deve satisfazer o seguinte:
- É composto apenas pelos caracteres 'N', 'E', 'S' e 'W'.
- Ele sai de qualquer labirinto ao qual é aplicado, se iniciado no início.
Como o conjunto de todos os labirintos possíveis inclui cada labirinto possível com cada ponto de partida válido possível, isso significa automaticamente que a string sairá de qualquer labirinto de qualquer ponto de partida válido. Ou seja, a partir de qualquer ponto de partida a partir do qual a saída seja alcançável.
Ganhando
O vencedor é a resposta que fornece a menor seqüência válida e inclui o código usado para produzi-la. Se mais de uma das respostas fornecer uma string com o menor comprimento, a primeira a postar esse comprimento vence.
Exemplo
Aqui está um exemplo de 500 caracteres, para oferecer a você algo para vencer:
SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE
Obrigado ao orlp por doar isso.
Entre os melhores
As pontuações iguais são listadas em ordem de publicação dessa pontuação. Essa não é necessariamente a ordem em que as respostas foram postadas, pois a pontuação de uma determinada resposta pode ser atualizada ao longo do tempo.
Juiz
Aqui está um validador Python 3 que utiliza uma sequência de caracteres NESW como argumento de linha de comando ou via STDIN.
Para uma sequência inválida, isso fornecerá um exemplo visual de um labirinto em que ela falha.
fonte
Respostas:
C ++,
979593918683828179 caracteresMinha estratégia é bastante simples - um algoritmo de evolução que pode crescer, encolher, trocar elementos e alterar seqüências válidas. Minha lógica de evolução agora é quase a mesma da @ Sp3000, pois a dele foi uma melhoria em relação à minha.
No entanto, minha implementação da lógica do labirinto é bastante bacana. Isso me permite verificar se as strings são válidas na velocidade de formação de bolhas. Tente descobrir olhando o comentário
do_move
e oMaze
construtor.fonte
do_move
agora é incrivelmente rápido.Python 3 + PyPy,
8280 caracteresEu tenho hesitado em postar esta resposta, porque eu basicamente peguei a abordagem do orlp e coloquei minha própria rotação nela. Essa string foi encontrada iniciando com uma solução de tamanho pseudo-aleatório 500 - várias sementes foram testadas antes que eu pudesse quebrar o recorde atual.
A única nova grande otimização é que eu olho apenas um terço dos labirintos. Duas categorias de labirintos são excluídas da pesquisa:
<= 7
quadrados são acessíveisA idéia é que qualquer corda que resolva o resto dos labirintos também resolva o problema acima automaticamente. Estou convencido de que isso é verdade para o segundo tipo, mas definitivamente não é verdade para o primeiro, portanto a saída conterá alguns falsos positivos que precisam ser verificados separadamente. No entanto, esses falsos positivos geralmente perdem apenas cerca de 20 labirintos, então eu pensei que seria uma boa troca entre velocidade e precisão, e também daria às cordas um pouco mais de espaço para respirar.
Inicialmente, examinei uma longa lista de heurísticas de pesquisa, mas horrorosamente nenhuma delas apresentou algo melhor que 140 ou mais.
fonte
0
paran
ao longo do caminho e suponha que a seqüênciaS
leva você de0
paran
. Em seguida,S
você também de qualquer célula intermediáriac
paran
. Suponha o contrário. Leta(i)
Ser a posição após asi
etapas começando em0
eb(i)
começando emc
. Entãoa(0) = 0 < b(0)
, cada etapa mudaa
eb
, no máximo, 1 ea(|S|) = n > b(|S|)
. Pegue o menort
tal quea(t) >= b(t)
. Claramentea(t) != b(t)
ou eles estariam sincronizados, eles devem trocar de lugar na etapat
, movendo-se na mesma direção.C ++ e a biblioteca do lingeling
Usando uma abordagem baseada em SAT , eu poderia resolver completamente o problema semelhante para labirintos 4x4 com células bloqueadas em vez de paredes finas e posições fixas de partida e saída em cantos opostos. Então, eu esperava poder usar as mesmas idéias para esse problema. No entanto, mesmo para o outro problema, eu usei apenas 2423 labirintos (enquanto isso foi observado em 2083) e ele tem uma solução de comprimento 29, a codificação SAT usou milhões de variáveis e a solução levou dias.
Então, decidi mudar a abordagem de duas maneiras importantes:
Também fiz algumas otimizações para usar menos variáveis e cláusulas de unidade.
O programa é baseado em @ orlp's. Uma mudança importante foi a seleção de labirintos:
is_solution
verifica se todas as posições alcançáveis são alcançadas.Dessa forma, recebo um total de 10772 labirintos com posições iniciais.
Aqui está o programa:
Primeiro
configure.sh
emake
olingeling
solucionador, compile o programa com algo comog++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl
, onde...
está o caminho em quelglib.h
resp.liblgl.a
são, então ambos poderiam ser, por exemplo../lingeling-<version>
. Ou simplesmente coloque-os no mesmo diretório e sem as opções-I
e-L
.O programa tem um argumento de linha de comando obrigatório, uma cadeia que consiste
N
,E
,S
,W
(para direções fixas) ou*
. Portanto, você pode procurar uma solução geral de tamanho 78, fornecendo uma sequência de 78*
s (entre aspas) ou procurar uma solução começando comNEWS
,NEWS
seguido de tantos*
s quanto desejar para etapas adicionais. Como primeiro teste, pegue sua solução favorita e substitua algumas das letras por*
. Isso encontra uma solução rápida para um valor surpreendentemente alto de "alguns".O programa dirá qual labirinto ele adiciona, descrito pela estrutura da parede e posição inicial, e também fornecerá o número de posições e paredes alcançáveis. Os labirintos são classificados por esses critérios e o primeiro não resolvido é adicionado. Portanto, a maioria dos labirintos adicionados tem
(9/4)
, mas às vezes outros aparecem também.Peguei a solução conhecida de comprimento 79 e, para cada grupo de 26 letras adjacentes, tentei substituí-las por 25. Também tentei remover 13 letras do começo e do fim e substituí-las por 13 no início e 12 no final e vice-versa. Infelizmente, tudo saiu insatisfatório. Então, podemos tomar isso como um indicador de que o comprimento 79 é ideal? Não, tentei da mesma forma melhorar a solução do comprimento 80 para o comprimento 79, e isso também não teve êxito.
Por fim, tentei combinar o início de uma solução com o final da outra e também com uma solução transformada por uma das simetrias. Agora que estou ficando sem idéias interessantes, decidi mostrar o que tenho, mesmo que não tenha levado a novas soluções.
fonte