Draw the Devil's Staircase
J (73 68 58 41 39 38 35 34 characters)
After thinking about the problem for some time, I found an entirely different way to generate the Devil's Staircase pattern. The old answer including its explanation has been removed, you can look into the revisions of this answer to figure out how it was.
This answer returns an array of blanks and sharps, representing the devil's staircase.
' #'{~1(]|.@=@#~[:,3^q:)2}.@i.@^>:
Here is the answer split into its two parts in explicit notation:
f =: 3 : '|. = (, 3 ^ 1 q: y) # y'
g =: 3 : '(f }. i. 2 ^ >: y) { '' #'''
Explanation
The approach is a bit different, so observe and be amazed.
>: 3– three incremented, that is,42 ^ >: 3– two to the power of three incremented, that is,16i. 2 ^ >: 3– the first2 ^ >: 3integers, that is,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15}. i. 2 ^ 4– the first2 ^ >: 3integers, beheaded, that is,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Let's call this sequence
s; we enterfnow.1 q: s– the exponents of 2 in the prime decomposition of each item ofs. In general,x q: yyields a table of the exponents for the firstxprimes in the prime decomposition ofy. This yields:0 1 0 2 0 1 0 3 0 1 0 2 0 1 03 ^ 1 q: s– three to the power of these exponents, that is,1 3 1 9 1 3 1 27 1 3 1 9 1 3 1, 3 ^ 1 q: s– the ravel (that is, the argument with it's structure collapsed into a vector) of the previous result. This is needed becauseq:introduces an unwanted trailing axis. This yields1 3 1 9 1 3 1 27 1 3 1 9 1 3 1(, 3 ^ 1 q: s) # s– each item ofsreplicated as often as the corresponding item in the previous result, that is,1 2 2 2 3 4 4 4 4 4 4 4 4 4 5 6 6 6 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 10 10 10 11 12 12 12 12 12 12 12 12 12 13 14 14 14 15= (, 3 ^ 1 q: s) # s– the self classification of the previous result, this is, a matrix where each row represents one of the unique items of the argument, each column represents the corresponding item of the argument and each cell represents whether the items of row and column are equal, that is,1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1|. = (, 3 ^ 1 q: s) # s– the previous result flipped along the vertical axis.(|. = (, 3 ^ 1 q: s) # s) { ' #'– the items of the previous result used as indices into the array' #', so0is replaced by1is replaced by#, that is,# ### # ######### # ### # ########################### # ### # ######### # ### #the result we want.
Hexagony, 217 bytes
This was immensely fun. Thank you for posting this challenge.
Full disclosure: The language (Hexagony) did not exist at the time this challenge was posted. However, I did not invent it, and the language was not designed for this challenge (or any other specific challenge).
){_2"_{\"{{""}"{'2//_.\><*\"\/_><[\]/3\'\_;|#__/(\2\'3_'}(#:|{$#{>_\//(#={/;01*&"\\_|[##={|}$_#></)]$_##|){*_.>.(/?#//~-="{}<_"=#/\}.>"%<.{#{x\"<#_/=&{./1#_#>__<_'\/"#|@_|/{=/'|\"".{/>}]#]>(_<\'{\&#|>=&{{(\=/\{*'"]<$_
Laid out hexagonally:
) { _ 2 " _ { \ "
{ { " " } " { ' 2 /
/ _ . \ > < * \ " \ /
_ > < [ \ ] / 3 \ ' \ _
; | # _ _ / ( \ 2 \ ' 3 _
' } ( # : | { $ # { > _ \ /
/ ( # = { / ; 0 1 * & " \ \ _
| [ # # = { | } $ _ # > < / ) ]
$ _ # # | ) { * _ . > . ( / ? # /
/ ~ - = " { } < _ " = # / \ } .
> " % < . { # { x \ " < # _ /
= & { . / 1 # _ # > _ _ < _
' \ / " # | @ _ | / { = /
' | \ " " . { / > } ] #
] > ( _ < \ ' { \ & #
| > = & { { ( \ = /
\ { * ' " ] < $ _
The program does not actually use the # instruction, so I used that character to show which cells are genuinely unused.
How does this program work? That depends. Do you want the short version, or the long?
Short explanation
To illustrate what I mean by “line” and “segment” in the following explanation, consider this dissection of the intended output:
segments →
│ │ │ │ │ │x lines
─┼───┼─┼─────────┼─┼───┼─ ↓
│ │ │ │ │xxx│
─┼───┼─┼─────────┼─┼───┘
│ │ │ │x│
─┼───┼─┼─────────┼─┘
│ │ │xxxxxxxxx│
─┼───┼─┼─────────┘
│ │x│
─┼───┼─┘
│xxx│
─┼───┘
x│
With that explained, the program corresponds to the following pseudocode:
n = get integer from stdin
# Calculate the number of lines we need to output.
line = pow(2, n+1)
while line > 0:
line = line - 1
# For all segments except the last, the character to use is spaces.
ch = ' ' (space, ASCII 32)
# The number of segments in each line is
# equal to the line number, counting down.
seg = line
while seg > 0:
seg = seg - 1
# For the last segment, use x’s.
if seg = 0:
ch = 'x' (ASCII 120)
# Calculate the actual segment number, where the leftmost is 1
n = line - seg
# Output the segment
i = pow(3, number of times n can be divided by 2)
i times: output ch
output '\n' (newline, ASCII 10)
end program
Long explanation
Please refer to this color-coded code path diagram.
Execution starts in the top left corner. The sequence of instructions ){2'"''3''"2}?) is executed (plus a few redundant cancelations, like "{ etc.) by pursuing a fairly convoluted path. We start with Instruction Pointer #0, highlighted in crimson. Halfway through, we switch to #1, starting in the top-right corner and painted in forest green. When IP #2 starts out in cornflower blue (middle right), the memory layout is this:
Throughout the entire program, the edges labeled 2a and 2b will always have the value 2 (we use them to calculate 2ⁿ⁺¹ and to divide by 2, respectively) and the edge labeled 3 will always be 3 (we use that to calculate 3ⁱ).
We get to business as we enter our first loop, highlighted in cornflower blue. This loop executes the instructions (}*{=&}{= to calculate the value 2ⁿ⁺¹. When the loop exits, the saddle brown path is taken, which takes us to Instruction Pointer #3. This IP merely dabbles along the bottom edge westwards in goldenrod yellow and soon passes control to IP #4.
The fuchsia path indicates how IP #4, starting in the bottom left, proceeds swiftly to decrement line, set ch to 32 (the space character) and seg to (the new value of) line. It is due to the early decrement that we actually start with 2ⁿ⁺¹−1 and eventually experience a last iteration with the value 0. We then enter the first nested loop.
We turn our attention to the branching indigo, where, after a brief decrement of seg, we see ch updated to x only if seg is now zero. Afterwards, n is set to line − seg to determine the actual number of the segment we’re in. Immediately we enter another loop, this time in the fair color of tomato.
Here, we figure out how many times n (the current segment number) can be divided by 2. For as long as the modulo gives us zero, we increment i and divide n by 2. When we are satisfied n is no longer thusly divisible, we branch into the slate gray, which contains two loops: first it raises 3 to the power of the i we calculated, and then it outputs ch that many times. Observe that the first of these loops contains a [ instruction, which switches control to IP #3 — the one that was only taking baby steps along the bottom edge earlier. The body of the loop (multiplying by 3 and decrementing) is executed by a lonely IP #3, imprisoned in an endless dark olive green cycle along the bottom edge of the code. Similarly, the second of these slate gray loops contains a ] instruction, which activates IP #5 to output ch and decrement, shown here in dark Indian red. In both cases, those Instruction Pointers trapped in servitude obediently execute one iteration at a time and yield control back to IP #4, only to bide the moment for their service to be called upon once again. The slate gray, meanwhile, rejoins its fuchsia and indigo brethren.
As seg inevitably reaches zero, the indigo loop exits into the lawn green path, which merely outputs the newline character and promptly merges back into the fuchsia to continue the line loop. Beyond the final iteration of the line loop lies the short sable ebon path of ultimate program termination.
Python 2, 78
L=[1]
i=3
exec"L+=[i]+L;i*=3;"*input()
while L:x=L.pop();print' '*sum(L)+'x'*x
Starting off with the list L=[1], we duplicate it and insert the next power of 3 in the middle, resulting in [1, 3, 1]. This is repeated n times to give us the row lengths for the Devil's staircase. Then we print each row padded with spaces.