Eu sei que existe um segmento (antigo) semelhante a este ( aqui ), mas eu gostaria de reiniciá-lo com algumas modificações.
O objetivo: gerar um labirinto de aparência aleatória usando um algoritmo de sua escolha e depois imprimir o labirinto graficamente (contagens de impressão).
- A largura e a altura são determinadas por você.
- Deve haver pelo menos um caminho de pelo menos uma entrada para pelo menos uma saída.
- O formato do labirinto (como você o exibe, marca entrada (s) ou saída (s)) também depende de você.
- Quanto mais bonita, melhor.
- Labirintos triviais (por exemplo, labirintos em branco, labirintos de treliça, labirintos de tamanho 1x1) são desencorajados.
- Ciclos no labirinto são permitidos e, são incentivados, se o resultado for razoável.
- Abuso de linguagem incentivado.
- O labirinto deve parecer razoavelmente aleatório (mas um algoritmo completamente determinístico (por exemplo, caótico) que gera isso também é bom).
Edit: o foco principal aqui é fazer a menor implementação possível. No entanto, quero permitir uma margem de manobra dentro dessa restrição para incentivar o brilho. Eu deixei deliberadamente exatamente quais "características" o labirinto tem em aberto, mas como uma diretriz aproximada, você deve tentar colocar a maior quantidade de estrondo no dinheiro menos lexical.
code-golf
popularity-contest
maze
imallett
fonte
fonte
Respostas:
C:
265253 bytes(Requer terminal de 65 caracteres) Gera um labirinto 31x31 relativamente aleatório com um caminho garantido da entrada para a saída.
Exemplo de saída (com terminal simulado de 65 caracteres):
fonte
int p,int c
.p,c
é suficiente ...Mathematica,
144132 bytesDesde o início, todos sabemos a maneira mais eficiente de desenhar um labirinto .
Saída ungolfed e exemplo:
Claro, as linhas são as paredes. Você é o minotauro que começa no centro e precisa sair.
fonte
C: 364 bytes
Nota: acima, adicionei novas linhas para ajustá-lo à página. Saída esperada (no terminal de 80 caracteres) (observe o início e o término no canto superior esquerdo):
fonte
Mathematica,
134130 caracteresDe fato, podemos usar esse algoritmo para gerar um labirinto a partir de qualquer gráfico (não direcionado).
Por exemplo, gere um labirinto a partir do gráfico de excursão do cavaleiro 8 * 8 (
KnightTourGraph[8,8]
):fonte
Bash, 53 bytes
Idéia semelhante ao código C64. Usa caracteres Unicode como barras, porque eles são muito mais agradáveis em um terminal que suporta Unicode. Exemplo de saída no OS X Terminal (fonte Menlo):
fonte
yes 'c=(╱ ╲);printf ${c[RANDOM%2]}'|bash
. Veja esta publicaçãoJavaScript (ES6), 174
Este é o labirinto que usei nesse outro desafio , apenas jogando golfe. É uma função com 2 parâmetros: linhas e colunas. O labirinto é totalmente conectado sem loops, então qualquer local pode ser o ponto inicial ou final.
Exemplo
Saída
Teste
fonte
ZX Basic - 54 caracteres
Aqui está o labirinto mostrando uma rota através dele (espaços entre linhas)
e um pequeno trecho de quando eu fiz isso pela primeira vez (há vários anos) e passei um pouco de tempo fazendo gráficos melhores.
fonte
BBC BASIC, 18 bytes
Uma melhoria no comprimento da versão de loop infinito C64 de 23 bytes da @nneonneo. O VDU envia um único caractere para o controlador VDU: 2 + 1 * 45 = ASCII 47
/
ou 2 + 2 * 45 = ASCII 92\
BBC BASIC, 35 bytes /
10795 bytes35 bytes é apenas para a última linha, que fornece um labirinto de 25 linhas no layout de 40 colunas. MODE1 garante que não haja espaço extra entre as linhas. O restante do programa é opcional e melhora a formatação. As instruções VDU23 redefinem a fonte dos caracteres 47 e 92 (8 bytes formando um bitmap de 8x8). Incluo um pixel claro nos quatro cantos para impedir que execuções retas sejam cortadas. O efeito colateral disso é que um ponto aparece nos diamantes vazios. Total de 107 bytes, incluindo 2 novas linhas.
Editar este programa pode ser reduzido para 95 bytes, codificando alguns dos códigos VDU de 8 bits em pequenos valores endianos de 16 bits (indicados por um ponto-e-vírgula depois deles em vez de vírgula) e representando a instrução MODE como um par de códigos VDU, da seguinte maneira .
Saída
Usando o BBC Basic para Windows em bbcbasic.co.uk
Somente última linha, 35 bytes
Programa inteiro,
10795 bytesComo comentei na resposta de @ Brian, a barra divide o quadrado em 2 triângulos escuros, cada um com exatamente 2 entradas / saídas. Isso garante um caminho (trivial, não ramificado) de qualquer ponto na borda do labirinto até algum outro ponto na borda do labirinto. Muitos deles são muito curtos, mas sempre parecem existir alguns longos. Claro, no meio do labirinto também existem alguns loops.
Como outras respostas não mencionaram isso, eu gostaria de dar uma boa olhada nas áreas claras. Elas são delimitadas por áreas escuras; portanto, como corolário da afirmação acima, uma área clara delimitada externamente por N áreas escuras toca a borda do campo em N (exatamente quantos) pontos. Portanto, algumas áreas de luz razoavelmente grandes ocorrem e elas formam labirintos interessantes e ramificados.
No exemplo abaixo, você pode ver a saída bruta (monocromática) do meu programa. Abaixo disso (usando o Windows Paint), pintei as duas áreas escuras mais longas em azul. Depois pintei a maior área clara em amarelo e as duas áreas delimitadas por azul em vermelho e verde. Os labirintos amarelos, verdes (e até vermelhos) são bastante interessantes e não triviais.
EDIT - Seleção automática de labirintos e seleção de partidas / finais
Para mais uma linha (59 caracteres), o programa pode selecionar automaticamente até 6 labirintos escolhendo quadrados aleatoriamente e preenchendo cores nas cores vermelho, verde, amarelo, azul, magenta e ciano. Nem sempre encontra um 6 completo, porque se ele escolhe um quadrado aleatório que já foi colorido, não faz nada.
O restante do código abaixo seleciona o início de cada cor, digitalizando cada coluna de cima para baixo e da esquerda para a direita e escolhendo o primeiro quadrado encontrado. Ele escolhe um fim, digitalizando na direção oposta.
Isso produz um conjunto de labirintos coloridos e entrelaçados. Às vezes, eles estão tão entrelaçados que parece que os labirintos devem atravessar algum lugar. Mas é claro que não!
Código e saída adicionais 59 + 187 = 246 caracteres adicionais a serem adicionados ao final do programa original (para aprimoramento além das especificações das perguntas)
fonte
C: 235 bytes
Nota: acima, adicionei novas linhas para ajustá-lo à página. Saída esperada (no terminal de 80 caracteres):
Lamento que este não seja um labirinto muito difícil (na verdade, não é necessário voltar atrás aos anéis internos (e você deve encontrar um caminho do perímetro para o centro trivialmente) .No entanto, ele tem uma boa implementação do círculo de Bresenham algoritmo de desenho em sua essência.
fonte
i+=2
parai+=3
, pode ficar mais claro o que está acontecendo.Ajudei meu filho a fazer isso, a aprender um pouco de programação: http://jsfiddle.net/fs2000/4KLUC/34/ como você gosta?
fonte
Commodore 64 BASIC - 38 bytes
Esta não é minha invenção, estou simplesmente repetindo um programa muito bonito e curto dos dias passados. De fato, há um livro inteiro chamado
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
celebrando esse pedaço de código!Você pode ver a saída deste vídeo do YouTube ; Aqui está um screencap:
Aqui nesta questão do StackOverflow, há mais implementações deste programa gerador de labirinto. A implementação mais curta do programa é o seguinte programa C64 BASIC de 23 bytes publicado pelo autor da pergunta:
onde as letras minúsculas são inseridas como estão e as letras maiúsculas são inseridas usando a tecla Shift (elas têm aparências diferentes na tela C64 real).
fonte
Java: 700
Aqui está um adicionador de parede recursivo. O algoritmo está descrito neste site :
Basicamente, ele divide cada retângulo em dois com uma parede (e passagem), depois os divide em dois, etc. Gera um labirinto "perfeito" - um sem ciclos - que tem um caminho de todos os pontos para todos os outros pontos. Muitos becos sem saída, por isso não é "trivial" em nenhum sentido para labirintos maiores.
Assim, a entrada e saída podem ser decididas arbitrariamente. Se eu tiver que escolher um, será apenas superior / esquerda e inferior / direita.
Ele é desenhado em ascii de largura dupla, por isso é uma boa idéia canalizar a saída para um arquivo se você estiver usando um tamanho qualquer. Aqui está um console 20x20:
E um 100x100 no bloco de notas ++ (eu tive que diminuir o zoom para obter tudo, então é um pouco ... pequeno ):
Código com quebras de linha:
fonte
ZX Basic - 281 caracteres
Este é mais um labirinto "adequado", menos golfista, mas mais labirinto. O chamado algoritmo de labirinto binário, cada célula pode ter uma saída descendente ou direita, mas não as duas. (Agora inclui as marcadas Start "S" e End "E", para evitar apenas seguir em frente).
O "::" é a maneira do ZXB de inserir caracteres gráficos do Spectrum em um arquivo de texto, igual a um caractere de bloco vendido.
fonte
C- 244
Aqui está como ele se parece:
Nota: esta solução é inspirada no jogo não confiável nível 8: na floresta.
fonte