Floco de neve de Koch - codegolf

21

O floco de neve Koch (também conhecido como estrela Koch e ilha Koch) é uma curva matemática e uma das primeiras curvas fractais já descritas. Baseia-se na curva de Koch, que apareceu em um artigo de 1904 intitulado "Em uma curva contínua sem tangentes, construtível a partir da geometria elementar" (título original em francês: "Sur une courbe continue sans tangente, obtenue par une construction geometrique élémentaire") por o matemático sueco Helge von Koch.

insira a descrição da imagem aqui

Aqui estão algumas representações ascii de várias iterações:

n=1
__
\/

n=2
__/\__
\    /
/_  _\
  \/

n=3
      __/\__
      \    /
__/\__/    \__/\__
\                /
/_              _\
  \            /
__/            \__
\                /
/_  __      __  _\
  \/  \    /  \/
      /_  _\
        \/ 

Como obviamente existe um limite para a resolução da representação ascii, devemos aumentar o tamanho do floco de neve em um fator de 3 para cada iteração para mostrar detalhes adicionais.

Escreva o código mais curto para gerar o floco de neve no mesmo estilo para n = 4

Seu programa não deve receber nenhuma entrada.
Seu programa deve gravar o floco de neve no console.

mordedor
fonte
Koch-floco de neve ..um tag .. isso é interessante .. !! .. Parece que você será disparar mais perguntas sobre esta tag :)
Aman Verma Zeek
5
Muito curto para uma resposta: wolframalpha.com/input/?i=koch+snowflake+4 : D
Dr. belisarius
11
A resposta aceita deve ser alterada? Existem soluções mais curtas agora.
Tim11

Respostas:

2

Python, 338 bytes

#coding:u8
print u"碜䄎쀠ࢻ﬊翀蝈⼖㗎芰悼컃뚔㓖ᅢ鄒鱖渟犎윽邃淁挢㇌ꎸ⛏偾࿵헝疇颲㬤箁鴩沬饅앎↳\ufaa4軵몳퍋韎巃๧瓠깡未늳蒤ꕴ⁵ᦸ䥝両䣚蟆鼺伍匧䄂앢哪⡈⁙ತ乸ሣ暥ฦꋟ㞨ޯ⿾庾뻛జ⻏燀䲞鷗﫿".encode("utf-16be").decode("zlib")

Apenas mais uma exploração unicode

correr em ideone

VOCÊS
fonte
5
É justo, mas certamente isso tornaria o arquivo de origem com mais de 300 bytes.
Timwi
o link está quebrado
Chiel ten Brinke em 01/01
10

Python, 650 612 594 574 caracteres

n='\n'
S='_a/G\F I\n'
A=dict(zip(S,('III','   ','__/','  G','\  ','F__','   ','III','')))
B=dict(zip(S,('III','   ','\  ',' aF','/a ','  G','   ','III','')))
C=dict(zip(S,('___','aaa','/  ','GII','II\\','  F','   ','III','')))
def T(s):
 a=b=c=d=r=u''
 for k in s:
    a+=A[k];b+=B[k];c+=C[k]
    if k=='I':a=a[:-3]+('II\\'if'a '==d[1:3]else'GII'if' a'==d[:2]else 3*k)
    d=d[3:]
    if k==n:d=c.replace('____','__/F').replace('aaaa','aa  ').replace('/  a','/a  ').replace('a  F','  aF');r+=a+n+b+n+d+n;a=b=c=''
 return r
print T(T(T('__\n\G\n'))).translate({97:95,71:47,73:32,70:92})

Isso funciona expandindo o triângulo por um fator de 3 a cada vez. Para fazer isso, precisamos acompanhar se cada símbolo é um limite esquerdo ou direito (por exemplo, como /é expandido depende de qual lado do lado de /dentro está). Usamos símbolos diferentes para os dois casos possíveis, como a seguir:

_: _, outside on the top
a: _, outside on the bottom
/: /, outside on the left
G: /, outside on the right
\: \, outside on the left
F: \, outside on the right
<space>: inside
I: outside

A dvariável lida com o caso especial em que a expansão de um aprecisa se estender para o 3x3 na próxima linha.

Keith Randall
fonte
+1 para obter a primeira resposta no quadro. Eu acho que você pode substituir os espaços duplos por uma guia no loop for. Além disso, tente usar se k < "C" em vez de K == "A" etc. Agora terei de olhar mais de perto o seu algoritmo :)
gnibbler
Você não pode remover as muitas instruções if com uma matriz associativa? E talvez as instruções de substituição encadeadas possam ser reduzidas com uma matriz.
Nabb 17/02/11
('acEei',r'_/\\ ')=> ('aecEi','_\/\ ')economiza mais 1. Você também pode querer verificar o unicode.translate().
Gnibbler
Isso também imprime cerca de 18 novas linhas antes do floco de neve, mas suponho que o OP não especificou se algo diferente do floco de neve pode ser impresso.
RomanSt
6

Código de máquina de 16 bits do MS-DOS: 199 bytes

Decodifique usando este site , salve como arquivo 'koch.com' e execute no prompt de comando do WinXP.

sCAAxo7ajsKLz/OquF9fulwvvUoBM9u+BADoiQDodgDocwDogADobQDoagDodwCK8TLSs0+I98cHDQrGRwIktAnNIf7GOO5+7MNWAVwBYwFsAXoBgwGJB4DDAsOIN/7D6QQA/suIF/7P6R0A/suAPyB1AogH/suIB8OBw/8AiDfpBgD+x4gX/sM4734Ciu84z30Cis/Dg8UIg8UCgf1WAXLzg+0Mw07/dgB0GV/o9v/o5v/o8P/o3f/o2v/o5//o1//o4f9Gww==

Atualizar

Aqui está uma versão do assembler de fácil leitura:

  ; L-System Description
  ;
  ; Alphabet : F
  ; Constants : +, -
  ; Axiom : F++F++F
  ; Production rules: F -> F-F++F-F 
  ;
  ; Register usage:
  ;                             _        _
  ; bp = direction: 0 = ->, 1 = /|, 2 = |\, 3 = <-, 4 = |/_, 5 = _\|
  ; cl = min y, ch = max y
  ; bl = x (unsigned)
  ; bh = y (signed)
  ; si = max level

  ; clear data
  mov al,20h
  add dh,al
  mov ds,dx
  mov es,dx
  mov cx,di
  rep stosb
  mov ax,'__'
  mov dx,'/\'

  ; initialise variables
  mov bp,Direction0
  xor bx,bx
  mov si,4

  call MoveForward
  call TurnRight
  call TurnRight
  call MoveForward
  call TurnRight
  call TurnRight
  call MoveForward

  mov dh,cl
  xor dl,dl
  mov bl,79
OutputLoop:
  mov bh,dh
  mov w [bx],0a0dh
  mov b [bx+2],24h
  mov ah,9
  int 21h
  inc dh
  cmp dh,ch
  jle OutputLoop  
  ret

Direction0:
  dw MoveRight
  dw MoveUpRight
  dw MoveUpLeft
  dw MoveLeft
  dw MoveDownLeft
  dw MoveDownRight
Direction6:

MoveRight:
  mov w [bx],ax
  add bl,2
  ret

MoveUpRight:
  mov b [bx],dh
  inc bl
  jmp DecBHCheckY

MoveUpLeft:
  dec bl
  mov b [bx],dl
DecBHCheckY:  
  dec bh
  jmp CheckY

MoveLeft:
  dec bl  
  cmp b [bx],20h
  jne MoveLeftAgain
  mov [bx],al
MoveLeftAgain:
  dec bl  
  mov [bx],al
  ret

MoveDownLeft:
  add bx,255
  mov b [bx],dh
  jmp CheckY

MoveDownRight:
  inc bh
  mov b [bx],dl
  inc bl

CheckY:
  cmp bh,ch
  jle NoMaxChange
  mov ch,bh
NoMaxChange:  
  cmp bh,cl
  jge NoMinChange
  mov cl,bh
NoMinChange:  
  ret

TurnRight:
  add bp,8

TurnLeft:
  add bp,2

  cmp bp,Direction6
  jb ret
  sub bp,12
  ret

MoveForward:
  dec si
  push [bp]
  jz DontRecurse
  pop di
  call MoveForward
  call TurnLeft
  call MoveForward
  call TurnRight
  call TurnRight
  call MoveForward
  call TurnLeft
  call MoveForward
DontRecurse:
  inc si
  ret
Skizz
fonte
Abolute mágica :), por favor me ajudar a entender isso (pelo menos fornecer um link sobre o que você fez)
Aman Verma Zeek
@ Aman: Ele usa uma descrição do sistema L da curva de Koch para desenhar a saída. O nível de detalhe é definido no registro SI, embora o tamanho seja limitado a 252 caracteres por linha. Você precisará modificar o código de impressão para obter linhas com mais de 79 caracteres (ou seja, alterar onde ele escreve os caracteres '\ n $').
Skizz 17/02
Também é possível usar "scAA...w==".decode("base64")a decodificação em python2 (não funciona para Python3)
gnibbler
+1 agora que tenho uma máquina Windows para executá-la. Alguma chance de você incluir a versão asm?
Gnibbler
2
@ellamokb: err, porque todo o código fonte está disponível, talvez?
Skizz 21/03
4

Perl, 176 175 bytes

Postando isso como uma resposta separada, porque ele usa um arquivo de origem binário, que talvez seja um pouco barato. Mas considerando que ainda é o código-fonte Perl , acho notável que ele supera a solução de código de máquina do MS-DOS !

Origem como codificado em base64

JF89IsLApwag0dhnMmAmMEcGIAcGQNHYwsDRFLsQ0djCwKcGoNHYwsDRFDdbECYwcRUxe1DCwNEUuxDR2
CI7c14uXiR4PW9yZCQmOyQieCgkeD4+MykucXcoXCAvXyBfXy8gXC8gX18gX1wgLyBfXy9cX18pWyR4Jj
ddXmVnO3NeLnsyN31eJF89cmV2ZXJzZSQmO3l+L1xcflxcL347cHJpbnQkJi4kXy4kL15lZw==

Um pouco mais legível

Substitua todas as instâncias /<[0-9a-f]+>/pelos dados binários relevantes:

# Raw data!
$_="<c2c0a706a0d1d86732602630470620070640d1d8c2c0d114bb10d1d8c2>".
   "<c0a706a0d1d8c2c0d114375b1026307115317b50c2c0d114bb10d1d8>";

# Decode left half of the snowflake (without newlines)
s^.^$x=ord$&;$"x($x>>3).qw(\ /_ __/ \/ __ _\ / __/\__)[$x&7]^eg;

# Reconstruct the right half and the newlines
s^.{27}^$_=reverse$&;y~/\\~\\/~;print$&.$_.$/^eg

Nesta versão, o floco de neve é ​​codificado da seguinte maneira:

  • Os 8 bits em cada byte são divididos assim:

    +---+---+---+---+---+---+---+---+
    |      5 bits       |   3 bits  |
    +---+---+---+---+---+---+---+---+
              R               C
    
  • Rcodifica uma série de espaços. A execução mais longa tem 27 caracteres, portanto, todas as execuções cabem em 5 bits.

  • Ccodifica uma sequência de caracteres que são simplesmente pesquisados ​​na matriz literal. (Eu costumava ter codificações um pouco mais loucas aqui, onde a matriz continha apenas / \ _, mas o código Perl necessário para decodificá-la era mais longo ...)

  • Tenho sorte de que os dados binários não contenham nenhum "/ 'ou \que precisariam escapar. Eu não planejei isso. Mas mesmo que isso acontecesse, eu provavelmente poderia ter mudado a ordem dos itens da matriz para corrigir isso.

  • É incrível como essa solução é comparada com as dezenas de outras soluções pelas quais eu passei antes de criar essa solução. Eu experimentei muitas codificações bit a bit diferentes e mais complexas que essa, e nunca me ocorreu que uma mais simples pudesse valer a pena simplesmente porque o código Perl para decodificá-la seria mais curto. Também tentei comprimir repetições nos dados usando interpolação variável (veja a outra resposta), mas com a versão mais recente que não ganha mais caracteres.

Timwi
fonte
3

Python, 284

for s in "eJyVkNENACEIQ/+dgg1YiIT9tzgENRyWXM4/pH1tIMJPlUezIiGwMoNgE5SzQvzRBq52Ebce6cr0aefbt7NjHeNEzC9OAalADh0V3gK35QWPeiXIFHKH8seFfh1zlQB6bjxXIeB9ACWRVwo=".decode('base64').decode('zlib').split('\n'):print s+'  '*(27-len(s))+'\\'.join([c.replace('\\','/')for c in s[::-1].split('/')])

Com um pouco mais de espaço em branco:

for s in "eJyVkNENACEIQ/+dgg1YiIT9tzgENRyWXM4/pH1tIMJPlUezIiGwMoNgE5SzQvzRBq52Ebce6cr0aefbt7NjHeNEzC9OAalADh0V3gK35QWPeiXIFHKH8seFfh1zlQB6bjxXIeB9ACWRVwo=".decode('base64').decode('zlib').split('\n'):
  print s + '  '*(27-len(s)) + '\\'.join([c.replace('\\','/') for c in s[::-1].split('/')])

O lado esquerdo está comprimido; o lado direito é reproduzido do lado esquerdo.

RomanSt
fonte
3

Perl, 224 223 caracteres

use MIME::Base64;$_=decode_base64 wsCnBqDR2GcyYCYwRwYgBwZA0djCwNEUuxDR2MLApwag0djCwNEUN1sQJjBxFTF7UMLA0RS7ENHY;s^.^$x=ord$&;$"x($x>>3).qw(\ /_ __/ \/ __ _\ / __/\__)[$x&7]^eg;s^.{27}^$_=reverse$&;y~/\\~\\/~;print$&.$_.$/^eg

Um pouco mais legível

use MIME::Base64;

# raw binary data in base-64-encoded form as a bareword
$_=decode_base64
    wsCnBqDR2GcyYCYwRwYgBwZA0djCwNEUuxDR2MLApwag0djCwNEUN1sQJjBxFTF7UMLA0RS7ENHY;

# Decode left half of the snowflake (without newlines)
s^.^$x=ord$&;$"x($x>>3).qw(\ /_ __/ \/ __ _\ / __/\__)[$x&7]^eg;

# Reconstruct the right half and the newlines
s^.{27}^$_=reverse$&;y~/\\~\\/~;print$&.$_.$/^eg

Como funciona

Para uma explicação de como funciona, veja a outra resposta na qual eu publico o mesmo em binário . Sinto muito por não estar realmente gerando o floco de neve Koch, apenas o comprimindo ...

Versões prévias

  • (359) Codificou o floco de neve inteiro em vez da metade esquerda. Os espaços foram incluídos na codificação de bits; ainda não há duração. Utilizou várias variáveis ​​interpoladas mais uma @_matriz que foi acessada usando s/\d/$_[$&]/eg. Novas linhas foram codificadas como !.

  • (289) Primeira versão que codificava apenas a metade esquerda do floco de neve.

  • (267) Primeira versão que usou codificação de execução para os espaços.

  • (266) Mude ' 'para $".

  • (224) Compressão radicalmente diferente, codificada como base-64. (Agora equivalente à versão binária .)

  • (223) Percebi que posso colocar a impressão dentro do último subst e, assim, salvar um ponto e vírgula.

Timwi
fonte