10 October 2006

Sierpinski — in ASCII, in Python

I wrote this in the fall of 2004 (I was taking a class with one of the best teachers I've ever had and she gave this as a bonus on an exam — this fractal was on her t-shirt and she asked its name). (this works under python 2.4)
>>> print_triangle(get_sierpinski(5))

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


# under mit license
#! /usr/bin/env python
#
# N = 4:
#                /\
#               /__\
#              /\  /\
#             /__\/__\
#            /\      /\
#           /__\    /  \
#          /\  /\  /\  /\
#         /__\/__\/__\/__\
#        /\              /\
#       /__\            /__\
#      /\  /\          /\  /\
#     /__\/__\        /__\/__\
#    /\      /\      /\      /\
#   /__\    /  \    /__\    /__\
#  /\  /\  /\  /\  /\  /\  /\  /\
# /__\/__\/__\/__\/__\/__\/__\/__\
#
# N = 3:
#        /\
#       /__\
#      /\  /\
#     /__\/__\
#    /\      /\
#   /__\    /__\
#  /\  /\  /\  /\
# /__\/__\/__\/__\
#
# N = 2:
#    /\
#   /__\
#  /\  /\
# /__\/__\
#
# N = 1:
#  /\
# /__\
#
# N = 0: (trivial case)
#
import sys

# returns a list of lines where
# each line contains a 2-element list:
# a character and a position
def get_sierpinski(n):
    assert n >= 0

    if n == 0:
        return []

    if n == 1:
        return [[['/', 1], ['\\', 2]],                       #  /\
                [['/', 0], ['_', 1], ['_', 2], ['\\', 3]]]   # /__\

    # ok, a bit more complicated:
    # let's assemble top part and the bottom parts seperately
    # check out the N=4 example above
    # there are 3 big triangles: the top one sits on the "spikes"
    # of the bottom two.
    # but those 3 triangles are made of 3 smaller triangles,
    # where the top of the small triangle sits on the bottom
    # 2, and so on...
    top, bottom = [], []
    for line in get_sierpinski(n-1):
        t, bl, br = [], [], []
        for (character, start) in line:
            t.append([character, start+2**(n-1)])
            bl.append([character, start])       # left triangle
            br.append([character, start+2**n])  # right triangle
        top.append(t)
        bottom.append(bl + br)
    return top + bottom

def print_triangle(triangle):
    for line in triangle:
        current_column = 0
        for (character, start) in line:
            while current_column != start:
                sys.stdout.write(" ")
                current_column += 1
            sys.stdout.write(character)
            current_column += 1
        sys.stdout.write("\n")


if __name__ == "__main__":
    size = 3
    if sys.argv[1:]:
        size = int(sys.argv[1])
    print_triangle(get_sierpinski(size))