text:
Draw the Devil's Staircase
The Devil's Staircase is a fractal-like function related to the Cantor set.

Your task is to replicate this funky function — in ASCII art!
Input
A single integer n >= 0, indicating the size of the output. Input may be given via STDIN, function argument or command-line argument.
Output
The ASCII-art rendition of the Devil's staircase at size n, either returned as a string or printed to STDOUT. Trailing spaces at the end of each row are okay, but leading spaces are not. You may optionally print a single trailing newline.
For size 0, the output is just:
x

(If you wish, you may use any other printable ASCII character other than space, in place of x.)
For size n > 0, we:

Take the output of size n-1 and stretch each row by a factor of three
Riffle between rows of single xs
Shift the rows rightward so that there is exactly one x in each column, and the position of the first x are minimal while decreasing with the rows

For example, the output for n = 1 is:
    x
 xxx
x

To get the output for n = 2, we stretch each row by a factor of three:
            xxx
   xxxxxxxxx
xxx

Riffle between rows of single x's:
x
            xxx
x
   xxxxxxxxx
x
xxx
x

Shift rightward:
                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

As another example, here is n = 3.
Scoring
This is code-golf, so the solution in the fewest bytes wins.

Pyth, 30
jb_u+G+*leGd*HNu+N+^3hTNUQ]1]k

This is a program that takes input from STDIN and uses grc's method of finding the Cantor set. Uses the " character to display the curve.
Try it online here.
Explanation:
I will explain the code in two parts, first, the cantor set generation:
u+N+^3hTNUQ]1
u        UQ]1         : reduce( ... , over range(input), starting with [1])
 +N                   : lambda N,T: N + ...
   +^3hTN             : 3 ** (T+1) + N   (int + list in pyth is interpreted as [int] + list)

And the output formatting:
jb_u+G+*leGd*HN    ]k
jb_                    : "\n".join(reversed(...)
   u               ]k  : reduce(lambda G,H: ... , over cantor set, starting with [""])
    +G+*leGd           : G + len(G[-1]) * " " + ...
            *HN        : H * '"'

Note that in pyth N = '"' by default.

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,
4

2 ^ >: 3 – two to the power of three incremented, that is,
16

i. 2 ^ >: 3 – the first 2 ^ >: 3 integers, that is,
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

}. i. 2 ^ 4 – the first 2 ^ >: 3 integers, beheaded, that is,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Let's call this sequence s; we enter f now.
1 q: s – the exponents of 2 in the prime decomposition of each item of s. In general, x q: y yields a table of the exponents for the first x primes in the prime decomposition of y. This yields:
0
1
0
2
0
1
0
3
0
1
0
2
0
1
0

3 ^ 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 because q: introduces an unwanted trailing axis. This yields
 1 3 1 9 1 3 1 27 1 3 1 9 1 3 1

(, 3 ^ 1 q: s) # s – each item of s replicated 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 ' #', so 0 is replaced by   and 1 is replaced by #, that is,
                                                                #
                                                             ###
                                                            #
                                                   #########
                                                  #
                                               ###
                                              #
                   ###########################
                  #
               ###
              #
     #########
    #
 ###
#

the result we want.

Inside the power loop (,],~3^#@~.)@] instead of (1,[:,1,"0~3*])  saves 1 byte. And if you're ok with ! as output char u:32+ instead of ' #'{~ saves another one.

#\  instead of i.@# and you overtake APL! :)

Your second solution doesn't work because a cap would be needed, but I found another way to beat APL.

The new output is the staircase for the n-1 not for n.

@randomra Ah… that's shitty. Let me see if it's fixable.

@randomra Not fixable. Let's see if beating APL is possible by other means.

Very interesting approach. You can extract the factors of 2 from a number m with m&-m (C or Ruby syntax). See my answer http://codegolf.stackexchange.com/a/46861/15599 I dont' know if it will be useful in any way.

@steveverrill That's a bit tricky to get right. Let me check…

@randomra Now we are on par with APL.

30 bytes: ' x'{~[:|.@=@I.3&(1,~1,@,.*)&1 -- retains the excellent self-classify idea, but uses a different method to generate the step sizes -- Try it online!

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.

Now this is just plain old-fashioned insanity.

Python 2, 78 bytes
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.

APL, 38
⊖↑'x'/⍨¨D,⍨¨0,¯1↓-+\D←{1,⍨∊1,⍪3×⍵}⍣⎕,1

Example:
      ⊖↑'x'/⍨¨D,⍨¨0,¯1↓-+\D←{1,⍨∊1,⍪3×⍵}⍣⎕,1
⎕:
      2
                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

Explanation:
⊖↑'x'/⍨¨D,⍨¨0,¯1↓-+\D←{1,⍨∊1,⍪3×⍵}⍣⎕,1

                                     ⎕       ⍝ read a number from the keyboard
                       {           }⍣ ,1      ⍝ apply this function N times to [1]
                               3×⍵           ⍝ multiply each value by 3
                           ∊1,⍪               ⍝ add an 1 in front of each value
                        1,⍨                  ⍝ add an 1 to the end
                     D←                      ⍝ store values in D (lengths of rows)
                   +\                        ⍝ get running sum of D
                  -                          ⍝ negate (negative values on / give spaces)
             0,¯1↓                           ⍝ remove last item and add a 0 to the beginning
                                             ⍝ (each row needs offset of total length of preceding rows)
         D,⍨¨                                ⍝ join each offset with each row length
   'x'/⍨¨                                    ⍝ get the right number of x-es and spaces for each row
 ↑                                           ⍝ make a matrix out of the rows
⊖                                            ⍝ mirror horizontally

That's a nice solution.

I love that the explanation of the code looks like a Devil's Staircase.

I found an even shorter APL solution.

GNU sed, 142
Not the shortest answer, but its sed!:
s/$/:/
:l
s/x/xxx/g
s/:/:x:/g
tb
:b
s/^1//
tl
s/:x/X/g
s/^/:/
:m
s/.*:([Xx]+)Xx*:$/&\1:/
tm
:n
s/([ :])[Xx](x*Xx*)/\1 \2/g
tn
s/:/\n/g
s/X/x/g

Because this is sed (no native arithmetic), I'm taking liberties with the rule "A single integer n >= 0, indicating the size of the output".  In this case the input integer must be a string of 1s, whose length is n.  I think this is "indicating" the size of the output, even though it is not a direct numerical equivalent to n.  Thus for n=2, the input string will be 11:
$ echo 11 | sed -rf devils-staircase.sed

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$

This appears to complete with exponential time complexity of O(cn), where c is about 17. n=8 took about 45 minutes for me.

Alternatively if it is required that n is entered numerically exactly, then we can do this:
sed, 274 bytes
s/[0-9]/<&/g
s/9/8Z/g
s/8/7Z/g
s/7/6Z/g
s/6/5Z/g
s/5/4Z/g
s/4/3Z/g
s/3/2Z/g
s/2/1Z/g
s/1/Z/g
s/0//g
:t
s/Z</<ZZZZZZZZZZ/g
tt
s/<//g
s/$/:/
:l
s/x/xxx/g
s/:/:x:/g
tb
:b
s/^Z//
tl
s/:x/X/g
s/^/:/
:m
s/.*:([Xx]+)Xx*:$/&\1:/
tm
:n
s/([ :])[Xx](x*Xx*)/\1 \2/g
tn
s/:/\n/g
s/X/x/g

Output:
$ echo 2 | sed -rf devils-staircase.sed

                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

$

This is really cool.

Python 2, 81
def f(n,i=1,s=0):
 if i<2<<n:q=3**len(bin(i&-i))/27;f(n,i+1,s+q);print' '*s+'x'*q

Program version (88)
def f(n,s=0):
 if n:q=3**len(bin(n&-n))/27;f(n-1,s+q);print' '*s+'x'*q
f((2<<input())-1)

The number of x's in the nth 1-indexed row is 3 to the power of (the index of the first set bit in n, starting from the lsb).

Python 2, 74
def f(n,s=0):
 if~n:B=3**n;A=s+B-2**n;f(n-1,A+B);print' '*A+'x'*B;f(n-1,s)

A recursive approach. The size-$n$ devil's staircase is split into three parts

The left recursive branch, a staircase of size n-1, whose length is 3**n - 2**n
The center line of x', of length 3**n
The right recursive branch, a staircase of size n-1, whose length is 3**n - 2**n

Note that the total length of the three parts is 3*(3**n) - 2*(2**n) or 3**(n+1) - 2**(n+1), which confirms the induction.
The optional variable s stores the offset of the current parts we're printing. We first recurse down to the left branch with larger offset, then print the center line, then do the right branch at the current offset.

CJam, 36 35 33 bytes
Here is another CJam approach (I haven't looked at Optimizer's code, so I don't know if it's actually much different):
L0sl~{{3*0s}%0s\+}*{1$,S*\+}%W%N*

This uses 0 for the curve. Alternatively, (using grc's trick)
LLl~){3\#a1$++}/{1$,S*\'x*+}%W%N*

which uses x.
Test it here.
Explanation
The basic idea is to first form an array with the rows, like
["0" "000" "0" "000000000" "0" "000" "0"]

And then to go through this list, prepending the right amount of spaces.
L0sl~{{3*0s}%0s\+}*{1$,S*\+}%W%N*
L                                 "Push an empty string for later.";
 0s                               "Push the array containing '0. This is the base case.";
   l~                             "Read and evaluate input.";
     {           }*               "Repeat the block that many times.";
      {    }%                     "Map this block onto the array.";
       3*                         "Triple the current string.";
         0s                       "Push a new zero string.";
             0s\+                 "Prepend another zero string.";
                   {       }%     "Map this block onto the result.";
                    1$            "Copy the last line.";
                      ,S*         "Get its length and make a string with that many spaces.";
                         \+       "Prepend the spaces to the current row.";
                             W%   "Reverse the rows.";
                               N* "Join them with newlines.";

The other version works similarly, but creates an array of lengths, like
[1 3 1 9 1 3 1]

And then turns that into strings of xs in the final map.

Dyalog APL, 34 characters
Using the approach by grc. Draws the staircase with ⌹ (domino) characters and takes input from stdin. This solution assumes ⎕IO←0.
' ⌹'[(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕]

⎕ – take input from stdin.
⌽⍳1+⎕ – the sequence of the numbers from ⎕ down to 0. (e.g. 3 2 1 0)
3*⌽⍳1+⎕ – three to the power of that (e.g. 27 9 3 1)
(⊢,,)/3*⌽⍳1+⎕ – the previous result folded from the right by the tacit function ⊢,, which is equal to the dfn {⍵,⍺,⍵} yielding the step lengths of the devil's staircase as per grc's approach.
{⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕ the step lengths converted into steps.
(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕ that self-classified, as in my J solution. Notice that ⊖ already flips the result correctly.
' ⌹'[(∪∘.=⊖){⍵/⍳≢⍵}⊃(⊢,,)/3*⌽⍳1+⎕] the numbers replaced by blanks and dominoes.

Ruby, 99
A different answer to my other one, inspired by FUZxxl's answer
FUZxxl notes that the numbers of x's correspond to the number of factors of 2 of the index. for example for n=2 we have the following factorization:
1 =1
2 =1 * 2
3 =3
4 =1 * 2 * 2
5 =5
6 =3 * 2
7 =7

I use a rather more straightforward way of extracting these powers of 2: i=m&-m which yields the sequence 1 2 1 4 1 2 1 etc. This works as follows:
m-1 is the same as min its most significant bits, but the least significant 1's bit becomes a zero, and all the zeros to the right become 1's.
To be able to AND this with the original, we need to flip the bits. There are various ways of doing this. One way is to subtract it from -1.
The overall formula is then m& (-1 -(m-1))  which simplifies to m&(-m)
Example:
          100   01100100
100-1=     99   01100011
-1-99=   -100   10011100
100&-100=   4   00000100

Here's the code: newlines are counted, indents are unnecessary and therefore not counted, as my other answer. It's slightly longer than my other answer due to the clumsy conversion from base 2: 1 2 1 4 1 2 1 etc to base 3: 1 3 1 9 1 3 1 etc (is there a way to avoid that Math:: ?)
def s(n)
  a=[]
  t=0
  1.upto(2*2**n-1){|m|i=3**Math::log(m&-m,2)
    a.unshift" "*t+"x"*i
    t+=i}
  puts a
end

Haskell, 99 characters
d=q.((iterate((1:).(>>=(:[1]).(*3)))[1])!!)
q[]=[];q(a:r)=sum r&' '++a&'x'++'\n':q r
(&)=replicate

The function is d:
λ: putStr $ d 3
                                                                x
                                                             xxx
                                                            x
                                                   xxxxxxxxx
                                                  x
                                               xxx
                                              x
                   xxxxxxxxxxxxxxxxxxxxxxxxxxx
                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

All these parentheses! Is there really no way to get around with less?

You can lose a byte by swapping the equations for q and doing q x=x in the empty list case. Also, it seems that the parentheses around iterate...[1] are unnecessary.

PHP - 137 bytes
function f($n){for($a=[];$i<=$n;array_push($a,3**$i++,...$a))$r=str_repeat;foreach($a as$v){$o=$r(' ',$s).$r(x,$v)."
$o";$s+=$v;}echo$o;}

I'm using here the same trick as grc. Here is the ungolfed version:
function staircase($n)
{
    $lengthsList = [];
    for ($i = 0; $i <= $n; ++$i) {
        array_push($lengthsList, 3 ** $i, ...$lengthsList);
    }

    $output = '';
    $cumulatedLength = 0;
    foreach ($lengthsList as $length)
    {
        $output = str_repeat(' ', $cumulatedLength) . str_repeat('x', $length) . "\n" . $output;
        $cumulatedLength += $length;
    }

    echo $output;
}

3**$i --> feels like PHP 5.6. You should specify it. This is incompatible with almost every installation of PHP. To save you a few bytes, you should start with $r=str_repeat; and where you have that function, you can replace with $r, saving you 2 bytes. Also, $r('x',$v) can be $r(x,$v) and it will work fine (notice that I've already replaced the function name with the variable). Also, I believe that ++$i<=$n can be rewritten as $n>++$i saving you another byte.

Here is your function, with a little cool trick: function f($n){$r=str_repeat;$a=[1];while($n>++$i)$a=array_merge($a,[3**$i],$a);foreach($a as$v){$o=$r(' ',$s).$r(x,$v)."\r$o";$s+=$v;}echo$o;} (instead of having that ugly newline, I've added the escape sequence \r inside a double-quoted string, with the variable $o inside it. Thus "\r$o" has the same byte-count as the ''.$o one, with newline ommited on the last one and produces the same result.

Actually, the condition of the while has to be $n>$i++ for this reduction to work properly.

@IsmaelMiguel PHP 5.6 is the last version of PHP, I don't have to say anything more. It's not my fault if almost everybody is using an old version, and if the majority is using an obsolete one. Thanks for the $r=str_repeat trick. I've been thinking only about $r='str_repeat';, which was not saving any byte. The undefined constant is a good trick also, well done ;). A newline is one byte smaller than writing \n, so I've kept it, but I've used double quotes to avoid a concatenation with $0. Thanks again !

It would only look good on you. If I wasn't aware of the 3 ** $i I would say that you have a terrible syntax. You may address that correction. I'm saying about this one only and not the [1] because that came from PHP5.4, which is quite 'old'. 1 year ago, I would ask you to specify that. Today, I ask you to simply specify (in a very short line) that specifies this. Speaking about the code, you still have the ++$i<=$n which can be replaced with $n>$i++. I had to convert all your code into PHP5.3 to test it. Which was painful. But I see you ate 7 bytes so far.

@IsmaelMiguel ++$i<$n isn't possible anymore with the new code reduction I've just done. Always uglier, always shorter :).

Well, at least it's shorter, right?

Late adoption of PHP releases is generally recommended. I wouldn't even recommend using 5.5 at this point. The current "stable" release is now on revision 22, and the last two revisions alone fixed over 50 bugs.

Ruby, 140 99
My second ever Ruby code, and my first nontrivial use of the language. Suggestions are most welcome. Byte count excludes leading spaces for indents, but includes newlines (it seems most of the newlines cannot be deleted unless they are replaced by a space at least.)
Input is by function call. Output is an array of strings, which ruby conveniently dumps to stdout as a newline-separated list with a single puts.
The algorithm is simply new iteration = previous iteration +  extra row  of n**3 x's + previous iteration. However there is a lot a fair amount of code just to get the leading spaces in the output right.
def s(n)
  a=["x"]
  1.upto(n){|m|t=" "*a[0].length
    a=a.map{|i|t+" "*3**m+i}+[t+"x"*3**m]+a}
  puts a
end

Edit: Ruby, 97
This uses the similar but different approach of building a numeric table of all the numbers of x's required in array a in the manner described above, but then building a table of strings afterwards. The table of strings is built backwards in array c using the rather oddly named unshift method to prepend to the existing array.
Currently this approach is looking better - but only by 2 bytes :-)
def s(n)
  a=c=[]
  (n+1).times{|m|a=a+[3**m]+a}
  t=0
  a.each{|i|c.unshift" "*t+"x"*i
    t+=i}
  puts c
end

You can replace for m in(0..n-1)do ... end with n.times{|m|...}.

@Omar Thanks, I'll try that tomorrow. You wouldn't believe how much effort it took to get that to run, due to the constant syntax errors. I didn't know how to access the iterating variable for n.times and I will certainly remember that. It eliminates an end too! However on this occasion I was wondering if for m in (1..n) might be better, to avoid the (m+1). Is there a shorter way of writing that?

for is long mainly because you are forced to use end (you can replace the do with a newline or with ;). For 1..n you can use 1.upto(n){|m|...}. I like the look of (1..n).each{|i|...} but it is slightly longer than using upto. And note that iterating by calling each or upto isn't just shorter, it's also consider more idiomatic Ruby.

@Thanks again, 1.upto(n) it is! With that and a few unnecessary brackets gone, I'm already down to 120. I think below 100 is possible, I will post the revised code later.

C, 165
#define W while
f(n){int i=n+1,j=1<<i,k=1,l,r,s,t;W(i--)k*=3;l=k-j;W(--j){r=j,s=1;W(!(r%2))r/=2,s*=3;l-=s;t=l;W(t--)putchar(32);W(++t<s)putchar(88);putchar('\n');}}

Here's the same code unpacked and slightly cleaned up:
int f(int n) {
    int i=n+1, j=1<<i, k=1;
    while (i--) k*=3;
    int l=k-j;
    while (--j) {
        int r=j,s=1;
        while (!(r%2))
            r/=2, s*=3;
        l-=s;
        int t=l;
        while (t--) putchar(' ');
        while (++t<s) putchar('X');
        putchar('\n');
    }
}

This is based on the same idea as FUZxxl's solution to the problem, of using an explicit rather than implicit form for the rows.  The declaration of j sets it to 2^(n+1), and the first while loop computes k=3^(n+1); then l=3^(n+1)-2^(n+1) is the total width of the staircase (this isn't too difficult to prove).  We then go through all the numbers r from 1 to 2^(n+1)-1; for each one, if it's divisible by (exactly) 2^n then we plan on printing s=3^n 'X's.  l is adjusted to make sure we start from the right spot: we write l spaces and s 'X's, then a newline.

define W to ;while and omit int to save some characters.

also t=l-=s for some saving.

@FUZxxl I tried both of those, but while C still allows implicit types on functions it wasn't allowing them on variable declarations even with the 'classic' flags (at least on GCC).  And I tried #define W ;while and it didn't seem to care for it, though I may have slipped up in the definition.

hm... I think you can only omit the type in a global variable. It doesn't bring you very much. You can try to add (*p)()=putchar; at the beginning to call putchar as p. I think it should work.

CJam, 46 43 41 39 36 35 bytes
L0ri),(a*+_W%(;+{3\#'x*+_,S*}%$1>N*

UPDATE using a different approach now.

Old approach:
]ri){3f*_,)"x"a*\]z:+}*_s,f{1$,U+:U-S*\N}

Pretty naive and long, but something to get started.
Will add explanation once I golf it.
Try it online here

Seems to need some work. Did not work properly for n =4, 5, 17.  Displayed  left-formatted riffles strings of x's at the upper part. With n=17 it dumped code to the screen and filled the bottom with x's.

@DavidCarraher For 4, 5 I think that's just the line wrapping. If you copy the output to a text editor with no line wrapping it looks okay to me.

Ok.  I know see.

Java, 271 269 bytes
Uses grc's method.
import java.util.*;String a(int a){List<Integer>b=new ArrayList<>();int c=-1,d=1;for(;c++<a;b.add(d),b.addAll(b),b.remove(b.size()-1),d*=3);String f="";for(;b.size()>0;f+="\n"){d=b.remove(b.size()-1);for(int g:b)for(c=0;c<g;c++)f+=' ';for(c=0;c<d;c++)f+='x';}return f;}

Indented:
import java.util.*;
String a(int a){
    List<Integer>b=new ArrayList<>();
    int c=-1,d=1;
    for(;c++<a;b.add(d),b.addAll(b),b.remove(b.size()-1),d*=3);
    String f="";
    for(;b.size()>0;f+="\n"){
        d=b.remove(b.size()-1);
        for(int g:b)
            for(c=0;c<g;c++)
                f+=' ';
        for(c=0;c<d;c++)
            f+='x';
    }
    return f;
}

Any suggestions are welcome.
2 bytes thanks to mbomb007

You could use b.size()>0 instead of !b.isEmpty(), saving 2 bytes.

Vyxal j, 16 bytes
Eɽ2Ǒ3$e₌ÞR‡\x*꘍Ṙ

Try it Online!
Eɽ               # range(1, 2**n-1)
  2Ǒ             # Multiplicity when divided by 2
    3$e          # 3 ** n
       ₌         # Apply both of the following to that:
        ÞR       # Cumulative sums with tail removed and 0 prepended
          ‡\x*   # And that many asterisks
              ꘍Ṙ # Pad with spaces to (cumulative sums) and reverse

your outputs are offset by one (0 should output x)

JavaScript (ES6) 104 106 118
Edit Removed the recursive function, the list of '*' for each line is obtained iteratively, fiddling with bits and powers of 3 (like in many other answers)
Inside the loop, a multiline string is buuilt from bottom up, keeping a running count of leading spaces to add on each line
F=n=>{
  for(i=a=s='';++i<2<<n;a=s+'*'.repeat(t)+'\n'+a,s+=' '.repeat(t))
    for(t=u=1;~i&u;u*=2)t*=3;
  return a
}

First Try removed
The recursive R function build an array with the number of '*' for each line.
For instance R(2) is [1, 3, 1, 9, 1, 3, 1]
This array is scanned to build a multiline string from bottom up, keeping a running count of leading spaces to add on each line
F=n=>
(R=n=>[1].concat(...n?R(n-1).map(n=>[n*3,1]):[]))(n)
.map(n=>a=' '.repeat(s,s-=-n)+'*'.repeat(n)+'\n'+a,a=s='')
&&a

Test In Firefox/FireBug console
F(3)

Output
                                                                *
                                                             ***
                                                            *
                                                   *********
                                                  *
                                               ***
                                              *
                   ***************************
                  *
               ***
              *
     *********
    *
 ***
*

Perl, 62
#!perl -p
eval's/x+/$&$&$&
x/g,s/\d*/x
/;'x++$_;s/x+/$"x$'=~y!x!!.$&/ge

First calculates the result iteratively without the leading spaces. Then adds them before each line according to the number of x characters in the rest of the string.

R - 111 characters
Straightforward implementation, building up the array iteratively and destroying it slowly.
n=scan()
a=1
if(n)for(x in 1:n)a=c(a,3^x,a)
for(A in a){cat(rep(' ',sum(a)-A),rep('x',A),'\n',sep='');a=a[-1]}

Usage:
> source('devil.r')
1: 2
2:
Read 1 item
                  x
               xxx
              x
     xxxxxxxxx
    x
 xxx
x

Good point, modified my code so it takes the n argument from the command line

You save 8 bytes by reading from STDIN. n=scan().

You don't need to declare x to use it as a cursor, nor do you need if(n). Also, line breaks count as a character I think.

Thanks, you're right about x. Not sure about if(n) however. I added that part to deal with the case n=0. The if(n) then returns F and hence returns a single x. If I remove it, n=0 gives unwanted results. New here, so didn't know about line breaks. Included now!

If you set a=0 and start the loop at x in 0:n it also works for n=0. Then you can omit the if(n).

If I'm right, that produces zeros between the steps (0 1 0 3 0 1 0), and consequently empty lines between the steps.

Husk, 41 bytes
!→⁰¡(↔§z+ömR' h∫mLtΘ`:"x"ṁȯe"x"Ṙ3f≠' );"x

Try it online!
Creates an infinite list of graphs and indexes into them, cause why not.

Julia 1.0, 64 bytes
!n=n<1 ? "x" : [' '^(L=2*3^n-2^n).*(m=!(n-1));lpad('x'^3^n,L);m]

Try it online!
output is a list of strings

Haskell, 81 bytes
d=unlines.f
f 0=["x"]
f n|z<-f$n-1=z%[[1..3^n]>>"x"]%z
a%b=map((a!!0>>" ")++)b++a

Try it online!
I counted d= to compete fairly with the older answer here.

Jelly, 22 bytes
‘2*Ṗọ2 3*µạ+ɼ;¹⁾ xx)ṚY

Try it online!
‘2*Ṗọ2 3*µạ+ɼ;¹⁾ xx)ṚY Main monadic link
‘                      Increment
 2*                    2 to the power
   Ṗ                   Range from 1 exclusive
    ọ2                 Order of 2
       3*              3 to the power
         µ         )   Map:
          ạ              Absolute difference with
           +ɼ              increment the register by the number
             ;           Join with
              ¹            the number
               ⁾ xx      Repeat " x" that many times
                    Ṛ  Reverse
                     Y Join with newlines

05AB1E, 20 bytes
0$F3*€1Ć}©×®ηO0š¨úR»

Outputs with 0 as character instead of x (could be any other digit by replacing the leading 0).
Try it online or verify the first few test cases.
Explanation:
0            # Push a 0
 $           # Push a 1 and the input-integer
  F          # Pop the input, and loop that many times:
   3*        #  Multiply the values by 3
     €1      #  Push a 1 before each integer in the list
       Ć     #  Enclose to also have a trailing 1
  }©         # After the loop: store the result in variable `®` (without popping)
    ×        # Pop it, and repeat the initial 0 that many times as string(s)
   ®         # Push list `®` again
    η        # Pop and push its prefixes
     O       # Sum each inner prefix
      0š     # Prepend a leading 0
        ¨    # Remove the last item
         ú   # Pad the "x"-string with that many leading spaces
          R  # Reverse the list
           » # Join the lines by newlines
             # (after which the result is output implicitly)


text:
Iterated Divisor Twist
Definitions
Let m and n be positive integers. We say that m is a divisor twist of n if there exists integers 1 < a ≤ b such that n = a*b and m = (a - 1)*(b + 1) + 1. If m can be obtained from n by applying zero or more divisor twists to it, then m is a descendant of n. Note that every number is its own descendant.
For example, consider n = 16. We can choose a = 2 and b = 8, since 2*8 = 16. Then
(a - 1)*(b + 1) + 1 = 1*9 + 1 = 10

which shows that 10 is a divisor twist of 16. With a = 2 and b = 5, we then see that 7 is a divisor twist of 10. Thus 7 is a descendant of 16.
The task
Given a positive integer n, compute the descendants of n, listed in increasing order, without duplicates.
Rules
You are not allowed to use built-in operations that compute the divisors of a number.
Both full programs and functions are accepted, and returning a collection datatype (like a set of some kind) is allowed, as long as it is sorted and duplicate-free. The lowest byte count wins, and standard loopholes are disallowed.
Test Cases
1 ->  [1]
2 ->  [2] (any prime number returns just itself)
4 ->  [4]
16 -> [7, 10, 16]
28 -> [7, 10, 16, 25, 28]
51 -> [37, 51]
60 -> [7, 10, 11, 13, 15, 16, 17, 18, 23, 25, 28, 29, 30, 32, 43, 46, 49, 53, 55, 56, 60]

@Zgarb if you allow for a chain of 0 divisor twists, then how is not every number a descendant of any other number?

@rcrmn To me, a chain of zero operations means the identity operation. So allowing zero divisor twists only implies that every number is a descendant of itself.

@Zgarb okay, so the definition should be changed to express that, because if not, as far as I can tell, any number is considered a descendant of every other number. I don't know why it's needed the reflexivity. Would you care to explain?

@rcrmn I changed the wording slightly, is it clearer now?

@Zgarb sorry but no, it's not an operation, you are defining a relationship between numbers. If you define the relationship < for the natural numbers, for every n you get every number smaller than it but not itself. I think this should be something similar. This way I think only 4 would be its own descendant (not sure about that, though).

@rcrmn Sure, let's phrase it like that. "Being obtainable by one divisor twist" is a binary relation between positive integers; denote it by n ~> m. Then, I define the descendant relation n *~> m by stating that there exists some chain a[1], a[2], ..., a[k] of numbers such that a[1] = n, a[k] = m and a[i] ~> a[i+1] for all i. The case m = n then corresponds to k = 1.

@Zgarb All right, point taken. I understood your meaning, I just didn't understand the why of it. I'm sorry for bothering, but thank you!

Python 2, 109 98 85 82 bytes
f=lambda n:sorted(set(sum(map(f,{n-x+n/x for x in range(2,n)if(n<x*x)>n%x}),[n])))

Since (a-1)*(b+1)+1 == a*b-(b-a) and b >= a, descendants are always less than or equal to the original number. So we can just start with the initial number and keep generating strictly smaller descendants until there are none left.
The condition (n<x*x)>n%x checks two things in one - that n<x*x and n%x == 0.
(Thanks to @xnor for taking 3 bytes off the base case)
Pyth, 32 bytes
LS{s+]]bmydm+-bk/bkf><b*TT%bTr2b

Direct translation of the above, except for the fact that Pyth seems to choke when trying to sum (s) on an empty list.
This defines a function y which can be called by appending y<number> at the end, like so (try it online):
LS{s+]]bmydm+-bk/bkf><b*TT%bTr2by60

CJam, 47 45 bytes
{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}

Also using the same method, with a few modifications. I wanted to try CJam for comparison, but unfortunately I'm much worse at CJam than I am at Pyth/Python, so there's probably a lot of room for improvement.
The above is a block (basically CJam's version of unnamed functions) that takes in an int and returns a list. You can test it like so (try it online):
{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}:G; 60 Gp

I'm no Python expert, but is there a reason why you need set() in there? Can't you just return the sorted list?

@Alex set() is to remove duplicates :)

Oh, okay. Neat. Nice work!

Can you perhaps do [n]+sum(...,[]) as sum(...,[n])?

@xnor Ah yes, I can. I've never used anything but [] as a base case for summing lists, so I completely forgot!

Java, 148 146 104 bytes
Golfed version:
import java.util.*;Set s=new TreeSet();void f(int n){s.add(n);for(int a=1;++a*a<n;)if(n%a<1)f(n+a-n/a);}

Long version:
import java.util.*;
Set s = new TreeSet();
void f(int n) {
    s.add(n);
    for (int a = 1; ++a*a < n;)
        if (n%a < 1)
            f(n + a - n/a);
}

So I'm making my debut on PPCG with this program, which uses a TreeSet (which automatically sorts the numbers, thankfully) and recursion similar to Geobits' program, but in a different manner, checking for multiples of n and then using them in the next function. I'd say this is a pretty fair score for a first-timer (especially with Java, which doesn't seem to be the most ideal language for this kind of thing, and Geobits' help).

Welcome to PPCG! You can save a couple by changing a*b to n on line 9.

Thanks for the welcome and the suggestion! Yeah, it'll take a while for me to spot these small things. Every byte counts! Thanks again!

You can also save two more by putting c=n+a-b inside add(). Alternatively, you could get rid of c altogether and just use n+a-b in both places for those same two bytes.

Speaking of which, I don't think I need to use add twice. Hold on a moment...

But the second loop isn't needed on the whole. If you have an a that you know divides n cleanly, then you shouldn't loop to find b, it's just n/a. At that point it starts getting closer and closer to mine ;)

So... how's that? I can't thank you enough for your help! I'll get the hang of this eventually, especially with more experience. :)

Looks good! It's pretty much what I would have if I moved the set out of the function. I decided against it because the function can only be used once this way (without clearing the set between calls, at least).

Java, 157 121
Here's a recursive function that gets descendants of each descendant of n. It returns a TreeSet, which is sorted by default.
import java.util.*;Set t(int n){Set o=new TreeSet();for(int i=1;++i*i<n;)o.addAll(n%i<1?t(n+i-n/i):o);o.add(n);return o;}

With some line breaks:
import java.util.*;
Set t(int n){
    Set o=new TreeSet();
    for(int i=1;++i*i<n;)
        o.addAll(n%i<1?t(n+i-n/i):o);
    o.add(n);
    return o;
}

Octave, 107 96
function r=d(n)r=[n];a=find(!mod(n,2:sqrt(n-1)))+1;for(m=(a+n-n./a))r=unique([d(m) r]);end;end

Pretty-print:
function r=d(n)
  r=[n];                          # include N in our list
  a=find(!mod(n,2:sqrt(n-1)))+1;  # gets a list of factors of a, up to (not including) sqrt(N)
  for(m=(a+n-n./a))               # each element of m is a twist
    r=unique([d(m) r]);           # recurse, sort, and find unique values
  end;
end

It's my understanding that Octave can end blocks with just end rather than endfor and endfunction. That would save you 11 bytes.

Hey, you are right! Not how I learned the language and never realized it could be done. Why are you the first one to point this out after I've done multiple golfs with it?

I only knew that because I recently looked it up after seeing it in someone else's golf on another question. I've never used Octave and it's been years since I've used Matlab. My guess is that there aren't all that many active Octave users on PPCG, but I could be wrong.

Well, thank you for pointing it out.

My pleasure, glad I could help. Nice solution.

Haskell, 102 100 bytes
import Data.List
d[]=[]
d(h:t)=h:d(t++[a*b-b+a|b<-[2..h],a<-[2..b],a*b==h])
p n=sort$nub$take n$d[n]

Usage: p 16 which outputs [7,10,16]
The function d recursively calculates all descendants, but does not check for duplicates, so many appear more than once, e. g. d [4] returns an infinite list of 4s. The functions p takes the first n elements from this list, removes duplicates and sorts the list. Voilà.

CJam - 36
ri_a\{_{:N,2>{NNImd!\I-z*-}fI}%|}*$p

Try it online
Or, different method:
ri_a\{_{_,2f#_2$4*f-&:mq:if-~}%|}*$p

I wrote them almost 2 days ago, got stuck at 36, got frustrated and went to sleep without posting.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Decode a Heat Map
Heatmaps
Consider a rectangular room, on whose ceiling we have a thermal camera pointing downward. In the room, there are some number of heat sources of intensity 1-9, the background temperature being 0. The heat dissipates from each source, dropping by one unit per (non-diagonal) step. For example, the 20x10 room
...........1........
....................
...8................
..5...............2.
....................
.1..................
................1...
.................65.
....................
............2.......

contains 9 heat sources, and the temperature gradient shown by the thermal camera is
34565432100100000000
45676543210000000000
56787654321000000110
45676543210000001221
34565432100000012321
23454321000000123432
12343210000001234543
01232100000012345654
00121000000011234543
00010000000121123432

In graphical form this might look like:

From the gradient, we can infer the positions and intensities of some heat sources, but not all. For example, all 9s can always be inferred, since they have the maximal temperature, and so can the 8 in this case, since it produces a local maximum in the gradient. The 2 near the right border can also be inferred, even though it is not at a local maximum, since it does not have another 2 as a neighbor. The 5s, on the other hand, are not inferred, since their heat might as well be produced by the more intense sources near them. The 0s are known to contain no heat sources, but all the other tiles may potentially contain one. Let's denote the uncertain tiles by hyphens -, certain heat sources by the corresponding digits, and certain empty space by periods .:
---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------

Your task shall be to produce this inferred pattern from the temperature gradient.
Rules
You are given the input as a string delimited by either newlines or vertical pipes |, whichever is more convenient, and the output shall be of the same form. There may be a trailing delimiter in the input and/or output, but no preceding one. The size of the input may vary, but its width and height are always at least 4. Both functions and full programs are acceptable. The lowest byte count wins, and standard loopholes are forbidden.
Additional Test Cases
Input:
898778765432100
787667654321100
677656543211210
678765432112321
567654321123210

which looks like this in graphical form:

Output:
-9---8-------..
-------------..
--------------.
--8---------3--
-----------3--.

Input:
7898
8787
7676
6565

Output:
--9-
8---
----
----

Input:
00001
00000
00000
10000

Output:
....1
.....
.....
1....

Do you mind if I add 2 heatmap graphics to your question if you think they add value? They are just a 2 minute experiment.

@CarpetPython Sure, go ahead. They look very nice to me. You can also add a "Courtesy of CarpetPython" to give yourself the credit. ;)

Done. No credit required, but I thought it would be rude not to ask before editing.

Why not allow the input as a 2-dimensional array instead of a string?

@feersum generally input methods are consistent.

@feersum As Optimizer said, I wanted the input and output to have the same format. In particular, I had to use only single digits, so string was a natural choice. Also, they look nicer than arrays. :P

@Zgarb I meant a 2-dimensional character array.

@feersum Well, I simply wanted parsing (or not) the input string to be an integral part of the challenge.

CJam, 73 69 62 55 bytes
UPDATE : New algorithm. Shorter and more scope for improvement
qN/5ff*{{[{_@_@<{I'0t}*\}*]W%}%z}4fI{):X-'-X~X'.??}f%N*

How it works
The logic is similar to the algorithm below, but here I am not checking for all 4 neighbors in a single iteration. Instead, I use a smaller approach to iterate through all rows and columns in both directions. Here are the steps involved:

Convert each character into sets of 5. The first 4 will be modified to tell if they are bigger than the adjacent cell in the row while iterating. Last one is for comparison purposes.
Iterate on each row and reduce on each row. While reducing, I have two 5 character string. I know what kind of iteration is [0 for rows normal, 1 columns reversed, 2 for rows reversed and 3 for columns normal] I update the ith character in the first 5 character string and make it 0 if it is smaller than the second.
After all 4 iterations, if all 5 characters are same and non-zero, that is the local maxima. I map through all 5 characters strings and convert them to either single digit, . or -.

Here is an example run on a small input:
7898
8787
7676
6565

After first step:
["77777" "88888" "99999" "88888"
 "88888" "77777" "88888" "77777"
 "77777" "66666" "77777" "66666"
 "66666" "55555" "66666" "55555"]

After second step:
["00777" "08888" "99999" "88088"
 "88888" "07007" "88808" "77007"
 "77707" "06006" "77707" "66006"
 "66606" "05005" "66606" "55005"]

After last mapping to single character, final output:
--9-
8---
----
----

Code Explanation:
qN/5ff*                         "Split the input on new line and convert each character";
                                "to string of 5 of those characters.";
{{[{             }*]W%}%z}4fI   "This code block runs 4 times. In each iteration, it";
                                "maps over each row/column and then for each of them,";
                                "It reduce over all elements of the row/column";
                                "Using combination of W% and z ensures that both rows and";
                                "columns are covered and in both directions while reducing";
    _@_@                        "Take a copy of last two elements while reducing over";
        <                       "If the last element is bigger than second last:";
         {I'0t}*\               "Convert the Ith character of the 5 char string of"
                                "second last element to 0";
                                "We don't have to compare Ith character of last two 5 char";
                                "string as the smaller one will be having more leading";
                                "0 anyways. This saves 4 bytes while comparing elements";
{):X-'-X~X'.??}f%N*             "This part of code converts the 5 char back to single char";
 ):X                            "Remove the last character and store in X. This last char";
                                "was not touched in the prev. loop, so is the original char";
    -                           "Subtract X from remaining 4 char. If string is not empty";
                                "then it means that it was not all same characters";
                                "In other words, this character was smaller then neighbors";
     '-      ?                  "If non-empty, then replace with - else ...";
       X~X'.?                   "if int(X) is zero, put . else put X";
               f%N*             "The mapping code block was run for each row and then";
                                "The rows are joined by newline.";

Try it here

Older approach
qN/~_,):L0s*]0s*:Q_,{QI=:A[W1LL~)]If+Qf=$W=<'-A?A~\'.?I\t}fIL/W<Wf<N*

How it works
The logic is simple, iterate through the grid and see if the current value is greater or equal to the remaining four neighbors - up, down, left and right. Then transform the current value based on the above rule and if the value is equal to 0, make it "." .
Code Explanation
qN/~_,):L0s*]0s*:Q         "This part of code pads the grid with 0s";
qN/~                       "Read the input, split on new lines and unwrap the arrays";
    _,):L                  "Copy the last row, taken length, increment and store in L";
         0s*               "Get L length 0 string";
            ]0s*           "Wrap everything in an array and join the rows by 0";
                :Q         "Store this final single string in Q";

_,{        ...      }fI    "Copy Q and take length. For I in 0..length, execute block";
   QI=:A                   "Get the I'th element from Q and store in A";
   [WiLL~)]If+             "This creates indexes of all 4 neighboring cells to the Ith cell";
              Qf=          "Get all 4 values on the above 4 indexes";
                 $W=       "Sort and get the maximum value";
<'-A?                      "If the current value is not the largest, convert it to -";
     A~\'.?                "If current value is 0, convert it to .";
           I\t             "Update the current value back in the string";
{ ... }fIL/                "After the loop, split the resulting string into chunks of L";
           W<Wf<           "Remove last row and last column";
                N*         "Join by new line and auto print";

Try it online here

I must say, I seldom hear "too long" when describing CJam code.

JavaScript (ES6) 99
F=h=>[...h].map((c,i)=>[o=~h.search('\n'),-o,1,-1].some(d=>h[d+i]>c)&c>0?'-':c=='0'?'.':c).join('')

Test In Firefox/FireBug console
console.log(F('\
34565432100100000000\n\
45676543210000000000\n\
56787654321000000110\n\
45676543210000001221\n\
34565432100000012321\n\
23454321000000123432\n\
12343210000001234543\n\
01232100000012345654\n\
00121000000011234543\n\
00010000000121123432\n'),'\n\n',
F('\
898778765432100\n\
787667654321100\n\
677656543211210\n\
678765432112321\n\
567654321123210\n'), '\n\n',
F('7898\n8787\n7676\n6565\n'))

Output
---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------

-9---8-------..
-------------..
--------------.
--8---------3--
-----------3--.

--9-
8---
----
----

Python 2: 154 byte
b=input()
l=b.index('\n')+1
print''.join(('\n.'+('-'+v)[all([v>=b[j]for j in i-l,i-1,i+l,i+1if 0<=j<len(b)])])[('\n0'+v).index(v)]for i,v in enumerate(b))

Input has to be of the form "00001\n00000\n00000\n10000".
Converting a string to a 2D-matrix is quite lengthy in Python. So I keep the original string format. I enumerate over the input, i is the index, v is the char (Finally enumerate saved bytes in a golf solution!!). For each pair (i,v) I compute the correct char of output, and join them. How do I choose the correct output char? If v == '\n', the output char is \n, it v == '0', than the output char is '.'. Otherwise I test the 4 neighbors of v, which are b[i-b.index('\n')-1] (above), b[i-1] (left, b[i+1] (right) and b[i+b.index('\n')+1] (under), if they are <= v and choose the char '-' or v. Here I'm comparing chars not the numbers, but it works quite fine, because the ascii values are in the correct order. Also there are no problems, if b[i-1] or b[i+1] equal '\n', because ord('\n') = 10.
Pyth: 61 58
JhxQbVQK@QN~k@++b\.?\-f&&gT0<TlQ<K@QT[tNhN-NJ+NJ)Kx+b\0K)k

More or less a translation of the Python script. Quite ugly ;-)
Try it online: Pyth Compiler/Executor Same input format as the Python solution.
JhxQb      Q = input()
  xQb      Q.index('\n')
 h         +1
J          store in J

VQK@QN~k.....)k   k is initialized as empty string
VQ           )    for N in [0, 1, 2, ..., len(Q)-1]:
  K@QN                K = Q[n]
      ~k              k += ... (a char, computed in the next paragraph)
             )    end for
              k   print k

@...x+b\0K   ... is a char of len 3 (is constructed below)
     +b\0    the string "\n0"
    x    K   find Q[d] in this string and return index, if not found -1
@...         lookup in string at the computed position (this is done mod 3 automatically!)

++b\.?\-f&&gT0<TlQ<K@QT[tNhN-NJ+NJ)K   not to the string
                       [tNhN-NJ+NJ)    the list [d-1, d+1, d-J, d+j]
        f                              filter the list for indices T which
           gT0                            T >= 0
          &                               and
              <TlQ                        T < len(Q)
         &                                and
                  <K@QT                   Q[d] < Q[T]
     ?\-                           K   use "-" if len(filter) > 0 else Q[d]
                                       this creates the third char
++b\.                                  "\n" + "." + third char

Perl, 77, 75, 72 70
Standard 2d regex matching tricks.
#!perl -p0
/
/;$x="(.{@-})?";y/0/./while s/$.$x\K$"|$"(?=$x$.)/-/s||($"=$.++)<9

Example:
$ perl heat.pl <in.txt
---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------

Try it here

Java, 307, 304, 303, 299 298
This is for sure a "perfect" challenge for some Java codegolf :)
class M{public static void main(String[]a){int c=a[0].indexOf('|'),i=c,d,v;char[]r=a[0].replace("|","").toCharArray(),m=new char[(v=r.length+c)+c];for(;i<v;){m[i]=r[i++-c];}for(i=c;i<v;i++){a[0]=i%c<1?"\n":"";d=m[i];System.out.print(a[0]+(d<49?'.':m[i-c]>d|m[i+c]>d|m[i-1]>d|m[i+1]>d?'-':m[i]));}}}

Input (pipe '|' method):
34565432100100000000|45676543210000000000|56787654321000000110|45676543210000001221|34565432100000012321|23454321000000123432|12343210000001234543|01232100000012345654|00121000000011234543|00010000000121123432

Output:
---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------

This can be 288 if you remove the space in char[]r=a[0].replace("|", <--here"").toCharArray().

Did not spot that one, thanks! Well this makes 298

APL, 92
('.-',⎕D)[1+(M≠0)+M{(1+⍺)×0≠⍺∧M[J/⍨Z∊⍨J←⍵∘+¨(⌽¨,+)(-,+)⊂0 1]∧.≤⍺}¨Z←⍳⍴M←↑{×⍴⍵:(⊂⍎¨⍵),∇⍞⋄⍬}⍞]

Example:
       ('.-',⎕D)[1+(M≠0)+M{(1+⍺)×0≠⍺∧M[J/⍨Z∊⍨J←⍵∘+¨(⌽¨,+)(-,+)⊂0 1]∧.≤⍺}¨Z←⍳⍴M←↑{×⍴⍵:(⊂⍎¨⍵),∇⍞⋄⍬}⍞]
34565432100100000000
45676543210000000000
56787654321000000110
45676543210000001221
34565432100000012321
23454321000000123432
12343210000001234543
01232100000012345654
00121000000011234543
00010000000121123432

---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------

The longest APL program I've ever seen. You might want to note that this is not standard APL as it uses dfns.

Ruby 140
f=->s{
r=s.dup
l=s.index(?\n)+1
(0...s.size).map{|i|
s[i]<?0||r[i]=r[i]<?1??.:[i-1,i+1,i-l,i+l].map{|n|n<0??0:s[n]||?0}.max>r[i]??-:s[i]}
r}

Nothing special; just iterate through the map and compare the current value with the value of the four neighbors.
Run it online with tests: http://ideone.com/AQkOSY

Perl - 226
sub f{for(split'
',$_[0]){chomp;push@r,r($_);}for(t(@r)){push@y,r($_)=~s/0/./gr}$,=$/;say t(@y);}sub r{$_[0]=~s/(?<=(.))?(.)(?=(.))?/$1<=$2&&$3<=$2?$2:$2eq'0'?0:"-"/ger;}sub t{@q=();for(@_){for(split//){$q[$i++].=$_;}$i=0;}@q}

You can try it on ideone. If anyone is interested in an explanation, let me know.

I think you have 226 chars, not 227.

@w0lf you're right, the newline got counted for 2 since I'm on Windows.

R, 223
About the best I can come up with at the moment.  Dealing with the string is quite expensive.  I think there is room for improvement, but can't see it at the moment
s=strsplit;a=c(m<-do.call(rbind,s(s(scan(w="c"),'|',T)[[1]],'')));w=(d<-dim(m))[1];n=c(-1,1,-w,w);cat(t(array(sapply(seq(a),function(x)if(a[x]>0)if(any(a[(n+x)[which(n+x>0)]]>a[x]))'-'else a[x]else'.'),d)),fill=d[2],sep='')

Test Result
> s=strsplit;a=c(m<-do.call(rbind,s(s(scan(w="c"),'|',T)[[1]],'')));w=(d<-dim(m))[1];n=c(-1,1,-w,w);cat(t(array(sapply(seq(a),function(x)if(a[x]>0)if(any(a[(n+x)[which(n+x>0)]]>a[x]))'-'else a[x]else'.'),d)),fill=d[2],sep='')
1: 898778765432100|787667654321100|677656543211210|678765432112321|567654321123210
2:
Read 1 item
-9---8-------..
-------------..
--------------.
--8---------3--
-----------3--.
> s=strsplit;a=c(m<-do.call(rbind,s(s(scan(w="c"),'|',T)[[1]],'')));w=(d<-dim(m))[1];n=c(-1,1,-w,w);cat(t(array(sapply(seq(a),function(x)if(a[x]>0)if(any(a[(n+x)[which(n+x>0)]]>a[x]))'-'else a[x]else'.'),d)),fill=d[2],sep='')
1: 34565432100100000000|45676543210000000000|56787654321000000110|45676543210000001221|34565432100000012321|23454321000000123432|12343210000001234543|01232100000012345654|00121000000011234543|00010000000121123432
2:
Read 1 item
---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------
>

J - 69 bytes
[:u:45+[:(+2 0 3{~"#1+*)@((]*]=(0,(,-)1 0,:0 1)>./@:|.])-0=])"."0;._2

Examples:
   ([:u:45+[:(+2 0 3{~"#1+*)@((]*]=(0,(,-)1 0,:0 1)>./@:|.])-0=])"."0;._2) (0 : 0)
34565432100100000000
45676543210000000000
56787654321000000110
45676543210000001221
34565432100000012321
23454321000000123432
12343210000001234543
01232100000012345654
00121000000011234543
00010000000121123432
)
---------..1........
----------..........
---8-------......--.
----------......--2-
---------......-----
--------......------
-------......-------
.-----......-----6--
..---.......--------
...-.......-2-------
   ([:u:45+[:(+2 0 3{~"#1+*)@((]*]=(0,(,-)1 0,:0 1)>./@:|.])-0=])"."0;._2) (0 : 0)
898778765432100
787667654321100
677656543211210
678765432112321
567654321123210
)
-9---8-------..
-------------..
--------------.
--8---------3--
-----------3--.

PS: the (0 : 0) is the standard J way of specifying strings. You might as well use | delimited strings (with a trailing |).

Excel VBA - 426
It'll be a rare occasion that VBA wins any code golf games, but as it's what I use the most, it's fun to play around with it. The first line is an edge case that made this longer than it seems it should have to be.
Sub m(a)
    b = InStr(a, "|")
    For i = 1 To Len(a)
        t = Mid(a, i, 1)
        Select Case t
            Case "|"
                r = r & "|"
            Case 0
                r = r & "."
            Case Else
                On Error Resume Next
                x = Mid(a, i - 1, 1)
                y = Mid(a, i + 1, 1)
                Z = Mid(a, i + b, 1)
                If i < b Then
                    If t < x Or t < y Or t < Z Then
                        r = r & "-"
                    Else
                        r = r & t
                    End If
                Else
                    If t < x Or t < y Or t < Z Or t < Mid(a, i - b, 1) Then
                        r = r & "-"
                    Else
                        r = r & t
                    End If
                End If
        End Select
    Next
    MsgBox r
End Sub

The count doesn't include initial line whitespace.
I played around with the idea of sending the input to a sheet and working from there, but I think looping the passed string character-by-character saves code.
Call from Immediate Window:
m "34565432100100000000|45676543210000000000|56787654321000000110|45676543210000001221|34565432100000012321|23454321000000123432|12343210000001234543|01232100000012345654|00121000000011234543|00010000000121123432"

Output (in a Window):
---------..1........|----------..........|---8-------......--.|----------......--2-|---------......-----|--------......------|-------......-------|.-----......-----6--|..---.......--------|...-.......-2-------

Haskell - 193
z='0'
r=repeat z
g s=zipWith3(\u t d->zip3(zip(z:t)u)t$zip(tail t++[z])d)(r:s)s$tail s++[r]
f=unlines.map(map(\((l,u),t,(r,d))->case()of _|t==z->'.'|maximum[u,l,t,r,d]==t->t|0<1->'-')).g.lines

f is a funtion that takes a string in the form 0001\n0000\n0000\n1000 and returns the required string.
g is a function that takes a list of lists of chars and returns a list of lists of ((left, up), this, (right, down)).

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Total number of topological sorts
For a given DAG (directed acyclic graph), each of its topological sorts is a permutation of all vertices, where for every edges (u,v) in the DAG, u appears before v in the permutation.
Your task is to calculate the total number of topological sorts of a given DAG.
Rules

You can use any format to represent the graph, like adjacency matrix, adjacency list or edge list, as long as you don't do useful computations in your encoding. You can also have things like vertex count or vertex list in the input, if those are useful.
You can assume the graph in the input is always a DAG (doesn't have any cycles).
Your program should work in theory for any input. But it can fail if it overflows the basic integer type in your language.
The names of vertices can be any consecutive values in any type. For example: numbers starting at 0 or 1. (And only if you are not storing code in this number, of course.)
This is code-golf. Shortest code wins.

Example
This is the same input in different formats. Your program don't have to accept all of them. Vertices are always integers starting at 0.
Adjacency list:
[ [1 2 3 5] [2 4] [] [2] [] [3] ]
Adjacency matrix:
[ [0 1 1 1 0 1] [0 0 1 0 1 0] [0 0 0 0 0 0] [0 0 1 0 0 0] [0 0 0 0 0 0] [0 0 0 1 0 0] ]
Edge list:
6 [ [0 1] [0 2] [0 3] [0 5] [1 2] [1 4] [3 2] [5 3] ]

It's the graph shown in this image:

The output should be:
9

The topological sorts are:
[0 1 4 5 3 2]
[0 1 5 4 3 2]
[0 1 5 3 4 2]
[0 1 5 3 2 4]
[0 5 1 4 3 2]
[0 5 1 3 4 2]
[0 5 1 3 2 4]
[0 5 3 1 4 2]
[0 5 3 1 2 4]

Function? Whole Program? Either?

@isaacg Either.

Nekomata + -n, 5 bytes
↕ᵚ{S=

Attempt This Online!
Takes input as a vertex count and a list of edges, e.g., 6 [[0,1],[0,2],[0,3],[0,5],[1,2],[1,4],[3,2],[5,3]].
↕ᵚ{S=
↕       Find a permutation of [0, ..., vertex count - 1]
 ᵚ{     For each element in the edges list:
   S        Find a subset of the permutation
    =       that is equal to the edge

-n counts the number of solutions.

Python, 58
f=lambda G,V:V<{0}or sum(f(G,V-{v})*(V-G[v]==V)for v in V)

The input consists of an adjacency dictionary G and a vertex set V.
G = {0:{1,2,3,5}, 1:{2,4}, 2:set(), 3:{2}, 4:set(), 5:{3}, 6:set()}
V = {0,1,2,3,4,5,6}

The code is recursive. The set V stores all nodes that still need visiting. For each potential next node, we check its suitability by seeing if no remaining vertices point to it, with V-G[v]==V checking that V and G[v] are disjoint. For all suitable such vertices, we add the number of topological sorts with it removed. As a base case, the empty set gives 1.

+1 for not using edge list.

why is 6 missing from V?

Mathematica, 80 57 51 bytes
Count[Permutations@#,l_/;l~Subsets~{2}~SubsetQ~#2]&

Very straight-forward implementation of the definition. I'm just generating all permutations and count how many of them are valid. To check if a permutation is valid, I get all pairs of vertices in the permutation. Conveniently, Subsets[l,{2}] not only gives me all pairs, it also maintains the order they are found in in l - just what I need.
The above is a function that expects the vertex list and edge list, like
f[{1, 2, 3, 4, 5, 6}, {{1, 2}, {1, 3}, {1, 4}, {1, 6}, {2, 3}, {2, 5}, {4, 3}, {6, 4}}]

if you call the function f.
I'll try to golf this, or maybe use another approach later.

Count[Permutations@#,l_/;Subsets@l~SubsetQ~#2]&

CJam - 25
q~{_f{1$-_j@j@&!*}_!+:+}j

With great help from user23013 :)
Try it online
Explanation:
The general algorithm is the same as in xnor's Python solution.
The key here is the j operator, which does memoized recursion. It takes a parameter, a value or array for the initial value(s) (as in f(0), f(1), etc) and a block to define the recursion. The j operator is used again inside the block for doing recursive (and memoized) calls to the same block. It can also be used with multiple parameters, but it's not the case here.
user23013's great innovation is to use j with different data types, making use of the adjacency list as the array of initial values.
q~             read and evaluate the input (vertex list followed by adjacency list)
{…}j           run the block on the vertex list, doing memoized recursion
                and using the adjacency list for initial values
    _          copy the vertex list
    f{…}       for each vertex and the vertex list
        1$-    copy the vertex and remove it from the list
                Python: "V-{v}"
        _j     copy the reduced list and call the j block recursively
                this solves the problem for the reduced vertex list
                Python: "f(G,V-{v})"
        @j     bring the vertex to the top of the stack and call the j block recursively
                in this case, it's called with a vertex rather than a list
                and the memoized value is instantly found in the list of initial values
                effectively, this gets the list of vertices adjacent to the current vertex
                Python: "G[v]"
        @&     bring the reduced list to the top of the stack and intersect
        !*     multiply the number of topological sorts of the reduced vertex list
                with 1 if the intersection was empty and 0 if not
                Python: equivalent to "*(V-G[v]==V)"
               after this loop we get an array of sub-results for the reduced vertex lists
    _!+        add 1 or 0 to the array if the array was empty or not
                because we want to get 1 for the empty array
                Python: equivalent to "V<{0}or"
    :+         add the numbers in the array
                Python: "sum(…)"

Edited to explicitly allow vertex list in the input. Now 25 bytes.

@user23013 What kind of sorcery is this? :o

Haskell, 102 107 100 89 85 bytes
import Data.List
(%)=elemIndex
n#l=sum[1|p<-permutations[0..n],and[u%p<v%p|[u,v]<-l]]

The input is the highest vertex number (starting with 0) and an edge list, where an edge is a two element list. Usage example: 5 # [[0,1], [0,2], [0,3], [0,5], [1,2], [1,4], [3,2], [5,3]]
How it works: count all permutations p of the vertices for which all edges [u,v] satisfy: position of u in p is less than position of v in p. That's a direct implementation of the definition.
Edit: my first version returned the topological sorts themselves and not how many there are. Fixed it.
Edit II: didn't work for graphs with not connected vertices. Fixed it.

I'm thinking of adding a test case with only vertices but not edges...

@user23013: works for graphs with not connected vertices, now. It even became shorter.

Pyth, 27 bytes
Mlf!sm}_dHfq2lYyTfqSZUZ^UGG

Defines a 2 input function, g. First input is the number of vertices, second is the list of directed edges.
To test:
Code:
Mlf!sm}_dHfq2lYyTfqSZUZ^UGGghQeQ

Input:
6, [ [0, 1], [0, 2], [0, 3], [0, 5], [1, 2], [1, 4], [3, 2], [5, 3] ]

Try it here.

@user23013 Boht count and list are being used, in the expression ^UGG, which generates all G entry lists of range(len(G)).

I meant, will it be shorter if you use [0, 1, ...] directly in the input?

@user23013 No, it would be the same length: ^GlG vs. ^UGG.

Rust, 241 226 214 182 149 129 bytes
use itertools::*;fn f(n:usize,e:Vec<[usize;2]>)->usize{(0..n).permutations(n).filter(|p|e.iter().all(|&[i,j]|p[i]<p[j])).count()}

Try it online!
Rust port of this C++ answer. -20 thanks to @att. Slightly less golfed
use itertools::*;
fn f(n:usize,e:Vec<[usize;2]>)->usize{
 (0..n).permutations(n).filter(|p|e.iter().all(|&[i,j]|p[i]<p[j])).count()
}

129 bytes

Rust, 607 bytes
Golfed version by @ceilingcat, greatly appreciated.
Try it online!
fn R()->Vec<i32>{let mut b=String::new();std::io::stdin().read_line(&mut b);b.trim().split(" ").map(|num|num.parse().expect("")).collect()}fn E(m:usize,N:&[i32],g:&[Vec<i32>],L:usize,D:&mut[i64],n:usize)->i64{if-1==D[m]{if m==L{D[m]=1}else{D[m]=0;for i in 0..n{if N[i]==0&&m&1<<i<1{let mut t=N.to_vec();for&v in&g[i]{t[v as usize]-=1}D[m]+=E(m|1<<i,&t,g,L,D,n)}}}}D[m]}fn main(){let f=R();let n=f[0]as usize;let(mut g,mut N,mut D)=(vec![vec![];n],vec![0;n],vec![-1;1<<n]);for _ in 0..f[1]{let I=R();let(u,v)=(I[0]-1,I[1]-1);g[u as usize].push(v);N[v as usize]+=1}println!("{}",E(0,&N,&g,(1<<n)-1,&mut D,n))}

Use the algorithm in @masked_huh's C++ code in the comment of this CodeForces post.
Ungolfed version. Attempt This Online!
use std::io;

fn read_ints() -> Vec<i32> {
    let mut buffer = String::new();
    io::stdin().read_line(&mut buffer).expect("Failed to read line");
    buffer.trim().split_whitespace()
          .map(|num| num.parse().expect("Failed to parse number"))
          .collect()
}

fn rec(mask: i64, ind: &[i32], g: &[Vec<i32>], all_visited: i64, dp: &mut [i64], n: usize) -> i64 {
    if dp[mask as usize] != -1 {
        return dp[mask as usize];
    }
    if mask == all_visited {
        dp[mask as usize] = 1;
        return 1;
    }

    let mut ans = 0;
    for i in 0..n {
        if ind[i] == 0 && (mask & (1 << i) == 0) {
            let mut temp = ind.to_vec();
            for &v in &g[i] {
                temp[v as usize] -= 1;
            }
            ans += rec(mask | (1 << i), &temp, g, all_visited, dp, n);
        }
    }

    dp[mask as usize] = ans;
    ans
}

fn main() {
    let first_line = read_ints();
    let (n, m) = (first_line[0] as usize, first_line[1]);

    let mut g: Vec<Vec<i32>> = vec![vec![]; n];
    let mut ind: Vec<i32> = vec![0; n];
    let mut dp: Vec<i64> = vec![-1; 1 << n];
    let all_visited: i64 = (1 << n) - 1;

    for _ in 0..m {
        let line = read_ints();
        let (mut u, mut v) = (line[0], line[1]);
        u -= 1;
        v -= 1;
        g[u as usize].push(v);
        ind[v as usize] += 1;
    }

    let ans = rec(0, &ind, &g, all_visited, &mut dp, n);

    println!("{}", ans);
}

JavaScript (Node.js), 74 bytes
f=(a,s=0,p)=>a.map(t=>s+=t&&!t.some(p=u=>a[u])&&f(a.map(u=>t!=u&&u)))|s+!p

Try it online!

a: Input array. For recurse reason, false means used
s: Sum to return
p: active if unused elements exist

C++ (gcc), 274 252 193 176 170 bytes
#import<regex>
int f(int n,int m,int*e,int*f){int V[n],c,d=n,i;for(;d--;)V[d]=d;do for(c=1,i=m;i--;)c*=V[e[i]]<V[f[i]];while(d-=c,std::next_permutation(V,V+n));return~d;}

Try it online!
This generates every permutation and filters out the invalid ones.
Slightly less golfed.
#import<regex>
int f(int n,int m,int*e,int*f){
 int V[n],c,d=n,i;
 for(;d--;)
  V[d]=d;
 do{
  c=1;
  for(i=m;i--;)
   c*=V[e[i]]<V[f[i]];
  d-=c;
 }while(std::next_permutation(V,V+n));
 return~d;
}

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Fourth grade math homework for the week: A most inefficient traveling salesman
My daughter had the following assignment for her math homework. Imagine six friends living on a line, named E, F, G, H, J and K. Their positions on the line are as indicated (not to scale) below:

Thus, F lives five units from E, and two units from G, and so forth.
Your assignment: craft a program that identifies a path that visits each friend exactly once with a total length of n units, taking the locations of the friends and n as inputs. It should report the path if it finds it (for example, for length 17 it might report "E,F,G,H,J,K", and it should exit gracefully if no solution exists. For what it's worth, I completed an ungolfed solution in Mathematica in 271 bytes. I suspect it's possible much more concisely than that.

This might be better as a program that takes inputs (ex. [0, 5, 7, 13, 16, 17] and 62) so that you can make sure it's not specifically hard-coded to this case.

@Doorknob, good point. I have adjusted the assignment accordingly.

I think @Doorknob 's idea was that you make the specification for the general case (position of friends may vary) and use the specific case as an example (to avoid answers hardcoded to the specific case). Maybe you agree with him, but it's not entirely clear from the current edit. Also, should the path found be exactly n units as specified by the user? Or the maximum possible? What was the intention?

Does the path start at any friend?

Can I define the format of the input and output strings? Is an input like "[0, 5, 7, 13, 16, 17], 62" and an output "(7, 16, 0, 17, 5, 13)" ok?

answering various questions above: (1) you can start at any friend. Given the six friends above counting reflected paths, there are 720 possible paths. (2) assume the locations of the friends and the target distance are provided at runtime. For every length where a solution is possible, at least two solutions are possible (because of reflection). You need to produce only one. If the requested length is impossible, exit gracefully.

@Geobits just sloppiness on my part. Corrected.

J, 54 bytes
Outputs one correct route. If no route exists it outputs nothing.
   f=.4 :'{.(x=+/|:2|@-/\"#.s A.y)#(s=.i.!6)A.''EFGHJK'''

   62 f 0 5 7 13 16 17
GJEKFH

52-byte code that outputs all routes (one per line):
f=.4 :'(x=+/|:2|@-/\"#.s A.y)#(s=.i.!6)A.''EFGHJK'''

38-byte code that outputs positions instead letters:
f=.4 :'p#~x=+/|:2|@-/\"#.p=.(i.!6)A.y'

I can't vet the code, but per your summary of it, this seems to be the shortest entry that does everything the problem requires.

Mathematica, 55 or 90 bytes
Mathematica you said? ;)
FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&

This is an anonymous function that first takes the positions of the friends (in any order), and then the target length. It returns Missing[NotFound], if no such path exists.
FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&[{0, 5, 7, 13, 16, 17}, 62]
(* {7, 16, 0, 17, 5, 13} *)

I can save four bytes if returning all valid paths is allowed (FirstCase -> Cases).
Returning an array of strings is a bit more cumbersome:
FromCharacterCode[68+#]&/@Ordering@FirstCase[Permutations@#,p_/;Tr@Abs@Differences@p==#2]&

Could you adjust so that it responds with the letters rather than just the locations?

@MichaelStern It's not really clear from the question how much should be hardcoded and how much should be part of the parameters? Should the input be something like a mapping from letters to positions?

Assume the letters are always in the order given in the number line above (E, F, G, H, J, K). The distances between them should be passed to the function as you do in your solution.

@MichaelStern I added a version that returns an array of strings. It supports any number of positions in the list, but after Z will continue with the next ASCII characters (not that you want to run my code for n > 20 anyway :D).

Python 2, 154 148 bytes
(or 118 bytes for the general solution)
This program accepts a line with a list and an integer like '[0, 5, 7, 13, 16, 17], n' on stdin and prints a path on the output of length n or nothing if impossible.
# echo "[0, 5, 7, 13, 16, 17], 62" | python soln.py
['G', 'J', 'E', 'K', 'F', 'H']

It is challenging to write small programs in Python that require permutations. That import and use is very costly.
from itertools import*
a,c=input()
for b in permutations(a):
 if sum(abs(p-q)for p,q in zip(b[1:],b))==c:print['EFGHJK'[a.index(n)]for n in b];break

The source for the OP requirement before the minifier:
from itertools import*

puzzle, goal = input()
for option in permutations(puzzle):
    if sum(abs(p-q) for p,q in zip(option[1:], option)) == goal :
        print ['EFGHJK'[puzzle.index(n)] for n in option];
        break

The general solution (not minified):
from itertools import*

puzzle, goal = input()
for option in permutations(puzzle):
    if sum(abs(p-q) for p,q in zip(option[1:], option)) == goal :
        print option;
        break

Due to the simple algorithm and vast number of combinations, execution for more than 20 initial positions will be very slow.

You could save a few bytes with from itertools import*. Also, Python 3 might be shorter with input() and *a,c=map(...) if it can work with the rest of your program.

Thanks for the import tip. I am resisting a py3 install and conversion of my code base. I am waiting until every 3rd party module I use is available and stable under py3 (I use many old and obscure ones).

Could you adjust so that it responds with the letters rather than just the locations?

chr(a.index(n)+69)?

Nice optimisation. But I think @MichaelStern really wants to see the 'EFGHJK', and it was easy enough so I wrote the code that way.

J (48 or 65)
I hypothesize that this can be golfed a hell of a lot more. Feel free to use this as a jumping off point to golf it further
]A.~[:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#))))

Or with letters:
([:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#)))))A.[:(a.{~65+[:i.#)]

What it does:
   62 (]A.~[:I.(=([:([:+/}:([:|-)}.)"1(A.~([:i.[:!#))))) 0 5 7 13 16 17
 7 16  0 17  5 13
 7 16  5 17  0 13
 7 17  0 16  5 13
 7 17  5 16  0 13
13  0 16  5 17  7
13  0 17  5 16  7
13  5 16  0 17  7
13  5 17  0 16  7

(I hope this I/O format is okay...)
How it does it:
(A.~([:i.[:!#))

Generates all permutations of the input
([:+/}:([:|-)}.)"1

Calculates the distance
(]A.~[: I. (= ([:distance perms)))

Sees which results are the same as the input, and re-generates those permutations (I suspect some characters can be shaved off here)
With letters:
((a.{~65+[:i.#))

Create a list of the first n letters, where n is the length of the input list
indices A. [: letters ]

does the same as above

Can you adjust it to report the answer in terms of letters?

@MichaelStern I could, but that would add quite a bit to the character count (J is terrible with strings). I'll try it now, to see what the damage might be.

Octave, 73
function r=t(l,d,s)r=perms(l)(find(sum(abs(diff(perms(d)')))==s,1),:);end

There's really no un-golfing this, so let me try to explain... from inside to out, we permute all the distances, then for each permutation, we take the differences between houses, take the absolute value as a distance, add them up, find the index of the first permutation with the desired distance, and permute the letters and find that particular permutation of letters.
octave:15> t(["E" "F" "G" "H" "J" "K"],[0 5 7 13 16 17],62)
ans = HEJFKG

which is 13-0-16-5-17-7 => 13+16+11+12+10=62.
octave:16> t(["E" "F" "G" "H" "J" "K"],[0 5 7 13 16 17],2)
ans =

(blank for impossible inputs)

I don't know what the deal is, but perms() in Octave 3.6.2 on ideone.com is having issues with the vector of strings.

Interesting. I have 3.8.1 locally.

Matlab (86)
x=input('');X=perms(1:6);disp(char(X(find(sum(abs(diff(x(X).')))==input(''),1),:)+64))

Example in which a solution exists:
>> x=input('');X=perms(1:6);disp(char(X(find(sum(abs(diff(x(X).')))==input(''),1),:)+64))
[0, 5, 7, 13, 16, 17]
62
DBFAEC
>>

Example in which a solution doesn't exist:
>> x=input('');X=perms(1:6);disp(char(X(find(sum(abs(diff(x(X).')))==input(''),1),:)+64))
[0, 5, 7, 13, 16, 17]
100
>>

Matlab (62)
If the output format can be relaxed by producing positions instead of letters, and producing an empty matrix if no solution exists:
X=perms(input(''));X(find(sum(abs(diff(X.')))==input(''),1),:)

Example in which a solution exists:
>> X=perms(input(''));X(find(sum(abs(diff(X.')))==input(''),1),:)
[0, 5, 7, 13, 16, 17]
62
ans =
    13     5    17     0    16     7

Example in which a solution doesn't exist:
>> X=perms(input(''));X(find(sum(abs(diff(X.')))==input(''),1),:)
[0, 5, 7, 13, 16, 17]
62
ans =
   Empty matrix: 0-by-6

Matlab (54)
If it's acceptable for the program to provide all valid paths:
X=perms(input(''));X(sum(abs(diff(X.')))==input(''),:)

Example in which a solution exists:
>> X=perms(input(''));X(sum(abs(diff(X.')))==input(''),:)
[0, 5, 7, 13, 16, 17]
62
ans =
    13     5    17     0    16     7
    13     5    16     0    17     7
    13     0    17     5    16     7
    13     0    16     5    17     7
     7    16     5    17     0    13
     7    16     0    17     5    13
     7    17     5    16     0    13
     7    17     0    16     5    13

Haskell, 109 bytes
import Data.List
a%b=abs$snd a-snd b
n#l=[map(fst)p|p<-permutations(zip['E'..]l),n==sum(zipWith(%)p(tail p))]

Usage example: 17 # [0, 5, 7, 13, 16, 17] which outputs all valid paths, i.e. ["EFGHIJ","JIHGFE"]. If there's no valid path, the empty list [] is returned.
The list of letters includes I (hope that's fine).
How it works: make a list of (name, position) pairs, permute and take those where the path length equals n and remove the position part.

Python + golfing-shortcuts, 123 bytes
A port of Logic Night's answer.
from s import*
def F(A,C):
 for B in Im(A):
  if s(abs(P-Q)for P,Q in z(B[1:],B))==C:p(['EFGHJK'[li(A,N)]for N in B]);break


text:
LCD Numbers - get my lost 190 bytes back
Years ago I read the "Best of Ruby Quiz" book by James Edward Gray II (also available online by now). For problem 2 in the book (which is problem 14 on his original RubyQuiz site), he mentions a golfed solution in under 300 bytes, even though he is not a big fan of golfing.
So I did wonder if I could beat that and maybe even find a solution of under 200 bytes. So once I beat the current best solution of 256 bytes I sent him a 210 bytes solution. Shortly thereafter I found a solution around 190 bytes, but didn't bother to send him that. But over the years I lost these 190 bytes somehow and couldn't find a backup anymore. In any case I know that a under 200 byte solution is possible in ruby (at least with ruby 1.8.7) so I hope some of you will be able to recreate it or maybe even find something better.
Even though I'm mostly interested in ruby solution other language solutions are of course also welcome!
The Challenge
Create a program which is called on the commandline and takes a non-negative integer as an argument and an optional -s argument followed by a positive integer. The default value for -s is 2.
The output should be the input argument in LCD-style adjusted by size by the -s parameter.
For example if the program is called like this
$ lcd.rb 012345

the correct display is this:
 --        --   --        --
|  |    |    |    | |  | |
|  |    |    |    | |  | |
           --   --   --   --
|  |    | |       |    |    |
|  |    | |       |    |    |
 --        --   --        --

And for this:
$ lcd.rb -s 1 6789

your program should print this:
 -   -   -   -
|     | | | | |
 -       -   -
| |   | | |   |
 -       -   -

Note the single column of space between digits in both examples. For other values of -s, simply lengthen the - and | bars.
Of course because this is code golf I have to be more specific than the original quiz about some rules:

It's ok if your program requires to be explicitly called by an interpreter (e.g. ruby lcd.rb 1234), so a shebang line is not required
It's not required to handle other than the above specified arguments in a sane way (e.g. negative numbers, no space between -s and the following number, extra arguments, or no arguments at all)
It should in principle be able to handle any number of digits and any positive size for the scale parameter -s. So only external factors like the maximum command line length of the shell should limit these parameters.
Non-printable characters are allowed, but your program must consist of the 128 characters of the ASCII set.

Have fun!

Thanks for the reference. But I can't see a ruby solution under <200 bytes there, so my question is still open. And doing the parameter parsing is an important aspect of the problem.

This should have tag [tag:Ruby].

I thought about that but thought it might discourage other language submissions. But I added it now anyway, because of my ruby specific question. But I still hope people don't think answers should be limited to ruby.

I'm sorry, but I think the input parsing is not a sufficiently substantial difference to not make this a duplicate. The core challenge is encoding the digits in a scalable way, and that is the same in both challenges. Since you're specifically looking for a short Ruby answer, I'd say the way to go is to offer a bounty on the old question instead of asking it again. And lastly, I think you had it right, the Ruby tag is misplaced here, as it suggests that you're looking for Ruby answers only.

@MartinBüttner the biggest difference isn't the input parsing, it's that the other one is a popularity contest whereas this is codegolf. However, bounty awarders get to decide their own criteria, distinct from the OP's, so I guess your suggestion is right.

@MartinBüttner: The output suggested in the other problem is different from my specification. Also it doesn't even seem to be enforced, since the answers use quite different styles. I'm sorry but I can not possible see how giving a bounty to the other question can answer my question. And as steveverrill mentions it's not even a codegolf contest.

@steveverrill You've got reopen-vote privileges. David, true, the format is slightly different, but I don't think adapting the format will make a big difference in terms of code size. And I agree that our duplicate policies are a bit harsh sometimes (and I'd personally prefer them to be relaxed a bit). Feel free to join us in chat if you want to discuss this. In the meantime I don't think the other being a popcon should stop you from putting up a bounty for short code. It's just one way to gather popularity.

David, there's nothing in the other question that says you must follow the OP's spec, and a PopCon encourages people to deviate. That type of question is often closed as an art contest (and so off topic) these days. Your question is a proper rigidly specified code golf, so I've decided to cast a reopen vote. One comment: I hate that you want input accepted in any order, it has nothing to do with meat of the challenge. @MartinBüttner I have the privilege but I must decide how to use it. David's "not enforced" comment convinced me to check: The answers to the previous question dont work here.

@steveverill: Ok, I removed the "any order" requirement. I like answers to be valid solutions for the original ruby quiz, but it doesn't specifcy this requirement explicitely, even though the sample answers in the book fulfill it.