18
\$\begingroup\$

Your task: generate a Koch snowflake to the nth depth. You do not need to make a complete Koch snowflake, just one side of the starting triangle. Wikipedia on Koch flakes: https://en.wikipedia.org/wiki/Koch_snowflake.

Rules:

  • The program must generate one side of the Koch snowflake to the nth depth.
  • Output must be ASCII.
  • You may generate the whole snowflake; this is not required.
  • Standard rules for input/output and loopholes and stuff apply.
  • Whitespace does not matter, as long as it all characters are in the right place relative to each other.
  • Shortest code wins!

Test cases:

n=0:

__

n=1:

__/\__

n=2:

      __/\__
      \    /
__/\__/    \__/\__

n=3:

                        __/\__
                        \    /
                  __/\__/    \__/\__
                  \                /
                  /_              _\
                    \            /
      __/\__      __/            \__      __/\__
      \    /      \                /      \    /
__/\__/    \__/\__/                \__/\__/    \__/\__

I hope this makes sense. Notice that in each test case, the fractal can be divided into three parts equal in length. Also notice that the width of each snowflake is three times the width of the previous generation of the snowflake.

\$\endgroup\$
  • \$\begingroup\$ FYI, it was agreed that this is not a dupe of this. \$\endgroup\$ – Comrade SparklePony Mar 29 '17 at 22:19
  • \$\begingroup\$ I don't think you have appropriately defined what the proper ASCII representation of the nth Koch curve is. \$\endgroup\$ – orlp Mar 30 '17 at 1:16
  • \$\begingroup\$ I'm not sure the proportions make sense. The non-dupe used __/\__ with two underlines, which made each iteration consistently 3 times as large as the previous one. Using only one underline seems to give contradictions that start getting really awkward in n=3. E.g. the outer parts have width 12 while the middle part has only width 10, as a consequence of the /_ and _\ that are too cramped. And even before that you have _ expanding to twice the width of / and \ . \$\endgroup\$ – Ørjan Johansen Mar 30 '17 at 1:20
  • \$\begingroup\$ I think the /_ and _\ are the only really fatal part - the underscores need to go, because they need to be in the same position as the / and \ . Once that's done, things can expand by 3 times from n=1 onwards (but n=0 doesn't fit.) \$\endgroup\$ – Ørjan Johansen Mar 30 '17 at 2:02
  • \$\begingroup\$ Alas, no, the middle part still has width not matching the outer parts, as evidenced by n=3 having width 52 rather than 54 = 2*3^3. Try one of these. I included upside down versions with parts only showing up from n=4 or n=5 - they differ from the upwards ones in where the underscores are dropped. \$\endgroup\$ – Ørjan Johansen Mar 30 '17 at 15:35
10
\$\begingroup\$

Haskell, 308 300 299 bytes

Edits:

  • -4 bytes: Changing zipWith(+) to zipWith(-) and adjusting encodings and offsets got rid of every negation sign.
  • -1 byte: Further tweaking the encoding allowed several variable names in # to be dropped by using r=reverse instead of direct pattern matching.
  • -2 bytes: Using an operator instead of alphanum for zipWith(-).
  • -1 byte: Defining o=[0,0] to shorten list constants.
  • -1 byte: Merging two branches of ?.
import Data.List
k n=0?sort(o#(f=<<scanl1(+)(iterate(>>=(:[1,4,1]))[6]!!n)))
x?l@(([_,w],c):r)|x>w='\n':0?l|0<1=([2..w-x]>>" ")++[c|w>x]++w?r
_?_=""
w#((c,l):m)=(l&w,c):r l&(l&w)#m
_#_=[]
f x=zip"_/\\_/\\"([id,r]<*>[0:1:o,[0,1,0,1],o++[1,1]])!!mod x 6<$[1,3..gcd 3x]
(&)=zipWith(-)
r=reverse
o=[0,0]

Try it online! (Sadly, anything bigger than n=3 gets horribly wrapped and unreadable, but you can copy it to another program to see it.)

Variations

  • If you change [6] into [6,4,4], you get a whole snowflake. Try it online!
  • If you remove ,3..gcd 3x, you get a curve in the style that this question was originally given with. Try it online!
  • Or both at once: Try it online!

How it works

  • k is the main function, it takes an Int n and returns a String.
  • iterate(>>=(:[1,4,1]))[6] generates an infinite list containing, for each n, the turns between consecutive lines in that curve iteration, turtle graphics style, as numbers nominally between 0 and 5. Each iteration is just the previous one with the turns 1,4,1 interleaved. The only reason the sublists start out with 6 instead of 0 is to make the gcd trick in f work by avoiding f 0.
  • scanl1(+) converts the turns into "absolute" directions, up to modulo 6. A 0 means rightwards, then each higher number is 60 degrees counterclockwise from the previous. (Well, it would be 60 degrees if this was a proper drawing rather than ASCII.)
  • f converts an absolute direction into a list of (character, offset encoding) pairs that encodes which characters to add to the curve (for horizontal directions it generates two pairs, otherwise one), and how the relative position changes.
  • The # operator iterates through the previous list of (character, offset encoding) pairs, generating actual (coordinate,character) pairs.
  • Encoding principles:
    • A character from _/\ nominally represents a line drawn from a starting corner through a rectangular cell to a different ending corner.
    • Cell coordinates are of the form [y,x], top to bottom, left to right, so that they sort in the order we want to print them. Columns are 1-based. Lists are used instead of tuples for shorter vector arithmetic with (&)=zipWith(-).
    • A corner is denoted with the same coordinates [y,x] as the cell to its upper left. This ensures that all offsets from a corner to its neighboring cells are nonnegative, avoiding negative constants.
    • However, corner coordinates are passed around negated to allow all vector operations to be subtractions instead of additions, which avoids all other explicit signs.
    • An offset encoding list is [y1,x1,x2,y2] where [y1,x1] is the coordinate offset from the starting corner to the character cell and [y2,x2] is the offset from the end corner to the character cell. This means:
      • The encoding lists for the directions 3..5 are just the reverse of the lists for 0..2, allowing them to be generated with [id,r]<*>.
      • All necessary vector arithmetic can be done by using (&)=zipWith(-) with either an encoding list or its reverse.
  • After sorting the list of (coordinate, character) pairs, they are passed to ?, which generates the final String from them.
    • In x?l@(([_,w],c):r) x is the x-coordinate of the previous character shown on this line, or 0 if at the start of a line; l is the whole current list, w is the x-coordinate of the next character to be added, c is the character, and r is the remaining list.
    • At this stage the y-coordinates are no longer needed. Because every line contains characters, and every line's first character is well to the left of the end of the previous one, the start of new lines is detected by checking if the x-coordinate has decreased.
    • Underscore has a larger ASCII value than \ and /, so it gets sorted last if it overlaps with another character in the same position. Thus a redundant underscore is detected by checking that an x-coordinate has been repeated.
\$\endgroup\$
  • \$\begingroup\$ Nice! I'll accept this if there is no more activity on this question today. \$\endgroup\$ – Comrade SparklePony Mar 31 '17 at 16:16

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.