StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>Overview</strong></p> <p>This question is appropriate for Adobe because it's essentially a rendering algorithm: given a pixel and a set of rules, calculate the appearance of that pixel. </p> <p>The most efficient way to do this is to come up with a test that answers "given the position (x,y) in a square of size n, should it be marked with <code>*</code>?", and then answer that question for each position.</p> <p>We can answer this question by first making a couple of observations.</p> <ul> <li>Note the symmetry of the output of this algorithm. If we cut the square along its diagnols, we are left with four triangular quadrants. Within each quadrant, notice that the triangle is simply striped.</li> <li>Vertical or horizontal stripes are simple to draw; just check if the row/column is an even distance from the nearest edge and shade it if so.</li> </ul> <p>So we'll do two computations per position: (1) which quandrant is this position in and (2) given this quadrant, should this position's row/column be shaded?</p> <p><strong>Example implementation (python)</strong></p> <pre><code>def getQuadrant(i,j,n): # 1 means top quadrant; 2 right; 3 bottom; 4 left half_n = float(n-1)/2 x = float(i) - half_n y = float(j) - half_n if x > 0: if y > 0: if x > y: return 3 else: return 2 else: if x > -1*y: return 3 else: return 4 else: if y > 0: if -1*x > y: return 1 else: return 2 else: if x < y: return 1 else: return 4 def isPixelShaded(x,y,n): q = getQuadrant(x,y,n) if q == 1: return (x % 2) == 0 elif q == 2: return ((n-y-1) % 2) == 0 elif q == 3: return ((n-x-1) % 2) == 0 else: return (y % 2) == 0 def getPixelShade(x,y,n): if isPixelShaded(x,y,n): return ' * ' else: return ' ' def printSquare(n): for i in range(n): print ''.join(map(lambda x: str(getPixelShade(i,x,n)),range(n))) printSquare(3) printSquare(6) printSquare(9) </code></pre> <p><strong>Output</strong></p> <pre><code> * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * </code></pre> <p><strong>Other thoughts</strong></p> <p>Instead of a the rendering approach taken here, we could also take an iterative approach by "walking out squares" a in pre-allocated matrix. That approach is simpler to think about but it requires more memory. Additionally, the approach described in this answer has the benefit that to determine wither a given position is shaded, we don't need to know about its neighboring positions (which an iterative approach does). This means we could render small swatches of the final rendering at once. In other words, this approach supports parallelism, which is always a nice bonus.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload