text:
Help Me Play My Harmonica
Yesterday, I bought a harmonica:

Figure 1: The harmonica.
However, my dreams of being able to play soulful blues harmonica that moves people and causes a grown man to cry were quickly dashed by two problems:

The harmonica can only play certain notes;
I am depressingly bad at playing the harmonica.

Despite my lack of skill at the harmonica, there are still some songs that I can play on it. However, it is not immediately obvious if I am able to play some piece of music on the harmonica or not. Given the notes of a piece of music, write a program to determine if I could play it on my harmonica or not.
As the above picture shows, my harmonica has ten holes in it. With each hole, I can either exhale into it or inhale into it -- the hole that I choose, and whether I inhale or exhale into it changes the pitch of the resulting sound. Each hole has a different pitch on exhaling and inhaling, but there are some combinations that result in the same note. Overall, my harmonica can play 19 unique different pitches. The pitches are presented in musical scientific notation - the letter represents the note, and the number represents which octave it is in.
 Hole   Breathing   Note
 1      Exhale      C4
 1      Inhale      D4
 2      Exhale      E4
 2      Inhale      G4
 3      Exhale      G4
 3      Inhale      B4
 4      Exhale      C5
 4      Inhale      D5
 5      Exhale      E5
 5      Inhale      F5
 6      Exhale      G5
 6      Inhale      A5
 7      Exhale      C6
 7      Inhale      B5
 8      Exhale      E6
 8      Inhale      D6
 9      Exhale      G6
 9      Inhale      F6
 10     Exhale      C7
 10     Inhale      A6

For example, if I exhaled on hole 3, I'd get a G4 note. If I inhaled on hole 2, I'd also get a G4 note. If I exhaled on hole 7, I'd get a C6.
When I breathe into the harmonica, apart from exhaling or inhaling, I can also choose whether to breathe thinly or widely. Breathing thinly causes only one hole to sound, whereas breathing widely causes one hole and both holes on either side of that hole to sound. I do not have the embouchure skills to blow onto two holes - it is either one or three.
For instance, if I thinly exhaled onto hole 4, only hole 4 would sound, so I would get a C5 sound. If I widely exhaled onto hole 4, holes 3, 4, and 5 would sound, and I'd get a G4,C5,E5 chord. If I widely inhaled onto hole 4, holes 3, 4, and 5 would sound but they would play the inhale pitches instead, which results in a B4,D5,F5 chord. Note that for the holes on either end, if I breath widely into them only two holes would sound (because there is no hole 0 or hole 11).
However, I cannot inhale and exhale at the same time.  For instance, I could exhale into holes 4, 5, and 6 to result in the notes C5, E5, and G5 sounding at the same time, forming a chord. However, I can't inhale and exhale at the same time, so it would be impossible for me to play the chord C5,F5,A5 as I'd have to somehow exhale in hole 4 and inhale in hole 5 and 6. If this is stil unclear, this comment thread might be useful.
The input is the notes of the music. The notes are notated in the same way they are above in the table, and they are comma separated. Notes wrapped in curly brackets represent a chord. For instance:
C4,D4,G4,{D5,F5,A5},B5

This means, "C4, then D4, then G4, then D5, F5, and A5 at the same time, then B5." Your program will take a string in this format as input and output True if it is possible for me to play the music on my harmonica, or False otherwise. For sample inputs and outputs, the example above should output True. The input {C5,F5,A5} on the other hand will output False.
This is code golf, so the shortest entry wins.
Here are some test cases:
Input (A C Major scale):
C4,D4,E4,F4,G4,A4,B4,C5

Output:
False

(because the harmonica cannot play F4 or A4)
Input (the opening 2 bars of Let It Go):
E6,F6,A5,E6,F6,F6,E6,A5,F6,E6

Output:
True

Input:
{E6,G6,F6}

Output:
False

Input:
{G4,C5,E5},{F5,A5,B5}

Output:
True

You may assume that chords will come in lower to higher pitch order.

Do you have to alternate exhaling and inhaling moving from note to note?

@COTO No. Assume I have infinite breath capacity.

the referenced comment thread link doesn't work for me. this works for me: http://meta.codegolf.stackexchange.com/a/2149/3348

do you have a set of test cases we can use?

@adrnew Sure, I'll edit some in now.

I CAN play bluesharp (Richter tuned harmonica), but I only play blues on it. Hole 7 with C6 going DOWN to B5 looks strange but is correct. You have two solutions: buy a more advanced harmonica with different tuning, or learn to bend the notes (if you can bend, you STILL won't be able to play all the notes, but you can play a howling blues to express your frustration.) The rule about only being able to play 1 or 3 notes is fairly accurate. Here's a nice representation of Richter tuning: http://en.wikipedia.org/wiki/Richter-tuned_harmonica. Section on different keys is also musically interesting

Python - 218 209 189 chars
Minimal:
def t(s):from re import sub as r;exec('l=bool([x for x in['+r('"{','("',r('}"','")',r(',','","','"'+s+'"')))+']if"".join(x)not in"C4E4G4C5E5G5C6E6G6C7|D4G4B4D5F5A5B5D6F6A6"])');return not l

For ease of reading:
def t(s):
    from re import sub as r
    exec('l=bool([x for x in'
         ' [' + r( '"{' , '("' ,
                  r( '}"' , '")' ,
                    r( ',' , '","' , '"' + s + '"' ))) +
         ']'
         ' if "".join(x) not in "C4E4G4C5E5G5C6E6G6C7|D4G4B4D5F5A5B5D6F6A6"])')
    return not l

Given a string formated as in the problem description, t return True if the sequence is playable on the described harmonica, and False if it isn't.
There is no check for the order of the notes in the chords. Unless told otherwise, I believe this is sufficient since that isn't in the problem statement, and it passes all given tests in:
assert not t("C4,D4,E4,F4,G4,A4,B4,C5")
assert t("E6,F6,A5,E6,F6,F6,E6,A5,F6,E6")
assert not t("{E6,G6,F6}")
assert t("{G4,C5,E5},{F5,A5,B5}")

You can remove a lot of spaces: ] if "".join(x) not -> ]if"".join(x)not Keywords can be adjacent to strings so "and" is correct.

First code golf here so I figured I was missing something. Thanks!

Javascript - 245 243 chars
Minified:
function p(s){function f(s){s=s.replace(/\W/g,'');l=s.length;return((l-6)*(l-2)?l-4?'':'C4E4 G6C7 D4G4 F6A6':'C4E4G4C5E5G5C6E6G6C7 D4G4B4D5F5A5B5D6F6A6').indexOf(s)<0?0:''}return s.replace(/{.*?}/g,f).split(',').map(f).join('')?'False':'True'}

And expanded:
function p(s) {
    function f(s) {
        s = s.replace( /\W/g, '' );
        l = s.length;
        return ( (l-6)*(l-2) ? ( (l-4) ? '' : 'C4E4 G6C7 D4G4 F6A6' ) : 'C4E4G4C5E5G5C6E6G6C7 D4G4B4D5F5A5B5D6F6A6' ).
            indexOf( s ) < 0 ? 0 : ''
    }
    return s.replace( /{.*?}/g, f ).split( ',' ).map( f ).join( '' ) ? 'False' : 'True'
}

The function p accepts a string as input and returns True if the note/chord sequence is playable, False otherwise.
It returns undefined results if the input isn't syntactically valid.
It also boldly assumes that chord notes are entered in order of ascending hole (such as in the example).
The character count can be reduced by 14 if the function is allowed to return logical true and false rather than their string equivalents.

JavaScript (ES6), 230
Just a rewritten version of @COTO's answer:
f=s=>{s=s.replace(/\W/g,'');l=s.length;return((l-6)*(l-2)?(l-4?'':'C4E4 G6C7 D4G4 F6A6'):'C4E4G4C5E5G5C6E6G6C7 D4G4B4D5F5A5B5D6F6A6').indexOf(s)<0?0:''};p=s=>{return s.replace(/{.*?}/g,f).split(',').map(f).join('')?'False':'True'}

Would appreciate any tips on golfing this down further as I am starting to learn ES6! :-)

JavaScript ES6, 211 209 190 chars
I know this can be golfed further. I will try to do so in a few hours;
Run this code in Latest Firefox's Web Console, you will get a method named C which you can then call like C("{G4,C5,E5},{F5,A5,B5}") and it will return True or False accordingly.
C=n=>(s='D4G4D5F5A5B5D6F6A6,C4E4G4C5E5G5C6E6G6C7',n.split(/[,}{]/g).some(a=>a&&!~s.search(a))||(m=n.match(/{[^}]+/g))&&m.some(a=>a.length!=9|!~s.search(a.replace(/{|,/g,"")))?'False':'True')

I am assuming a syntactically valid input.
EDIT: Simplified the regex and the length check.

Scala 178
print(readLine./:(""){(a,c)=>if("..C4E4G4C5E5G5C6E6G6C7...D4G4B4D5F5A5B5D6F6A6...."sliding(6)flatMap(y=>Seq("{"+y.diff("..")+"}",y take 2))contains a+c)""else a+c diff ","}=="")

Ungolfed:
print(
  readLine.foldLeft(""){(a,c)=>                             # loop through the input
    if("..C4E4G4C5E5G5C6E6G6C7...D4G4B4D5F5A5B5D6F6A6...."  # from the harmonica
      .sliding(6)                                     # take 6 at a time
      .flatMap(y=>Seq("{"+y.diff("..")+"}",y take 2)) # chords + single notes
      .contains(a+c)) ""                              # clear matches
    else a+c diff ","                                 # drop commas
  }==""                                               # did everything match?
)

Note that malformed input is handled badly - any string is accepted, and many malformed strings return true, for example:
{C,7.D}.C

prints true.

Rebol - 188
t: func[s][trim/with s ","h: next split n:"C4E4G4C5E5G5C6E6G6C7..D4G4B4D5F5A5B5D6F6A6"2 forskip h 2[i

Ungolfed:
t: func [s] [
    trim/with s ","
    h: next split n: "C4E4G4C5E5G5C6E6G6C7..D4G4B4D5F5A5B5D6F6A6" 2
    forskip h 2 [insert h '|]
    h: head h

    parse s [
        any [
            h | "{" x: copy c to "}" (unless find n c [c: n])
            :x c "}"
        ]
    ]
]

Example usage (in Rebol console):
>> t "C4,D4,G4,{D5,F5,A5},B5"
== true

>> t "{C5,F5,A5}"
== false

>> t "C4,D4,E4,F4,G4,A4,B4,C5"
== false

>> t "E6,F6,A5,E6,F6,F6,E6,A5,F6,E6"
== true

>> t "{E6,G6,F6}"
== false

>> t "{G4,C5,E5},{F5,A5,B5}"
== true

While this code will catch gibberish like this:
>> t "{C,7.D}.C"
== false

However it will allow things like this through:
>> t "C,4,D4"
== true

Because its parsing it as "C4,D4".
Here's a more stricter version of the code:
t: func [s] [
    h: next split n: "C4E4G4C5E5G5C6E6G6C7..D4G4B4D5F5A5B5D6F6A6" 2
    forskip h 2 [insert h '|]
    h: head h
    d: ["," | end]

    parse s [
      any [
            [
                h | "{" x: copy c to "}" (
                    unless all [
                        parse c [any [h d]]
                        find n trim/with copy c ","
                    ] [c: n]
                )
                :x c "}"
            ]
            d
      ]
    ]
]

This golfs down to 228 chars and now returns false on...
>> t "C,4,D4"
== false

source: Stack Exchange

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

sort: votes


text:
What's that number in Shortlex?
Most computers store integers in binary, but output them in decimal. However, decimal is just one representation, we just happen to find it convenient.
This challenge is to write some code to output an integer value in shortlex decimal.
What's that?
http://en.wikipedia.org/wiki/Shortlex_order
Shortlex takes the length of the sequence of digits as the primary signifier of value. The sequence, starting from an empty string representing zero, is...
ε,0,1,...,8,9,00,01,...98,99,000,001,...,998,999,0000,...

(Think of Excel columns, but using only the decimal digits.)
Write a program or function that accepts an integer and returns a string corresponding to the shortlex-decimal representation of that integer as described above.
Test values:
0 → ""  (Empty string)
1 → "0"
10 → "9"
11 → "00"
42 → "31"
100 → "89"
800 → "689"
1060 → "949"
10270 → "9159"
100501 → "89390"

It might be important to note that the sequence 19, 20, 21, 22 in decimal maps to 08, 09, 10, 11 in shortlex. That's why I used confused that 100 -> 89!

Related

Note that what you're calling the "shortlex decimal" of a number is also its bijective base-ten numeral, with symbols {0,1,2,3,4,5,6,7,8,9} substituted for the usual digits {1,2,3,4,5,6,7,8,9,A}. E.g, 2014 in the usual bijective base-ten notation is 1A14, and in shortlex decimal it is 0903.

JavaScript (ES6) 42 74
n=>(n-~(n+'').replace(/./g,8)+'').slice(1)

Test in FireFox console
;[0,1,10,11,42,100,800,1060,10270,100501]
.forEach(x => console.log(x +" -> '" + S(x) + "'"))

Output
0 -> ''
1 -> '0'
10 -> '9'
11 -> '00'
42 -> '31'
100 -> '89'
800 -> '689'
1060 -> '949'
10270 -> '9159'
100501 -> '89390'

How did I think of this?
Given a fixed number of digits, the output sequence is simply ascending, so there is a fixed delta between input and output. Have a look:
  1..10 -> 0..9 (delta -1)
 11..110 -> 00..99 (delta -11)
111..1110 -> 000..999 (delta -111) mmm there's a pattern here...

But the leading 0s are difficult to manage, so I have a standard trick, add a first digit and work modulo (that is, cut the first digit in output). Then -1-> +9, -11 -> +89, -111 -> +889 and so on.
Last step: I don't care what the first digit is, so there is no need to check if the iinput number is < or > than 111... (honestly I found this by trial and error)
Test

var F=
n=>(n-~(n+'').replace(/./g,8)+'').slice(1)

function update()
{
  var i=+I.value
  O.textContent = F(i)
}

update()
<input id=I value=99 type=number oninput='update()'>

I have no idea why this works.

Why do you do n-~(n+'') instead of just n-~n?

@Claudiu it's (n+'').replace(...), replace works on strings, not numbers.

@edc65: Oops yes just caught it now, mismatched my parentheses. Dayum this is quite brilliant

That's very clever! It would make a mean CJam answer (14 bytes).

@Dennis feel free to port it. You are winning already

Marbelous 177 173 170
@0@6000000@5
}0&0&0&0&0
>0@6&3
\\--\/&2
@0/\@4\/&1!!
@4@1..@2@5@3
IIIIIIIIIIII
FF&1FF&2FF&3
@1OO@2OO@3OO
:I
}1..}10001F7
=9&1++..&1&0
&0}0&1&0{1{1
{>\/{0//
:O
}0
+Z
+C
{0

It works for only for values under 256 since Marbelous is an 8 bit language.
How it works
Marbelous is a 2D language with values represented by 8 bit marbles that fall down one cell on each tick unless some device prevents them from falling down. This Marbelous program consists of 3 boards; let's start with the easiest one:
:O
}0
+Z
+C
{0

:O is the name of the board (to be precise, O is the name and : tells the interpreted that this line is a name. By giving boards a name, other boards can call on them
}0 is an input device, this can be seen as an argument of this function. This cell will get replaced by an input marble (value) when the function gets called.
+Z adds 35 to any marble that passes over it and lets it fall through. +C does the same but only adds 12. {0 is an output cell, when a marble reaches this cell, the function will exit and return the value in this output device.
So all together, this board takes one value and then adds 47 to it. For us this means it turns any single digit number into the ascii code of the digit -1 (this will of course also work for 10).
:I
}1 .. }1 00 01 F7
=9 &1 ++ .. &1 &0
&0 }0 &1 &0 {1 {1
{> \/ {0 //

This board is looking a bit more complicated. You should be able to identify :I as the name of the board and have spotted some input and output devices. You'll notice that we have two different input devices, }0 and }1. This means this function takes 2 inputs. You'll also notice that there are two instances of the }1 device. Upon calling the function, both of these cells will contain the same value. The }0 input device is directly above a \/ device, this acts as a trashcan and removes any marble that falls upon it immediately.
Let's have a look at what happens to one of the marbles put into the board by the }1 input devices:
}1
=9 &1
&0
{>

It will fall down on the first tick and hit the =9 device. This compares the value oif the marble to 9 and lets the marble fall through if the statement =9 evaluates to through. The marble gets pushed to the right if not. &0and &1 are synchronizers. They hold on to marbles that fall onto them until all other &nsynchronizers are filled as well. As you can expect, this will conditionally trigger different behaviour on some other part of the board.
}1 00 01 F7
++ .. &1 &0
&1 &0 {1 {1
{0 //

If I tell you that ++ is an incrementor, you should already be able to tell what the different synchronizers will be filled with. The left &1 will contain the input value }1 + 1, the &0 next to it will contain 0 (00 is a language literal, represented in hexadecimal). The second &1 will contain the value 1 and the right &0 gets filled with an F7, which subtracts 9 from a value since addition in Marbelous is modulo 256.
// is a deflector device, which pushes any marble to the left instead of letting it fall down.
Putting this all together gives you this: if the marble in }1 is 9, the &0 synchronizers get filled. This will cause the value 0 to fall into the {0 output and F7 (or -9) into the {1 output.
If }1 is not 9, {0 will be filled with }1 + 1 and {0 will contain 1.
There is also a {> device, this is a special output that outputs a marble next to a board in stead of underneath it. This will get filled with }1 if it equals 9.
@0 @6 00 00 00 @5
}0 &0 &0 &0 &0
>0 @6 &3
\\ -- \/ &2
@0 /\ @4 \/ &1 !!
@4 @1 .. @2 @5 @3
II II II II II II
FF &1 FF &2 FF &3
@1 OO @2 OO @3 OO

Okay, now for the big one. This board does not have an explicit name, since it is the main board of the file. Its implicit name is Mb. You should be able to recognize some cells. There is an input device, some language literals (00 and FF). There are some synchronizers and there's a deflector. lets step through this piece by piece.
@0 @6
}0 &0
>0 @6
\\ --
@0 /\ @4

So the input value (the command line input since this is the main board) starts at the second cell from the top where }0 is located. It will fall down and reach the >0 device, which is another comparison device. any marble larger than 0 falls through, any other marble gets pushed to the right. (since Marbelous variables are unsigned, only exactly 0 will get pushed to the right). This zero value marble will then hit the @6 device. This is a portal and transports the marble to another corresponding portal, in this case right above it. The 0 marble will then reach the &0 synchronizer and trigger some things elsewhere.
If the marble is not 0, it falls down, gets deflected to the right by \\ hits -- which decrements it by one and then falls onto /\, a cloner. This device takes a marble and outputs one copy of it to the right and one to the left. The left one will be taken upwards to the other @0 where the marble will go through the same sequence again. The left one will be taken elsewhere.
This gives us a loop, which decrements the command line input once per loop and triggers some behaviour on every loop until it reaches 0. It then triggers some other behaviour.
Let's have a look at what happens with the marble pushed into @4 on each loop.
@4 @1 .. @2 @5 @3
II II II II II II
FF &1 FF &2 FF &3
@1 OO @2 OO @3 OO

There are 3 language literals here (FF), which will immediately fall into portals. These portals will take them to three of the II devices. II refers to the board :I we defined further down the file. Since :I has 2 distinct input devices, it's representation on another board must be 2 cells wide. Since we have 6 cells containing II, we cam tell we have 3 instances of this function on the board.
The FF (or 256 or -1 if you will) marbles will sit in the input cells of the :I function waiting untill there are enough input marble sto start the function (one more that is). That's where the @4 portal comes in. A copy of the decremented command line input falls through there on each loop. This will trigger the leftmost :I board. Initialy with the values 256 (or -1) and whatever the command line input was -1. The left marble will be put into the }0 devices of the :I board and the right one into the }1. If you recall what this board did, you'll be able to tell what result this has. It will output an incremented version of the right input on the left output (and it turns a 9 into a 0, not 10) and outputs either 1 or -9 on the right.
The incremented value will be taken right back to the right input cell by a portal, and the value on the right falls into a synchronizer. If a synchronizer is already holding a marble, the two marbles will collide. Colliding marbles get added together modulo 256. So the values in the synchroizers will do the folowing: They start out empty, then turn to 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and then to 1 again (since 247 gets added modulo 256).
You also might remember that a marble gets output to the right when the input value loops back to 0. Since the :I boards are right next to each other, thsi will trigger the board to the right once. This will fill the three synchronizers with values that are one higher than they should be to be a shortlex representation of the command line input, by the time this has looped down to 0.
You might also remember that the :O function turns a value into the ascii value of the digit that represents the value -1. The output of these OO cells will then fall off the board, which prints their corresponding ascii chars to STDOUT.
00 00 00 @5
&0 &0 &0
&3
\/ &2
   \/ &1 !!
      @5

So what happens when the command line input marble reaches 0 and fills that &0 synchronizers? well, a few 0 value marbles fall down and trigger the three synchronizers that are holding the digits (+ 1) of the shortlex number at the bottom of the board. &3 gets triggered first, since it contain the most significant digit, then comes &2 followed by &1. This marble then gets teleported to the other @5 device before eventually hitting the !! cell, which terminates the board.

It almost looks as if this could be valid Perl code too

CJam, 14 11 bytes
l40f-Ab)s1>

Try it online.
How it works
This approach is heavily based on edc65's answer (with his explicit permission):
" Read a line L from STDIN. ";

l

" edc65's answer now forms an integer N by replacing each digit in L by an 8 and computes
  L - ~N = L + N + 1. Instead of adding L and N, we subtract 40 from each char code of L.
  Since the char code of the digit `D` is `D + 48`, this basically adds 8 to each digit.  ";

40f-

" Turn the resulting array into an integer by considering its elements a base 10 number.
  This is implemented as A ↦ A[-1] + 10 * A[-2] + 100 * A[-3] + ⋅⋅⋅, so it won't choke
  on digits greater than the base.                                                        ";

Ab

" Increment the integer on the stack to complete the calculation of L + N + 1.            ";

)

" Push the integers string representation and discard its first character.                ";

s1>

Example run
$ for i in 0 1 10 11 42 100 800 1060 10270 100501
> do echo $i: $(cjam <(echo 'l40f-Ab)s1>') <<< $i)
> done
0:
1: 0
10: 9
11: 00
42: 31
100: 89
800: 689
1060: 949
10270: 9159
100501: 89390

This is obscene

+1 for finding a way to shorten it even more

Python 2 (38)  (43)
f=lambda n:n*'_'and f(~-n/10)+`~-n%10`

No character substitution, just arithmetic.
Ungolfed:
def f(n):
    if n==0: return ''
    else: return f((n-1)//10) + str((n-1)%10)

I don't have a good reason why the recursion works, I just fit this pattern to the list of values. If you changed each n-1 to n, you'd get the regular digit representation.
For golfing, I use ~-n to compute n-1 with higher precedence than /10 or %10, saving on parens. The n*'_' is just to produce the empty string when n=0 and any other string otherwise. The '_' can be any string for this purpose.

Ruby, 70 68 66 64 57 bytes
f=->n{i=-1;n-=10**i while n>=10**i+=1;i<1?'':"%0#{i}d"%n}

Defines a function to be called like f[42]. Here is the rough breakdown of the algorithm:

Treat 0 separately.
Subtract powers of 10 until the next power of 10 doesn't fit into the number any more.
Turn the number into a string padded with zeroes on the left.

Credits for the idea of using a format string go to Falko!

Alternatively, using edc65's approach:
f=->n{"#{n-~n.to_s.tr('^.',?8).to_i}"[1..-1]}

That's 45 bytes and I'm only including it, because I'm not beating him with it. ;)

Sure. I guess I won't catch you anyway with my lengthy Python code. ;)

@Optimizer I'm sure if someone used that approach in one of the golfing languages they'd get below 20. (That being said, I can't quite reach 44 in Ruby with that approach... currently at 45)

@Optimizer I don't agree with that. For starters, J and APL aren't golfing languages and win about as often as GolfScript and CJam. But moreover, golfing isn't about the green checkmark but about beating submissions "in your league". If I write a Ruby submission that beats all but the those 4 languages I can be quite happy about that, and I don't need those to be banned to enjoy golfing in more verbose languages. In fact, a clever golf in a "normal" language like edc's is much more likely to get a lot of upvotes than a naive (but shorter) implementation in a golfing language.

Haskell, 67 bytes
n('9':x)='0':n x
n(c:x)=succ c:x
n""="0"
f x=reverse$iterate n""!!x

this solution basically adds 1 the given number of times, in shortlex notation.
usage:
>f 9
"8"
>f 100
"89"

CJam, 16 bytes
li_)9*,{`1>}%_&=

Try it online. Requires at least O(n) time and memory, so leave 100501 to the offline interpreter...
How it works
The basic idea behind this approach is to compute at least N shortlex decimals in their natural order and discard all but the Nth. Not very efficient, but short.
li                " Read an integer N from STDIN.                                   ";
  _)9*            " Push M := (N + 1) * 9.                                          ";
      ,           " Push A := [ 0 1 ... M - 1 ].                                    ";
       {   }%     " For each I ∊ A:                                                 ";
       {`1>}%     " Push its string representation and discard the first character. ";
             _&   " Remove duplicates from the resulting array.                     ";
               =  " Retrieve the Nth element.                                       ";

Example run
$ for i in 0 1 10 11 42 100 800 1060 10270 100501
> do echo $i: $(cjam <(echo 'li_)9*,{`1>}%_&=') <<< $i)
> done
0:
1: 0
10: 9
11: 00
42: 31
100: 89
800: 689
1060: 949
10270: 9159
100501: 89390

Bash+coreutils, 27 bytes
Port of @edc65's clever answer, with @Dennis's improvements:
cut -b2-<<<$[$1-~${1//?/8}]

Output:
$ for n in 0 1 10 11 42 100 110 111 800 1060 1110 1111 10270 100501; do echo "./shortlex.sh $n = \"$(./shortlex.sh $n)\""; done
./shortlex.sh 0 = ""
./shortlex.sh 1 = "0"
./shortlex.sh 10 = "9"
./shortlex.sh 11 = "00"
./shortlex.sh 42 = "31"
./shortlex.sh 100 = "89"
./shortlex.sh 110 = "99"
./shortlex.sh 111 = "000"
./shortlex.sh 800 = "689"
./shortlex.sh 1060 = "949"
./shortlex.sh 1110 = "999"
./shortlex.sh 1111 = "0000"
./shortlex.sh 10270 = "9159"
./shortlex.sh 100501 = "89390"
$

Previous answer:
Bash+coreutils, 71 54 bytes
Here's a slightly different way to do it:
jot -w%x $1$1|tr 0-9a a0-9|grep -P ^\\d+$|sed $1!d 2>-

jot outputs increasing hexadecimal integers
tr converts this to (0,1,...,8,9,b,...f,0a,00,01,...,99,9b,...,ff,0aa,...,000,...)
grep simply filters all lines containing digits to give (0,1,...,8,9,00,...,99,000....)
sed deletes all but the nth line
STDERR is redirected to a throwaway file '-' so that we simply get the empty string when 0 is passed in (sed counts line numbers starting at 1, so errors if 0 is passed)
Because we are filtering numbers out with grep, we need to generate more base 11 integers with seq/dc than the input number.  Repeating the digits of n is more than sufficient.

Note that once the shortlex number is printed, seq continues generating numbers up to $1$1, which slow especially for larger input numbers - O(n²), I think.  We can speed up by having the seq quit immediately after printing at the cost of 7 bytes:
jot -w%x $1$1|tr 0-9a a0-9|grep -P ^\\d+$|sed -n $1{p\;q} 2>-

There is no speed requirement in the question, so I'm going with the shorter version for my main answer.

@Optimizer nope: try s='jot -w%x $1$1|tr 0-9a a0-9|grep -P ^\\d+$|sed $1!d 2>-'; echo ${#s}. I suspect you might be using python to measure string length, which treats the "\" as one character.

My answer has changed by now, but if I did something clever in the first revision, it was entirely by accident. It was a direct por of edc65's answer; the 8's are all his... -- The auxiliary variable $a seems to be unnecessary; cut -b2-<<<$[$1-~${1//?/8}] should work just fine.

@Dennis Right I see.  Thanks for the suggestion!

Python 2 - 84, 70 66
n=input()
i=0
while n>=10**i:n-=10**i;i+=1
print"%%0%dd"%i%n*(i>0)

Alternative approach (same length):
n=input()
k=len(`9*(n+1)/10`)
print"%%0%dd"%k%(n-int('1'*k))*(n>0)

Using a format string is clever! I hope you don't mind if I use that as well. :)

Python 3, 107 characters
This didn't end up winning but I thought it was clever:
def G():yield'';yield from(r+c for r in G()for c in'0123456789')
S=lambda n:list(zip(range(n+1),G()))[n][1]

I define a generator for the entire sequence in 64 characters. Unfortunately, I have to go through some contortions to get the nth element of the generator... if only I could do S=lambda n:G()[n].

Pyth, 12
Another port of @edc65's answer, who is the clear winner (IMO):
t`+hQv*l`Q\8

Test package (Thanks to @DigitalTrauama):
$ for n in 0 1 10 11 42 100 110 111 800 1060 1110 1111 10270 100501; do echo "shortlex.pyth $n = \"$(pyth programs/shortlex.pyth <<< $n)\""; done
shortlex.pyth 0 = ""
shortlex.pyth 1 = "0"
shortlex.pyth 10 = "9"
shortlex.pyth 11 = "00"
shortlex.pyth 42 = "31"
shortlex.pyth 100 = "89"
shortlex.pyth 110 = "99"
shortlex.pyth 111 = "000"
shortlex.pyth 800 = "689"
shortlex.pyth 1060 = "949"
shortlex.pyth 1110 = "999"
shortlex.pyth 1111 = "0000"
shortlex.pyth 10270 = "9159"
shortlex.pyth 100501 = "89390"

Explanation:
Q = eval(input())             Implicit.
t`                            All but the first digit of
  +hQ                         Q+1 +
   v                          eval(
    *l`Q                      len(repr(Q)) *
     \8                       "8"

CJam vs Pyth; the battle continues. :P

I tried to give Pyth a shot for this challenge, but I couldn't find a way to turn a List into an integer (for example, [8, 8, 9] -> 889). How do you do that?

@Dennis To get from list to int, you basically have to go through string. jk will turn your list to a string, and v will turn that into an int. So vjk[8 8 9] will give the number 889.

OK, thanks. Sadly, string conversion makes some tricks impossible. With CJam/GolfScript base conversion, [2 -1] -> 19 and [1 11] -> 21.

@Dennis Yeah, once I actually add base conversion to Pyth, that will work. But I haven't yet.

Java 8, 60 bytes
n->(n-~new Long((n+"").replaceAll(".","8"))+"").substring(1)

Port of @edc65's amazing JavaScript (ES6) answer, since I doubt it can be done shorter in an arithmetic way in Java.
Try it here.

Haskell, 57 bytes
((g=<<[0..])!!)
g 0=[""]
g n=[c:s|c<-['0'..'9'],s<-g$n-1]

Try it online!
Constructs an infinite list of shortlex numbers and indexes into it for the answer. g n constructs the nth "generation" of numbers by prepending the next digit in front of each of the numbers in the previous generation.

05AB1E, 7 bytes
Uses edc65's replace by 8 trick
8sg×+>¦

Try it online!
Explanation
8          # push 8
 sg×       # repeat it len(input) times
    +      # add to input
     >     # increment
      ¦    # discard the first digit

Jelly, 5 bytes
ḃ⁵ịØD

Try it online!
I'm very new to Jelly, so if you can improve this, please comment!
Explanation:
ḃ⁵ịØD   Main link.
ḃ       Convert to bijective base ...
 ⁵      10.
  ị     Each number (1 - 10) is converted to the character at its index in the string...
   ØD   “0123456789” (digits)

(According to r.e.s.'s comment above, the problem is equivalent to convert the number to bijective base 10)

Excel, 37 bytes
Using @edc65's approach:
=REPLACE(REPT(8,LEN(A1))+A1+1,1,1,"")

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


text:
Generate Hofstadter's Figure-Figure Sequence
In Gödel, Escher, Bach, Douglas Hofstadter introduces an integer sequence which is commonly referred to as the figure-figure sequence:
2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ...

You may enjoy working out the definition of the sequence yourself as part of the challenge, but if you can't or don't want to figure it out you can find it on OEIS as sequence A030124 and a slightly clearer definition on Wikipedia.
Write a program or function which, given n via STDIN, ARGV or function argument, prints a list of the first n numbers of the sequence to STDOUT in any reasonable list format.
This is code golf, the shortest solution in bytes wins.

CJam, 38 30 29 21 bytes
li_3*,2>\{(_pX+:X-}*;

Try it online.
How it works
li                     " Read an integer N from STDIN.              ";
  _3*,2>               " Push S := [ 2 3 ... (N * 3 - 1) ].         ";
        \{        }*   " Do the following N times:                  ";
          (            " Shift an integer I from S.                 ";
           _p          " Print a copy of I, followed by a linefeed. ";
             X+:X      " Execute X += I. (X is initialized to 1.)   ";
                 -     " Remove X from S.                           ";
                    ;  " Discard S from the stack.                  ";

Example run
$ cjam <(echo 'li_3*,2>\{(_pX+:X-}*;') <<< 20
2
4
5
6
8
9
10
11
13
14
15
16
17
19
20
21
22
23
24
25

You've missed the s out of aditsu when typing the url for the interpreter

@BetaDecay then why not edit to fix it ;)

@Martin I didn't think I had enough rep...

@BetaDecay You don't, but you can still suggest them (which even gives you 2 rep if they are accepted).

I felt so clever for golfing off 8 additional bytes of my code. Then I realized that it now does exactly the same as the answers from histocrat, matsjoyce and Peter Taylor...

Haskell, 67 61 60 56 55 53 characters
g n=take n$2:4:h
a#(x:s)=[a..x-2]++x#s
h=5#scanl(+)8h

back to the first algorithm.
this solution computes the complement sequence by summing the starting elements of the sequence. it then computes the sequence as all the numbers between the complement's sequence numbers.
(#) is the function that calculates the numbers between the complement sequence.
h is the sequence itself.
g is the function that answers the question.
the g function is defined to just take the needed amount of elements from h.
subtleties:
h is actually the figure figure sequence except for the first 2 elements.
not the complement sequence is computed, but the complement sequence with added 1 for each element.
these two subtleties are the reason scanl(+)8h (which is the code for the complement sequence (except for the first 2 elements) with added 1's) has 8 in it. it is for the third element of the complement sequence with 1 added to it.
the reason the computation is not missing the first two elements is because they are added in g in 2:4:h.
example:
>g 50
[2,4,5,6,8,9,10,11,13,14,15,16,17,19,20,21,22,23,24,25,27,28,29,30,31,32,33,34,36,37,38,39,40,41,42,43,44,46,47,48,49,50,51,52,53,54,55,57,58,59]

Ruby, 54 48
f=->n{x=1
b=*2..n*n
n.times{b-=[x+=p(b.shift)]}}

Demo
Edit: Golfed this a bit more once I realized I don't need to hold the full complement sequence in memory. Here's how it works now: We use x to keep track of the largest computed number in the complement sequence, and b is a pool of candidates for the sequence. n times, we output the smallest remaining element in b and add it to x to compute the next number in the complement sequence. Then we remove both numbers from the pool of candidates, so we're always outputting the smallest number that wasn't already added to either sequence.
Ruby golf tricks: Stabby lambda syntax is shorter than a method definition. The requirement that output is given to STDOUT instead of as return value inspired me to use the fact that the return value of p(x) is x, which I don't normally remember because it's not the case in the Ruby version used in Anarchy Golf.

How does it work?

FWIW you could use 2..2*n. I have to use n*n because I'm doing effectively b = [x]^b so I need the largest element of b to be larger than the largest value of x, but your b -= [x] just requires that b contains the largest possible value of the output sequence.

GolfScript (24 21 bytes)
~.3*,1>\{(\(.p@+\|}*;

Online demo
This started out quite differently, but ended up converging on a GolfScript port of histocrat's Ruby solution before Dennis made some suggestions which take it in a slightly different direction. In particular, printing the numbers as we identify them saves quite a bit over gathering them in an array for printing at the end; the reason is that it means that at no point do we have to worry about more than 3 items on the stack.
Dissection
~.3*,           # Eval input n, dup, multiply by 3, make list [0 1 ... 3n-1]
1>              # Discard 0, which is part of neither sequence
\{              # Execute n times: stack contains pool of numbers not yet seen
                # in either sequence and the first element of it is the next element of the
                # complement sequence
  (\(           #   Pop two numbers from the start of the pool: stack is
                #     pool[0] pool[2..max] pool[1]
  .p            #   Print pool[1]
  @+            #   Rotate pool[0] to top and add to pool[1]
  \|            #   Place pool[0]+pool[1] at the start of the pool and
                #   (this is the clever bit) remove it from later in the pool
}*
;               # Discard the unused remainder of the pool

If you replace ^ with \-, you can replace ).* with 3*. This won't save any bytes, but it drastically reduces run time and memory usage. -- You should be able to save one byte by keeping the integer on top of the array. The loop will have the same byte count, but initialization will be one byte shorter.

Set union works even better than difference: ~.3*,1>\{(\(.p@+\|}*;

Java - 183 158
This was the most I have ever golfed anything, and I am proud of it! (Although it is nowhere near the top of the charts(because it's Java))
Thanks to Peter Taylor for suggestions
class f{public static void main(String[]a){int q=1,m=Byte.valueOf(a[0]),w=2,n[]=new int[m*m*2];for(n[q+=w]=1;m-->0;){System.out.println(w);for(;n[++w]>0;);}}}

bigger -
public class f {
    public static void main(String[] a) {
        int q = 1, m = Byte.valueOf(a[0]), w = 2, n[] = new int[m * m * 2];
        for (n[q += w] = 1; m-- > 0;) {
            System.out.println(w);
            for (; n[++w] > 0;)
                ;
        }
    }
}

That inner for loop is quite impressively obfuscated, but I think you can save a few bytes. Byte.valueOf saves three, and since the question doesn't specify the range of input I think it should be acceptable. Outside the loops, m is only used to initialise n, so k++<m could be m-->0, eliminating k entirely. int[] n can be initialised as int n[] and merged into the previous initialiser. n never holds values other than 1, so n[...]!=0 could be n[...]>0. The initialiser can then become the initialiser part of the first for loop.

And if you get rid of u and just use ++w, there's no need to set n[q] or n[w]. There's one bug, in that you run off the end of n when m==2, which seems to be best fixed by initialising n=new int[2*m*m], but I think it's down to 157 bytes.

What I meant about the initialiser becoming the initialiser part of the first for loop was for(int q=1,w=2,m=...,n[]=...;m-->0;){... saving a semicolon.

J - 28 char
Function taking n as argument.
($+/\(-.~2+i.)&:>:+/)^:_&2 4

We run a function, with n as left argument, onto its right argument repeatedly until it produces no change. The argument to start is the list 2 4.
In the function itself, we take the partial sums +/\ and the full sum +/, and then increment them both with &:>:. We then generate every integer from 2 to the one more than full sum (2+i.), and set subtract (-.) the partial sums, leaving a longer figure-figure sequence by definition. Finally, we shorten or cyclically extend the list to length n.
The result is that 2 4 becomes 3 7, and this is removed from 2..8 leaving 2 4 5 6 8. After another round, 2 4 5 6 8 becomes 3 7 12 18 26 becomes
2 4 5 6 8 9 10 11 13 14 15 16 17 19 20 21 22 23 24 25 27

In this way, we repeatedly extend the figure-figure sequence. The $ length behaviour is just a non-trivial character saving way of waiting for the sequence to grow to length n or greater, and outputting the n first values when they stop changing. We don't have to wait very long, either: we can get as many as 46336 terms from four applications of the inner verb.
The same function in k:

k2, 37 chars: {{x#y@&~_lin[y:1+!1+/y;1+\y]}[x]/2 4}
k4, 36 chars: {{x#y@&~(y:2+!1+/y)in\:1+\y}[x]/2 4}

Python 2 -- 77 bytes

Code:
n=input();x=1;b=range(2,n*n)
while n:v=b.pop(0);x+=v;print v;b.remove(x);n-=1

Works the same as @histocrat's solution, except input comes from stdin.

Python 2 - 68
R=[1]
s=0
n=input()
while n:s+=1+(s+1in R);R+=[R[-1]+s];print s;n-=1

Jelly, 15 bytes
SƤŻ‘µṀ‘Rḟ
2Ç³¡ḣ

Try it online!
Memory error at the input of 6.
How it works
SƤŻ‘µṀ‘Rḟ  Aux. link (monad). Input: part of the desired sequence
SƤŻ‘       Sum of prefixes, then prepend a zero and increment
           This is a list of numbers to exclude from the next iteration
    µ      Re-focus on the above
     Ṁ‘Rḟ  Create range 1..Max + 1, then remove all elements of the above
           +1 is needed to progress from [2] to [2,4]

2Ç³¡ḣ  Main link (monad). Input: n, number of terms
2Ç³¡   Starting from 2, apply aux. link n times
    ḣ  Take n elements from the beginning

More efficient version, 16 bytes
SƤŻ‘µṀ‘Rḟḣ³
2ÇÐL

Try it online!
Uses an idea from this J answer. Truncate to the desired length each iteration, and take the fixpoint. I thought using S (sum) instead of Ṁ‘ (max+1), but I can't guarantee its correctness.

12 bytes.

authors: Маша Разумная

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


text:
Code-Golf Ascii Art Mini-Golf
Intro
Let's play some mini-golf! The golf ball is represented by a . and the hole by a O.
You want to get a hole in one on every hole, but you are not good at putting. In fact, you refuse to attempt putting diagonally! Only up, down, and to either side.
You plan to cheat by placing extra bumpers \ and / so you can put the ball in with one shot. The ball bounces off of the bumpers at right angles, as shown in this picture.

Remember to call your shot! Tell us what direction you're putting.

Holes
1: The first hole is easy, a straight shot! No bumpers needed to place here.
Input:
.         O

Output:
right
.         O

2: Another basic one, a short turn. The ball is hit off the bumper into the hole.
Input:
     .
O

Output:
left
/    .
O

or
down
     .
O    /

3: Some holes have bumpers already!
Input:
.   \O

Output:
right
.   \O
    \/

or
right
   / \
.  /\O

4: Some holes are overly complex!
Input:
    /  \  \    /
   /  . \  \  /
  /  /\/   /\ \  /
 /  /     /  \ \/
/  /   /\ \  /  \  /
\  \  /  \ \/    \/
      \  /          /
  /\   \//\ \      /
 /  \   /  \ \     \/
 \  /\  \  /  \     \
  \/  \  \/    \ O/  \
      /         \/

Output: (one possible solution, more exists)
down
    /  \  \    /
   /  . \  \  /
  /  /\/   /\ \  /
 /  /     /  \ \/
/  /   /\ \  /  \  /
\  \  /  \ \/    \/
/     \  /          /
  /\   \//\ \      /
\/  \   /  \ \     \/
 \  /\  \  /  \  /  \
  \/  \  \/    \ O/  \
      /  \      \/
                \   /

Rules

The input is the mini-golf hole on STDIN.
The output is the direction you hit the ball and the mini-golf hole with newly placed bumpers on STDOUT.
Existing bumpers cannot be moved.
You can add any number of bumpers to solve a hole.
Assume there are valid locations for the bumpers to be placed that will allow the course to be solved in one putt.
The outputted hole may be bigger than the input.
The input may be padded with trailing white space, but please specify in your answer if you do this.
The output must look correct, but can have leading or trailing white space.
Your program should work for any valid hole. Feel free to post your test cases too!

Scoring
This is code-golf. Your score is the number of characters in your program. Lowest score wins!

I'm pretty sure the directions (up, left, right, down) are wrong in the following examples: #2 example 2 should be right, #3 example 1 should be down, and #3 example 2 should be up. Interesting challenge, though!

@Doorknob thanks! . is the ball you're hitting and O is the hole. I messed up on #2 example 1 but they should be good now.

Javascript (ES6) - 651 bytes
G=s=>{Q='\\';S=[[]];n=L=1;s.split(N='\n').map(t=>{j=S[L++]=[];l=t.length;n=n>l?n:l;k=1;t.split('').map(T=>{j[k++]=T})});S[O=L++]=[];n++;for(r=0;r<L;r++)for(c=0;c<=n;c++){v=S[r][c];if(!v)S[r][c]=' ';if(v=='.'){x=c;y=r}if(v=='o'){X=c;Y=r}}f=M=>{J=M?'.':'o';K=M?'o':'.';R=0;for(D=0;1;D++){R=D&4;D=D&3;c=e=D;g=M?X:x;h=M?Y:y;while(c!=K){c=S[h+=[-1,0,1,0][e]][g+=[0,1,0,-1][e]];e=c=='/'?(B=c,e^1):c==Q?(B=c,3-e):e;E=h*(h-O)?g*(g-n)?0:2:1;if(R&&c==' '){S[h][g]=Q;R=D=0;c=K}if(c==J||E){E&&(S[h][g]=(E+M)%2?Q:'/');H=M?E?H:(e+2)&3:D;return}}}};f(0);f(1);S[0][0]=S[O][n]='/';S[0][n]=S[O][0]=Q;return['up','right','down','left'][H]+N+S.map(t=>t.join('')).join(N)}

Creates a function G that accepts a string (golf course) as input and returns the requested putting solution. The input string may or may not have leading lines, trailing lines, and trailing whitespace. The output will not have leading or trailing whitespace.
Expanded code is:
G = s => {
    Q = '\\';
    S = [[]];
    n = L = 1;
    s.split( N = '\n' ).map( t => {
        j = S[L++] = [];
        l = t.length;
        n = n > l ? n : l;
        k = 1;
        t.split('').map( T => {
            j[k++] = T;
        } );
    } );
    S[O = L++] = [];
    n++;
    for( r = 0; r < L; r++ )
        for( c = 0; c <= n; c++ ) {
            v = S[r][c];
            if( !v )
                S[r][c] = ' ';
            if( v == '.' ) {
                x = c;
                y = r;
            }
            if( v == 'o' ) {
                X = c;
                Y = r;
            }
        }
    f = M => {
        J = M ? '.' : 'o';
        K = M ? 'o' : '.';
        R = 0;
        for( D = 0; 1; D++ ) {
            R = D & 4;
            D = D & 3;
            c = e = D;
            g = M ? X : x;
            h = M ? Y : y;
            while( c != K ) {
                c = S[h += [-1,0,1,0][e]][g += [0,1,0,-1][e]];
                e = c == '/' ? (B=c,e^1) : c == Q ? (B=c,3-e) : e;
                E = h*(h-O) ? g*(g-n) ? 0 : 2 : 1;
                if( R && c == ' ' ) {
                    S[h][g] = B;
                    R = D = 0;
                    c = K;
                }
                if( c == J || E ) {
                    E && (S[h][g] = (E+M)%2 ? Q : '/');
                    H = M ? E ? H : (e+2)&3 : D;
                    return;
                }
            }
        }
    };
    f(0);
    f(1);
    S[0][0] = S[O][n] = '/';
    S[0][n] = S[O][0] = Q;
    return ['up','right','down','left'][H] + N + S.map( t => t.join('') ).join( N );
}

The solver operates on the premise that any path from the ball (hole) will either

lead back to the ball (hole) again
lead to the hole (ball)
exit the course

We trace the ball's path in all four directions. If we find case 3, the problem is solved. If we find case 2, we mark the ball's exit location. If all four directions result in case 1, we convert the first non-bumper space along any trajectory to a bumper (if the problem is solvable, such a space is always guaranteed to exist) and try again. The bumper we convert to will have the same type as the last bumper our trajectory encountered*. If the ball is still stuck in a loop, we repeat the process as many times as needed. If the problem is solvable, this procedure is guaranteed to eventually lead to outcome 2 or 3.
(*Note that if we simply convert to a fixed bumper [say, \], there exist extremely contrived but nevertheless possible cases where a solution exists but we will fail to find it.)
We perform a similar trace from the hole, leading to either outcome 2 or outcome 3.
If both the ball trace and hole trace result in outcome 2, we place bumpers on the periphery of the course that link the two exit points (in fact, these periphery bumpers are placed regardless of the trace outcomes, to shorten the code). This completes the solution.
Test Cases and Outputs
In
   /   \   / \ /\
   \\      /    \  \
       /     / o   /
   /   \       /
   \   .  \  \    \\
       /  /     \ \
       \          /
           \      /
 \ /\     /  \/  //\

Out
right
/   /               \
   /   \   / \ /\
   \\      /    \  \
       /     / o   /
   /   \       /
   \   .  \  \    \\
       /  /     \ \
       \          / /
           \      /
 \ /\     /  \/  //\
\                   /

In
  / \   / /    /  \    / \  /  \\ /
\   \ /  \  // \    \   /   /\   \
/ \   // \  //   \ \   \ /  / \\ \
 \  / \    /   \  \  / / \\ / /  //
/ /   /\ \\ //  / \   /  \ / \\ \ \
\   \  \ \ // \ /  /    \ \  /  / /
/ \ /   /  / \     / \ /\   /  \  /
\ /\  //\   .\  \ \ //\ /  \  / \ /
/ \/ \ /\ //\   /   \   / o// \ / \
/   / \    / \ / \\ / \   / \   \ \
/ /   / \  / \ //   \    / \/  /\/
   / \   / \  /   \\  / \    /\ / \
/ \/   \   /   \/  \   /  \    /\\
/ /\\ //\  / \  /\ /\   /  / \ / \/

Out
left
/                                   \
   / \   / /    /  \    / \  /  \\ /
 \   \ /  \  // \    \   /   /\   \
 / \   // \  //   \ \   \ /  / \\ \
  \  / \    /   \  \  / / \\ / /  //
 / /   /\ \\ //  / \   /  \ / \\ \ \
 \   \  \ \ // \ /  /    \ \  /  / /
 / \ /   /  / \     / \ /\   /  \  /
 \ /\  //\   .\  \ \ //\ /  \  / \ /
 / \/ \ /\ //\   /   \   / o// \ / \
 /   / \    / \ / \\ / \   / \   \ \
 / /   / \  / \ //   \    / \/  /\/
    / \   / \  /   \\  / \    /\ / \
 / \/   \   /   \/  \   /  \    /\\
 / /\\ //\  / \  /\ /\   /  / \ / \/
\         \                         /

In
/\/ \
\  \ \
 \ \\ \   o
  \ .\ \
   \ / /
    \ /

Out
down
/   \      /\
 /\/\\
 \ \\ \
  \ \\ \   o
   \ .\ \
    \ / /
     \ /
\           /

Fails on this test case: "/\\/\\\n\\.//\n// \\\n\\/  \no \\/"


text:
Laser Mirror Portal Party
A 2D board will contain the following objects:

^,>,v, or <: A laser emitter facing up, right, down, or left respectively. There may be more than one. Lasers will travel in a straight line in empty space (empty space is represented with a dot .). Lasers do not pass through emitters.
*: A target. Lasers pass through targets. There may be more than one.

The board may also contain the following objects:

@: A solid wall. The laser will not pass through here.
\: A left-leaning reflector. Changes the direction of lasers according to the following table:
Direction laser is travelling     Direction of laser after hitting reflector
Up                                Left
Right                             Down
Down                              Right
Left                              Up

It should be pretty intuitive as to how the reflectors work. Just imagine them as an actual two-sided mirror and the directions should be clear.
/: A right-leaning reflector. Changes the direction of lasers according to the following table:
Direction laser is travelling     Direction of laser after hitting reflector
Up                                Right
Right                             Up
Down                              Left
Left                              Down

1,2,3...9: A portal. The number indicates the channel of the portal - there will be exactly two portals of the same channel (for instance, there won't be three 1's). The portal changes the position of lasers to the position of the other portal of the same channel. For instance:
>     1     @     1     *

The laser will hit the target because when it hits the first 1, it is teleported to the second 1 on the other side. Lasers retain the same direction that they were in before.
A portal will not teleport the laser to a portal of a different channel (i.e. a 1 won't teleport the laser to a 9.

Your program will recieve a 2D representation of the board as input. The board will always be rectangular shaped. The output should be True if all the targets have lasers passing through them, or False otherwise.
Here are some test cases:

Input
>....\
..*...
>./../
..*...

Output
True

Input
>..........\
1........../
2..........1
3..........2
4..........3
5..........4
6..........5
7..........6
8..........7
9..........8
*..........9

Output
True

Input
>.@............*
>..@...........*
>...@..........*
>....@.........*
>.....@........*
>...*..@........
>.......@......*

Output
False

Input
../\.
>./**

Output
False

Input
/.......*.......\/3.....
@..............//\.\....
*.............2\.1\/\...
\..............///.....<
.........*...//\\/.....\
>.............\.1.///.4.
4.......*/...\2\/3/\/..^

Output
True

Input
vvvvvvvvvvvvvvvvv
\\\\\\\\\\\\\\\\\
/////////////////
\\\\\\\\\\\\\\\\\
/////////////////
\\\\\\\\\\\\\\\\\
/////////////////
*****************

Output (note the target at the far right)
False

Wouldn't it make more sense if a right-leaning reflector (/) changed the direction of a laser beam from left (←) to down (↓)?

@squeamish ossifrage I'm sorry, I don't understand your question. Which reflection rule on the left leaning reflector table do you think is incorrect?

I think you got left and right mixed up

@squeamishossifrage "Direction of laser before" i.e. the direction the laser was travelling in before it hit the laser, not the direction is was travelling from. So "left" here means -->

In that case (a) ????? and (b) you got up and down mixed up

@MartinBüttner I fixed it. I confused left and right in English, that is my mistake.

What happens if the laser reaches the grid boundary?

@DavidG Nothing, or it bounces back the way it came. (These are equivalent in this case). It does not 'wrap around' as can be seen from example 6.

Python, 310 302 287 278 277 260
Not radically different than the existing Python post, but has one or two noteworthy tricks, I think.
It also handles "non-terminating" input, such as 1>1. EDIT: Oops! emitters block lasers.
def t(b):
 w=len(b[0])+1;B=list('@'*w+'@'.join(b));i=l=len(B);C="<>^v@"
 while i:
    j=l-i;i-=1;d=C.find(B[j]);c='.'
    while c not in C:
     if'+'>c:B[j]='.'
     if'0'<c<C:j=(B*2).index(c,j+1)%l
     elif'.'<c:d^=2+(c<C)
     j-=[1,-1,w,-w,j][d];c=B[j%l]
 return'*'not in B

t takes a list of strings (the input lines) and returns a boolean result.
Here's a nice gif of the code being golfed down:

EDIT: Awsome gif courtesy of Will. Thanks Will!

The spec specifies that "Lasers do not pass through emitters." so 1>1 will terminate. I've not been able to find something that doesn't terminate, though I've not put much effort into it and pretty much assumed it doesn't happen for my implementation. I will of course reconsider if someone can present one.

@VisualMelon: The rules are time-symmetric except at spots where lasers are born or die, which means everything has to terminate (since you can always uniquely trace it back to the point where it was born, and emitters can't themselves be part of a loop).

@Micah hehe, thanks for a proper explanation, like I said I went with intuition and didn't worry about it much, thanks for putting another tool in my box.

Yup, I read it wrong.

Hats off to Ell!  Very nicely done.  I think you can shave a few more bytes off by using the fact that .find(d) returns -1 if not found.  If you remove the if-1<d: statement and instead do j+=[-1,1,w,-w,-i][d] at the top of the while loop, a not-found -1 will turn into adding the last element in that array to j, which will make j 0, which we know is @...?

@Will: Thanks, great idea!

I think this solution beautiful.  I particularly like the d^=2 trick.  You can gain another byte by swapping the signs to be j-=[1,-1,-w,w,j][d] ;)

I can't get your byte-count to be 260, but I have a rearrangement that's 255 you can borrow: https://gist.github.com/williame/c40b785ce465902256d9 (note the indent level is one space, two spaces, then tab)

@Will: SE replaces tabs with spaces, which is probably why you get a slightly higher count. Your suggested indentation does save a few bytes, though; I'll look into it later.

I think the answer for the second test case is wrong: http://ideone.com/mkLUaV. It sould be True, but it's False

actually, I think 3 out of the 5 test cases fail: http://pastie.org/9551185http://pastie.org/9551185

@w0lf: You're testing Will's program, not mine :P

Yours fails as well.

sorry for the double-paste; the unit tests link is http://pastie.org/9551185

@w0lf: You're giving wrong input. The function takes a list of strings (for each line), not a single string.

You're right; now I see you also specified this in your answer.

>1.1* is also nonterminating :)

Perl, 647
This is my first ever attempt at code-golf, and I'm a bit embarrassed I didn't even beat the C# score, but I thought it would be interesting (or fun, or just masochistic) to do the entire thing as a series of regex substitutions. (I also thought it would be fun to brush up on my Perl, but by the end I was deeply regretting not implementing it in Ruby or Python.)
I haven't done a lot of testing, but I think it should handle every case.
The grid is input via STDIN. There must be at least one newline in the input (i.e. a single row without a newline won't work).
%s=(d,'[|+#$vk%ZX]',u,'[|+#$^W%KX]',r,'[-G+#>k%KX]',l,'[-G+#<W%ZX]');%o=(d,'[-.*G/k\\\\Z',u,'[-.*G/W\\\\K',r,'[|.*$\\\\/kK',l,'[|.*$\\\\/ZW');for$d(d,u,r,l){$o{$d}.='123456789qwertyuio]'}%u=(d,'.|-+*$G#/Wk%\KZX',u,'.|-+*$G#/kW%\ZKX',r,'.-|+*G$#/Wk%\ZKX',l,'.-|+*G$#/kW%\KZX');@q=split//,"qwertyuio";local$/;$_=<STDIN>;for$i(1..9){$m{$i}=$q[$i-1];$m{$m{$i}}=$i;s/$i/$m{$i}/e}/.*?\n/;$l='.'x((length$&)-1);do{$c=0;for$d(d,u,r,l){%p=(d,"(?<=$s{d}$l)$o{d}",u,"$o{u}(?=$l$s{u})",r,"(?<=$s{r})$o{r}",l,"$o{l}(?=$s{l})");%h=split//,$u{$d};$c+=s!$p{$d}!$h{$&}||($v=$&,($o{$d}=~s/$v// && $s{$d}=~s/]/$m{$v}]/),$v)!es}}while($c);print/\*/?"False\n":"True\n"

Explanation: the code iteratively updates the grid string as the lasers pass through it. - represents a horizontal laser, | a vertical laser, + crossed lasers, K a \ mirror with a laser bouncing off the top, k a / mirror with a laser bouncing off the bottom, Z a \ mirror with a laser bouncing off the bottom, and W a / mirror with a laser bouncing off the top. % is a / mirror with lasers on both sides, while X is a \ mirror with lasers on both sides. (These are case sensitive. I tried to pick letters that look somewhat appropriate--for instance, k and K are somewhat obvious choices--but unfortunately the effect really isn't that helpful. I should really put this info into a table, but I'm exhausted right now.)
Handling portals in the same way (i.e. assigning each digit a set of extra characters based on the possible input/output laser positions) would require 144 characters (including the original 9), so instead, when a laser hits an "input" portal, I add the "output" portal character to the set of characters that emit a laser in the proper direction. (This does require differentiating between input and output portals; I used the letters qwertyuio for this.)
Somewhat un-golfed, with print statements so you can see the substitutions happening (each substitution represents one "round" of laser-progression), and with the g flag added to the main s/// so that it doesn't take so many iterations:
# Throughout, d,u,r,l represents lasers going down, up, left, or right
# `sources` are the character classes representing laser "sources" (i.e. any
# character that can, on the next round, cause a laser to enter the space
# immediately adjacent to it in the proper direction)
%sources=(d,'[|+#$vk%ZX]',u,'[|+#$^W%KX]',r,'[-G+#>k%KX]',l,'[-G+#<W%ZX]');
# `open` characters will not block a laser
%open=(d,'[-.*G/k\\\\Z',u,'[-.*G/W\\\\K',r,'[|.*$\\\\/kK',l,'[|.*$\\\\/ZW');
# One of each portal is changed into the corresponding letter in `qwertyuio`.
# At the start, each portal is 'open' and none of them is a source.
for$d(d,u,r,l){$open{$d}.='123456789qwertyuio]'}
# A mapping of 'open' characters to the characters they become when a laser
# goes through them. (This is used like a hash of hashes; see the assignment
# of `%h` below.)
%update=(d,'.|-+*$G#/Wk%\KZX',
    u,'.|-+*$G#/kW%\ZKX',
    r,'.-|+*G$#/Wk%\ZKX',
    l,'.-|+*G$#/kW%\KZX');
@q=split//,"qwertyuio";
local$/;$_=<STDIN>;
for$i(1..9){
    $m{$i}=$q[$i-1];
    $m{$m{$i}}=$i;
    s/$i/$m{$i}/e}
print "After substituting portals:\n";
print;
print "\n";
# Find the number of characters in each line and create a string of `.`'s,
# which will be used to correlate characters above/below one another in the
# grid with each other.
/.*?\n/;
$l='.'x((length$&)-1);
do{
    $changes=0;
    for$d(d,u,r,l){
        # `patterns` is a mapping from each direction to the regex representing
        # an update that must occur (i.e. a place where a laser must progress).
        # Each pattern is either a lookahead or lookbehind plus the necessary
        # "open" character class.
        %patterns=(d,"(?<=$sources{d}$l)$open{d}",
            u,"$open{u}(?=$l$sources{u})",
            r,"(?<=$sources{r})$open{r}",
            l,"$open{l}(?=$sources{l})");
        %h=split//,$update{$d};
        # Match against the pattern for each direction. Note whether any
        # matches were found.
        $changes+=s!$patterns{$d}!
            # If the "open" character for a map is in the `update` map, return
            # the corresponding value. Otherwise, the "open" character is a
            # portal.
            $h{$&} || ($v=$&,
                        # For portals, remove the input portal from the
                        # proper "open" list and add the output portal to
                        # the proper "source" list.
                       ($open{$d}=~s/$v// && $sources{$d}=~s/]/$m{$v}]/),
                       $v)
                    # This whole substitution should allow `.` to match
                    # newlines (see the definition of `$l` above), and the
                    # replacement must be an expression rather than a string
                    # to facilitate the portal logic. The `g` allows multiple
                    # updates per "frame"; it is left out of the golfed code.
                    !egs
    }
    # Print the next "frame".
    print;
    print "\n";
# Continue updating until no "open" spaces are found.
}while($changes);
# Print whether `*` is still present in the input.
print/\*/?"False\n":"True\n"

I experimented with this kind of approach (using bool arrays rather than regex) in Python but couldn't get anywhere close to this small.  I think this a really thought-provoking approach!  My attempts were wrong-headedly influenced by http://catpad.net/michael/apl/ with nice vid https://www.youtube.com/watch?v=a9xAKttWgP4 and http://www.petercollingridge.co.uk/blog/python-game-of-life-in-one-line

@Will Thanks! I definitely realized how similar my efforts were to GoL around the time I worked out just how feasible it would be to use a different character for each possible combination of lasers going into and out of a portal. I think I might be able to shave off a few more characters, but...this clearly is not the optimal approach!

Also, if anyone knows a better way to handle the triple-escaped \'s in the character classes in the first few lines, that would be lovely...

Python 338 351
def t(b):
 L=len;w=L(b[0])+3;b=list("@"*w+"@@".join(b)+"@"*w);w-=1;I=b.index
 for i in range(L(b)):
  c=b[i];d={"^":-w,"<":-1,">":1,"v":w}.get(c)
  if d:
   while c!='@':
    i+=d;c=b[i]
    if c=='*':b[i]='.'
    elif c in '/\\':d={-w:-1,w:1,1:w,-1:-w}[d]*(-1 if c=='/' else 1)
    elif c>'0':i+=I(c)-i or I(c,i+1)-i
 return "*" not in b

My unminified version actually plots the laser paths on the board, which is pretty:
>-+--\
..X..|
>-/--/
..X...

>----------\
1----------/
2----------1
3----------2
4----------3
5----------4
6----------5
7----------6
8----------7
9----------8
X----------9

>-@............*
>--@...........*
>---@..........*
>----@.........*
>-----@........*
>---X--@........
>-------@......*

/-------X+------\/3.....
@........|.....//\+\....
X........|....2\+1\/\...
\--------+----+///+++--<
.........X...//\\/+++--\
>--------+---+\+1+///-4|
4-------X/...\2\/3/\/..^

vvvvvvvvvvvvvvvvv
\\\\\\\\\\\\\\\\\
/////////////////
\\\\\\\\\\\\\\\\\
/////////////////
\\\\\\\\\\\\\\\\\
/////////////////
XXXXXXXXXXXXXXXX*

def debug(board,x,y):
    emit_dir = {
        "^":    ( 0, -1),
        "<":    (-1,  0),
        ">":    ( 1,  0),
        "v":    ( 0,  1),
    }
    class PortalException(Exception): pass
    xdir, ydir = emit_dir[board[y][x]]
    while True:
        # print "step (%d, %d) (%d, %d)" % (x, y, xdir, ydir)
        x += xdir
        y += ydir
        if y < 0 or y >= len(board) or x < 0 or x >= len(board[y]):
            return
        ch = board[y][x]
        if ch == '/':
            xdir, ydir = -ydir, -xdir
        elif ch == '\\':
            xdir, ydir = ydir, xdir
        elif ch in '@^><v':
            return
        elif ch == '*':
            board[y] = board[y][:x] + 'X' + board[y][x+1:]
        elif ch in '.-|':
            ch = ('-' if xdir else '|') if ch == '.' else '+'
            board[y] = board[y][:x] + ch + board[y][x+1:]
        elif ch in '123456789':
            try:
                for r in range(len(board)):
                    for c in range(len(board[r])):
                        if board[r][c] == ch and (r != y or c != x):
                            x, y = c, r
                            raise PortalException()
                raise Exception("could not find portal %s (%d,%d)" % (ch, x, y))
            except PortalException:
                pass

C# - 515 414 400 bytes
Complete C# program, no nice output like Will's. Works by following the laser path for each emitted individually, and keeping an array of which cells we've visited, so that we can check that we've visited all the stars at the end. Edit: striped a large number of bytes by making everything 1D and by using a char instead of an int to store the current char
w0lf reminded me that I had an under utilized for-loop right in the middle of my code, so I figured I'd better make one last effort and put it to work, and now I'm down to the absolute minimum number of curly braces. I won't pretend to like the collapsing of the second for loop, the code is horribly disorderly now, but it saved a few bytes. In the process I re-wrote the portal handling. I also found a shorter method for performing the "move" with nested rather than aggregated conditional operation.
Golfed code:
using C=System.Console;class P{static void Main(){var S=C.In.ReadToEnd().Replace("\r","");int W=S.IndexOf('\n')+1,l=S.Length,i=l,d,m,n;var M=new int[l];for(char c;i-->0;)for(d="^<v>".IndexOf(c=S[m=i]);c>14&d>-1;d=(m+=d==2?W:d>0?d-2:-W)>=0&m<l&&"@^<v>".IndexOf(c=S[m])<0?d:-1)for(d=c==47?3-d:c==92?d^1:d,M[n=m]=1;c%49<9&&(m=S.IndexOf(c,m+1))==n|m<0;);for(;l-->0;)W*=S[l]==42?M[l]:1;C.WriteLine(W>0);}}

Less golfed code:
using C=System.Console;

class P
{
    static void Main()
    {
        var S=C.In.ReadToEnd().Replace("\r",""); // read the grid, remove pesky carriage returns
        int W=S.IndexOf('\n')+1,l=S.Length,i=l,d,m,n; // find "width"
        var M=new int[l]; // defaults to 0s

        for(char c;i-->0;) // for each cell

            for(d="^<v>".IndexOf(c=S[m=i]); // find initial direction, if any
                c>14&d>-1; // loop only if we have direction
                d=(m+=d==2?W:d>0?d-2:-W) // move (after iteration)
                >=0&m<l&&"@^<v>".IndexOf(c=S[m])<0?d:-1) // terminate if we hit something or go off edge

                for(d=c==47?3-d:c==92?d^1:d, // mirrors
                    M[n=m]=1; // we have seen this spot
                    c%49<9&&(m=S.IndexOf(c,m+1))==n|m<0;); // portals

        for(;l-->0;) // for each cell
            W*=S[l]==42?M[l]:1; // if *, then mul by whether seen

        C.WriteLine(W>0);
    }
}

The new portal handling code utilizes the fact that the String.IndexOf function happily returns -1 (i.e. char not found) if you ask it start looking 1 character beyond the string (throws an exception if you ask it to start any further beyond). This was news to me, but was awfully convenient in this instance.

+1 Awesome golfing! I just thought of a trick: you could take the m+=(d>0?d-2:0)+(d<3?d-1:0)*W; and shove it in the for, like this: for(char c;i-->0;m+=(d>0?d-2:0)+(d<3?d-1:0)*W). This way, you'll save one char, because you'll lose a semicolon.

@w0lf made a last effort and managed to collapse the for loops completely, thanks for the nudge ;)

authors: สุทธิสาร ปานสัสดี


text:
Pick the longest stick
You are a young programming geek living with your 2 other best friends. Every week, one of you has to do all the chores of the house and you decide whose turn it is by picking a stick. The one who picks the shortest stick loses and does all the chores.
As all of you are programmers and love creating puzzles, you have modified the "Pick the shortest stick" into a computer puzzle.
Here are the rules of the puzzle.

You will be given a 2D matrix, where each column represents a stick.
In each column, 1 represents a portion of the stick and 0 is an empty space
When going from top to bottom in each column, initially you have 0's and as soon as you hit a 1, the stick has started and rest of the column will be filled with 1 only
You can write your program to pick one column. The size of the stick in that column determines the winner/loser. Size of stick == number of 1s in that column.
However, that program can only have a linear worst-case time complexity.

As all of you are programmers, you will know if someone else's program is shooting the time complexity limit.
Your job is to:

Write a program or function that accepts input in either a 2D format or array of strings.
Input can be taken from STDIN/prompt/console or a function argument.
If you are reading the input from STDIN/prompt then you can assume that the reading of input and converting it to an array takes 0 time (even though the code to do so has to be there in your answer)
Determine the column with the longest stick in it.
Output can be the function's return value or to STDOUT/console/alert.
The program/function must have linear worst-case time complexity, O(m+n) where m is the number of rows and n the number of columns.

Input can be either one of the following formats:
2D array:
[ [0, 0, 0, 0],
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [1, 1, 1, 1] ]

Array of Strings:
[ "0000", "1000", "1101", "1111" ]

The input will have following properties:

Size of the array is unknown, assume a rectangle of any size
In any column, coming top down, if you see a 1, then everything below will be a one
Empty-columns (i.e. 0-length) sticks are allowed.

This is a code-golf so shortest code wins!*
Please explain your code, or give the ungolfed version (to verify time complexity) along with which of the two input formats you expect.
UPDATE
Linear time complexity here means O(n+m) where n is column size and m is row size. (For those who were unclear)
UPDATE 2  This definitely can be done in linear time. And if you are posting an answer, feel free to delay posting the logic/algorithm by a couple of days for a fair fight :)
UPDATE 3 I'll go over all answers in couple of hours to validate time complexity and the program :)

I'd argue that this can't be done in O(n+m), since each cell could contain the crucial value (i.e. the first "1" of the longest stick/column). So you need to look at each cell, which takes O(n*m).

Could there be empty columns?

@Optimizer: Oh, I see. You're right. :)

@Martin - Yes. stick length is 0 for that column then

It can't be done in O(n+m). Once the input has been converted into a format which allows random access then the remaining processing can be O(n+m), but you require writing a program, and in the worst case that the only 1 in the input is the very last cell then it's necessary to read the entire input. Even if a language's standard library fakes random access to stdin, under the scenes it's buffering it and so the time taken is Omega(n*m).

You can ignore the complexity achieved by reading the input from the STDIN and converting it into an array. Or, simply make a function which accepts an array :)
But other than that, read Update 2 :)

If you want to allow people to "simply make a function which accepts an array", the question shouldn't state that they must write a program. And if you require solutions which are in O(N^0.5) where N is the size of the input, you shouldn't ask for linear time solutions. A linear time solution can read the entire input.

@Optimizer you should make it clearer that the columns can't have 1's and 0's in any combination, but that the 1's have to be continuous and start from the start of the array. it really isn't specified, and there's only one example.

@proud haskeller - Done

Can I take a MultiList<of int> instead of List<of List<of int>>?

GolfScript, 45 chars
:^,:y;0:x{^y(=x=2%y*{y(:y;x\}{x):x}if^0=,<}do

Takes input as an array of strings, returns (0-based) index of tallest column.
It runs in O(rows + columns) iterations, and each iteration should take essentially constant time (at least assuming constant-time arithmetic).  The only array/string operations done within the loop are element lookups (=) and taking the length of a string (,), both of which take constant time in GolfScript.
Try it online.
Explanation:
Like most of the solutions here, this code works by starting at the lower left corner of the matrix, walking up or right depending on whether the current element of the matrix is 1 or 0, and keeping track of the column where it last moved up.
At the beginning of the program, I assign the input array to the variable ^, its length (i.e. the number of rows) to y, and 0 to x.  The value 0 is also left on the stack; during the following loop, it will be replaced by the index of the tallest column.
Within the main loop, ^y(=x= extracts the x-th character of the y-1-th row in ^.  This actually returns the ASCII code of the character, so 2% is needed to drop all but the last bit.  As a special case, if y equals 0 (which can happen if the tallest column found so far reaches all the way to the top row), the bit looked up will actually come from the last row in the matrix (index -1), but the following y* forces it to zero, thus effectively creating a virtual all-zeros row at the top of the matrix.
The following if will then execute one of the two code blocks preceding it, depending on whether the looked-up bit is non-zero (true) or zero (false).  If non-zero, y is decremented by one, and the current value of x replaces the tallest column index on the stack (with the old value temporarily left on top of it).  If zero, x is simply incremented by one (and temporarily left on the stack, on top of the tallest column index).
Finally, ^0= extracts the first row of the matrix, , returns its length, and < compares it with the column index temporarily left on the stack (which will equal x if it was just incremented)  If the index is less that the length of the row, the loop repeats.
Ps. Based on my testing, it should be possible to shorten this program by one character by replacing the string length test ,< at the end of the loop with >, which cuts the string at the given index and returns the end portion (which will be empty, and thus false, at the end of the loop).  However, while cutting a string like that appears to be implemented as a constant-time operation in GolfScript (or, rather, in Ruby, which GolfScript runs on top of), I have not found any official documentation saying so.  Just to be safe, I've chosen to feature the slightly longer, but definitely O(1), version above.

Ruby, 83 75 68 66 63 bytes
f=->m{m[b=c=i=0].map{(c=i;b-=1)while(r=m[b-2])&&r[i]>0;i+=1};c}

Defines a function f which takes the 2D array form as input.

 I'm starting at the bottom left, keeping track of maximum stick length (actually, minus that) and the corresponding column. In each column, if there are still 1s above the previous maximum stick length, I walk up the stick to the end and remember the new maximum length and column. That means that I'm iterating once along the columns and at most once along the rows (specifically I'm iterating as far as the maximum stick length), which is precisely O(m+n).

@Optimizer I didn't see your second edit until after I posted it, so it was in the edit history anyway. That's why I just put it in a spoiler for people who want to figure it out themselves.

Python 2 - 71, 69, 73, 75 81
j=i=-1
M=input()
for m in M[0]:
 j+=1
 while-i<len(M)and M[i][j]:i-=1;J=j
print J

Is this intended to run in Python 2 or 3? What is the input supposed to look like?

@feersum Python 2, the array of arrays.

@feersum: Quincunx is right. Input is a 2D array of ints, as you suggested.

Won't i go out of bounds if a stick takes up a whole column?

@xnor: You're right. I hope I fixed it with 4 more bytes.

Actually, M can be non-square, so I think you'd have to initialize i and j separately, which is costly.

Oh, how could I overlook this one... Too much codegolf today! ;) Luckily I only need 2 bytes to fix it since the direction of j does not matter.

Sorry, but it looks like changing j to count from 0 breaks the loop condition i*j.

C, 64 bytes
Edit: I learned that the question asks for the location of the longest column and not its length.
The first line is the golfed code and the rest is the sample invocation.
g(int m,int n,int**a,int*r){for(*r=n;n*m;a[m][n]?m--,*r=n:--n);}

/* usage:
    m = number of rows
    n = number of columns
    a = 1-based 2D array such that a[i][j] gives the value at the ith row and jth column
    r = address of return value
    Returns (to r) the 1-indexed location of a column with the longest length, or 0 if n=0
    */

int main()
{
    int flat[4*4] = {1, 0, 0, 0,
                     1, 0, 0, 1,
                     1, 1, 0, 1,
                     1, 1, 1, 1};
    int*twoD[4] = {flat-1,flat+3,flat+7,flat+11};
    int ret;
    g(4,4,twoD-1,&ret);
    printf("%d", ret);
    return 0;
}

// old function which determines longest length (65 bytes)
f(int m,int n,int**a,int*r){for(*r=m;n*m;a[m][n]?m--:--n);*r-=m;}

Impressive! Can you ditch the ints in the function signature by any chance or does that not work due to the pointers in there?

The input should only contain the array. You cannot tell the program about the size of the array.

Wait, does that actually work? This seems to be returning the length of the longest stick and not its position: http://ideone.com/YEzqzl

@Optimizer that is basically impossible in C.

Might be, but that is the question :)

@Martin oops, I thought the question wanted the length of the stick. It is correct that the presence of pointers foils the usual plan to drop type specifiers.

@Optimizer I suppose it could use null-terminated arrays if you really wanted ;) Edit: er, not really since some of the values are 0...

@Optimizer seems a bit unfair. Just because Falko and my answer don't depend on the array size explicitly, they both use it implicitly, because the languages provide a way to determine it from the array itself. I don't see a good reason why working around that in a language like C should be disallowed, especially since it makes the code longer.

@feersum make them 2 terminated :P ... but I think that would be even further away from the challenge spec than just including the array size.

@Martin - well, All questions have some elements in them which are super easy in some language and tough in others. loops are super easy in functional languages like ruby, haskell, while in JS, you have so much bloat. As feersum pointed, he can take in null terminated arrays.

@Optimizer no you can't, because 0 is a valid element of the array. You could take 2-terminated arrays (or -1 or some other integer other than 0 or 1) but I think that's much further from the input spec than adding array sizes. This is not about making it harder on some languages but literally impossible.

Now it finds the location of the longest column instead of its length. This actually helped it to be shorter.

@MartinBüttner it does say that, buried in the last line of the comment.

@feersum your code seems to use a flat array as the input format, but it is not one of the legal input formats.

@proudhaskeller It does use a 2D array. int**a is a pointer-to-pointer type which is dereferenced twice to access the data.

C++ :: 78
Unlike the other C solution, this is the whole program. (no invocation needed, no need to tell the function the size of the array).  Unfortunately this means it is longer as main must be used instead of a single character function name, I have to interpret the input and then output the answer, where the other solution handles that "elsewhere".
Also my first code golf.
compiled with g++ file.cpp -include iostream, run with ./a 000 010 110 111 (for example) == array of strings (I believe this is allowed in the question spec)
int c;main(int r,char**v){for(r--;r*v[r][c];v[r][c]-48?std::cout<<c,r--:++c);}

The above version outputs the current best found so far on each iteration. The final output digit is the answer. Switching from processing from bottom left instead of bottom right and 0 indexing reduced this solution by 10(!) characters.
switching to c++ drops submission by one more character as std::cout<< is shorter than putchar(-48) and it should also explicitly support more than 9 sticks with proper output (though it may get harder to differentiate each output)
Removing the answer field and outputting it direcly cut another 6 characters.  It now only outputs the current best when it moves up which cuts out some output at least.
Entire file is now only 78 bytes in size - approaching the function only solution that the other C submission uses. (with lots of extra code to support said function).
As below description is out of date:

c is global so is initialised with 0
r is the number of inputs (rows) +1 (name of program)
v is the array of strings with v[0] being invalid (name of program)
As it is 0 indexed, r is out of bounds, so decrement.
While r!=0 (pointing at valid string) and character c in the string is not the null terminator '\0'
   if character is not '0'
      go up a row (r) and output the column (c)
   else go to next column (c)

done

Can I even golf this further?
Ungolfed code (with extra output):

#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[])
{
  int rows = argc-1;
  int cols = strlen(argv[1]);
  int ans;

  printf("rows: %d, cols: %d\n",rows, cols);

  while((rows)&&cols)
  {
    if (argv[rows][cols-1]-'0')
    {
      printf("stick @%d,%d\n",cols,rows);
      ans = cols;
      rows--;
    }
    else
    {
      printf("no stick @%d,%d\n",cols,rows);
      cols--;
    }
  }
  printf("%d",ans);
}

 It uses the length of the strings to find out the number of columns and argc to find the number of rows.  Starting in the bottom right corner, it follows these simple rules:
 If cell is a stick, then move up, set answer to current column.
 If cell is not a stick, then move to the left.
 O(n+m): as it only moves up and left, it can only have max n+m reads.  It exits early if it falls off the top or left of the array.

PHP 5.4 - 108 bytes
(113 if you include the <?php)
Input format: Array will be read as a JSON string.
php longest_stick.php "[[0, 0, 0, 0],[1, 0, 0, 0],[1, 1, 0, 1],[1, 1, 1, 1]]"

Whitespace added for readability - all newlines and leading spaces can be removed.
<?php
$t=count($s=json_decode($argv[1]))-1;
foreach($s[0] as $k=>$_)
    while($s[$t][$k]) {
        $t--;
        $l = $k;
    }
echo $l?:0;

Minified version:
<?php $t=count($s=json_decode($argv[1]))-1;foreach($s[0] as $k=>$_)while($s[$t][$k]){$t--;$l=$k;}echo $l?:0;

Kind of stealing the algorithm from Martin here, but it's nice to play around with languages that aren't seen as often here XD

@MartinBüttner I've "stolen" your algorithm, so it should be O(n+m) now. I think it's right XD

You can replace $s=json_decode($argv[1]);$t=count($s)-1; with $t=count($s=json_decode($argv[1]))-1; (-3 bytes).

@Blackhole Indeed you can. Thank you!

@Blackhole I think that would break functionality. It will perform the assignments even if the condition isn't met.

@Blackhole Still breaks it, I'm afraid XD $t-- must only happen if the condition is met.

C#: 236 Chars
int p(int[,] a){int y=0,s=0,i=0,x;for(;++y<=a.GetUpperBound(0);)for(x=i;x<=a.GetUpperBound(1);){if(a[y,x++]==0)break;s=y;i++;}return s;}

ungolfed:
int p(int[,] a)
{
    int selectedRow=0;
    int maxLength=0;
    for(var y = 0; y<=a.GetUpperBound(0); y++)
        for(var x=maxLength; x<=a.GetUpperBound(1); x++)
        {
            if(a[y,x++]==0)
                break;
            selectedRow=y;
            maxLength++;
        }
    return selectedRow;
}

Cobra - 98
def f(a)
    s,x,y=0,0,a.count-1
    while y+1and x<a[0].count
        while a[y][x],y,s=y-1,x
        x+=1
    print s

OCaml - 144 characters
let s a=Array.(let rec f i j m=if i=0then m else if a.(i).(j)=0then if j=length a.(i)-1then m else f i(j+1)m else f(i-1)j j in f(length a-1)0 0)

Takes an int array array as input, and starts from below left, moving up or right if it sees a 1 or a 0. Column count starts at 0.
Usage
 s [| [| 0; 0; 0; 0 |]; [| 0; 0; 1; 0|]; [| 1; 0; 1; 0 |]; [| 1; 1; 1; 0 |]; [| 1; 1; 1; 1 |] |];;
 - : int = 2

Ungolfed
let s a = Array.(
  let rec f i j m = (* m is the longest stick seen so far *)
    if i=0 then m (* A column is full: this is the longest possible stick and j=m anyway *)
    else if a.(i).(j)=0 then (* current column is shorter than a previously seen stick *)
      if j=length a.(i)-1 then m (* we have examined all columns, just return m *)
      else f i(j+1) m (* start examining next column *)
    else f (i-1) j j (* current column is longer than all the ones previously seen. Check how long the stick is *)
  in
  f (length a-1) 0 0)

T-SQL - 71 64
Takes table A as input
SELECT IDENTITY(INT, 1, 1) R, A INTO A
FROM (VALUES
 ('0000')
,('1000')
,('1101')
,('1111')
) AS A(A)

And the query is
SELECT TOP(1)CHARINDEX('1',A)FROM A WHERE A LIKE'%1%' ORDER BY R

SQLFiddle
This returns the first row from the table a ordered by r where there is a 1 in string a.
TOP(1) restricts the result to the first row returned.
CHARINDEX('1',A) returns the position of the first 1 in the string or zero if it isn't found.
WHERE A LIKE'%1%' filters to rows where A contains a 1
ORDER BY R ensures the table is read from top down

Can you explain what's going on in that code ? :D No experience with T-SQL

I see, so isn't the filtering on each row part an O(n*m) operation ? i.e. not linear time complexity.

Difficult to say.  The SQL engine will check all the rows for a 1 in the column.  It will only return only the first row from the top down that qualifies.  So in this situation it scans the entire table.  Filters the rows with the column containing 1.  Sorts the results on the identity column and returns the first result.

Look at it like this : What if your rows are like "0000","0000","0000","0001" . In this case, it will have to go till the last row and till the last character of the row to figure out the presence of 1

That's what it is doing in the background.  It is reading each row of the table.  Then for each value in column A it is scanning the string for the existence of a 1.

So yeah, it is O(m*n) then :)

Delphi 122 chars
Sigh...it is such a voluminous language.
Update: had to add 6 characters in changing function the return type from I to integer. The function still compiled as the test program had a "type I=integer;" statement left over from an earlier version of the program.
function S(A:array of string):integer;var n,c:integer;begin n:=0; repeat c:=Pos('1',A[n]);inc(n) until c>0; result:=c;end;

Are you doing the Pos() call on each row (in your case, string) of the Array ?

@Optimiser Yes, the program searches each string in the array (using 'inc(n)') until it finds a '1'. The first '1' found will be the highest (or equal highest) '1', so its position in the string (strings are 1-ndexed in delphi) will be the position of the longest column. Routine fails if there are no '1's in the array, but I believe that this would be broken input as there would then not be a "longest stick" to be found.

So first of all, this is a valid input: "0000", "0010", "1111" , secondly, your answer is not meeting the linear time complexity requirement

@Optimizer Yes, that would be valid input and correctly identifies the 3rd stick. But I realised after making the post that I had converted my valid order N program that used arrays, into an invalid order N^2 program that used strings (chasing a reduction from ~160 characters).

scheme - 236 chars
Even longer than the delphi version...there is probably a way to do this much more efficiently with scheme. And even worse - I just noticed it is order m*n.
(define (s l) (cond ((eq? (cdr l) '()) (car l)) (else (map + (car l) (s (cdr l)))))) (define (u l) (define (t n p q l) (cond ((eq? l '()) p) ((< n (car l)) (t (car l) q (+ 1 q) (cdr l))) (else (t n p (+ 1 q) (cdr l))))) (t 0 0 1 (s l)))

l is a list of the form '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1)). I think that is a fair representation of a 2D array input for scheme.
(s l) sums the n-th elements of each of the sub-lists of a list of lists of nuimbers, so (s '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))) would return (3 2 1 2).
(u l) returns the 'index' of the largest entry of a list of numbers (using the helper function t), so (u '(3 2 1 2)) will return 1 (as the largest element '3 in the list '(3 2 1 2) is at position 1).

Summing all sublists is an O(m*n) operation.

Racket 70
Golfed:
(define(h m)(for/last([r m]#:final(memv 1 r))(length(takef r even?))))

Assumes input is a two-dimensional array, which in Racket would be a list of lists:
(define m
  '((0 0 0 0)
    (1 0 0 0)
    (1 1 0 1)
    (1 1 1 1)))

Ungolfed:
(define (h m)
  ;; step through rows, stopping at the first that contains a 1
  (for/last ([r m] #:final (memv 1 r))
    (length (takef r even?)))) ; pop off the leading zeroes to get the column index

Returns the column index with the longest stick.

So basically you are going through each column and counting the number of 1's ?

I see your point. Algorithm updated.

This still has a worst-case complexity of O(m*n) (for the case in which there is no 1 in the matrix, or only in the bottom row).

JavaScript, ES6, 76 characters
W=a=>(j=>{for(k=i=a.length-1;~i&~j;)a[i][j]?(k=j,i--):j--})(a[0].length-1)|k

Takes array of array input.

JavaScript ES6, 65 bytes
Takes both input formats
f=(a,t)=>a.reduceRight((p,c)=>t+1?t:(x=c.indexOf(1,p))+1?x:t=p,0)

Explained:
Iterates from bottom to top. Uses String.prototype.indexOf() or Array.prototype.indexOf() depending on the input on each value. Finds the first index of each row with a 1 from the previous offset, if it finds none then it sets the t variable to the last offset and doesn't perform anymore indexOf calls.

indexOf works in either O(log n) or O(n), so the overall algorithm will never be in O(m + n)

@Optimizer Yeah realised that was its O(m*n) wasn't thinking straight.

@Optimizer Updated to be O(m+n)

authors: Алексей Баранов

authors: Джохар Дзохов


text:
Integer Emotions
Write a program or function that "reacts" to a given integer n (input via function parameter/args/stdin)
The program doesn't care about negative numbers, likes even, dislikes odd numbers and fears the number 13.
It should output the following:
if n<0:
 --------------------------
 |                        |
 |                        |
(|      _          _      |)
 |                        |
 |                        |
 |                        |
 |                        |
 |       oooooooooo       |
 |                        |
 |                        |
 |                        |
 --------------------------

if n%2 == 0 and n>-1:
 --------------------------
 |                        |
 |                        |
(|      ^          ^      |)
 |                        |
 |                        |
 |                        |
 |     o            o     |
 |       oooooooooo       |
 |                        |
 |                        |
 |                        |
 --------------------------

if n%2 == 1 and n>-1 and n!=13:
 --------------------------
 |                        |
 |                        |
(|      >          <      |)
 |                        |
 |                        |
 |                        |
 |                        |
 |       oooooooooo       |
 |     o            o     |
 |                        |
 |                        |
 --------------------------

if n==13:
 --------------------------
 |                        |
 |                        |
(|     (O)        (O)     |)
 |                        |
 |                        |
 |       oooooooooo       |
 |       o        o       |
 |       oooooooooo       |
 |                        |
 |                        |
 |                        |
 --------------------------

The shortest solution in bytes wins.

13 is odd. Do we only output one face? Negatives are odd and even...

@MartinBüttner, in that case the first rule about negative numbers is completely unnecessary. The only priority which actually requires all of the rules is for the first and last ones to have priority over the middle ones.

@PeterTaylor oops, good point.

@StandardToaster I edited the output conditions to avoid any misunderstandings

CJam - 169
S24*aB*2li_D=3{_0<2{_2%}?}?\;:X"^^<>__":s"(O)"a2*+2/=~6X3=-{S*_@+_,C\-S*2*+@@++}:F~t7'o5*_7F:MtX3={5Mt6'o_7Ft}*X2<{X2*6+'o_5Ft}*{" |"\+'|+}%S'-26*+aa2*\*_3=1>"()"\*3\tN*

Try it at http://cjam.aditsu.net/
High-level explanation:
S24*aB* makes a matrix full of spaces, for the face without the edges
li_D=3{_0<2{_2%}?}?\;:X reads the number and converts it to 0 (even), 1 (odd), 2 (negative) or 3 (13), storing it in X
X"^^<>__":s"(O)"a2*+2/=~ selects the eye types (2 strings)
{S*_@+_,C\-S*2*+@@++}:F - function F takes 2 strings (say S1, S2) and a number (say N) and makes a 24-char string containing N spaces, S2, other spaces, S1, N spaces
2 (eyes) 6X3=- (F)~t puts the eyes line in the matrix
7'o5*_7F:Mt puts the common mouth line in the matrix, and also saves it in M
X3={5Mt6'o_7Ft}* if X is 3, it puts M again in the matrix, 2 lines higher, and puts the mouth sides in between
X2<{X2*6+'o_5Ft}* if X is 0 or 1, it puts the mouth corners in the appropriate position
{" |"\+'|+}% adds vertical edges and a space on the left on every line
S'-26*+aa2*\* adds the horizontal edges
_3=1>"()"\*3\t adds the ears
N* adds newline separators

Ruby, 241 224
f=->n{s=" #{?-*26}
"
s+=" |#{' '*24}|
"*11+s
s[84]=?(
s[110]+=?)
s[233,12]=m=?O*12
s[91,3]=s[102,3]=n<0?' _ ':n==13?(s[177,12]=m;s[205]=s[216]=?O;'(O)'):(s[203+d=n%2*56]=s[218+d]=?O;" #{n%2<1??^:b=?>} ")
s[103]=?<if b
$><<s}

This defines a function to be called like f[13]. I'm sure there's a lot of room for improvement, similar what Ventero helped me do here.
Basically, I'm building the rough framework first, and attach ears as well as the mouth. Then I place the eyes depending on the number. While working out the characters to put into the eyes, I also take care of the different mouths so I don't have to check for the type of number again. Finally I need to fix the right eye for odd numbers, because the code above puts the same string into both eyes.

C# - 349 bytes
Certainly not going to win any awards, but a different way of doing things.
Golfed:
class P{static void Main(string[]A){int j=64,i,r=0,n=int.Parse(A[0]);for(var f=(n<0?"IDID-TDTD-":n==13?"HDHD(IDIDOJDJD)SDSD(TDTDOUDUD)KIRI JHSJo":n%2<1?"IDID^TDTD^HIHIoUIUIo":"IDID>TDTD<HKHKoUKUKo")+@"JJSJoCBZM BB[M|BA[N-ADAD(\D\D)AA\N AA]N"+"\n";j++<78;)for(i=64;i++<93;System.Console.Write(f[r]))for(r=0;f[r++]>i|f[r++]>j|i>f[r++]|j>f[r++];r++);}}

Less golfed:
class P
{
    static void Main(string[]A)
    {
        int j=64,i,r=0,n=int.Parse(A[0]); // everything is offset by 65 in this program

        for(
            var f=(n<0?"IDID-TDTD-": // this string describes a set of rectangles (x1,y1,x2,y2,ch)
                n==13?"HDHD(IDIDOJDJD)SDSD(TDTDOUDUD)KIRI JHSJo":
                n%2<1?"IDID^TDTD^HIHIoUIUIo":
                "IDID>TDTD<HKHKoUKUKo"
                )+@"JJSJoCBZM BB[M|BA[N-ADAD(\D\D)AA\N AA]N"+"\n";

            j++<78;) // the loop then prints the rectangles to the screen
            for(i=64;i++<93;System.Console.Write(f[r]))
                for(r=0;f[r++]>i|f[r++]>j|i>f[r++]|j>f[r++];r++);
    }
}

Python 2 - 255
Not really short, but I'll post it anyway:
n=input()
o='o'
S='  '
w=y=7*S
b=' '+'-'*26+'\n'
p=' |%19s     |\n'
E=p%y*2
v=S+o*10+S
u=z=o+6*S+o
A=a='^ '
if n%2:A='< ';a='> ';u=y;w=z
if n<0:A=a='_ ';u=w=y
if n==13:A=a='(O)';u=w=v;v=S+o+S*4+o+S
print b+E+'(|%8s%11s     |)\n'%(a,A)+E+p%u+p%v+p%w+E+b

I miss item assignment for strings in Python! :(
Then one could start with the character matrix and simply modify eyes and mouth.

Originally I actually learned Ruby for a similar PPCG challenge where I need immutable strings for precisely that reason. :D

You can do b=bytearray() and then b+'mystring' will generate a mutable bytearray, which prints the same way as any other string.

Python 2, 257
Not a winner, but an alternate approach, got quite close! I have hope I can squeeze a few more chars out of it. Builds all the lines piece by piece, using common substrings to really squeeze out the bytes.
X,Z=R=" |"
Q=X*5
Y=X*7
A=X+"-"*26
B=R+X*24+Z
n=input()
a,b,c,d,e,f,g=((("^>^<o  o "+Q)[n%2::2],"OO  ()o")[n==13],"__"+Q)[n<0]
for F in(A,B,B,"(|"+Q+e+a+f+Y+X+e+b+f+Q+"|)",B,B,R+Y+g*10+Y+Z,R+Q+c+X+g+Y+X+g+X+c+Q+Z,R+Y+"o"*10+Y+Z,R+Q+d+Y+Q+d+Q+Z,B,B,A):print F

CJam, 202
[S'-26*N]:Z[S'|:PS24*PN]:RR'(PS5*qi:XD=X0<-X2%2*+:Y[" ^ "_" > ""(O)"" - "__]=S8*Y[" ^ ""   "" < ""(O)"" - "__]=S5*P')NRRXD=[SPS7*'oA*S7*PN]:QR?Y[[SPS5*'oSC*'oS5*PN]:T_R[SPS7*'oS8*'oS7*PN]RRR]=QY2=TR?RRZ