# Koch Snowflake - codegolf

The Koch snowflake (also known as the Koch star and Koch island) is a mathematical curve and one of the earliest fractal curves to have been described. It is based on the Koch curve, which appeared in a 1904 paper titled "On a continuous curve without tangents, constructible from elementary geometry" (original French title: "Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire") by the Swedish mathematician Helge von Koch. Here are some ascii representations of various iterations:

n=1
__
\/

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

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


Since there is obviously a limit to the resolution of the ascii representation, we must enlarge the size of the snowflake by a factor of 3 for each iteration to show the extra detail.

Write the shortest code to output the snowflake in the same style for n=4

Your program should not take any input.
Your program should write the snowflake to the console.

• Koch-snowflake ..a tag .. thats interesting..!!.. seems you will be firing more questions on this tag :) Feb 17, 2011 at 19:22
• Too short for an answer: wolframalpha.com/input/?i=koch+snowflake+4 :D Feb 18, 2011 at 21:05
• Should the accepted answer be changed? There are shorter solutions now. Apr 2, 2011 at 11:36

## Python, 650612594 574 characters

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})


This works by expanding the triangle by a factor of 3 each time. To do that, we need to keep track of whether each symbol is a left or right boundary (e.g. how / is expanded depends on which side of the / is the inside). We use different symbols for the two possible cases, as follows:

_: _, 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


The d variable handles the special case where the expansion of an a needs to extend into the 3x3 in the next row.

• +1 for getting the first answer on the board. I think you can replace the double spaces with a tab in the for loop. Also try using if k<"C" instead of K=="A" etc. Now I shall have to look closer at your algorithm :) Feb 17, 2011 at 9:12
• Can't you remove the many if statements with an associative array? And maybe the chained replace statements can be shortened with an array.
– Nabb
Feb 17, 2011 at 11:55
• ('acEei',r'_/\\ ') => ('aecEi','_\/\ ') saves 1 more. You may also want to check out the unicode.translate(). Feb 17, 2011 at 20:12
• This also prints about 18 newlines before the snowflake, but I suppose the OP didn't specify whether anything other than the snowflake may be printed. Mar 21, 2011 at 10:41

## MS-DOS 16 bit machine code: 199 bytes

Decode using this site, save as 'koch.com' file and execute from WinXP command prompt.

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


Update

  ; 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
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
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:
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:

TurnLeft:

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

• Abolute magic :) , please help me understand this (atleast provide a link on what you did) Feb 17, 2011 at 16:09
• @Aman: It uses an L-system description of the Koch curve to draw the output. The level of detail is set in the SI register although the size is limited to 252 characters per line. You'll need to modify the printing code to get lines longer than 79 characters (i.e. change where it writes the '\n$' characters). Feb 17, 2011 at 16:24 • can also use "scAA...w==".decode("base64") to decode in Python2 (doesn't work for Python3) Feb 17, 2011 at 20:04 • +1 now that I have a windows machine to run it on. Any chance you can include asm version? Feb 18, 2011 at 1:06 • @mellamokb: err, because all the source code is available perhaps? Mar 21, 2011 at 14:20 # Perl, 176 175 bytes Posting this as a separate answer because it uses a binary source file, which is perhaps a bit cheaty. But considering that it’s still Perl source code, I think it’s remarkable that it beats the MS-DOS machine code solution! ### Source as base64-encoded JF89IsLApwag0dhnMmAmMEcGIAcGQNHYwsDRFLsQ0djCwKcGoNHYwsDRFDdbECYwcRUxe1DCwNEUuxDR2 CI7c14uXiR4PW9yZCQmOyQieCgkeD4+MykucXcoXCAvXyBfXy8gXC8gX18gX1wgLyBfXy9cX18pWyR4Jj ddXmVnO3NeLnsyN31eJF89cmV2ZXJzZSQmO3l+L1xcflxcL347cHJpbnQkJi4kXy4kL15lZw==  ### Somewhat more readable Replace all instances of /<[0-9a-f]+>/ with the relevant binary data: # 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


In this version, the snowflake is encoded in the following way:

• The 8 bits in each byte are divided like this:

+---+---+---+---+---+---+---+---+
|      5 bits       |   3 bits  |
+---+---+---+---+---+---+---+---+
R               C

• R encodes a run of spaces. The longest run is 27 characters, so all runs fit into 5 bits.

• C encodes a sequence of characters which are simply looked up in the literal array. (I used to have slightly crazier encodings here where the array contained only / \ _, but the Perl code necessary to decode it was longer...)

• I am lucky that the binary data does not contain any "/' or \ that would need escaping. I didn’t plan for this. But even if it did, I probably could have just changed the order of the items in the array to fix that.

• It is amazing how simple this solution is compared to the tens of other solutions I went through before I came up with this. I experimented with many different bitwise encodings more complex than this one, and it never occurred to me that a simpler one might be worth it simply because the Perl code to decode it would be shorter. I also tried to compress repetitions in the data using variable interpolation (see the other answer), but with the newest version that doesn’t gain any characters anymore.

## 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('/')])


With a bit more whitespace:

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('/')])


The left side is compressed; the right side is reproduced from the left side.

# Perl, 224 223 characters

use MIME::Base64;$_=decode_base64 wsCnBqDR2GcyYCYwRwYgBwZA0djCwNEUuxDR2MLApwag0djCwNEUN1sQJjBxFTF7UMLA0RS7ENHY;s^.^$x=ord$&;$"x($x>>3).qw(\ /_ __/ \/ __ _\ / __/\__)[$x&7]^eg;s^.{27}^$_=reverse$&;y~/\\~\\/~;print$&.$_.$/^eg  ### Somewhat more readable 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


### How it works

For an explanation of how it works, see the other answer in which I post the same in binary. I am really sorry that I am not actually generating the Koch snowflake, just compressing it...

### Previous versions

• (359) Encoded the entire snowflake instead of just the left half. Spaces were included in the bit encoding; no run-length yet. Used several interpolated variables plus a @_ array which was accessed using s/\d/$_[$&]/eg. Newlines were encoded as !.

• (289) First version that encoded only the left half of the snowflake.

• (267) First version that used run-length encoding for the spaces.

• (266) Change ' ' to \$".

• (224) Radically different compression, encoded as base-64. (Now equivalent to the binary version.)

• (223) Realised that I can put the print inside the last subst and thus save a semicolon.

## Python, 338 bytes

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


Just another unicode exploit

run at ideone

• Fair enough, but surely that would make the source file more than 300 bytes long. Mar 22, 2011 at 14:36
• the link is broken Jan 1, 2019 at 19:29