21
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ Koch-snowflake ..a tag .. thats interesting..!!.. seems you will be firing more questions on this tag :) \$\endgroup\$ – Aman ZeeK Verma Feb 17 '11 at 19:22
  • 5
    \$\begingroup\$ Too short for an answer: wolframalpha.com/input/?i=koch+snowflake+4 :D \$\endgroup\$ – Dr. belisarius Feb 18 '11 at 21:05
  • 1
    \$\begingroup\$ Should the accepted answer be changed? There are shorter solutions now. \$\endgroup\$ – Timwi Apr 2 '11 at 11:36
2
\$\begingroup\$

Python, 338 bytes

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

Just another unicode exploit

run at ideone

\$\endgroup\$
  • 5
    \$\begingroup\$ Fair enough, but surely that would make the source file more than 300 bytes long. \$\endgroup\$ – Timwi Mar 22 '11 at 14:36
  • \$\begingroup\$ the link is broken \$\endgroup\$ – Chiel ten Brinke Jan 1 at 19:29
10
\$\begingroup\$

Python, 650 612 594 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.

\$\endgroup\$
  • \$\begingroup\$ +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 :) \$\endgroup\$ – gnibbler Feb 17 '11 at 9:12
  • \$\begingroup\$ Can't you remove the many if statements with an associative array? And maybe the chained replace statements can be shortened with an array. \$\endgroup\$ – Nabb Feb 17 '11 at 11:55
  • \$\begingroup\$ ('acEei',r'_/\\ ') => ('aecEi','_\/\ ') saves 1 more. You may also want to check out the unicode.translate(). \$\endgroup\$ – gnibbler Feb 17 '11 at 20:12
  • \$\begingroup\$ 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. \$\endgroup\$ – RomanSt Mar 21 '11 at 10:41
6
\$\begingroup\$

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

Here's an easy-to-read assembler version:

  ; 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
\$\endgroup\$
  • \$\begingroup\$ Abolute magic :) , please help me understand this (atleast provide a link on what you did) \$\endgroup\$ – Aman ZeeK Verma Feb 17 '11 at 16:09
  • \$\begingroup\$ @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). \$\endgroup\$ – Skizz Feb 17 '11 at 16:24
  • \$\begingroup\$ can also use "scAA...w==".decode("base64") to decode in Python2 (doesn't work for Python3) \$\endgroup\$ – gnibbler Feb 17 '11 at 20:04
  • \$\begingroup\$ +1 now that I have a windows machine to run it on. Any chance you can include asm version? \$\endgroup\$ – gnibbler Feb 18 '11 at 1:06
  • 2
    \$\begingroup\$ @mellamokb: err, because all the source code is available perhaps? \$\endgroup\$ – Skizz Mar 21 '11 at 14:20
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.