text:
Cofactor Matrices
The cofactor matrix is the transpose of the Adjugate Matrix. The elements of this matrix are the cofactors of the original matrix.
The cofactor  (i.e. the element of the cofactor matrix at row i and column j) is the determinant of the submatrix formed by deleting the ith row and jth column from the original matrix, multiplied by (-1)^(i+j).
For example, for the matrix

The element of the cofactor matrix at row 1 and column 2 is:

You can find info on what the determinant of a matrix is and how to calculate them here.
Challenge
Your goal is to output the cofactor matrix of an input matrix.
Note: Built-ins that evaluate cofactor matrices, or adjugate matrices, or determinants or anything similar are allowed.
Input
The matrix may be inputed as a command line argument, as a function parameter, in STDIN or in any way that is most appropriate for the language you use.
The matrix will be formatted as a list of lists, each sublist corresponding to one row, which contains factors ordered from left to right. Rows are ordered from top to bottom in the list.
For example, the matrix
a b
c d

will be represented by [[a,b],[c,d]].
You may replace the square brackets and commas with something else if it fits your language and is sensible (e.g. ((a;b);(c;d)))
Matrices will only contain integers (which can be negative).
Matrices will always be square (i.e. same number of rows and columns).
You may assume that the input will always be correct (i.e. no formatting problem, nothing other than integers, no empty matrix).
Output
The resulting cofactor matrix may be outputed to STDOUT, returned from a function, written to a file, or anything similar that naturally suits the language you use.
The cofactor matrix must be formatted in the exact same way the input matrices are given, e.g. [[d,-c],[-b,a]]. If you read a string, then you must return/output a string in which the matrix is formatted exactly like in the input. If you use something like e.g. a list of lists as input, then you must return a list of lists too.
Test cases

Input: [[1]]

Output: [[1]]

Input: [[1,2],[3,4]]

Output: [[4,-3],[-2,1]]

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

Output: [[-8,-5,4],[18,12,-6],[-4,-1,2]]

Input: [[3,-2,7,5,0],[1,-1,42,12,-10],[7,7,7,7,7],[1,2,3,4,5],[-3,14,-1,5,-9]]

Output:
[[9044,-13580,-9709,23982,-9737],[-1981,1330,3689,-3444,406],[14727,7113,2715,-9792,414],[-28448,-2674,-707,16989,14840],[-2149,2569,-2380,5649,-3689]]

Scoring
This is code-golf so the shortest answer in bytes wins.

I am not sure how to interpret the cofactor matrix must be formatted in the exact same way the input matrices are given for function submissions that get input from arguments and return a value. Do we read/return actual matrices or their string representations?

In short: if you read a string, then you must return/output a string in which the matrix is formatted exactly like in the input. If you use something like e.g. a list of lists, then you must return a list of lists too.

Does a 1x1 matrix really have a cofactor matrix?

Also your penultimate test case seems to be the adjugate matrix (the transpose of what it should be), unless I'm mistaken.

@ICanHazHats Correct, I fixed it, thanks.

J, 29 bytes
3 :'<.0.5+|:(-/ .**%.)1e_9+y'

Same epsilon/inverse/determinant trick. From right to left:

1e_9+ adds an epsilon,
(-/ .**%.) is determinant (-/ .*) times inverse (%.),
|: transposes,
<.0.5+ rounds.

Matlab, 42 33 bytes
Using an anonymous function:
@(A)round(inv(A+eps)'*det(A+eps))

Input and output are matrices (2D numeric arrays).
eps is added in case the matrix is singular. It is "removed" using round (the true result is guaranteed to be an integer).
Example:
>> @(A)round(inv(A+eps)'*det(A+eps))
ans =
    @(A)round(inv(A+eps)'*det(A+eps))
>> ans([-3,2,-5; -1,0,-2; 3,-4,1])
ans =
-8    -5     4
18    12    -6
-4    -1     2

Example with singular matrix:
>> @(A)round(inv(A+eps)'*det(A+eps))
ans =
    @(A)round(inv(A+eps)*det(A+eps)')
>> ans([1,0 ; 0,0])
ans =
     0     0
     0     1

Or try it online in Octave.

Matlab definitely feels like "the right tool for the job" in this challenge

Wait until someone posts a Mathematica answer... it probably has a builtin for this :-)

However I do have a concern that I haven't talked about in the challenge: this answer assumes that the input matrix is invertible. Using your code on say [1,0 ; 0,0] gives an error when it should output [0,0 ; 0,1]

Hm. You're right. I hadn't thought of that

Corrected! With a dirty trick, I admit

Since you are returning from a function, I don't think you should need mat2str: "resulting cofactor matrix may be... returned from a function"

@FryAmTheEggman Thanks! But "The cofactor matrix must be formatted in the exact same way the input matrices are given". That's why I think I need mat2str

Can you explain a bit more to non-Matlab people like me what the eps and fix commands do? Sounds like you tell Matlab to add a small epsilon to the matrix and fix magically removes its effects afterwards, but is there a guarantee that it always yields exactly the correct cofactor matrix?

@Fatalize Yes, it's that. eps is about 1e-16. So it makes the matrix non-singular (but very ill-conditioned). The result is not exactly integer; so fix (round towards zero) fixes that. This works provided the error doesn't exceed .5. I'm afraid there are no guarantees. For very large integers it might fail. I said it was a dirty trick :-P

@Fatalize for clarity, could you say whether mat2str is needed here? To me it feels like since this is a function, the input actually is the unformatted matrix. Like if you try f=... then do f(f(...)) this won't work, but removing mat2str makes that work fine.

@FryAmTheEggman Now I see what you mean. Yes, without mat2str, the function output could be used as a new input. Let's wait for @Fatalize's clarification

WHY NOT MATL??? PS: The ' is in the wrong position, I think.

@flawr I didn't include much of linear algebra in MATL :-) Thanks for the correction!

Mathematica, 27 35 bytes
Thread[Det[#+x]Inverse[#+x]]/.x->0&

Does this work for non-invertible matrices, e.g. [[1,0],[0,0]]?

@FryAmTheEggman That doesn't seem to work.

R, 121 94 bytes
function(A)t(outer(1:(n=NROW(A)),1:n,Vectorize(function(i,j)(-1)^(i+j)*det(A[-i,-j,drop=F]))))

This is an absurdly long function that accepts an object of class matrix and returns another such object. To call it, assign it to a variable.
Ungolfed:
cofactor <- function(A) {
    # Get the number of rows (and columns, since A is guaranteed to
    # be square) of the input matrix A
    n <- NROW(A)

    # Define a function that accepts two indices i,j and returns the
    # i,j cofactor
    C <- function(i, j) {
        # Since R loves to drop things into lower dimensions whenever
        # possible, ensure that the minor obtained by column deletion
        # is still a matrix object by adding the drop = FALSE option
        a <- A[-i, -j, drop = FALSE]

        (-1)^(i+j) * det(a)
    }

    # Obtain the adjugate matrix by vectorizing the function C over
    # the indices of A
    adj <- outer(1:n, 1:n, Vectorize(C))

    # Transpose to obtain the cofactor matrix
    t(adj)
}

80 bytes using mapply instead of outer and Vectorize

GAP, 246 Bytes
You can tell this is good coding by the triple nested for-loops.
It's pretty straightforward. GAP doesn't really have the same tools to deal with matrices that other math oriented languages do. The only thing really used here is the built in determinant operator.
f:=function(M)local A,B,i,j,v;A:=StructuralCopy(M);if not Size(M)=1 then for i in [1..Size(M)] do for j in [1..Size(M)] do B:=StructuralCopy(M);for v in B do Remove(v,j);od;Remove(B,i);A[i][j]:= (-1)^(i+j)*DeterminantMat(B);od;od;fi;Print(A);end;

ungolfed:
f:=function(M)
    local A,B,i,j,v;
    A:=StructuralCopy(M);
    if not Size(M)=1 then
        for i in [1..Size(M)] do
            for j in [1..Size(M)] do
                B:=StructuralCopy(M);
                for v in B do
                    Remove(v,j);
                od;
                Remove(B,i);
                 A[i][j]:= (-1)^(i+j)*DeterminantMat(B);
            od;
        od;
    fi;
    Print(A);
end;

Verbosity v2, 196 bytes
IncludeTypePackage<Matrix>
IncludeTypePackage<OutputSystem>
print=OutputSystem:NewOutput<DEFAULT>
input=Matrix:Adjugate<ARGV0>
input=Matrix:Transpose<input>
OutputSystem:DisplayAsText<print;input>

Try it online!
NB: Doesn't currently work on TIO, awaiting a pull. Should work offline
Takes input in the form ((a b)(c d)) to represent
$$
\bigg[
\begin{matrix}
a \: b \\
c \: d
\end{matrix}
\bigg]
$$
Despite having a builtin for the adjugate, Verbosity's verbosity still cripples it. Fairly basic how it works, just transposes the adjugate of the input.


text:
Robot optimization
Your task is to program a robot so that it reaches the hole in the ground on each of the maps within reasonable time. If the robot reaches the hole, it falls down into it and thus victory is assured, even if the program never stops running.
Since the robot has to be programmed by manually punching in ones and zeroes, you want to solve the problems using as few commands as possible. Labels are translated to positions by the assembler and integrated into the gotoblocked and call commands, so the programmer never has to punch them into the robot. Therefore, they do not count towards the score. If the robot tries to move into a wall or off the map, nothing happens.
The language consists of these statements:

forward move the robot forward one step
right rotate 90 degrees clockwise
left rotate 90 degrees counter-clockwise
for X {A1 A2 .. An} repeat commands A1, A2, ..., An X times
call X call a subroutine, beginning at label X
return return from the subroutine
gotoblocked X jump to label X if there is a wall immediately in front of the robot
mylabel: a label used by call and/or gotoblocked. Loops may not contain any labels. Labels may only contain letters.

The input files consist of:
testcase_name
N M
and then an N by M grid of:

. empty square
# blocked square
M the hole in the ground that we want to end up in
< > ^ v starting position of the robot, directed left, right, up or down, respectively.

The maps can be found at http://progolymp.se/uploads/robot.zip
Your task is to solve all the maps.
Validation:
The code you submit will be executed against all the test cases, starting at the label testcasename for each map. Follow the formatting in the example program.
Scoring:
The score is the number of statements (excluding labels) in the whole file, i.e. the code used to solve all testcases. Code reuse between testcases is ok.
Example program with starting points for testcases robot_cross and robot_maze (that solves neither):
walkandreturn:
  for 100 {
    forward
  }
robotmaze:
  gotoblocked done
  right
  right
  for 100 {
    for 3 {
      forward
    }
  }
done:
  return

robotcross:
  for 100 {
    call walkandreturn
    right
  }

Automated judge can be found at http://progolymp.se/uploads/robot.jar.
To test a file against the testcase robot_ew_manuell, add this to the end of your program file:
main:
  call robotewmanuell

The judge starts execution at the label main, but we want it to start at robotmaze instead. This causes the judge to jump to where it should start, and saves me from having to write a new judge.
The actual judge can then be run like this:
java -cp robot.jar parser.Runner robot_ew_manuell.in < my_solution.ans
Help wanted
If you have a good place to mirror the files, or a way to post them on the site, please do.
This problem is based on the final problem of the 2016 online qualifier of Programmeringsolympiaden. https://po.kattis.com/problems/robotoptimering The original problem was authored by Johan Sannemo and Anton Grensjö. CC BY-SA licensed, just like Stack Exchange.

Pretty sure this is just going to involve implementing A* (or similar) in your custom robolang.

@Draco18s How would you implement A* in this language? By using the robot to simulate a turing machine? Keep in mind that the challenge is to use as few statements as possible. Writing the commands one-by-one to take the robot from start to finish would probably use less statements.

Ah, there are specific test cases, no general case solution needed.  Never mind then.

You could write a single solution that handles all the test cases if you want to.

Yes, but it would handle only those cases.  It wouldn't handle every possible case.  That was my misunderstanding

Does the interpreter for this language implement comments?

Or are non-keywords ignored?

You can use labels for comments, without ever jumping to them. Non-keywords shouldn't be in the code.

I know this is an old question, but I stumbled upon it and have a question: Can labels be nested inside for-loops, and what happens if those labels are jumped to?

@R.M You're allowed to jump to labels in the currently running loop, in which case the loop counter doesn't change, or to a label in any outer loop if you've nested them, since you're technically in that loop as well.

So you can jump outside a loop, but can't jump inside a loop, did I understand correctly?

@R.M Exactly. You can jump around within the same loop iteration, or break out of any number of loops.

source: Stack Exchange

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

sort: votes


text:
Playing Billiards
In this code golf, you will have to determine the direction of the shortest shot that hits exactly n cushions before falling into a pocket.
The billiard table is a 6 pocket pool table with the following characteristics:

Dimensions are variable (a x b)
No friction : the ball will roll forever until it falls into a pocket
Pockets and ball sizes are almost zero. This means that the ball will fall in the pocket only if they have same position.
The ball is placed at the bottom left hole at the beginning (but doesn't fall in it)

Create a full program or function that takes the dimensions (a,b) of the table and a the number of cushions to hit n as input and returns the angle in degrees of the shortest path hitting exactly n cushions before falling into a pocket.

a > 0
b > 0
0 <= n < 10000000
0 < alpha < 90 (in degrees) precision : at least 10^-6

examples :
with a = 2, b = 1, n = 1
there are three possible paths : (1) (2) (3) on the following figure.
the number (1) is the shortest so the output should be atan(2) = 63.43494882292201 degrees

The solution for a = 2, b = 1, n = 4 is atan(4/3) = 53.13010235415598 degrees

test samples :
a = 2,    b = 1,    n = 1,       -> alpha = 63.43494882292201
a = 2,    b = 1,    n = 2,       -> alpha = 71.56505117707799
a = 2,    b = 1,    n = 3,       -> alpha = 75.96375653207353
a = 2,    b = 1,    n = 4,       -> alpha = 53.13010235415598
a = 2,    b = 1,    n = 5,       -> alpha = 59.03624346792648
a = 2,    b = 1,    n = 6,       -> alpha = 81.86989764584403
a = 4.76, b = 3.64, n = 27,      -> alpha = 48.503531644784466
a = 2,    b = 1,    n = 6,       -> alpha = 81.86989764584403
a = 8,    b = 3,    n = 33,      -> alpha = 73.24425107080101
a = 43,   b = 21,   n = 10005,   -> alpha = 63.97789961246943

This is code/billiard golf : shortest code wins!

Does the ball have to hit exactly n cushions, or at least n cushions?

@PeterTaylor exactly n cushions

isn´t the shortest path always back and forth between the left side top and bottom and then into one of the middle holes?

no, look at the 2 1 4 example. This path is sqrt(25) = 5 long whereas your solution is sqrt(26)

Python 2.7, 352 344 281 bytes
from math import*
def l(a,b,n):
 a*=1.;b*=1.
 r=set()
 for i in range(1,n+3):
  t=[]
  for k in range(1,i):
   for h in[0,.5]:
    x=(i-k-h)
    if 1-(x/k in r):r.add(x/k);t+=(x*a,k*b),
 d=(a*n+1)**2+(b*n+1)**2
 for x,y in t:
  if x*x+y*y<d:d=x*x+y*y;o=degrees(atan(y/x))
 return o

-16 bytes thanks to @Dschoni

Explanation: instead calculating the cushions hits, I'm adding n tables and taking the new holes as valid :

Black border/holes is the original, green border/holes is the valid for n=1, red border/holes is the valid for n=2 and so on.
Then I remove the invalid holes (e.g. the blue arrow for n=1). I'll have a list of valid holes and their coordinates, then I calculate their distance from initial point, and then the angle of the smaller distance.

Notes:

a=4.76, b=3.64, n=27 - give 52.66286, trying to figure out why fixed, and saved 8 bytes in the process =D

a=43, b=21, n=10005 - takes ~80 seconds (but gives the right angle)
readable version:
from math import *
def bill(a,b,n):
    a=float(a)
    b=float(b)
    ratios = set()
    for i in range(0,n+2): # Create the new boards
        outter = []
        j=i+1
        for k in range(1,j): # Calculate the new holes for each board
            #y=k
            for hole_offset in [0,0.5]:
                x=(j-k-hole_offset)
                if (x/k) not in ratios:
                    ratios.add(x/k)
                    outter.append((x*a,k*b))
    min_dist = (a*n+1)**2+(b*n+1)**2
    for x,y in outter:
        if x*x+y*y<min_dist:
            min_dist = x*x+y*y
            min_alpha=degrees(atan(y/x))
    return min_alpha

You can save a byte by removing the space in  : degrees

I have no idea how your answer works (mathwise) but I think you can gain 1 byte by removing the space after the colon. :) (What @MorganThrapp said)

This path is valid, but it's not the shortest in all cases, for example with 2 1 4..

This also assumes that b < a. That could easily fixed by getting the minimum/maximum of a and b though.

fixed  ( sorta )

Looks better now! a=4.76, b=3.64, n=27 is designed to test invalid path like your blue one. This path falls in a middle pocket after 13 hits. It might be due to floatting point precision. I would suggest you calculate paths ratios as a couple of integer (y=2k,x=2j-2k-2hole_offset) and use only a,b to calculate angles and length.

some hints... instead of explicit type conversion, use the inbuilt implicit when doing multiplication: a=1.0*a (saves 6 byte). the not in line can be made to: if -(x/y in r) , can be definitely golfed further by using lambdas and for loop bracketing etc...

Probably also shouldn't use b inside b()

Wow, I found out so much about python by playing with your example, that I had to come back again. list.append((a,b)) can be written as list+=(a,b), (With coma)

Haskell, 133 117 bytes
This is my implementation:
With a 2x1 table, a path will hit exactly n cushions before going into a pocket if:
(x-1)/2 + (y-1) == n and x,y are mutually primes.
where x,y are the distance of the ball over horizontal/vertical axes.
Paths are the same with arbitrary table size, so we just have to update lengths and angles with (a,b) and keep the shortest.
Path length is sqrt((x*a/2)^2+(y*b)^2) and angle is atan((y*b)/(x*a/2))
z=toEnum
f a b n=minimum[[z x^2+r^2,180/pi*atan(r/z x)]|x<-[1..2*n+2],y<-[n+1-div(x-1)2],r<-[2*b/a*z y],gcd x y<2]!!1

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


text:
You're on a 8 day streak!
Duolingo, the language learning app, has a lot of things going for it, but there is one major issue that drives me crazy. It tells me how many days in a row I've used the app with a message like You're on a 7 day streak! Setting aside hyphenation and whether the number should be spelled out, this works fine for most numbers, but is indisputably wrong when it says You're on a 8 day streak! I'm not using it to learn English but this is still unfortunate behavior for a language app.
You're going to help out the Duolingo team by writing a complete program or function that figures out whether a given number should be preceded by a or an. A number is preceded by a if its pronunciation in spoken English begins with a consonant or semivowel sound, and preceded by an if its pronunciation begins with a vowel sound. Thus the only numbers preceded by an are those whose pronunciation begins with eight, eleven, eighteen, or eighty.
Presumably the Duolingo dev team left this bug in because they ran out of space for more source code in the app, so you need to make this code as short as possible in the hopes they can squeeze it in.
Your code must take an integer from 0 to 2,147,483,647 and output a or an. A trailing newline is optional. For the purposes of this challenge, 1863 is read as one thousand eight hundred and sixty-three, not eighteen hundred and sixty-three.
Test cases:
0 → a
8 → an
11 → an
18 → an
84 → an
110 → a
843 → an
1111 → a
1863 → a
8192 → an
11000 → an
18000 → an
110000 → a
180000 → a
1141592 → a
1897932 → a
11234567 → an
18675309 → an

I thought this would be really easy... then I noticed 218 uses the 8's letter, not the 2's.

Is this endorsed by Duolingo? If not, you should get them to pay us for improving the language on a language learning site.

Is 1100 (an) eleven hundred or (a) one thousand and one hundred?

Bilbo would disagree with some of your test cases. :)

@user3819867: Wasn't it, it has to be the word's first non silent letter the article is refering to is an a, e, i, o or u so it is an "an"? This confuses me, why it isn't in that case an one thousand and one hundred? is the "one" not considered to be part of the number? would be strange in my eyes too. Or did I just miss something when we had this topic in school? :x

@Zaibis: "one" here is pronounced like "wun", which has a consonant sound. Hence, "a one thousand and one hundred day streak".

@El'endiaStarman: oh yeah.... you are right. I never realized that. I had to speak out loud 3 times "one" and "wun" to notice that its actually some thing kinda close to w but definetly not an o.... really never realized. ok now its clear.

They probably left this bug because they thought no one would reach a 8 day streak.

@user3819867 Just like one thousand eight hundred, we're treating it as one thousand one hundred (see the eighth test case.)

Wow, that is just sad, an app for teaching language and it has a grammatical error. Good catch @Luke.

https://www.duolingo.com/comment/12400979. Okay, I posted on their forums, they may fix it if it gets noticed.

@AshwinGupta Here you go! ♦ A hard earned lingot.

"Thus the only numbers preceded by an are those whose pronunciation begins with eight, eleven, eighteen, or eighty." You just made Undecillion cry... I hope you're happy

@PandaLion98: an 8 day streak.

You do know how long we have to wait to get a 2,147,483,647-day streak, right?  I'll be back in 5.8 million years to see how we're getting on...

Pyth, 23 bytes
<>n\8hz}hjsz^T3,hT18"an

This selects how many letters to slice off the end of "an" by checking whether the first letter is not an 8 and that the first digit of the number when considered in base 1000 is neither 11 nor 18. The resulting boolean is the number of characters to slice of the end.

Very creative. Also, terrifying.

Python 2, 60 bytes
lambda n:'a'+'n'[:`n`[0]=='8'or`n`[:2]in len(`n`)%3/2*'118']

An anonymous function. Adds an n if either:

The first digit is 8
The first two digits are 11 or 18, and the length is 2 modulo 3.

I know this is a super old question, but I think `n`>='8' saves three bytes.

@Lynn Won't that mess up nines though?

Oh, of course! I was fooled by the test suite :)

GNU Sed, 32
Score includes +1 for -E option to sed.
s/^8.*|^1[18](...)*$/an/
t
ca
:

Try it online.

Remove groups of 3 digits from the end of each number until there is only 1 to 3 digits left
Match any number starting with 8 or exactly 11 or 18 and change to an
Change all other numbers to a

Thanks to @MartinBüttner for his retina approach that saved 10 bytes.

Shell + bsd-games, 30
number -l|sed '/^e/{can
q};ca'

Input read from STDIN.
number converts a decimal string into words.  It is then a simple matter to decide whether or not the result begins with e.

+1 for using bsd-games, I didn't actually think they'd ever be useful :)

@ASCIIThenANSI yep, bsd-games are useful here and there :)

Retina, 27 bytes
This isn't very different from DigitalTrauma's Retina answer, but they insisted I post this myself.
^8.*|^1[18](...)*$
an
\d+
a

Try it online.
The first regex replaces all relevant numbers with an, and the second replaces all remaining numbers with a. This works for the same bytes:
^8.*|^1[18](...)*$
n
^\d*
a

+1 this is almost the same level of abuse of regex as primality testing :)

And the good thing is, Duolingo is actually written in Retina so it should be a breeze to integrate this. Or wait, what language was it?

@ceasedtoturncounterclockwis I'm being told it's actually written in Hexagony, but they wrote a Retina-to-Hexagony transpiler, so this shouldn't be an issue.

C++, 101
This is my challenge, so this isn't meant to be a competitive answer. Just wanted to see how short I could get it in C++. String operations are just too verbose so this is done with math. I feel like there must be a way to get that condition smaller but I can't quite figure it out.
const char*f(int i){int n=0,d=0;for(;i;(!(d++%3)&(i==18|i==11))|i==8?n=1:0,i/=10);return n?"an":"a";}

Mathematica, 53 bytes
If[#~IntegerName~"Words"~StringStartsQ~"e","an","a"]&

A solution using string processing would actually end up being longer.

JavaScript (ES6) 70 61 46 38 bytes
n=>/^8|^1[18](...)*$/.test(n)?'an':'a'

Community wiki because the current solution is so different than my original.  Thanks everyone!
Demo: http://www.es6fiddle.net/iio40yep/

I'm missing the reason for eval

eval returns the result of the last expression.  I could use a multi-line function and an explicit return, but that's 1 more byte unfortunately.

that makes sense. Thanks for explaining.

It can be done in 64 bytes if you make the function body a single expression via comma operator: n=>(s=''+n,s[0]==8||(/^11|^18/.test(s)&&s.length%3==2)?'an':'a')

Also, a byte can be shaved of the regex: /^1[18]/

@Pavlo Very nice, I forgot about single expressions after discovering the eval trick!  I knew there had to be a better regular expression as well, but I couldn't figure anything out that was shorter. Thank you!

@ScottKaye also, since && has higher precedence than || you can skip inner parenthesis: n=>(s=''+n,s[0]==8||/^1[18]/.test(s)&&s.length%3==2?'an':'a')

@Pavlo Sweet, updated again!  Learning lots, thank you very much :)

Can't you just do n=>(n+='')[0]==8||/^1[18]/.test(n)&&n.length%3==2?'an':'a'? It seems to work. (Test: http://www.es6fiddle.net/iie8gis6/)

How about n=>/^8|^1[18]/.test(n+='')&&n.length%3==2?'an':'a'? Seems to work fine. Try it on http://www.es6fiddle.net/iie8oauz/. The code is 50 bytes long.

@IsmaelMiguel the first one works (good job!), the second one fails: http://www.es6fiddle.net/iiegbo0r/ (because if the number start with 8 it must be 'an', no matter the length).

@Pavlo Here is a new version, that passes all the tests: n=>/^8|^(?=1[18])..((\d){3})*$/.test(n)?'an':'a' (http://www.es6fiddle.net/iiehbub9/). It has -2 bytes (48 bytes total).

URGH! Forgot to shave 2 bytes! Here is the final one: n=>/^8|^(?=1[18])..(\d{3})*$/.test(n)?'an':'a' (http://www.es6fiddle.net/iiehl1ex/). It is 46 bytes long.

@IsmaelMiguel You guys are crazy, I don't even understand this code anymore, nice!  Community wiki!

@ScottKaye The code is very simple: It checks if it starts with 8, if it starts with 1[18] and if the length of numbers is 2 * (3n). Basically, it is your entire code, but within a regular expression.

PostScript, 119 113 characters
10 string cvs dup 0 get 56 eq exch dup length 3 mod 2 eq{0 2 getinterval dup(11)eq exch(18)eq or or}{pop}ifelse

With test code:
/An
{
    10 string cvs dup 0 get 56 eq exch dup length 3 mod 2 eq{0 2 getinterval dup(11)eq exch(18)eq or or}{pop}ifelse
} def

/ShouldBeFalse [ 0 110 1111 1863 110000 180000 1141592 1897932 ] def
/ShouldBeTrue [ 8 11 18 84 843 8192 11000 18000 11234567 18675309 ] def

() = (ShouldBeFalse) = ShouldBeFalse {An =} forall
() = (ShouldBeTrue)  = ShouldBeTrue  {An =} forall

Seriously, 43 40 bytes
9⌐9τk,;;$l3@\3*╤@\(íub)$#p'8=)XkΣ'n*'a+

The strategy here is to only look at the 1, 2, or 3 most significant digits, by integer-dividing the input by the largest value 10^(3n) that is less than the input.
Try it online
Explanation:
9⌐9τk,;;$l3@\3*╤@\(íub)$#p'8=)XkΣ'n*'a+
9⌐9τk                                    push [11, 18]
     ,;;                                 push 3 copies of input (n)
        $l                               get length of n as string (effectively floor(log(n,10)))
          3@\3*╤                         get largest 10^(3n) less than the length
                @\                       get most significant digits of n (x)
                  (í                     bring list from back, push the index of x in the list or -1 if not in list
                    ub)                  increment by 1, convert to boolean, shove to bottom
                       $#p               push first digit from n (as string)
                          '8=            push 1 if "8" else 0
                             )X          shove to bottom of stack, discard remaining digits
                               kΣ'n*     push sum of stack, push a string containing that many "n"s
                                    'a+  push "a", concatenate

Retina, 34
Direct translation of my sed answer:
+`(.)...$
$1
^8.*|^1[18]$
an
\d+
a

Try it online.
One byte saved thanks to @Timwi.

Perl 6,  31  30 bytes

{'a'~'n'x?/^8|^1<[18]>[...]*$/} # 31 bytes

{<a an>[?/^8|^1<[18]>[...]*$/]} # 31 bytes

{<a an>[?/^8|^[11|18][...]*$/]} # 31 bytes

{'a'~'n'x?/^8|^1[1|8][...]*$/} # 30 bytes

{<a an>[?/^8|^1[1|8][...]*$/]} # 30 bytes

( Perl 6 uses [ ] in regexes for non-capturing ( ), and uses <[ ]> for character sets )
Usage:
# store it in a lexical code variable for ease of use
my &code = {...}

my @a  = <0 110 1111 1863 110000 180000 1141592 1897932>;
my @an = <8 11 18 843 8192 11000 18000 11234567 18675309>;

say @a.map: &code;
say @an.map: &code;

(a a a a a a a a)
(an an an an an an an an an)

PostScript, 109 bytes
(a)exch 10 string cvs dup[exch length 3 mod 2 eq{(11)(18)}if(8)]{anchorsearch{pop pop(an)exch}if}forall pop =

The code verifies if the number starts with certain prefixes. The prefix 8 is always checked (eight, eighty-something, eight-hundreds-and), but 11 and 18 (eleven and eighteen) are checked only when the number of digits is a multiple of 3 plus 2.
We start with a tentative result of a and when a prefix is found the result gets replaced with an. anchorsearch is used to avoid extracting a prefix from the string. Even if a match is found we continue verifying the rest of the prefixes – why waste 5 bytes for the  exit? –, but because the original string gets replaced with a we are sure not to get any false positives.
To return the a-or-an result on the operand stack instead of printing it, remove the trailing  = (resulting length: 107 bytes).
Test code:
/DO {
    ... the code above ...
} def

(Should be "a"s:)  = {0 110 1111 1863 110000 180000 1141592 1897932}     { DO } forall
(Should be "an"s:) = {8 11 18 84 843 8192 11000 18000 11234567 18675309} { DO } forall
flush

PostScript (with binary tokens), 63 bytes
(a)’>10’¥’1’8[’>’b3’j2’={(11)(18)}if(8)]{’${’u’u(an)’>}if}’I’u=

The ’ are bytes with the value 146 (decimal), ¥ is a 165 and $ is a 3. All others are printable 7-bit ASCII characters.
This is the same as my PostScript [pure ASCII] version, but uses binary tokens where this helps reduce the total length. I post it separately for 3 reasons:

In the general case, an implementation that minimizes the ASCII code is not necessarily the same as the one minimizing the binary version. Some longer piece of ASCII PostScript code could compress better than another and its corresponding binary version be shorter.
Binary code is not suitable everywhere, so a pure ASCII answer may be preferred even if longer.
It wouldn’t be fair to compare the length of a pure ASCII PostScript answer with one using binary encodings.

Pyth, 29 31
?:_ec_z3"(^18$|^11$|^8)"0"an"\a

Reverses the string, splits it into sections of three, reverses it again, then chooses the appropriate ending.

This is wrong on the input 111 - it gives an

You're right. Fixed.

Python 3, 110 93 91 76 74 70 65 64 bytes
Here is a long one, but a simple one.
Edit: Corrected with thanks to isaacg. Saved some whitespace after the comparisons. Many bytes saved thanks to Timwi, Mego, benpop and Alissa.
n=input();print("a"+"n"*(len(n)%3>1and n[:2]in"118"or"8"==n[0]))

or for the same number of bytes.
n=input();print("a"+"n"[:len(n)%3>1and n[:2]in"118"or"8"==n[0]])

Ungolfed:
def a():
    n=input()
    if "8"==n[:1]:
        a = "n"
    elif len(n)%3 == 2 and (n[:2] in ["11", "18"]):
        a = "n"
    else:
        a = ""
    return "a"+a

This is incorrect on the input 843, "eight hundred fourty-three", which should be an.

@isaacg Not only are you correct, but this simplifies my code immensely. Thanks! It turns out I was only looking at eight, eight thousand, eight million, while ignoring cases like eighty and eight hundred.

Why (-~len(n)%3)<1 instead of len(n)%3==2?

Could (n[:2]=="11"or n[:2]=="18") be shortened to "118".contains(n[:2])?

Or even n[:2]in"118"?

Why not wrap the statement with print()? n=input();print("an"if"8"==n[:1]or len(n)%3==2and n[:2]in"118"else"a")

You can shorten "8"==n[:1] to "8"==n[0] also you can use "a"+"n"*(conditions) instead of "an"if conditions else "a". And then you can shorten conditions by one more space by moving "8"==n[0] to the end. So the final version will be n=input();print("a"+"n"*(len(n)%3==2and n[:2]in"118"or"8"==n[0]))

@Alissa Thanks! Added another version with the same byte count so I didn't copy you completely

Japt, 28 27 bytes
'a+'npUì v ¥8ª[B18]d¥UìA³ v

Try it online!
Unpacked & How it works
'a+'npUì v ==8||[B18]d==UìAp3  v

'a+'np  "a" + "n".repeat(...)
Uì v ==8    First digit in decimal == 8
||          or...
[B18]d      [11,18].some(...)
==UìAp3  v  == First digit in base 10**3

You can replace 1e3 with A³

Java 10, 102 bytes
n->{var N=n+"";return(n>9&&"118".contains(N.substring(0,2))&N.length()%3>1)|N.charAt(0)==56?"an":"a";}

Try it online.
Explanation:
n->{                  // Method with integer parameter and String return-type
  var N=n+"";         //  Input integer as String
  return(n>9&&        //  If the input has at least two digits,
    "118".contains(N.substring(0,2))
                      //  and the first two digits are "11" or "18",
    &N.length()%3>1)  //  and the length modulo-3 is 2
   |N.charAt(0)==56?  //  Or if the first digit is an '8':
     "an"             //   Return "an"
   :                  //  Else:
     "a";}            //   Return "a"

05AB1E, 26 21 bytes
₄внŽ4$2ôQàI8Å?+>„ans∍

Try it online or verify all test cases.
Explanation:
₄в          # Convert the (implicit) input-integer to base-1000 as list
  н         # Pop and push the first integer in this list
            #  i.e. 11234567 → [11,234,567] → 11
            #  i.e. 110000 → [110,0] → 110
            #  i.e. 8192 → [8,192] → 8
   Ž4$      # Push compressed integer 1118
      2ô    # Split it into parts of size 2: [11,18]
        Q   # Check for each if it's equal to the integer
         à  # Pop and push the maximum to check if either is truthy
            #  11 → [1,0] → 1
            #  110 → [0,0] → 0
            #  8 → [0,0] → 0
I           # Push the input-integer again
 8Å?        # Check if it starts with an 8
            #  11234567 → 0
            #  110000 → 0
            #  8192 → 1
+           # Add the two checks together
 >          # Increase it by 1
            #  1+0 → 1 → 2
            #  0+0 → 0 → 1
            #  0+1 → 1 → 2
  „an       # Push string "an"
     s∍     # And shorten it to a length equal to the integer
            #  2 → "an"
            #  1 → "a"
            #  2 → "an"
            # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ž4$ is 1118.

GNU sed -r + BSD number, 34 bytes
s/(e?).*/number &/e
s//a\1/
y/e/n/

First we convert to English number.  Then delete everything except a possible initial e, and prefix with a.  Then convert the e (if present) to n.  The only golfing trick is to match the optional e in the first substitution, so we can reuse the pattern in the following line.
Demo
for i in 0 8 11 18 84 110 843 1111 1863 8192 \
    11000 18000 110000 180000 1141592 1897932 11234567 18675309
do printf "%'10d → %s\n" $i $(./66841.sed <<<$i)
done

         0 → a
         8 → an
        11 → an
        18 → an
        84 → an
       110 → a
       843 → an
     1,111 → a
     1,863 → a
     8,192 → an
    11,000 → an
    18,000 → an
   110,000 → a
   180,000 → a
 1,141,592 → a
 1,897,932 → a
11,234,567 → an
18,675,309 → an

Perl 5 -p, 26 bytes
$_=a.n x/^8|^1[18](...)*$/

Try it online!

TeaScript, 35 bytes
[18,11,8,80]I(+xh(x.n%3¶3©?'an':'a'

Try it here.
Explanation
               xh(x.n%3¶3           get the relevant digits from the input
                                    xh compiles to x.head which returns the
                                    first n chars of x (implicit input)
                                    ¶ ('\xb6') compiles to ||
              +                     cast the result to an integer since
                                    .includes does a strict comparison
                         ©          ('\xa9') compiles to ))
[18,11,8,80]                        array of the special cases
            I(                      I( is an alias for .includes( which
                                    returns true if the array contains the
                                    argument
                          ?'an':'a' finally, return 'an' if the array
                                    contains the number, 'a' otherwise

Python 2.7, 66
s=`input()`
print['a','an'][s[:1]=='8'or s[:2]in len(s)%3/2*'118']

Obviously not as short as the lambda one.

QuadS, 32 bytes
'a',⍵
^8.*|^1[18](...)*$
⊃⍵L/'n'

Try it online!

Stax, 25 bytes
â-x▬♪°∞▄'δL|÷æ╪║>₧4¢ÿ·7åR

Run and debug it
Unpacked, ungolfed, and commented, it looks like this.
Vk|Eh       get the first "digit" after converting to base 1000
AJ|Eh       get the first "digit" after converting to base 100
c20>9*^/    if the result is greater than 20, divide it by 10 again
"AMj"!#     is the result one of [8, 11, 18]?
^           increment by 1
.an(        keep that many characters of the string "an"

Run this one

C++, 80 79 bytes
[](int i){for(;i>999;i/=1e3);return i-11&&i-18&&i/100-8&&i/10-8&&i-8?"a":"an";}

It turned out 4 bytes shorter to explicitly test against 8xx and 8x than to have another /=10 loop, like this:
[](int i){for(;i>999;i/=1e3);for(i==11|i==18?i=8:0;i>9;i/=10);return i-8?"a":"an";}

Demo
#include <locale>
#include <cstdio>
int main(int argc, char**argv)
{
    auto const f =
        [](int i){for(;i>999;i/=1e3);return i-11&&i-18&&i/100-8&&i/10-8&&i-8?"a":"an";}
    ;

    std::locale::global(std::locale{""});
    for (int i = 1;  i < argc;  ++i) {
        auto const n = std::stoi(argv[i]);
        printf("%'10d → %s\n", n, f(n));
    }
}

         0 → a
         8 → an
        11 → an
        18 → an
        84 → an
       110 → a
       843 → an
     1,111 → a
     1,863 → a
     8,192 → an
    11,000 → an
    18,000 → an
   110,000 → a
   180,000 → a
 1,141,592 → a
 1,897,932 → a
11,234,567 → an
18,675,309 → an

I don't know C++ too well, but can i/=1000 be i/=1e3, and can all && become &?

It indeed seems to work: Try it online.

@Kevin - I did at one point have 1e3 there; I changed it during debugging and forgot to change it back.  The && can't all be &, because subtraction yields integers and not booleans - e.g. 19-11 is 8, and 19-18 is 1; see that 8 && 1 is true, but 8 & 1 is false.  We could use & but we'd need to change - to != and also add parentheses.

Ah of course.. & indeed doesn't work here, my bad. Btw, why don't you add a TIO-link to your answer as well?

Whitespace, 243 bytes
[S S S T    T   S S S S T   N
_Push_97_a][T   N
S S _Print_as_character][S S S T    N
_Push_1][S N
S _Duplicate_1][S N
S _Duplicate_1][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][N
S S S T N
_Create_Label_LOOP][S N
T   _Swap_top_two][S S S T  N
_Push_1][T  S S S _Add][S N
T   _Swap_top_two][S N
S _Duplicate][S S S T   T   S S T   S S N
_Push_100][T    S S T   _Subtract][N
T   T   T   N
_If_negative_jump_to_Label_TWO_DIGITS][S S S T  S ST    S N
_Push_10][T S T S _Integer_division][N
S N
S T N
_Jump_to_Label_LOOP][N
S S T   N
_Create_Label_TWO_DIGITS][S N
S _Duplicate][S S S T   S S S N
_Push_8][T  S S T   _Subtract][N
T   S S S N
_If_zero_jump_to_Label_PRINT_n][S N
S _Duplicate][S S S T   S T T   N
_Push_11][T S S T   _Subtract][N
T   S S N
_If_0_jump_to_Label_2_MOD_3][S N
S _Duplicate][S S S T   S S T   S N
_Push_18][T S S T   _Subtract][N
T   S S N
_If_0_jump_to_Label_2_MOD_3][S S S T    S ST    S N
_Push_10][T S T S _Integer_division][S N
S _Duplicate][N
T   S N
_If_0_jump_to_Label_EXIT][N
S N
T   N
_Jump_to_Label_TWO_DIGITS][N
S S S N
_Create_Label_2_MOD_3][S N
T   _Swap_top_two][S S S T  T   N
_Push_3][T  S T T   _Modulo][S S S T    S M
_Push_2][T  S S T   _Subtract][N
T   T   N
_If_negative_jump_to_Label_EXIT][N
S S S S N
_Create_Label_PRINT_n][S S S T  T   S T T   T   S N
_Push_110_n][T  N
S S _Print_as_character][N
S S N
_Create_Label_EXIT]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.
Try it online (with raw spaces, tabs and new-lines only).
Program stops with an error: No exit found.
Explanation in pseudo-code:
Print "a"
Integer input = STDIN as integer
Integer counter = 1
Start LOOP:
  counter = counter + 1
  If(input < 100)
    Jump to function TWO_DIGITS
  input = input integer-divided by 10
  Go to next iteration of LOOP

function TWO_DIGITS:
  If(input == 8)
    Jump to function PRINT_n
  If(input == 11 or input == 18)
    Jump to function 2_MOD_3
  input = input integer-divided by 10
  If(input == 0)
    Exit program
  Recursive call to TWO_DIGITS

function 2_MOD_3:
  If(counter modulo-3 != 2)
    Exit program
  Jump to function PRINT_n

function PRINT_n:
  Print "n"
  Exit program

Perl, 71 55 49 bytes
$_=<>;$_=/^8/||/^1[18]/&&length%3==1?'an':'a';say

I knew the ternary operator would help one day...
Let me break this down.

$_=<> accepts a number as input.
The big $_=... block will set the value of $_ after it's used.

...?...:... is the ternary operator. If the condition (first argument) is true, it returns the second argument. Otherwise, it returns the third.
/^8/||(/^1[18]/&&length%3==2) checks to see if the number starts with 8 or begins with 11 or 18 (1[18] accepts either) and has a length mod 3 of 2.
If that's true, $_ is set to an. Otherwise, it's set to a.

It then prints out the contents of $_ (either a or an) with say.

Changes

Saved 16 bytes thanks to msh210.
Saved 6 bytes by removing parens and using defaults.

$_=<>;$_=(/^8/)||/^1[18]/&&length($_)%3==1?'an':'a';say saves a few bytes. (Though the number to compare to it depends on what your newline character is, but that doesn't change the byte count.)

@msh210 It looks like that's only 55 bytes meaning it saves 16 bytes. I'll add that in. Thanks!

You're welcome. Oh, and you can drop the first parens (I assume. I haven't tested). I'd think you could also change length($_) to length (or at least drop the parens) but that's not working for me for some reason.

@msh210 Yep, you can drop the parens and ($_) to get $_=<>;$_=/^8/||/^1[18]/&&length%3==1?'an':'a';say, which is only 49 bytes.

You can save some bytes by using -p instead of $_=<> and say, y///c instead of length, and dropping the quotes around a and an: perl -pe'$_=/^8/||/^1[18]/&&y///c%3==2?an:a' (34 bytes + 1 for -p). Note that input cannot end with a newline: echo -n 11 | perl -pe'...'. This also fixes a bug: length%3==2 is parsed as length(%3)==2, not as length($_)%3==2, so it always returns false.

$ perl -nE 'say/^(8|1[18](...)*$)/?an:a' 27+1

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


text:
Motzkin Numbers
The nth Motzkin Number is the number of paths from (0, 0) to (n, 0) where each step is of the form (1, -1), (1, 0) or (1, 1), and the path never goes below y = 0.
Here's an illustration of these paths for n = 1, 2, 3, 4, from the above link:

The desired sequence is OEIS A001006. OEIS has some other characterizations of the sequence.

You will be given a positive integer n as input. You should output the nth Motzkin Number.
Here are Motzkin numbers 1 to 10:
1, 2, 4, 9, 21, 51, 127, 323, 835, 2188

All standard input and output methods are allowed. Standard loopholes apply.
This is code golf. Fewest bytes wins.

What's the minimum set of Motzkin numbers we must be able to generate?

Related

@FlagAsSpam All of them, up to limitations of time/memory/data type.

I think languages need a Dyck words builtin now.

MATL, 13 14 bytes
i-2/t.5+hH4Zh

Example:
>> matl i-2/t.5+hH4Zh
> 6
51

EDIT (June 16, 2017): you can try it online! Note also that in modern versions of the language (that post-date this challenge) the i could be removed.
Explanation
Pretty straightforward, using the equivalence (see equation (10)) with the hypergeometric function:
$$M_n = {}_2F_1 \left( \frac {1-n} 2, -\frac n 2 ; 2 ;4 \right)$$
From the definition of the hypergeometric function
$${}_2F_1(a,b; c; z) = \sum ^ \infty _ {n=0} \frac {(a)_n (b)_n} {(c)_n} \frac {z^n} {n!}$$
it's clear that the order of the first two arguments can be interchanged, which saves one byte.
i         % input
-2/       % divide by -2
t.5+      % duplicate and add 0.5
h         % horizontal concatenation into a vector
H         % number 2
4         % number literal
Zh        % hypergeometric function with three inputs (first input is a vector)

This answer is tied for the shortest, and older by about an hour and a half, so I'm accepting it.

Thanks! I could hardly imagine MATL would even be tied with Pyth. It's such a hard language to beat, good job designing it!

Retina, 59 58 bytes
+`(\D*)1(1*)
:$1<$2:$1>$2:$1_$2:
:(_|()<|(?<-2>)>)+:(?!\2)

Takes input in unary. Input 7 (i.e. 1111111) takes quite a while but still completes in less than a minute. I wouldn't go much further than that.
Try it online.
Explanation
A different characterisation of the Motzkin numbers is the number of strings of three different characters, where two of them are correctly balanced (hence the close relation to Catalan numbers, which are the same without the third character which is independent of the balancing).
.NET's balancing groups are pretty good at detecting correctly matched strings, so we simply generate all strings of length N (using _, < and > as the three characters) and then we count how many of those are correctly balanced. E.g. for N = 4 the valid strings are:
____
__<>
_<_>
_<>_
<__>
<_>_
<>__
<<>>
<><>

Compared with the definition in the challenge, _ corresponds to a (1,0) step, < to (1,1) and > to (1,-1).
As for the actual code, the : is used as a separator between the different strings. The second regex is just a golfed form of the standard .NET regex for balanced strings.
Something to note is that there is only a single : inserted between strings in each step, but the second regex matches a leading and a trailing : (and since matches cannot overlap, this means that adjacent strings generated from one template in the last step cannot both match). However, this is not a problem, because at most one of those three can ever match:

If the string ending in _ matches, the prefix without that _ is already balanced correctly, and < or > would throw off that balance.
If the string ending in > matches, the string is balanced with that >, so _ or < would throw off that balance.
Strings ending in < can never be balanced.

It's a shame that '' has special meaning otherwise using '_/' characters would better suit the spirit of the question.

Python 2, 51 bytes
M=lambda n:n<1or sum(M(k)*M(n-2-k)for k in range(n))

Uses the formula from Mathworld

Saves chars by putting the M[n-1] term into the summation as k=n-1, which gives M[-1]*M[n-1], with M[-1]=1 as part of the initial condition.
Edit: One char shorter writing the sum recursively:
M=lambda n,k=0:n<1or k<n and M(k)*M(n-2-k)+M(n,k+1)

Other approaches that turned out longer:
M=lambda n,i=0:n and(i>0)*M(n-1,i-1)+M(n-1,i)+M(n-1,i+1)or i==0
M=lambda n:+(n<2)or(3*~-n*M(n-2)+(n-~n)*M(n-1))/(n+2)

Pyth, 15 bytes
Ls*V+KyMb1+t_K1

This defines a function y. Try it online: Demonstration
Explanation:
Let y[n] be the n-th Motzkin Number. I calculate y[n] with the formula
y[n] = dot product of (y[0], ..., y[n-1], 1) and (y[n-2], ..., y[0], 1)

Notice that the first vector is larger than the second one (except when calculating y[0]). When this is the case, than Pyth automatically ignores the 1 at the end of the first vector, so that both vectors are of equal length.
Ls*V+KyMb1+t_K1
L                 define a function y(b), which returns:
      yMb            compute the list [y[0], y[1], ..., y[b-1]]
     K               assign it to K
  *V                 vectorized multiplication of
    +K   1             * K with a 1 at the end
          +t_K1        * reverse(K), remove the first element, and append 1
 s                   return the sum (dot product)

This formula is a variation of one of the formulas listed on OEIS. It may be a little bit stupid. Because of the 1 at the end of the first vector (which make the lengths unequal), I don't actually have to give the recursion a base case. And I had hopes, that the two +...1s can be golfed somehow. Turns out I can't.
You can define a similar recursion with a dot product of equal length vectors and define the base case y[0] = 1 with with the same byte count.

CJam (20 bytes)
.5X]{__W%.*:++}qi*W=

Online demo
As Mego noted in the comments on the question, this is very closely related to the Catalan numbers: change the .5 to 1 and offset the index by one (or simply remove the .5 entirely and leave the index unchanged) to get Catalan numbers.
The recurrence used is

a(n+2) - a(n+1) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0). [Bernhart]

from the OEIS page. The corresponding recurrence for the Catalan numbers is listed as

a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).

Seriously, 21 bytes
,;╗r`;τ╜█@;u@τ╣║\*`MΣ

Borrows some code from quintopia's Catalan Numbers solution, specifically the improvement I made in the comments.
I use the following formula:

Since nCk is 0 for k > n, I sum all the way to n-1, since those values will all be 0 and thus do not affect the sum.
Try it online
Explanation:
,;╗r`;τ╜█@;u@τ╣║\*`MΣ
,;╗                    push input, dupe, store one copy in register 0
   r                   push range(0, n) ([0,n-1])
    `             `M   map the function:
     ;τ╜█@               dupe k, push C(n, 2*k), swap with k
          ;u@τ╣║\        push the kth Catalan number
                 *       multiply
                    Σ  sum

C(n, 2*k) does what now?

@FlagAsSpam C(n,k) = nCk, or the number of combinations of k items from a pool of n items.

Oh, that makes way more sense than what I thought it was. +1.

@FlagAsSpam I don't think I want to know what you thought it was...

R, 64 bytes
f=function(n)ifelse(n<2,1,f(n-1)+sum(rev(s<-sapply(2:n-2,f))*s))

Uses also the Mathworld formula of @xnor's python answer.
Thanks to rules of precedence, 2:n-2 is equivalent to 0:(n-2).
Test cases:
> f(0)
[1] 1
> f(1)
[1] 1
> f(5)
[1] 21
> f(10)
[1] 2188
> sapply(0:20,f)
 [1]        1        1        2        4        9       21       51      127
 [9]      323      835     2188     5798    15511    41835   113634   310572
[17]   853467  2356779  6536382 18199284 50852019

Mathematica, 31 30 bytes
AppellF1[-#/2,.5,-#/2,2,4,4]&

For fun, here's a 37 byte version
Hypergeometric2F1[(1-#)/2,-#/2,2,4]&

and 52 byte version
SeriesCoefficient[1-x-Sqrt[1-2x-3x^2],{x,0,#+2}]/2&

Jelly, 17 14 13 bytes
×US;
1;HÇƓ¡1ị

This uses the recurrence relation from @PeterTaylor's answer. Try it online!
How it works
×US;      Define a helper link. Left argument: a (list)

×U        Multiply (×) a by its reverse (U).
  S       Compute the sum of the resulting list.
   ;      Prepend it to a.
          Return the result.

1;HÇƓ¡1ị  Define the main link.

1         Set the left argument to 1.
 ;H       Append the half of 1 to 1. Result: [1, 0.5].
    Ɠ     Read an integer n from STDIN.
   Ç ¡    Call the helper link (Ç) n times.
      1ị  Retrieve the result at index 1.

10 bytes in the latest version of Jelly

Mathematica, 44 42 34 bytes
Sum[#!/(i!(i+1)!(#-2i)!),{i,0,#}]&

A 35 bytes version:
Coefficient[(1+x+1/x)^#,x]/#&[#+1]&

05AB1E, 13 12 bytes
ÝI<ãʒ.øDŸQ}g

Try it online!
While most answers use a formula or recurrence relation, this is a simple counting approach.
Each possible path through the grid is represented by the list of its y coordinates. For n segments, there are a total of (n+1) points, but the first and last one are necessarily 0, so that leaves (n-1) points to specify.
Ý           # range [0..n]
 I<         # n - 1
   ã        # cartesian power

We now have a list of paths (not yet including the initial and final 0). By construction, none of them ever go below 0. However, some of them have illegal slopes (e.g. jump from 0 to 2), so we need to filter them out.
ʒ      }g   # count how many paths satistfy the following condition
 0.ø        # surround with 0
      Q     # is equal to
    DŸ      # its own fluctuating range

Ÿ is the fluctuating range built-in. If there's any pair of non-adjacent numbers, it will fill in the missing numbers (e.g. [0, 2] becomes [0, 1, 2]). Only legal paths will be left unchanged.
A perhaps more intuitive way to check for illegal slopes would be üαà (assert the maximum of pairwise absolute differences equals 1). However, this misses the flat [0, 0, ... 0] path, which costs one extra byte to fix.
Finally, note that the actual code uses .ø where this explanation uses 0.ø. Instead of surrounding the path with 0s, this surrounds the implicit input with two copies of the path. This turns the coordinate system upside-down and inside-out, but is otherwise equivalent.

Stax, 12 bytes
îu¬@Y≤ÅÉÑ(πε

Run and debug it
I don't know how to do fancy math typesetting, but this essentially relies on a dynamic programming construction
M(0) = 1
M(1) = 1
M(n + 1) = M(n) + sum(M(k) * M(n - k - 1) for k in [0..n-1])

Pari/GP, 38 36 26 bytes
n->(1+x+x^2)^n++/n\x^n++%x

Try it online!
Using equation (11) from MathWorld:
\$ M_n = \dfrac{1}{n + 1} \dbinom{n + 1}{1}_2 \$
where \$ \binom{n}{k}_2 \$ is a trinomial coefficient. By definition, \$ \binom{n}{k}_2 \$ is the coefficient of \$ x^{n + k} \$ in the expansion of \$ (1 + x + x^2)^n \$.

A 14-bytes Samau function using the first definition of the trinomial coefficient: );;7 2D$ⁿ$)╡$÷. I won't post it as an answer because the language is newer than the question.

Posting it is just fine, you just have to add a disclaimer that the submission isn't eligible to win because, as you said, the language is newer than the question.

Ruby, 50
straightforward implementation of the recurrence relation.
g=->n{n<2?1:(3*(n-1)*g[n-2]+(2*n+1)*g[n-1])/(n+2)}

Haskell, 55 52 bytes
Straightforward implementation of the recursion. Thanks @Delfad0r for -3 bytes!
a n|n>2=div((2*n+1)*a(n-1)+(3*n-3)*a(n-2))$n+2
a n=n

Try it online!

52 bytes

@Delfad0r Thanks, I updated it!

Brain-Flak, 90 bytes
(([{}]<(())>)<{({}()<{<>([({})]({}[({})]({}<>{}<>)))<>}<>>)}>){({}()<{}>)}{}({}{}[{}{}]<>)

Try it online!
Computes \${\binom{n}{0}}_2 - {\binom{n}{2}}_2\$, where \$\binom{n}{k}_2\$ is a trinomial coefficient.  I couldn't find this formula anywhere, so I can't reference it, but it can be proved in the same way as the analogous formula \$C_n = \binom{2n}{n} - \binom{2n}{n+1}\$.

Maxima, 49 bytes
Use the formula
\$
M_n=\frac{1}{n+1}\cdot[z^{n+2}](1+x+x^2)^n
\$
f(n):=coeff(expand((1+x+x^2)^(n+1)),x,n+2)/(n+1);

Try it online!

ES6, 44 bytes
f=(n,k=0)=>n<1?1:k<n&&f(k)*f(n-2-k)+f(n,k+1)

Straightforward port of @xnor's recursive Python solution. Needs n<1?1: because n<1|| would make f(0) return true.

Nekomata + -n, 8 bytes
3$ŧ←∫Ɔž≥

Attempt This Online!
3$ŧ←∫Ɔž≥    Let n be the input
3$ŧ         Find an n-tuple of integers in [0, 3)
   ←        Decrement each element
    ∫       Take the cumulative sum
     Ɔž     Check that the last element is 0
       ≥    And that each element is non-negative

-n counts the number of solutions.


text:
How many weeks?
Your task is to output a single number; the number of ISO weeks that a given date range intersects. To quote Wikipedia: An average year is exactly 52.1775 weeks long, but this is not about the average.
Input consists of two space-separated ISO dates:
0047-12-24 2013-06-01

The end date is never before the start date. We'll use the extrapolated Gregorian calendar for simplicity.
Test cases:
Format: input -> output
2015-12-31 2016-01-01 -> 1    (both are within week 53 of 2015)
2016-01-03 2016-01-04 -> 2    (the 3rd is within week 53, and the 4th is in week 1)
2015-12-24 2015-12-24 -> 1    (this single day is of course within a single week)

Your solution should handle dates between 0001-01-01 and 9999-12-31.

Can the input be an array of strings instead of a single space-separated string? Alternatively, can the two dates be two arguments to a function?

I assume you mean Proleptic Gregorian Calendar.

Also, do weeks start on Sunday or Monday? According to your second test case, it's Monday, but just making sure.

@Doorknob冰  Wikipedia quote: "A date is specified by the ISO week-numbering year in the format YYYY, a week number in the format ww prefixed by the letter 'W', and the weekday number, a digit d from 1 through 7, beginning with Monday and ending with Sunday" So starting on Monday as per ISO 8601

According to the ISO standard, Weeks start with Monday.

@BradGilbertb2gills yes. I used the term that wolframalpha uses, but it's the same thing.

Ruby, 89 88 86 bytes
->s{a,b=s.split.map{|x|Time.gm *x.split(?-)}
n=1
(a+=86400).wday==1&&n+=1until a==b
n}

A very primitive solution: given the first date a and the second date b, increment a, check if it's a Monday (if so, we've "rolled over" to a new week), and stop once a is b.
Takes input in the exact format specified in the question: a single space-separated string. (The way it parses the input is fancy-ish: it uses Ruby's "splat" operator, *. This operator "expands" an array or enumerable out, so Time.gm *[2013, 06, 01] becomes Time.gm 2013, 06, 01.)
Imported from a comment discussion:

We don't care about "weeks in a year;" we only care about "weeks overall." So whether a year has 52 or 53 weeks doesn't make any difference.

Just to avoid future confusion with whether this handles year boundaries correctly—according to Wikipedia, all weeks always start on Monday and end on Sunday.
For some more fancy tricks, these are all equivalent:
until a==b;a+=86400;n+=a.wday==1?1:0;end
[a+=86400,n+=a.wday==1?1:0]until a==b
n+=(a+=86400).wday==1?1:0 until a==b
(a+=86400).wday==1&&n+=1 until a==b
(a+=86400).wday==1&&n+=1until a==b

Can't you can save 1 char replacing a==b by a<b ?

 VBA , 125 Bytes
Expecting 2 function inputs as strings
Function u(k,j)
f=DateValue(k)
For i=0 To (DateValue(j)-f)
q=DatePart("ww",f+i,2,2)
If q<>j Then u=u+1
j=q
Next
End Function

Pretty sure This can be golfed. This is looping though everyday between the 2 dates and increments the counter every time the ISO date changes.
DatePart("ww",f+i,2,2) is the ISO week number in VBA the first 2 means Monday (complies with ISO standard 8601, section 3.17). then second 2 means Week that has at least four days in the new year (complies with ISO standard 8601, section 3.17)
 140 bytes w/single input
Function g(k)
y=Split(k)
f=DateValue(y(0))
For i=0 To (DateValue(y(1))-f)
q=DatePart("ww",f+i,2,2)
If q<>j Then g=g+1
j=q
Next
End Function

R, 76 bytes
d=as.Date(scan("","raw"));sum(strftime(seq(d[1],d[2],"day")[-1],"%w")==1)+1

After the talk with @Doorknob, it's finally as easy as counting the Mondays.
seq allow to create a vector of dates (of each day between two dates) and strftime transform it to the 'number of the day in the week', now counts the times it's 1 to get the number of time you changed week and add 1 to take in account previous week.
Another approach looping:
R, 85 bytes
n=1;d=as.Date(scan("","raw"));z=d[1];while(z<d[2]){n=n+(strftime(z<-z+1,"%w")==1)};n

Regarding your second approach, you should only add 1 to the total number of Mondays if the first date does not fall on a Monday.

@DavidCarraher Thanks, reading your answer made me think I could remove the first day of range, thus fixing the problem :)

Mathematica 135 79 96 84 74 bytes
Consistent with @Doorknob's suggestion, this

generates all the dates in the range

counts the number of Mondays (ISOWeekDay =="1") in the DateRange(excluding d), and

adds 1 to the total.

Count[DateString[#,"ISOWeekDay"]&/@Rest@(DateRange@@StringSplit@#),"1"]+1&

Count[DateString[#,"ISOWeekDay"]&/@Rest@(DateRange@@StringSplit@#),"1"]+1&
/@ {"2015-12-31 2016-01-01", "2016-01-04 2016-01-05","2016-01-03 2016-01-04",
"2015-12-24 2015-12-24", "1876-12-24 2016-01-01"}

{1, 1, 2, 1, 7255}


text:
Help, I'm trapped in a Sierpinski triangle!
Drawing the Sierpinski triangle has been done to death. There's other interesting things we can do with it though. If we squint hard enough at the triangle, we can view upside-down triangles as nodes of a fractal graph. Let's find our way around that graph!
First, let's assign a number to each node. The largest upside-down triangle will be node zero, and then we just go down layer by layer (breadth-first), assigning consecutive numbers in the order top-left-right:

Click for larger version where the small numbers are a bit less blurry.
(Of course, this pattern continues ad infinitum inside the blue triangles.) Another way to define the numbering is that the centre node has index 0, and the children of node i (adjacent triangles of the next-smaller scale) have indices 3i+1, 3i+2, and 3i+3.
How do we move around this graph? There are up to six natural steps one can take from any given triangle:

One can always move through the midpoint of one of the edges to one of the three children of the current node. We'll designate these moves as N, SW and SE. E.g. if we're currently on node 2, these would lead to nodes 7, 8, 9, respectively. Other moves through the edges (to indirect descendants) are disallowed.
One can also move through one of the three corners, provided it doesn't touch the edge of the triangle, to either the direct parent or one of two indirect ancestors. We'll designate these moves as S, NE and NW. E.g. if we're currently on node 31, S would lead to 10, NE would be invalid and NW would lead to 0.

The Challenge
Given two non-negative integers x and y, find the shortest path from x to y, using only the six moves described above. If there are several shortest paths, output any one of them.
Note that your code should work for more than just the 5 levels depicted in the above diagram. You may assume that x, y < 1743392200. This ensures that they fit inside a 32-bit signed integer. Note that this corresponds to 20 levels of the tree.
Your code must process any valid input in less than 5 seconds. While this rules out a brute force breadth-first search, it should be a fairly loose constraint — my reference implementation handles arbitrary input for depth 1000 in half a second (that's ~480-digit numbers for the nodes).
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.
The output should be a flat, unambiguous list of the strings N, S, NE, NW, SE, SW, using any reasonable separator (spaces, linefeeds, commas, ","...).
Standard code-golf rules apply.
Test Cases
The first few test cases can be worked out by hand using the diagram above. The others ensure that answers are sufficiently efficient. For those, there may be other solutions of the same length that are not listed.
0 40                    => N N N N
66 67                   => S SW N N N
30 2                    => NW NW -or- NE SW
93 2                    => NE SW
120 61                  => NW NW NW NW N SE SW N
1493682877 0            => S S NW NW
0 368460408             => SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130 1242824      => NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
520174 1675046339       => NE NW NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW
312602548 940907702     => NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873   => NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
547211529 1386725128    => S S S NE NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199   => NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE

Python 2, 208 205 200 bytes
A=lambda n:n and A(~-n/3)+[-n%3]or[]
f=lambda x,y:f(A(x),A(y))if x<[]else["SSNEW"[m::3]for m in
y[len(x):]]if x==y[:len(x)]else min([["NNSWE"[m::3]]+f(x[:~x[::-1].index(m)],y)for
m in set(x)],key=len)

A function, f, taking a pair of node numbers, and returning the shortest path as a list of strings.
Explanation
We start by employing a different addressing scheme for the triangles;
the address of each triangle is a string, defined as follows:

The address of the central triangle is the empty string.
The addresses of the north, south-west, and south-east children of each triangle are formed appending 0, 1, and 2, respectively, to the address of the triangle.

Essentially, the address of each triangle encodes the (shortest) path from the central triangle to it.
The first thing our program does is translating the input triangle numbers to the corresponding addresses.

Click the image for a larger version.
The possible moves at each triangle are easily determined from the address:

To move to the north, south-west, and south-east children, we simply append 0, 1, and 2, respectively, to the address.
To move to the south, north-east, and north-west ancestors, we find the last (rightmost) occurrence of 0, 1, and 2, respectively, and trim the address to the left of it.
If there is no 0, 1, or 2 in the address, then the corresponding ancestor doesn't exist.
For example, to move to the north-west ancestor of 112 (i.e., its parent), we find the last occurrence of 2 in 112, which is the last character, and trim the address to the left of it, giving us 11;
to move to the north-east ancestor, we find the last occurrence of 1 in 112, which is the second character, and trim the address to the left of it, giving us 1;
however, 112 has no south ancestor, since there is no 0 in its address.

Note a few things about a pair of addresses, x and y:

If x is an initial substring of y, then y is a descendant of x, and therefore the shortest path from x to y simply follows the corresponding child of each triangle between x and y;
in other words, we can replace each 0, 1, and 2 in y[len(x):] with N, SW, and SE, respectively.
Otherwise, let i be the index of the first mismatch between x and y.
There is no path from x to y that doesn't pass through x[:i] (which is the same as y[:i]), i.e., the first common ancestor of x and y.
Hence, any path from x to y must arrive at x[:i], or one of its ancestors, let's call this triangle z, and then continue to y.
To arrive from x to z, we follow the ancestors as described above.
The shortest path from z to y is given by the previous bullet point.

If x is an initial substring of y, then the shortest path from x to y is easily given by the first bullet point above.
Otherwise, we let j be the smallest of the indices of the last occurrences of 0, 1, and 2 in x.
If j is greater than, or equal to, the index of the first mismatch between x and y, i, we simply add the corresponding move (S, NE, or NW, respectively) to the path, trim x to the left of j, and continue.
Things get trickier if j is less than i, since then we might get to y fastest by ascending to the common ancestor x[:j] directly and descending all the way to y, or we might be able to get to a different common ancestor of x and y that's closer to y by ascending to a different ancestor of x to the right of i, and get from there to y faster.
For example, to get from 1222 to 1, the shortest path is to first ascend to the central triangle (whose address is the empty string), and then descend to 1, i.e., the first move takes us to the left of the point of mismatch.
however, to get from 1222 to 12, the shortest path is to ascend to 122, and then to 12, i.e., the first move keeps us to the right of the point of mismatch.
So, how do we find the shortest path?
The "official" program uses a brute-force-ish approach, trying all possible moves to any of the ancestors whenever x is not an initial substring of y.
It's not as bad as it sounds!
It solves all the test cases, combined, within a second or two.
But then, again, we can do much better:
If there is more than one directly reachable ancestor to the left of the point of mismatch, we only need to test the rightmost one,
and if there is more than one directly reachable ancestor to the right of the point of mismatch, we only need to test the leftmost one.
This yields a linear time algorithm, w.r.t. the length of x (i.e., the depth of the source triangle, or a time proportional to the logarithm of the source triangle number), which zooms through even much larger test cases.
The following program implements this algorithm, at least in essence—due to golfing, its complexity is, in fact, worse than linear, but it's still very fast.
Python 2, 271 266 261 bytes
def f(x,y):
 exec"g=f;f=[]\nwhile y:f=[-y%3]+f;y=~-y/3\ny=x;"*2;G=["SSNEW"[n::3]for
n in g];P=G+f;p=[];s=0
 while f[s:]:
    i=len(f)+~max(map(f[::-1].index,f[s:]));m=["NNSWE"[f[i]::3]]
    if f[:i]==g[:i]:P=min(p+m+G[i:],P,key=len);s=i+1
    else:p+=m;f=f[:i]
 return P

Note that, unlike the shorter version, this version is written specifically not to use recursion in the conversion of the input values to their corresponding addresses, so that it can handle very large values without overflowing the stack.
Results
The following snippet can be used to run the tests, for either version, and generate the results:
def test(x, y, length):
    path = f(x, y)
    print "%10d %10d  =>  %2d: %s" % (x, y, len(path), " ".join(path))
    assert len(path) == length

#         x           y        Length
test(          0,          40,    4   )
test(         66,          67,    5   )
test(         30,           2,    2   )
test(         93,           2,    2   )
test(        120,          61,    8   )
test( 1493682877,           0,    4   )
test(          0,   368460408,   18   )
test( 1371432130,     1242824,   17   )
test(     520174,  1675046339,   23   )
test(  312602548,   940907702,   19   )
test( 1238153746,  1371016873,   22   )
test(  547211529,  1386725128,   23   )
test( 1162261466,  1743392199,   38   )

Golfed Version
         0         40  =>   4: N N N N
        66         67  =>   5: S SW N N N
        30          2  =>   2: NE SW
        93          2  =>   2: NE SW
       120         61  =>   8: NW NW NW NW N SE SW N
1493682877          0  =>   4: S S NW NW
         0  368460408  =>  18: SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130    1242824  =>  17: NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
    520174 1675046339  =>  23: NE NE NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW
 312602548  940907702  =>  19: NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873  =>  22: NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
 547211529 1386725128  =>  23: S S S S NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199  =>  38: NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE

Efficient Version
         0         40  =>   4: N N N N
        66         67  =>   5: S SW N N N
        30          2  =>   2: NW NW
        93          2  =>   2: NE SW
       120         61  =>   8: NW NW NW NW N SE SW N
1493682877          0  =>   4: NE S NW NW
         0  368460408  =>  18: SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130    1242824  =>  17: NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
    520174 1675046339  =>  23: NE NW NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW
 312602548  940907702  =>  19: NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873  =>  22: NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
 547211529 1386725128  =>  23: S S S S NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199  =>  38: NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE

Damn that was fast. I can't tell you how happy it makes me every time I get you to answer one of my challenges. :)

@MartinBüttner Thanks, that's a huge compliment! FWIW, I hugely enjoy solving your challenges. I might, or might not, have started working on this one while it was still in the sandbox... :)

The addressing scheme is brilliant. This is awesome.

Excellent answer. But how did you type all this up in less than an hour? ;-)

@BrainSteel the first thing that occured to me was to try that addressing scheme, but to see the whole thing conceptualized, implemented and written up in under an hour is awesome. +1

I believe this may be slightly off, as the largest center triangle does not have a value of 0, nor match the case in the OP where i is the value in the center node, and going counter-clockwise, the values are 3i+1, 3i+2, and 3i+3

@Zymus I'm not sure I follow, but if you're referring to the picture, it's not supposed to match the OP—this is a different addressing scheme, as described in the post.,

@Ell, got it, I misunderstood.

The addressing system described here is a base-3 bijective numeration (using digits 0-2 rather than the more conventional 1-3).

Ruby, 195 194 190 184 bytes
Original: With apologies to Ell, as this is essentially a port of their answer and with many thanks to Doorknob for their help in debugging this answer. There's probably another algorithm for this problem - something to do with *f[x[0,**however far x matches with y**],y] - but I will save that for another time.
a=->n{n<1?[]:a[~-n/3]+[-n%3]}
f=->x,y{j=x.size
(Array===x)?x==y[0,j]?y[j..-1].map{|m|%w[SE SW N][m]}:x.uniq.map{|m|[%w[NW NE S][m],*f[x[0,x.rindex(m)],y]]}.min_by(&:size):f[a[x],a[y]]}

EDIT: The greedy algorithm doesn't work for h[299792458, 1000000]. I have returned the byte count to 195, while I repair my algorithm once more. Fixed it only for the byte count to rise to 203. Sigh
Under construction: This program uses a greedy algorithm to find common ancestors x[0,j]==y[0,j] (note: there may be several common ancestors). The algorithm is based very loosely on Ell's recursive ancestor search. The first half of the resulting instructions are how to get to this common ancestor, and the second half is getting to y based on y[j..-1].
Note: a[n] here returns a base-3 bijective numeration using the digits 2,1,0 instead of 1,2,3.
As an example, let's run through f[59,17] or f[[2,0,2,1],[2,1,1]]. Here, j == 1. To get to x[0,j], we go 0 or NW. Then, to get to y, go [1,1] or SW SW
a=->n{n<1?[]:a[~-n/3]+[-n%3]}
h=->m,n{x=a[m];y=a[n];c=[];j=x.size
(j=x.uniq.map{|m|k=x.rindex(m);x[0..k]==y[0..k]?j:k}.min
c<<%w[NW NE S][x[j]];x=x[0,j])until x==y[0,j]
c+y[j..-1].map{|m|%w[SE SW N][m]}}

APL (Dyalog Unicode), 144 132 129 118 133 132 130 124 117 bytesSBCS
Thank you very much to Ven and ngn for their help in golfing this in The APL Orchard, a great place to learn the APL language. ⎕IO←0. Golfing suggestions welcome.
Edit: -12 bytes thanks to Ven and ngn by changing how n is defined and switching from 1-indexing to 0-indexing. -3 due to fixing a bug where not everything was switched to 0-indexing. -11 bytes due to changing how P and Q are defined. +15 bytes due to fixing a problem where my algorithm was incorrect with many thanks to ngn for help with figuring the s[⊃⍋|M-s] section. -2 bytes from rearranging the method of finding the backtracking path and +1 byte to bug fixing. -2 bytes thanks to Adám from rearranging the definition of I. -6 bytes thanks to ngn from rearranging the definition of 'S' 'NE' 'NW' 'N' 'SW' 'SE' and from rearranging how t is defined (it is no longer a separate variable). -7 bytes thanks to ngn from golfing how s is defined.
{M←⊃⍸≠⌿↑1+P Q←⍵{(⍵/3)⊤⍺-+/3*⍳⍵}¨⌊3⍟1+⍵×2⋄(∪¨↓6 2⍴'SSNENWNNSWSE')[P[I],3+Q↓⍨⊃⌽I←⍬{M≥≢⍵:⍺⋄(⍺∘,∇↑∘⍵)s[⊃⍋|M-s←⌽⊢.⊢⌸⍵]}P]}

Try it online!
An explanation of the bug in the algorithm
The basic problem is that I went thought the shortest path went directly through the common ancestor, and could not, in fact, go through an ancestor of the common ancestor. This is incorrect as the following examples will demonstrate.
From 66 to 5
66 → 0 2 2 2 → 0 2 2 2
5  → 0 1     → 0 1
      ↑ common ancestor

The two ancestors of 0 2 2 2 are:
0 2 2
(empty)

(empty) has the shorter path back to 0 1 as it only needs two forward moves,
while 0 2 2 requires two more backtracks and one more forward move.

From 299792458 to 45687
299792458 → 0 2 1 1 0 1 1 2 1 1 1 2 1 0 2 2 2 0
45687     → 0 2 1 1 0 1 1 1 2 2
                         ↑ common ancestor

The three ancestors of 299792458 are:
0 2 1 1 0 1 1 2 1 1 1 2 1 0 2 2 2
0 2 1 1 0 1 1 2 1 1 1 2            ← choose this one
0 2 1 1 0 1 1 2 1 1 1 2 1 0 2 2

And the three ancestors of 0 2 1 1 0 1 1 2 1 1 1 2 are:
0 2 1 1
0 2 1 1 0 1 1 2 1 1
0 2 1 1 0 1 1 2 1 1 1

0 2 1 1 0 1 1 1 2 2    ← 45687 for reference
             ↑ common ancestor

While it seems like `0 2 1 1` is the shorter path,
it actually results in a path that is 8 steps long
(2 backtracks, 6 forward steps to 45687).

Meanwhile, `0 2 1 1 0 1 1 2 1 1` is at an equal distance
to the common ancestor and has the following ancestors:
0 2 1 1
0 2 1 1 0 1 1 2 1
0 2 1 1 0 1 1

0 2 1 1 0 1 1 1 2 2    ← 45687 for reference
             ↑ common ancestor

Clearly, this is the superior path, as with three backtracks, we have reached
the point of the common ancestor. With 3 backtracks and 3 forward moves,
we have a path that is 6 steps long.

Explanation of the code
                       ⍝ ⍵ should be an array of 2 integers, x y
SierpinskiPath←{⎕IO←0  ⍝ 0-indexing
        ⍝ P Q←{...}¨⍵  ⍝ First, the bijective base-3 numeration of x and y
    P Q←{
        n←⌊3⍟1+⍵×2  ⍝ The number of digits in the numeration
        z←+/3*⍳n    ⍝ The number of numerations with ≤ n digits
        (n/3)⊤⍵-z   ⍝ And a simple decode ⊤ (base conversion) of ⍵-z
    }¨⍵             ⍝ gets us our numerations, our paths

    A←↑1+P Q      ⍝ We turn (1+P Q) into an 2-by-longest-path-length array
                  ⍝ ↑ pads with 0s and our alphabet also uses 0s
                  ⍝ So we add 1 first to avoid erroneous common ancestor matches
    Common←⊃⍸≠⌿A  ⍝ We find the length of the common ancestor, Common

        ⍝ I←⍬{...}P  ⍝ Now we get the shortest backtracking path from P
    I←⍬{
        Common=≢⍵:⍺       ⍝ If P is shorter than Common, return our backtrack path
        s←⌽⊢.⊢⌸⍵          ⍝ Get the indices of the most recent N SW SE
        t←s[⊃⍋|Common-s]  ⍝ and keep the index that is closest to Common
                          ⍝ and favoring the ancestors to the right of
                          ⍝ Common in a tiebreaker (which is why we reverse ⊢.⊢⌸⍵)
        (⍺,t)∇t↑⍵         ⍝ Then repeat this with each new index to backtrack
    }P                    ⍝ and the path left to backtrack through

    Backtrack←P[I]   ⍝ We get our backtrack directions
    Forward←(⊃⌽I)↓Q  ⍝ and our forward moves to Q
                     ⍝ starting from the appropriate ancestor
    (∪¨↓6 2⍴'SSNENWNNSWSE')[Backtrack,Forward]    ⍝ 'S' 'NE' 'NW' 'N' 'SW' 'SE'
}                    ⍝ and return those directions

Alternative solution using Dyalog Extended and dfns
If we use ⎕CY 'dfns''s adic function, it implements our bijective base-n numeration (which was the inspiration for the version I use) for far fewer bytes. Switching to Dyalog Extended also saves quite a number of bytes and so here we are. Many thanks to Adám for his help in golfing this. Golfing suggestions welcome!
Edit: -8 bytes due to changing how P and Q are defined. -14 bytes due to switching to Dyalog Extended. -2 due to using a full program to remove the dfn brackets {}. +17 bytes due to fixing a problem where my algorithm was incorrect with many thanks to ngn for help with figuring the s[⊃⍋|M-s] section. +1 byte to bug fixing. -2 bytes thanks to Adám from rearranging the definition of I and -1 byte from remembering to put my golfs in both solutions. -3 bytes thanks to ngn by rearranging the generation of the cardinal directions, +1 byte from correcting a buggy golf, and -3 bytes thanks to ngn by rearranging how t is defined (it is no longer a separate variable). -7 bytes thanks to ngn by rearranging how s is defined.
APL (Dyalog Extended), 123 115 101 99 116 117 114 109 102 bytes
M←⊃⍸≠⌿↑1+P Q←(⍳3)∘⌂adic¨⎕⋄(∪¨↓6 2⍴'SSNENWNNSWSE')[P[I],3+Q↓⍨⊃⌽I←⍬{M≥≢⍵:⍺⋄(⍺∘,∇↑∘⍵){⍵[⊃⍋|M-⍵]}⌽⊢.⊢⌸⍵}P]

Try it online!


text:
Find the number in the Champernowne constant
Introduction
In base 10, the Champernowne constant is defined by concatenating representations of successive integers. In base 10: 0.1234567891011121314151617... and so on.
You can see that the first appearence of 15 starts at the 20th decimal:
  Position
  0000000001111111111222222222233333333334444444444555555555566666666
  1234567890123456789012345678901234567890123456789012345678901234567
                     ^
0.1234567891011121314151617181920212223242526272829303132333435363738...
                     ^^
                     15 = position 20

The first appearence of 45 starts at the 4th decimal:
  Position
  0000000001111111111222222222233333333334444444444555555555566666666
  1234567890123456789012345678901234567890123456789012345678901234567
     ^
0.1234567891011121314151617181920212223242526272829303132333435363738...
     ^^
     45 = position 4

So, the task is easy. Given a non-negative integer, output the position of the integer in the Champernowne constant.
Rules

You may provide a function or a program
This is code-golf, so the submission with the least amount of bytes wins!

Test cases
Input: 20
Output: 30

Input: 333
Output: 56

Input: 0
Output: 11 (note that the 0 before the decimal point is ignored)

Input: 2930
Output: 48

What's the highest position we need to work for? Eg, will the number ever be 987654321123456877654234354675.

@MorganThrapp I'll probably test integers in the range 0 <= x <= 99, but it should theoretically work for integers higher than 99.

Obligatory OEIS

Pyth, 10
hxjkS+QT`Q

Concatenates first input + 10 numbers then finds the 0 based index plus one.. The extra ten are only needed for 0.
Test Suite

I think implicit input was implemented before 2015-12-17 15:01:23Z or something?

@EriktheOutgolfer It was added in 2016: https://github.com/isaacg1/pyth/commit/3f7cbe42d143eeeb7eb1633bdf3d5a7fdb348007

LabVIEW, 29 LabVIEW Primitives
This uses strings for now. It matches the input as a pattern and outputs the offset - (input lenght -1).

Javascript, 57 bytes
a=prompt();for(y=b=" ";y<a+11;)b+=++y;alert(b.indexOf(a))

Saved 1 byte thanks to Conor O'Brien.

I think you can move the y= part to the y=b=" "; incrementing a space is like incrementing zero. (a=prompt(y=b=" ");...)

@CᴏɴᴏʀO'Bʀɪᴇɴ Nice find.

Japt, 11 bytes
This was originally beating Pyth, but apparently it didn't work for input 0.
1+1oU+B ¬bU

Try it online!
How it works
1+1oU+B ¬ bU
1+1oU+B q bU  // Implicit: U = input integer
  1oU+B       // Generate the range [0, U+11).
        q bU  // Join and take the index of U.
1+            // Add one to get the correct result.
              // Implicit: output last expression

Why does your "How it works" section contains a q in the code and not the logical negation symbol ¬?

@Fatalize ¬ is a shortcut for q  (that's q with a following space). This seems to often be a point of confusion, so I've lined up the shorter version with the full one.

Haskell, 62 bytes
a#b|and$zipWith(==)a b=1|1<2=1+a#tail b
(#(show=<<[1..])).show

Usage example: (#(show=<<[1..])).show $ 2930-> 48.
How it works: a # b finds the position of a within b: if a is prefix of b return 1, else add 1to a recursive call with a # tail b.  The pointfree function (#(show=<<[1..])).show expects an (unnamed) argument n and calls show n # show=<<[1..].
The function subIndex would also do the job of #, but the required import Data.List.Utils doesn't pay off.

I don't think you need the .show

And some friendly competition. albeit two years late.

Ruby, 28
->n{[*0..n+10]*''=~/\B#{n}/}

Includes a 0 at the beginning so that matches are 1-indexed, but uses \B to require that the match not be at the beginning of the string.

Lua, 54 Bytes
s=""for i=1,1e4 do s=s..i end print(s:find(io.read()))

Note: Currently this program prints both the first occurrence of the first char of the string, and the point where it ends. If this is not allowed, it will cost a few more bytes. I would like to petition for a bonus because my program prints out both the first position and last position of the input number.

Do you mean the start indices and end indices for the first occurence of the number?  Because theoretically the number would be in there an infinite amount of times.

Yeah, start and end for the first occurrence.

MATL (release 1.0.1), 22 bytes
iXK10+:"@Ys]N$hKYsXf1)

Example
>> matl iXK10+:"@Ys]N$hKYsXf1)
> 333
56

Explanation
i       % Input
XK      % Copy to clipboard K
10+     % Add 10. This is needed in case input is 0
:       % Vector of equally spaced values, starting from 1
"       % For each
  @Ys   %   For loop variable as a string
]       % End
N$h     % Horizontal concatenation of all stack contents
KYs     % Paste from clipboard K (input number) and convert to string
Xf      % Find one string within another
1)      % First value

MATL (release 20.8.0), 16 bytes (language postdates challenge)
Credit to @Giuseppe for this version of the program (slightly modified)
10+:"@V]&hGVXf1)

Try it online!
Explanation
10+     % Implicit Input. Add 10. This is needed in case input is 0
:       % Vector of equally spaced values, starting from 1
"       % For each
  @V    %   For loop variable as a string
]       % End
&h      % Horizontal concatenation of all stack contents
GV      % Paste from automatic clipboard G (input number) and convert to string
Xf      % Find one string within another
1)      % First value

I don't think this handles 0 :(

@David Now it does. Thanks for noticing! It only cost 3 bytes :-)

now that clipboard G contains the input (and implicit input), I guess this answer can be shortened by quite a lot, and all the Ys need to change to V anyway; I came up with 10+:"@Vv]!GVXf1) for 16 bytes.

@Giuseppe Thanks for the heads-up! Updated, with due credit (and with a "language postdates challange" note; I'm not a big fan of the new rule)

I don't mind that rule so much (the flags one drives me crazy, though); I was mostly commenting here since I noticed that Ys needed to change to V to use in the most up-to-date version of the interpreter. I'm always impressed with how much the language has improved!

@Giuseppe Thanks! Yes, I'm not a big fan of that other rule either...

MATL, 22 bytes
it10+:Yst' '=~)wYsXf1)

Take the input (i), make the vector 1 to input+10 (10+:), converts the vector to a string (Ys), and remove the spaces, which is painful, (t' '=~)). Then, convert the input to a string (Ys), find where the input string is in the string of numbers (Xf) and take the first location (1)). The t's and w's are manipulating the stack (duplicate and swap, respectively).

PowerShell, 39 44 bytes
[Edit: my assumption doesn't hold, building an array from 1-0 doesn't find 0 at place 11. Instead, build from 1-x+10 to handle 0 as well, now 44 bytes]
param($i)(1..($i+10)-join'').IndexOf("$i")+1

You will always find x when building a string of the Champernowne constant at the latest point when you add x onto the end, so an array from 1-x will always have the answer in it. The question becomes "does it occur any sooner than that?". This code
param($i)(1..$i-join'').IndexOf("$i")+1

e.g.

PS C:\Temp> .\Champer.ps1 20
30

generates a range of numbers, casts it to a string, and searches for the parameter inside it. Because PowerShell is an object oriented shell, the parameter is actually an [int] type, so trying to save two characters with .IndexOf($i) would search the string for an integer and find nothing. That's why I use string interpolation "$i".

Clever way of doing it. Frustrating that .IndexOf() apparently has higher operating preference than unary -join forcing the parens and quotes. :-/

PowerShell, 54 50 Bytes
for($c='';!($x=$c.IndexOf("$args")+1)){$c+=++$i}$x

Thanks to TessellatingHeckler for the idea of swapping the while loop for a for loop.
Executes via a for loop. As with other languages, the first statement in the loop can construct variables and assignments, so this starts with $c equal to just the empty string '' so that we have zero-indexing of the string lining up with the decimal indexing of the challenge. We're then in a loop that checks whether $c has the input integer ($args) somewhere within it (i.e., since .IndexOf() returns -1 if the string isn't found, we add one to that (0) and not it ($TRUE) to continue the loop). If it's not found, we add on our pre-incremented $i counter variable, then recheck the string. Once the string is found, .IndexOf() will return a positive value, the not of which will be $FALSE, breaking out of the loop. Finally, we output the index with $x.

Ideal for a classic for loop... for($c='.';($x=$c.IndexOf("$args"))-lt0;$c+=++$i){}$x and save 1 character. Since most of the IndexOf calls will return -1, add one to it and boolean ! cast it, for a shorter test. But you need parens to do that. Empty $c and +1 inside existing parens, bonus it's shorter. for($c='';!($x=$c.IndexOf("$args")+1);$c+=++$i){}$x 51 bytes. (but I posted my 39 byte one as its own answer because it's a completely different approach :P).

@TessellatingHeckler Nice way to rewrite the loop - thanks! I moved the $c concatenation into the loop to golf a semicolon. Now at 50.

JavaScript (ES6), 40 bytes
x=>(f=n=>n?f(n-1)+n:" ")(x+11).search(x)

Uses the recursive function f to avoid loops. The search method works the same as indexOf except that it takes a RegExp as a parameter, which is irrelevant for this challenge.
Adding a " " for the n=0 case (zero is falsy in JS) coerces the + to perform string concatenation instead of addition, and corrects for zero-based indexing.

Python 3, 54.
print(''.join(map(str,range(1,9**7))).find(input())+1)

CJam, 11 bytes
r_i),s\#Be|

Test it here.
I'm finding the position of N in the string 01234...N to account for the 1-based indexing. Finally I fix 0 by applying logical OR with 11.

Seriously, 13 bytes
;≈9u+R`$`MΣí

Takes input as an integer. Contains unprintables, so hexdump:
0c3bf739752b526024604de4a1

Try it online
Explanation:
;≈9u+R`$`MΣí
<form feed>   push str(input)
;≈9u+R        dupe, push [1,...,input+10]
      `$`MΣ   string concatenation of list
           í  get index of input

, 13 chars / 22 bytes
1+⩥(1,ï+ḋ)⨝ÿï

Try it here (Firefox only).

k4, 21 bytes
{*1+(,/$1+!10+x)ss$x}

Same algo as everyone else—concatenate [1..10+x] as strings, search for x as string, convert to one-based indexing, return first hit.
Checking the test cases:
  &/20 4 30 56 11 48={*1+(,/$1+!10+x)ss$x}'15 45 20 333 0 2930
1b

Mathematica, 101 bytes
(If[#==0,11,m=Min@SequencePosition[s=Flatten[(K=IntegerDigits)/@Range[0,#]],K@#];Length@s[[;;m-1]]])&

Haskell, 82 73 55 bytes
Migrated from the duplicate
x!b|or$zipWith(==)x b=0
x!(_:b)=1+x!b
(!(show=<<[1..]))

Try it online!
Explanation
First we define !.  x!b truncates b to the first appearance of x.  It does this by checking if b starts with x (or$zipWith(==)x b) returning x if it does and moving one down the string otherwise.  Then we define our main function.  Our main function is a point-free function that takes the constant (show=<<[1..]) and truncates it to the first appearance of x.  This takes x as a string.

Jelly, 5 bytes
+⁵RVw

Try it online!

JavaScript (ES6), 50 39 38 bytes
x=s=``
f=n=>-~s.search(n)||f(n,s+=++x)

Try it

x=s=``
f=n=>-~s.search(n)||f(n,s+=++x)
o.innerText=f(i.value=15);oninput=_=>o.innerText=f(+i.value)
<input id=i type=number>

05AB1E, 6 bytes
nLJsk>

Try it online!

Stax, 6 bytes
⌐╛∙#»▓

Run and debug it

Perl 6, 26 bytes
{[~](0..$_).index($_)||11}

Try it online!
Finds the index of the element in the concatenated range from 0 to that element, or 11 if the number is a zero

Husk, 6 5 bytes
€ṁdNd

Try it online!
-1 thanks to Razetime
€        The 1-based index, in
  d      decimal digits
 ṁ       concat-mapped over
   N     all natural numbers,
    d    of the decimal digits of the input.

-1

@Razetime Knew how you did it before I clicked the link!

Vyxal, 6 bytes
₁+ɾṅḟ›

Try it Online! ɾṅḟ would be enough if not for the zero edgecase.
₁+ɾṅḟ›
     › # 1 +
    ḟ  # Index of input in
   ṅ   # Concatenation of
  ɾ    # 0...
₁+     # 100+n

Perl 5, 42 31 + 1 (-p) = 32 bytes
(join'',0..$_+10)=~/$_/;$_="@-"

Try it online!
Explanation
(join'',0..$_+10)   # concatenate all of the numbers from 0 to 10 over the input
=~/$_/;             # skip the first 0, then find the input
$_="@-"             # @- holds the index of the start of the last match

J, 30 Bytes
{.I.(":E.[:}.' '-.~":@i.@+&11)

Could probably be golfed down a bit more, specifically in concatenating the first n+10 integers.
Explanation:
{.I.(":E.[:}.' '-.~":@i.@+&11)
                      i.@+&11   | Integers 0 to n+10
                   ":@          | Format list to string
             ' '-.~             | Strip spaces
           }.                   | Behead (remove leading 0)
         [:                     | Cap (previous verbs executed in order, not as a fork)
     ":E.                       | Find matches to the string n (returns a boolean vector)
  I.                            | Indexes of 1s
{.                              | Take only the first

Note that this is 0-indexed. Examples:
    {.I.(":E.[:}.' '-.~":@i.@+&11) 1
0
    {.I.(":E.[:}.' '-.~":@i.@+&11) 0
10
    {.I.(":E.[:}.' '-.~":@i.@+&11) 333
55

Perl 6/Rakudo 29 bytes
{$_~=$++until /(.+)$^a/;$0.chars}

Defines a function with one input ($^a). Call thus:
say {$_~=$++until /(.+)$^a/;$0.chars}(333)
> 56

Appending $, an anonymous variable, incrementing $++ until the input $^a is found, and then counting the number of chars before it. Requiring at least 1 char before it .+ in the regex usefully excludes the 0->0 case