Curva ASCII Hilbert

23

Dada uma nsaída inteira, a niteração da Curva de Hilbert em ASCII usando os caracteres _e |.

Aqui estão as primeiras 4 iterações:

n=1
 _ 
| |

n=2
 _   _ 
| |_| |
|_   _|
 _| |_

n=3
 _   _   _   _ 
| |_| | | |_| |
|_   _| |_   _|
 _| |_____| |_ 
|  ___   ___  |
|_|  _| |_  |_|
 _  |_   _|  _ 
| |___| |___| |

n=4
 _   _   _   _   _   _   _   _ 
| |_| | | |_| | | |_| | | |_| |
|_   _| |_   _| |_   _| |_   _|
 _| |_____| |_   _| |_____| |_ 
|  ___   ___  | |  ___   ___  |
|_|  _| |_  |_| |_|  _| |_  |_|
 _  |_   _|  _   _  |_   _|  _ 
| |___| |___| |_| |___| |___| |
|_   ___   ___   ___   ___   _|
 _| |_  |_|  _| |_  |_|  _| |_ 
|  _  |  _  |_   _|  _  |  _  |
|_| |_| | |___| |___| | |_| |_|
 _   _  |  ___   ___  |  _   _ 
| |_| | |_|  _| |_  |_| | |_| |
|_   _|  _  |_   _|  _  |_   _|
 _| |___| |___| |___| |___| |_ 

Esclarecimentos

  • Minha pergunta é semelhante a Draw the Hilbert Curve e Draw the Hilbert curve usando barras .
  • A conversão entre sublinhados ( _) e as barras verticais ( |) é u=2*v-1onde uestá o número de _s e vé o número de |s.
  • Para manter a consistência com o meu post original, a curva deve começar e terminar na parte inferior.
  • Você pode ter um programa completo ou uma função.
  • Saída para stdout (ou algo semelhante).
  • Você pode ter espaços em branco à esquerda ou à direita; a saída só precisa ser alinhada para parecer com os exemplos.
  • Este é o código-golfe, pelo que a resposta mais curta em bytes vence.
Bobas_Pett
fonte
3
Você poderia incluir uma definição da Curva de Hilbert em suas publicações e as especificações exatas de como a versão ASCII é construída?
Loovjo
@Bobas_Pett: Não Kolmogorov-complexidade
shooqie
@shooqie há algum debate sobre isso na meta
Trichoplax
@Loovjo Adicionei em um ponto sobre os comprimentos de sublinhados (_) e barras verticais (|) em "Esclarecimentos", se mais informações ou uma definição rigorosa ainda forem necessárias, por favor me diga.
24816 Bobas_Pett
@shooqie i removido a tag
Bobas_Pett

Respostas:

5

Befunge, 444 368 323 bytes

&1>\1-:v
0v^*2\<_$00p>
_>:10p\:20pv^_@#-*2g00:+1,+55$
^!-<v*2g000<>$#<0>>-\:v
g2*^>>10g20g+v \ ^*84g_$:88+g,89+g,\1+:00
v#*!-1g02!g01_4^2_
>::00g2*-!\1-:10g-\20g-++>v
87+#^\#p01#<<v!`g01/2\+76:_
vv1-^#1-g01:\_$:2/20g`!
_ 2/^>:10g#vv#`g02/4*3:\+77
v>0p^^/2:/2_
<^2-1-g02</2`#*3:
0g+10p2*:^*3_1
! "#%$
%$"#!
 !!##%
|||_
 _ __

Experimente online!

A abordagem típica para desenhar a curva de Hilbert é seguir o caminho como uma série de traços e curvas, renderizando o resultado em um bitmap ou em alguma área da memória e, em seguida, gravando essa renderização quando o caminho estiver completo. Isso não é viável no Befunge quando temos apenas 2000 bytes de memória para trabalhar, e isso inclui a fonte do próprio programa.

Portanto, a abordagem que adotamos aqui é criar uma fórmula que nos diga exatamente qual caractere produzir para uma determinada coordenada x, y. Para entender como isso funciona, é mais fácil de ignorar a prestação ASCII para começar, e apenas pensar na curva como composta de caracteres de caixa: , , , , , e .

Quando olhamos para a curva assim, podemos ver imediatamente que o lado direito é um espelho exato do lado esquerdo. Os caracteres à direita podem ser simplesmente determinados procurando o parceiro à esquerda e refletindo-o horizontalmente (ou seja, ocorrências de e são trocadas, como são e ).

Curva Hilbert de nível 3, mostrando a reflexão no eixo vertical

Então, olhando para o canto inferior esquerdo, novamente podemos ver que a metade inferior é um reflexo da metade superior. Assim, os caracteres na parte inferior são simplesmente determinados procurando o parceiro acima e refletindo-o verticalmente (ou seja, ocorrências de e são trocadas, como são e ).

Curva Hilbert de nível 3, mostrando o reflexo no eixo horizontal no canto inferior esquerdo

A metade restante deste canto é um pouco menos óbvia. O bloco do lado direito pode ser derivado de uma reflexão vertical do bloco na diagonal adjacente a ele.

Curva Hilbert de nível 3, mostrando como o bloco superior direito do canto inferior esquerdo pode ser derivado

E o bloco da mão esquerda pode ser derivado de uma reflexão vertical do bloco no canto superior esquerdo da curva completa.

Curva de Hilbert de nível 3, mostrando como o bloco superior esquerdo do canto inferior esquerdo pode ser derivado

Neste ponto, tudo o que resta é o canto superior esquerdo, que é apenas mais uma curva de Hilbert uma iteração mais baixa. Em teoria, agora precisamos repetir o processo novamente, mas há um problema - nesse nível, as metades esquerda e direita do bloco não são espelhos exatos uma da outra.

Portanto, em qualquer coisa que não seja o nível superior, os caracteres do canto inferior precisam ser tratados como um caso especial, onde o caractere é refletido como e o caractere é refletido como .

Curva de Hilbert de nível 3, mostrando como o bloco superior esquerdo do canto inferior esquerdo pode ser derivado

Mas, fora isso, podemos realmente repetir esse processo recursivamente. No último nível, codificamos o caractere superior esquerdo como e o caractere abaixo dele como .

Sequência de imagens mostrando como as partes restantes da curva são derivadas

Agora que temos uma maneira de determinar a forma da curva em uma determinada coordenada x, y, como podemos traduzir isso na renderização ASCII? Na verdade, é apenas um mapeamento simples que traduz cada bloco possível em dois caracteres ASCII.

  • torna-se  _(espaço mais sublinhado)
  • torna-se   (dois espaços)
  • torna-se |_(barra vertical mais sublinhado)
  • torna-se (barra vertical mais espaço)
  • torna-se (novamente uma barra vertical mais espaço)
  • torna-se __(dois sublinhados)

Esse mapeamento não é intuitivo a princípio, mas você pode ver como ele funciona quando olha duas renderizações correspondentes lado a lado.

Curva Hilbert de nível 2, renderizada como arte ASCII e com caracteres de caixa

E isso é basicamente tudo o que existe. Na verdade, implementar esse algoritmo no Befunge é outro problema, mas deixarei essa explicação para outro momento.

James Holderness
fonte
2

C, 267 bytes

const n=4,s=1<<n,a[]={1,-s,-1,s};l,p,q;
t(d){d&=3;p-q||printf("%.2s",&"__|      _|       |___ _|_| | | "[l*8+d*2]);p+=a[l=d];}
h(d,r,n){n--&&(h(d+r,-r,n),t(d+r),h(d,r,n),t(d),h(d,r,n),t(d-r),h(d-r,-r,n));}
main(){for(;p=s*s-s,l=1,q<s*s;++q%s||putchar(10))h(0,1,n),t(3);}

Experimente online!

h()usa recursão para gerar os traços da curva hlibert. t()somente imprime o caractere de traçado se a posição da caneta pfor igual à posição de saída atual q.

Isso é ineficiente, mas simples.

Se a curva começar no canto superior esquerdo, o código poderá ser reduzido para 256 bytes.

Milo Yip
fonte
Sugerir em puts("")vez de putchar(10)e em "..."+l*8+d*2vez de &"..."[l*8+d*2]e em n--?h(d+r...-r,n):0vez den--&&(h(d+r...-r,n))
tetocat 21/07