This page is still under construction.

Parts of this page are still being built. What you see may change.

The Sierpinski Fractal

Interview

Time limit1sMemory limit128 MB

Summary
Draw the outline of a depth-n Sierpinski triangle in ASCII, 2^n rows tall, with no trailing spaces and blank lines between the test cases.
Level

Medium5 of 10

Topics
Divide and conquer, Recursion, Implementation, String
Solved
No attempts yet

Problem

Consider a solid equilateral-triangular region. Divide it into four congruent triangles of half the height and remove the middle one. Apply the same operation recursively to each of the three remaining triangles. Repeating this procedure infinitely many times yields a shape whose area is zero. The fractal produced this way is called the Sierpinski Triangle. Although its topological dimension is 22, its Hausdorff–Besicovitch dimension is log⁡(3)/log⁡(2)≈1.58\log(3)/\log(2)\approx 1.58, a non-integer value (which is why it is called a fractal). For comparison, the Hausdorff–Besicovitch dimension of the Norwegian coastline is about 1.521.52, while its topological dimension is 11.

In this problem you must draw the outline of the Sierpinski Triangle up to a given recursion depth, using only ASCII characters. Because the drawing resolution is fixed, the picture must grow with the recursion depth. Draw the smallest triangle (the one that is not subdivided any further) with two slashes (/), two backslashes (\), and two underscores (_) like this:

 /\
/__\

To see how larger triangles are drawn, look at the example outputs below. A picture of depth nn consists of exactly 2n2^n rows: a triangle of depth nn is formed from three triangles of depth n−1n-1 — one placed at the bottom left, one at the bottom right, and one centered above the other two.

Input

The input contains several test cases. Each test case is a single integer nn. The input is terminated by n=0n=0. Otherwise 1≤n≤101 \le n \le 10, where nn is the recursion depth.

Output

For each test case, draw the outline of the Sierpinski Triangle; the picture has 2n2^n rows. Align the output to the left, that is, print the bottom-left slash in the first column. No line may contain trailing blanks. Print a single empty line between consecutive test cases, and do not print an extra empty line after the last test case.

Examples3

  1. Example 1

    Input
    3
    2
    1
    0
    
    Expected output
           /\
          /__\
         /\  /\
        /__\/__\
       /\      /\
      /__\    /__\
     /\  /\  /\  /\
    /__\/__\/__\/__\
    
       /\
      /__\
     /\  /\
    /__\/__\
    
     /\
    /__\
    
  2. Example 2

    Input
    1
    0
    
    Expected output
     /\
    /__\
    
  3. Example 3

    Input
    2
    0
    
    Expected output
       /\
      /__\
     /\  /\
    /__\/__\