13
\$\begingroup\$

Generate a Koch Snowflake

A Koch snowflake is a triangle that for each n, another equilateral point is added in the middle of each side: http://en.wikipedia.org/wiki/Koch_snowflake#Properties

We already had a Koch Snowflake challenge for n=4. The new challenge is to draw a Koch snowflake with any n between 1 and 10.

Rules

The snowflakes may not be hardcoded in the program or in files - they must be generated by your program.

Your program must support all sized n between 1 and 10.

The number of sides must be input by the user through std-in.

You must print a graphical representation of the snowflake to the screen.

Sample Koch Snowflakes with n equaling 1, 2, 3, and 4 (green lines for clarity only, do not reproduce them):

Koch Snowflakes

In the event of a tie-breaker, the program with the highest number of upvotes wins (pop-contest).

\$\endgroup\$
  • \$\begingroup\$ I'm not making sense of this: "You must use a function to calculate where to place the pixel. If your program does not have a built-in function for this purpose, you may deduct the cost of implementing one from your score." What pixel? \$\endgroup\$ – xnor Nov 5 '14 at 5:16
  • \$\begingroup\$ @xnor It was originally meant to calculate how to draw the snowflake on a per-pixel/character basis (the challenge was originally an ASCII-art challenge too). Most people will probably just use lines, so I will remove that. \$\endgroup\$ – Hosch250 Nov 5 '14 at 5:17
  • \$\begingroup\$ Can one draw the whole snowflake filled in? \$\endgroup\$ – xnor Nov 5 '14 at 5:18
  • \$\begingroup\$ Of course. This comment needs to be longer. \$\endgroup\$ – Hosch250 Nov 5 '14 at 5:19
  • \$\begingroup\$ Beyond n=7, you can't see the newly added triangles in the snowflake on a computer screen. Is any "best effort" here OK? Is there a minimum resolution for pixel-based solutions? \$\endgroup\$ – xnor Nov 5 '14 at 5:23

11 Answers 11

7
\$\begingroup\$

Mathematica 72

Region@Line@AnglePath[Nest[Join@@({#,1,4,1}&/@#)&,{4,4,4},Input[]-1]π/3]

n=3

enter image description here

Thanks for alephalpha.

\$\endgroup\$
  • \$\begingroup\$ Nice job. Golf it by two characters, and you get the win! \$\endgroup\$ – Hosch250 Nov 25 '14 at 16:24
  • \$\begingroup\$ @Hosch250 Updated, Thank you. \$\endgroup\$ – chyanog Apr 22 '15 at 3:45
  • \$\begingroup\$ You can use AnglePath in Mathematica 10.1. \$\endgroup\$ – alephalpha Apr 22 '15 at 3:45
  • \$\begingroup\$ @chyaong Graphics@Line@AnglePath[Nest[Join@@({-1,2,-1,#}&/@#)&,{2,2,2},Input[]-1]Pi/3] \$\endgroup\$ – alephalpha Apr 22 '15 at 6:08
  • 1
    \$\begingroup\$ @alephalpha 73 chars: ListLinePlot@AnglePath[Nest[Join@@({#,1,4,1}&/@#)&,{4,4,4},Input[]-1]π/3] \$\endgroup\$ – chyanog Apr 28 '15 at 7:32
15
\$\begingroup\$

MATLAB, 119 115

In an unusual turn of events, I found that this program actually worked better as I golfed it. First, it became much faster due to vectorization. Now, it displays a helpful prompt ~n:~ reminding the user of which quantity to enter!

Newlines are not part of the program.

x=exp(i*pi/3);
o='~n:~';
P=x.^o;
for l=2:input(o);
P=[kron(P(1:end-1),~~o)+kron(diff(P)/3,[0 1 1+1/x 2]) 1];
end;
plot(P)

n = 9: n=9

o is an arbitrary string which is equal to [0 2 4 0] modulo 6. eiπ/3 raised to these powers gives the vertices of an equilateral triangle in the complex plane. The first kron is used to make a copy of the list of points with each one duplicated 4 times. ~~o is the convenient way to get a vector of 4 ones. Secondly diff(P) finds the vector between each pair of consecutive points. Multiples of this vector (0, 1/3, (1 + e-iπ/3)/3, and 2/3) are added to each of the old points.

\$\endgroup\$
  • \$\begingroup\$ Uhm, could you explain somewhat more how this code works? I thought I knew some Matlab but this is ... insanity?? =) \$\endgroup\$ – flawr Apr 24 '15 at 20:30
  • \$\begingroup\$ @flawr I added a few notes, does that help any? \$\endgroup\$ – feersum Apr 24 '15 at 22:09
  • \$\begingroup\$ Thank you very much! I'm gonna keep that string-abuse trick in mind=) \$\endgroup\$ – flawr Apr 25 '15 at 11:52
10
\$\begingroup\$

LOGO: 95

to w:c ifelse:c=1[fd 2 lt 60][w:c-1 w:c-1 lt 180 w:c-1 w:c-1]end
to k:c repeat 3[w:c rt 180]end

Defines function k with a single level parameter.

Edit

In the this online editor http://www.calormen.com/jslogo/ you can add k readword to use prompt for input, but for some reason this command does not support the standard abbreviation rw.

The 102 characters solution below works in USBLogo with standard input as specified in the question. However the code needed slight changes as UCBLogo has some weird parser. It requires to and end to be in separate lines and space before : is required but on the other hand : are optional.

to w c
ifelse c=1[fd 2 lt 60][w c-1 w c-1 lt 180 w c-1 w c-1]
end
to k c
repeat 3[w c rt 180]
end
k rw
\$\endgroup\$
9
\$\begingroup\$

T-SQL: 686 (excluding formatting)

For SQL Server 2012+.

Even though this will never be a contender, I had to see if I could get it done in T-SQL. Gone for the approach of starting with the three initial edges, then recursing through each edge and replacing them with 4 edges for each level. Finally unioning it all up into a single geometry for the level specified for @i

DECLARE @i INT=8,@ FLOAT=0,@l FLOAT=9;
WITH R AS(
    SELECT sX,sY,eX,eY,@l l,B,1i
    FROM(VALUES(@,@,@l,@,0),(@l,@,@l/2,SQRT(@l*@l-(@l/2)*(@l/2)),-120),(@l/2,SQRT(@l*@l-(@l/2)*(@l/2)),@,@,-240))a(sX,sY,eX,eY,B)
    UNION ALL
    SELECT a.sX,a.sY,a.eX,a.eY,l/3,a.B,i+1
    FROM R 
        CROSS APPLY(VALUES(sX,sY,sX+(eX-sX)/3,sY+(eY-sY)/3,sX+((eX-sX)/3)*2,sY+((eY-sY)/3)*2))x(x1,y1,x2,y2,x3,y3)
        CROSS APPLY(VALUES(x2+((l/3)*SIN(RADIANS(B-210.))),y2+((l/3)*COS(RADIANS(B-210.)))))n(x4,y4)
        CROSS APPLY(VALUES(x1,y1,x2,y2,B),
            (x3,y3,eX,eY,B),
            (x2,y2,x4,y4,B+60),
            (x4,y4,x3,y3,B-60)
        )a(sX,sY,eX,eY,B)
WHERE @i>i)
SELECT Geometry::UnionAggregate(Geometry::Parse(CONCAT('LINESTRING(',sX,' ',sY,',',eX,' ',eY,')')))
FROM R 
WHERE i=@i

enter image description here enter image description here

\$\endgroup\$
  • \$\begingroup\$ I had no idea such wizardry could be achieved with T-SQL! \$\endgroup\$ – Harry Mustoe-Playfair May 11 '15 at 20:56
8
\$\begingroup\$

BBC BASIC, 179

REV 1

INPUTn
z=FNt(500,470,0,0,3^n/9)END
DEFFNt(x,y,i,j,a)
LINEx-36*a,y-21*a,x+36*a,y-a*21PLOT85,x,y+a*42IFa FORj=-1TO1FORi=-1TO1z=FNt(x+24*a*i,y+j*14*a*(i*i*3-2),i,j,-j*a/3)NEXTNEXT
=0

As before, but in black and white, in ungolfed (but streamlined) and golfed versions. Not a winner, despite the fact that doing it ths way avoids the need for a special treament for n=1.

  INPUTn
        REM call function and throw return value away to z
  z=FNt(500,470,0,0,3^n/9)
  END

        REM x,y=centre of triangle. a=scale.
        REM loop variables i,j are only passed in order to make them local, not global.
  DEFFNt(x,y,i,j,a)

        REM first draw a line at the bottom of the triangle. PLOT85 then draws a filled triangle,
        REM using the specified point (top of the triangle) and the last two points visited (those used to draw the line.)
  LINEx-36*a,y-21*a,x+36*a,y-21*a
  PLOT85,x,y+42*a

        REM if the absolute magnitude of a is sufficient to be truthy, recurse to the next level.
        REM j determines if the triangle will be upright, inverted or (if j=0) infinitely small.
        REM i loops through the three triangles of each orientation, from left to right.
  IFa FORj=-1TO1 FORi=-1TO1:z=FNt(x+24*a*i,y+j*14*a*(i*i*3-2),i,j,-j*a/3):NEXT:NEXT

        REM return 0
  =0

enter image description here

REV 0

According to the OP's answer to @xnor, filled in snowflakes are OK. This answer was inspired by xnor's comment. The colours are just for fun and to show the way it is constructed. Take a triangle (magenta in this case) and overplot with 6 triangles 1/3 of the base.

  INPUTn
  z=FNt(500,470,n,1,0,0)
  END

  DEFFNt(x,y,n,o,i,a)
  a=3^n/22
  GCOLn
  MOVEx-36*a,y-o*21*a
  MOVEx+36*a,y-o*21*a
  PLOT85,x,y+o*42*a
  IFn>1FORi=-1TO1:z=FNt(x+24*a*i,y+14*a*(i*i*3-2),n-1,-1,i,a):z=FNt(x+24*a*i,y-14*a*(i*i*3-2),n-1,1,i,a)NEXT
  =0

enter image description here

\$\endgroup\$
  • 1
    \$\begingroup\$ I like how it looks like 7 of them merged together. \$\endgroup\$ – Hosch250 Nov 6 '14 at 0:34
  • \$\begingroup\$ @hosch250 Indeed, I seem to have "invented" a new fractal whose silhouette happens to be a Koch snowflake, and if you delete the magenta part you are left with 6 smaller Koch snowflakes. The golfed version will be just a plain black silhouette, but I will leave this image up, too. \$\endgroup\$ – Level River St Nov 6 '14 at 0:40
  • \$\begingroup\$ Do you write it BBC Basic or BBC BASIC? I go for the latter but I don't know if it's correct... \$\endgroup\$ – Beta Decay Nov 7 '14 at 20:45
  • 2
    \$\begingroup\$ @BetaDecay BASIC is a backronym for Beginners' All-purpose Standard/Symbolic Instruction Code. The "Standard" bit is debatable as there are so many variants. en.wikipedia.org/wiki/BASIC. Most variants of BASIC prefer the capitalised version, but according to the Wikipedia page, Visual Basic prefers lowercase. I think BBC BASIC as shipped was uppercase. I'm using the version at bbcbasic.co.uk/bbcwin/bbcwin.html. It's uppercase in the website and IDE, So I'd say the uppercase version is more correct. But I don't think it matters much. \$\endgroup\$ – Level River St Nov 7 '14 at 21:19
  • \$\begingroup\$ Ahh okay, I'll carry on with the uppercase version \$\endgroup\$ – Beta Decay Nov 7 '14 at 21:21
8
\$\begingroup\$

Mathematica - 177

r[x_, y_] := Sequence[x, RotationTransform[π/3, x]@y, y]
Graphics@Polygon@Nest[
 ReplaceList[#, {___, x_, y_, ___}  Sequence[x,r[2 x/3 + y/3, 2 y/3 + x/3], y]
  ] &, {{0, 0}, {.5, √3/2}, {1, 0}, {0, 0}}, Input[]]

enter image description here

Bonus clip of varying the angle of middle piece

enter image description here

\$\endgroup\$
6
\$\begingroup\$

Python 3 - 139

Uses the turtle graphics library.

from turtle import*
b=int(input())
a=eval(("FR"*3)+".replace('F','FLFRFLF')"*~-b)
for j in a:fd(9/b*("G">j));rt(60*(2-3*("Q">j))*("K"<j))])
\$\endgroup\$
  • \$\begingroup\$ Cool. I like your string-based approach of finding the shape with no more than two lines of code! But can't you check for "G">j, "Q"<j and use fd(9/b) to save 3 bytes? Furthermore you can avoid the if statements multiplying, e.g., ("G">j) with the argument 9/b and put them all in one line behind for. Oh! Then you can even combine rt and lt using 120*(...)-60*(...) \$\endgroup\$ – Falko Nov 6 '14 at 5:19
  • \$\begingroup\$ This appears to render the Koch snowflake input+1. An input of 1 should just be a triangle like the picture above shows. \$\endgroup\$ – Hosch250 Nov 6 '14 at 5:33
  • \$\begingroup\$ @Falko Thanks for all that help! \$\endgroup\$ – Beta Decay Nov 6 '14 at 7:06
  • \$\begingroup\$ @hosch250 Edited \$\endgroup\$ – Beta Decay Nov 6 '14 at 7:07
  • \$\begingroup\$ Now it doesn't draw anything, and an input of 1 creates a division by 0 error. \$\endgroup\$ – Hosch250 Nov 6 '14 at 17:05
4
\$\begingroup\$

Python 3, 117 bytes

from turtle import*
ht();n=int(input())-1
for c in eval("'101'.join("*n+"'0'*4"+")"*n):rt(60+180*(c<'1'));fd(99/3**n)

Method:

  • The solution uses Python's turtle graphics.
  • n is input - 1
  • Starting from the string 0000 we join its every character with 101 n times iteratively with the eval trick (thanks to @xnor for that).
  • For every character in the final string we turn 60 degrees right or 120 degrees left based on the character value (1 or 0) and then move forward a length (99/3^n) which guarantees a similar size for all n's.
  • The last 0 in the string will be useless but it just redraws the same line the first 0 draws.

Example output for input = 3:

koch

\$\endgroup\$
2
\$\begingroup\$

R: 240 175

Because I trying to get my head around R, here's another version. There's likely to be lot better ways to do this and I'm happy to receive pointers. What I've done seems very convoluted.

n=readline();d=c(0,-120,-240);c=1;while(c<n){c=c+1;e=c();for(i in 1:length(d)){e=c(e,d[i],d[i]+60,d[i]-60,d[i])};d=e};f=pi/180;plot(cumsum(sin(d*f)),cumsum(cos(d*f)),type="l")

enter image description here

\$\endgroup\$
2
\$\begingroup\$

Wise fwom youw gwave...

I knew I'd want to try implementing this in Befunge-98 using TURT, but I couldn't figure out how to go about it and I sat on it for several months. Now, only recently, I figured out a way to do it without using self-modification! And so...

Befunge-98 with the TURT fingerprint, 103

;v;"TRUT"4(02-&:0\:0\1P>:3+:4`!*;
>j$;space makes me cry;^
^>1-:01-\:0\:01-\:0
0>I@
^>6a*L
^>ca*R
^>fF

Let's get some implementation details out of the way first:

  • I tested this using CCBI 2.1, whose implementation of TURT (the turtle graphics fingerprint) makes I "print" the image to a SVG file. If you run this in CCBI without the command-argument --turt-line=PATH, it will come out as a file named CCBI_TURT.svg by default. This is the closest I could come to "print a graphical representation of the snowflake to the screen" with available Funge interpreters I could find. Maybe someday there will be a better interpreter out there that has a graphical display for the turtle, but for now...
  • There has to be a newline at the end for CCBI to run it without hanging (this is included with the character count). I know, right?

Basically, this works by using the stack as a sort of makeshift L-system and expanding it on the fly. On each pass, if the top number on the stack is:

  • -2, then it prints and stops;
  • -1, the turtle turns counterclockwise 60 degrees;
  • 0, it turns clockwise 120 degrees;
  • 1, it moves forward (by 15 pixels here, but you can change it by modifying the f on the last line);
  • some number n that's 2 or greater, then it is expanded on the stack to n-1, -1, n-1, 0, n-1, -1, n-1.

For n = 10, this process takes a very long time (a couple of minutes on my system), and the resulting SVG is ~10MB in size and invisible when viewed in the browser because you can't adjust the size of the brush using TURT. IrfanView seems to work decently if you have the right plugins. I'm not super familiar with SVG, so I don't know what the preferred method is for viewing those files (especially when they're really big).

Hey, at least it works - which, considering it's Befunge, is something to be thankful for on its own.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 127 bytes

from turtle import *
def L(l,d=input()-1):
 for x in[1,-2,1,0]:[L(l,d-1),rt(60*x)] if d>0 else fd(l)
for i in'lol':lt(120);L(9)
\$\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.