text:
Predict where the man will go
A man lives in the north-west corner (0, 0) of a town with height h and width w . Everyday he walks from his home to the border (?, w) or (h, ?). In the following example, the man goes to (3, 3) today.
(0, 0) +--+  +  +  . (0, 4)
          |
       +  +--+--+  .
                |
       +  +  +  +  .
                |
(3, 0) .  .  .  .  . (3, 4)

The man records a bit at each points (+ in example above). Every time he reaches a point, he goes east if the bit is 1 and south otherwise. The bit is flipped after he leaves. For example:
Day 1: 1--0  1  1    Day 2: 0  1  1  1    Day 3: 1--1--1--1--  Day 4: 0  0  0  0
          |                 |                                         |
       0  1--0  0           0  0  1  0           1  0  1  0           1--0  1  0
             |              |                                            |
       1  0  1--0           1--0  0  1           0  1  0  1           0  1--0  1
                |              |                                            |
Destination: (3, 3)  Destination: (3, 1)  Destination: (0, 4)  Destination: (3, 2)

Given the size of the town and the man's record, calculate the man's destination after n days.
Input:
In the first line are three integers, h, w and n.
In the following h lines are w integers, denoting the man's record.
h <= 1000, w <= 1000, n <= 1000000000
Output:
Two integers, denoting the man's destination after n days.
Sample Input:
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

Sample Output:
0 4

Sample Code:
#include <iostream>
using namespace std;
bool d[1000][1000];
int main(){
    int h, w, n;
    cin >> h >> w >> n;
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            cin >> d[i][j];
    int i, j;
    while(n--)
        for(i = 0, j = 0; i < h && j < w;){
            bool &b = d[i][j];
            d[i][j] ? j++ : i++;
            b = !b;
        }
    cout << i << " " << j << endl;
}

Scoring:

Lowest byte count in UTF-8 wins.
If the running time of your code is independent of n, reduce your score by 50%.

Don't just calculate the results of all 1000000000 days or do anything similarly stupid to get this bonus. Find an efficient algorithm!

2 things I dont understand. The output, sometimes you use 0 index other times you dont. How does that work? Should it be like border+1? Second thing is the second line with scoring. How do you mean that?

Day 4 should output 3,2 right?

If, no matter what n is, my code calculates the results of all 1000000000 days, then output the result of n, do I still get the -50% bonus?

@ace now you put it like that, it does make sense doesnt it? Thanks for that :P

@TeunPronk Yes. It's my fault.

@ace Literally you do, but you'll definitely get my down-vote and I won't accept that as an answer.

@johnchen902 aww, dont downvote my answer, ill change it after lunch. :)

And the cheeky answer is print "0 0" since he always returns home every day.

@johnchen902 deleted my answer for a bit, think thats better :P

@johnchen902: That's not very sporting, to punish somebody who finds a loophole in your rules. The better approach would be to fix the rules so there's no loophole.

@Claudiu I know. I did fix the loophole and I didn't down-vote anyone. That comment was just a fierce version of don't do that.

Anyone who finds this scenario interesting might also like to read about Chris Langton's ant.

GolfScript, 52.5 (105 characters with 50% bonus)
~](;(\((2$(1,*+\@/{]zip 0\{~@@+.2$!+2/\@+.2/\@[\1&]}%zip~@;}%\;[{.0=0=\1${{1>}%}{1>}if.{~}%}do;].1-,n@0-,

The version is very efficient and can be tested online even for large values.
It uses an approach similar to user2357112's solution.

Please don't ask for an explanation ;-) I can't even change it without breaking and debugging this beast is horrible.

Python 2, 192 bytes * 0.5 bonus = 96
To solve this problem efficiently, the key realization is that we can compute how many times each cell is visited based on the number of times the cells above and to the left are visited, without needing to determine the exact paths taken. Effectively, we simulate n trips at once and keep track of how many times each cell is used.
Substantial improvement due to push-based approach inspired by johnchen902's solution:
r=lambda:map(int,raw_input().split())
h,w,n=r()
v=[n]+w*[0]
x=y=0
for i in range(h):
 for j,b in enumerate(r()):
    if i-x==j-y==0:d=v[j]&1^b;x+=d;y+=1^d
    f=v[j]+b>>1;v[j]-=f;v[j+1]+=f
print x,y

Previous, pull-based implementation:
r=lambda i:map(int,raw_input().split())
h,w,n=r(0)
x=range(h)
g=map(r,x)
v=[w*[0]for i in x]
v[0][0]=n-1
for i in x:
 for j in range(w):v[i][j]+=(i and(v[i-1][j]+(1^g[i-1][j]))/2)+(j and(v[i][j-1]+g[i][j-1])/2)
i=j=0
while i<h and j<w:f=g[i][j]^v[i][j]&1;j+=f;i+=1^f
print i,j

Original, ungolfed version:
h, w, n = map(int, raw_input().split())
grid = [map(int, raw_input().split()) for i in xrange(h)]

# Determine the number of times each cell was visited in the first n-1 trips
visits = [[0]*w for i in xrange(h)]
visits[0][0] = n-1
for i in xrange(h):
    for j in xrange(w):
        if i:
            # Count visits from above cell
            visits[i][j] += (visits[i-1][j] + (not grid[i-1][j])) // 2
        if j:
            # Count visits from left cell
            visits[i][j] += (visits[i][j-1] + grid[i][j-1]) // 2

# Flip the bits corresponding to each cell visited an odd number of times
for i in xrange(h):
    for j in xrange(w):
        grid[i][j] ^= visits[i][j] & 1

# Figure out where the final trip ends
i = j = 0
while i < h and j < w:
    if grid[i][j]:
        j += 1
    else:
        i += 1

print i, j

You can shorten the not  to 1^ and the long if condition can be written f=g[i][j]^v[i][j]&1 j+=f i+=1^f.

@Howard: Thanks. Edits applied.

If you allow r to take a parameter (r = lambda x: ...), then you can shorten g=[r()for i in x] to g=map(r,x).

@RobertoBonvallet: Yup. Advice implemented.

Ruby, 159 143
n,*l=$<.read.split$/
i=->a{a.split.map &:to_i}
x=y=l.map!{|k|i[k]}
(n=i[n])[-1].times{x=y=0
(x+=f=l[x][y]^=1;y+=f^1)while x<n[0]&&y<n[1]}
p x,y

The first line uses the * operator to grab the first line of input in one variable, and the rest of the input in another. Then an i function is defined to convert "1 2 3 4" into [1, 2, 3, 4], which is applied to both l and n. (x and y are saved for later.)
n[-1] is the last element of n, so the following block (the simulation) is executed that many times. First, x and y are initialized to zero (they are declared outside the block so that their scope is large enough), and then the simulation line is executed, which is pretty self-explanatory, but here's some commentary anyway:
l[x][y]<1?            is it zero (less than one)?
x+=l[x][y]=1          if it's zero, set it to one, and (conveniently) we can add that to x
:y+=(l[x][y]=0)+1     otherwise, set it to zero, add one, and add that to y
 while x<n[0]&&y<n[1] keep doing this while we're still inside the array

Edit: new simulation line provided by Howard, thanks! I'm pretty sure I understand how it works but I don't have time to add an explanation, so one will be added later.
Finally, p x,y outputs the numbers, and we are done!

Some basic wins: change the newline to $/ and the while loop can be reduced to (x+=f=l[x][y]^=1;y+=f^1)while x<n[0]&&y<n[1]}.

C++ 213 bytes * 0.5 = 106.5
Here is my solution. It's similar to user2357112's solution, but there are several difference:

First, I dispatch visiting times to the right and bottom, instead of compute them from the top and left.
Second, I do everything (reading input, dispatching, tracking the man's location) simultaneously.
Third, I keep only one row of memory.

#include <iostream>
int o[1001],h,w,r,c,i,j,t,u;int main(){std::cin>>h>>w>>*o;for(;i<h;i++)for(j=0;j<w;)std::cin>>t,u=o[j],o[j]/=2,u%2&&o[j+t]++,r-i|c-j||((u+t)%2?r:c)++,o[++j]+=u/2;std::cout<<r<<" "<<c<<"\n";}

Here is the ungolfed version:
#include <iostream>
using namespace std;
int o[1001];
int main(){
    int h, w, n;
    cin >> h >> w >> n;
    o[0] = n;
    int r = 0, c = 0;
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++){
            bool t;
            cin >> t;
            int u = o[j];
            o[j + 1] += u / 2;
            o[j] = u / 2;
            if(u % 2)
                (t ? o[j + 1] : o[j])++;
            if(r == i && c == j)
                ((u + t) % 2 ? r : c)++;
        }
    cout << r << " " << c << endl;
}

These three differences make things much terser. We can shorten the indexing and combine several redundant data structures. The logic for pushing visits forward turns out to be much shorter than the logic for pulling visits from previous cells. Horizontal boundary conditions are handled simply by extending the data structure an extra space to the right, and vertical boundary conditions aren't an issue.

I've upvoted your answer and incorporated the concepts into my own code. So far, they've taken 84 bytes out of my solution, an improvement of 30%.

I suspect you might be able to save some bytes by not doing --*o;, and instead switching which case you move the guy down and which case you move the guy to the right.

@user2357112 Implemented, but code length increase due to a previous mistake (It should have been 218 bytes).

Delphi XE3 (437 bytes|| 897874 without bonus counted)
When thinking about how to solve this with the bonus I thought of the following.
If you walk 4 days cell 0,0 is changed 4 times. The cell on its right is changed twice aswell as the cell beneath it.
If there is an uneven number of days and the number in the cell starts with 1 the cell on the right gets one more than the cell beneath, and the other way around if the cell is 0.
By doing this for every cell you can see if the end value should be changed by: Cell was changed X times. if X mod 2>0 then change the cell.
Results in the following code:
{Whispers at JohnChen902} do I get your upvote now? :P
uses SysUtils,Classes,idglobal;var a:TArray<TArray<byte>>;b:TArray<TArray<int64>>;h,w,x,y,t:int16;n:int64;s:string;r:TStringList;tra:byte;begin r:=TStringList.Create;readln(h,w,n);h:=h-1;w:=w-1;for y:=0to h do begin readln(s);r.Add(StringReplace(s,' ','',[rfReplaceAll]));end;SetLength(a,h);SetLength(b,h);for y:=0to h do begin SetLength(a[y],w);SetLength(b[y],w);for x:=1to Length(r[y])do a[y][x-1]:=Ord(r[y][x])-48;end;b[0][0]:=n-1;for Y:=0to h do for X:=0to w do begin t:=b[y][x];if x<w then b[y][x+1]:=b[y][x+1]+iif((t mod 2=1)and(a[y][x]=1),(t div 2)+1,t div 2);if y<h then b[y+1][x]:=b[y+1][x]+iif((b[y][x]mod 2=1)and(a[y][x]=0),(t div 2)+1,t div 2);end;for Y:=0to h do for X:=0to w do if b[y][x]mod 2=1then a[y][x]:=iif(a[y][x]=1,0,1);y:=0;x:=0;repeat a[y][x]:=iif(a[y][x]=1,0,1);if a[y][x]=1then inc(y) else inc(x);until(y>h)or(x>w);write(Format('%d %d',[y,x]));end.

Ungolfed
uses
  SysUtils,Classes,idglobal;
var
  a:TArray<TArray<byte>>;
  b:TArray<TArray<int64>>;
  h,w,x,y,t:int16;
  n:int64;
  s:string;
  r:TStringList;
  tra:byte;
begin
  r:=TStringList.Create;
  readln(h,w,n);
  h:=h-1;w:=w-1;
  for y:=0to h do
  begin
    readln(s);
    r.Add(StringReplace(s,' ','',[rfReplaceAll]));
  end;
  SetLength(a,h);
  SetLength(b,h);
  for y:=0to h do
  begin
    SetLength(a[y],w);
    SetLength(b[y],w);
    for x:=1to Length(r[y])do
      a[y][x-1]:=Ord(r[y][x])-48;
  end;
  b[0][0]:=n-1;
  for Y:=0to h do
    for X:=0to w do
    begin
      t:=b[y][x];
      if x<w then
        b[y][x+1]:=b[y][x+1]+iif((t mod 2=1)and(a[y][x]=1),(t div 2)+1,t div 2);
      if y<h then
        b[y+1][x]:=b[y+1][x]+iif((b[y][x]mod 2=1)and(a[y][x]=0),(t div 2)+1,t div 2);
    end;
  for Y:=0to h do
    for X:=0to w do
      if b[y][x]mod 2=1then
        a[y][x]:=iif(a[y][x]=1,0,1);
  y:=0;x:=0;
  repeat
    a[y][x]:=iif(a[y][x]=1,0,1);
    if a[y][x]=1then
      inc(y)
    else
      inc(x);
  until(y>h)or(x>w);
  write(Format('%d %d',[y,x]));
end.

You haven't get my vote yet. I was eating dinner. (Upvoted)

Python, 177 bytes
My first try ever in Code Golfing, so sorry if I got something wrong here!
Code used to grab the input based on user2357112's code.
l=lambda:map(int,raw_input().split())
h,w,n=l()
m=[l() for i in[1]*h]
while n>0:
 n-=1;x=y=0
 while x!=w and y!=h:
  if m[y][x]>0:m[y][x]=0;x+=1
  else:m[y][x]=1;y+=1
print y,x

Input:
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

Output:
0 4

R, 196 bytes * 0.5 = 98
f=function(h,w,n,x){I=J=rep(1,n);for(i in 1:h)for(j in 1:w){M=which(I==i&J==j);N=length(M);if(N){z=seq(1,N,by=2);if(x[i,j])z=-z;f=M[-z];s=M[z];I[f]=i;J[f]=j+1;I[s]=i+1;J[s]=j}};cat(I[n]-1,J[n]-1)}

Ungolfed:
f=function(h,w,n,x) {
  I = J = rep(1,n)

  for(i in 1:h) for(j in 1:w) {
    M = which(I==i&J==j)
    N = length(M)
    if (N) {
      z = seq(1,N,by=2)
      if (x[i,j]) z = -z
      f = M[-z]
      s = M[z]
      I[f] = i
      J[f] = j+1
      I[s] = i+1
      J[s] = j
    }
  }
  cat(I[n]-1, J[n]-1)
}

Usage:
f(3,4,4,matrix(c(1,0,1,0,1,0,1,0,1,1,0,0),3))
3 2


text:
Which is better - Emacs or Vim? (Google fight)
Greetings, noble code golfers. Today you will resolve the most ancient and distinguished of debates - Emacs or Vim?
Your challenge is to take two search terms as input, and output which of those terms has the most Google search results. (This is obviously completely fair. What do you mean, biased?)
Here are some example inputs and outputs:
Input: emacs and vim
Output: vim (totally not creating any flamewars in the comments)
Input: google and microsoft
Output: google
Input: code golf stack exchange and code review stack exchange
Output: code golf stack exchange (yeah!)
And here are some edge cases just for fun (and for testing your solutions):
Input: About 1,000,000 results and About 100,000 results
Output: About 100,000 results
Input: This will autocotrect and Another testcase
Output: Another testcase (if you don't consider autocorrecting, then the first one will win)
For the following test cases, you must remove the # signs in the search terms first, since they rely on the term having a specific amount of results and posting the term here would ruin that.
Input: Thissear#chter#mhasno#results and Another testcase
Output: Another testcase (just a test for zero results)
Input: "These exact wo#rds do#n't exi#st# on the Internet" and Another testcase
Output: Another testcase (testing "s)
Input: Abo#ut 1,65#2,85#3,2#86 re#sults and Another testcase
Output: Another testcase (this one is tricky - the above search term has one result)
Input: "Abo#ut 4#8,234,8#75,14#7 res#ults" and Another testcase
Output: Another testcase (also tricky - no results, so it displays the search term)
You don't need to handle the corner-case of "quoted" searches returning "No results, showing results without quotes instead" because that would just be too complicated. You don't need to handle inputs with the same number of results either.
This is code-golf, so the shortest code in bytes will win!

Psst... you should change the accepted answer :D

@tac Alternatively, I can golf it down instead, which I did. ;)

How flexible's the output / return value? Does it have to be a string, or can it be an array containing the string and the number of results it had, or an array containing just the string?

it's so clear than vim is better I was surprised on this question that anyone could believe that something is better

Factor, 305 201 196 200 201 188 184 182 179 169 178 171 165 199 171 170 165 163 bytes
A language nearly as verbose as Java, beating Ruby... and Powershell! :D
Better regex, now. Thanks to @fede s. for 5 bytes off!
[ dup [ url-encode "google.com/search?nfpr=1&q="prepend http-get R/ s">About [\d,]+/ first-match " "split second 10 >base ] map zip [ last ] sort-with last first ]

Or 159 157 if the output can be like { "vim" 9782948234 }:
[ dup [ url-encode "google.com/search?nfpr=1&q="prepend http-get R/ s">About [\d,]+/ first-match " "split second 10 >base ] map zip [ last ] sort-with last ]

On the other hand, if we want to be unkillable, for 199 196 193 bytes:
[ dup [ url-encode "google.com/search?nfpr=1&q="prepend scrape-html nip dup "resultStats"find-by-id-between second text>> " "split second string>number ] map zip [ last ] sort-with last first ]

Unkillable because it parses HTML, so way more robust than the answers using regex.

And python. Good for Factor. :P

@EasterlyIrk so close yet so far

@EasterlyIrk I did it!

This is missing the nfpr query string parameter, so it will fail for the autocorrect test cases. It also probably fails for a search term containing About 1 or similar. (I don't have Factor, so I can't test it.)

@Doorknob fixed

@Doorknob In that case, wouldn't any other regex solution also fail?

Someone should make a Factor golfing dialect, so much whitespace, words so long... Well done, man!

@fedes. I've been thinking about it, in fact, I'm just not sure how to actually do it since there are so. many. words and so. many. vocabularies just in the standard lib. If you've got ideas, I'm all ears :D

Thank you for the unkillable method.  It's actually shorter in powershell than using a regex.  (Yet still 2 bytes longer than your regex answer).  I wouldn't call powershell succint though, it's command names are rarely short (iwr happens to be a default alias for invoke-webrequest and sort for sort-object, otherwise it'd be that much longer)

Ruby, 203 180 bytes
->*s{s.map{|x|[(open("http://www.google.com/search?nord=1&q=#{URI.escape x}&nfpr=1").read.match(/s">(About )?([\d,]+) result/)||[?0])[-1].split(?,).join.to_i,x]}.max[1]}

+11 bytes for the -ropen-uri flag (plus space).
Input is taken as two arguments.
URL explanation:

?nord=1: prevent auto-redirect from HTTP to HTTPS
&q=#{URI.escape x}: escape the query so "s work
&nfpr=1: no autocorrect

The whole map turns ['emacs','vim'] into [[2150000, 'emacs'], [14900000, 'vim']]. (You can see this by changing the .max[1] at the end to .inspect.) Then, the max is taken, which will grab the one with the most results, and [1] is used to get the search term.

It doesn't work for me. http://ideone.com/UqEyBn

@TheDoc It doesn't work on Ideone - run it on actual Ruby

You can save a few more bytes by requiring in the command ruby -ropen-uri instead of in the file.

Why won't this (and the other regex answers) break on searches like "About 100,000,000 results"?

@cat Note the s"> at the start of the regex. That makes sure the result count is preceded by a certain HTML tag (I don't remember which one; probably something like  or something).

@Doorknob Ooh, I didn't see that at first (by the way, it's
 :P)

Of the text editors mentioned in the problem, only one of them can solve this on its own...
Emacs: 137 keystrokes
<C-o><C-u><C-k>(if(<<C-y><C-y><M-<><C-n><F3><C-a>http://google.com/search?nfpr=1&q=<C-S-e><M-x>r-st<RET> <RET>+<RET><C-a><C-k><M-x>b-em<RET><C-y><RET><C-x><C-q><C-s><RET>ts"><RET><M-z><<C-x>0<C-y>0 r<C-a><C-M-s><RET>[0-9]<RET><C-b><M-z> <C-a><C-y><C-k><C-S-a><M-x><up><up><RET>,<RET><RET><F4><C-n><F4><C-e>)(next-line)())<C-x><C-e><C-n><C-a><C-k><C-x>h<C-y>

It expects the first search terms to be on the first line and the second search terms to be on the second line, with the cursor at the beginning of the buffer.
For those unfamiliar with Emacs,

C-s means Ctrl-S.
M-z means Alt-Z (Alt is likely your meta key)
M-< means Alt-< or Alt-Shift-,
C-S-e means Ctrl-Shift-e

For those familiar with Emacs,

Start emacs with emacs -q. That doesn't load your .emacs file, so any fancy packages won't intefere with this.

Explanation

Write the beginning of the elisp statment shell

<C-o><C-u><C-k> Saves the arguments with a newline
(if(<<C-y><C-y> Write the start of the if statement and places 2 copies of the arguments
<M-<><C-n> Move to the second line

Define the HTTP macro. This converts the argument to a Google search URL and then returns the number of search results.

<F3> Start defining the keyboard macro
<C-a> Move to the start of the search term.
http://google.com/search?nfpr=1&q= Prepend the search URL
<C-S-e><M-x>r-st<RET> <RET>+<RET> Replace all the spaces with + signs.
<C-a><C-k><M-x>b-em<RET><C-y><RET> Emacs retrieve the raw HTML (b-em is short for browse-url-emacs)
<C-x><C-q> Make the file writable (required so the macro doesn't error ou t)
<C-s><RET>ts"><RET> Move to the number of results div (need to do a regular search because emacs macros rely on isearch to work)
<M-z><Cut the text of of the diff (this is why the  was required)
<C-x>0 Switch back to the original buffer
<C-y>0 r;; Put the results back on the line ('0 r' handles no results)
<C-a><C-M-s><RET>[0-9]<RET><C-b><M-z> <C-a><C-y><C-k>;; Extract the number from the string.
<C-S-a><M-x><up><up><RET>,<RET><RET> Strips commas out of the number
<F4> Finish the keyboard macro

Move down and execute the keyboard macro on the next line.

<C-n> Goes to the next line
<F4> Repeat the macro once.

Finish up the elisp statement and execute it

<C-e>)(next-line)())  Finish up the elisp statement
<C-x><C-e> Evaluate the elisp command
<C-n><C-a><C-k> Kill the winning argument
<C-x>h Delete everything else
<C-y> Paste the winning argument

Running It Yourself
Luckily you don't have to type all those keystrokes in perfectly! The meat and potatoes is all in a macro that you can just copy and paste. The macro can be copy and pasted into emacs!
1.Edit the keyboard macro <C-x><C-k><C-e>
2.Paste this into the whole buffer (paste should be <C-y>)
;; Keyboard Macro Editor.  Press C-c C-c to finish; press C-x k RET to cancel.
;; Original keys: C-a http://google.com/search?nfpr= 1&q= S-C-e M-x r-st RET SPC RET + RET C-a C-k M-x b-em RET C-y RET C-x C-q C-s RET ts"> RET M-z < C-x 0 C-y 0 SPC r C-a M-C-s [0-9] 5*DEL RET [0-9] RET C-b M-z SPC C-a C-y C-k S-C-a M-x 2*<up> RET , 2*RET
Command: last-kbd-macro
Key: none
Macro:
C-a         ;; move-beginning-of-line
http://google.com/search?nfpr=  ;; self-insert-command * 30
1&q=            ;; self-insert-command * 4
S-C-e
M-x         ;; execute-extended-command
r-st            ;; self-insert-command * 4
RET         ;; newline
SPC         ;; self-insert-command
RET         ;; newline
+           ;; self-insert-command
RET         ;; newline
C-a         ;; move-beginning-of-line
C-k         ;; kill-line
M-x         ;; execute-extended-command
b-em            ;; self-insert-command * 4
RET         ;; newline
C-y         ;; yank
RET         ;; newline
C-x C-q         ;; read-only-mode
C-s         ;; isearch-forward
RET         ;; newline
ts">            ;; self-insert-command * 4
RET         ;; newline
M-z         ;; zap-to-char
<           ;; self-insert-command
C-x 0           ;; delete-window
C-y         ;; yank
0           ;; self-insert-command
SPC         ;; self-insert-command
r           ;; self-insert-command
C-a         ;; move-beginning-of-line
M-C-s           ;; isearch-forward-regexp
RET         ;; newline
[0-9]           ;; self-insert-command * 5
RET         ;; newline
C-b         ;; backward-char
M-z         ;; zap-to-char
SPC         ;; self-insert-command
C-a         ;; move-beginning-of-line
C-y         ;; yank
C-k         ;; kill-line
S-C-a
M-x         ;; execute-extended-command
2*<up>          ;; previous-line
RET         ;; newline
,           ;; self-insert-command
2*RET           ;; newline

Type <C-c><C-c> to save the macro.
If following the explanation steps, replace step 2 with <F4> to run the macro (or just run it on its own to try)

Caveats

You can't run the macro on the same search twice without killing the buffer the HTML gets loaded into. Kill the buffers

<C-x><k> search<TAB>
Choose one of the buffers in this list to kill.
Repeat for all the buffers beginning with "search"

If you run the macro too much, Google will think you are a robot and block access for atime

If the macro returns something like <input type="submit" name="submit" value="Submit"...>, then this likely occurred.
You can confirm it by looking at the raw HTML (<C-x><C-b> and choose the buffer with the search term in it).
If you see stuff about robots and captcha, Google's blocking you. It's not my fault.

This is really cool! Of the text editors mentioned in the problem, only one of them can solve this on its own... is that even true? are there really no HTTP libraries for vimscript?

There's at least nothing in vanilla vim, but brief googling didn't pop up any  vimscript HTTP libraries. I can't imagine why anyone would actually write that when you could just read the results of curl and get the same effect. (but then your answer should indicate that it's vim+curl).

Java, 828 800 783 744 739 687 bytes
import java.net.*;import java.util.*;import java.util.regex.*;interface G{static Scanner s(String a)throws Exception{URL u=new URL("http://google.com/search?q="+a);HttpURLConnection c=(HttpURLConnection)u.openConnection();c.addRequestProperty("User-Agent","Mozilla/4.0");return new Scanner(c.getInputStream());}static void main(String[]r)throws Exception{String a,b;String c=s(a=r[0]).useDelimiter("\\Z").next(),d=s(b=r[1]).useDelimiter("\\Z").next();Matcher m=Pattern.compile("ut ([0-9,]+) res").matcher(c);m.find();long i=new Scanner(m.group(1)).nextLong();m=Pattern.compile("ut ([0-9,]+) res").matcher(d);m.find();long j=new Scanner(m.group(1)).nextLong();System.out.print(i>j?a:b);}}

Holy cats. The imports alone are 79 bytes... perhaps you should try Groovy? :P

I'm really entertained by the fact you have to set the user-agent string yourself. Like, as if Java wasn't verbose enough

Because google gives a 403 if you don't.

Why not take input from args instead of StdIn?

Python 3, 227 226 208 213 226 220 221 206 202 200 198 bytes
import re,requests as r,urllib.parse as u
lambda*t:sorted(zip(map(lambda a:int(re.findall("s\">About ([\d,]+)",r.get("http://google.com/search?q="+u.quote(a)).text)[0].replace(",","")),t),t))[-1][1]

Assign the lambda to something to call it.
Uses the requests library.
Ungolfed:
import re, requests as r, urllib.parse as u
lambda*t:
  sorted(
  list(
      zip(map(
              lambda a: int(re.findall("About ([\d,]+)",
               r.get("http://google.com/search?q="+u.quote(a)).text)[0].replace(",","")),
              t
          ),
       t)
   )
)[-1][1]

This doesn't work on my machine even after installing requests: NameError: name 'quote' is not defined

@shelvacu Oops, I'm smart, I forgot to change quote back to urllib.parse.quote after an absolute import.

did you test this? It also looks like google.co/search gives 404 whereas google.com/search works

@shelvacu yes, I tested it, it gives the same results as the ruby answer and the question says.

Powershell, 175, 172 bytes
($args|%{[pscustomobject]@{'a'=$_;'b'=[int]((iwr "google.com/search?nord=1&q=$_&nfpr=1").parsedhtml.getelementbyid('resultstats').innertext-split" ")[1]}}|sort -des b).a[0]

Showing the score as well as the name would cut 2 more bytes.
This uses the same unkillable feature as the 196 Byte Factor answer (Parsed HTML) and cuts down from the previous regex answer.

Racket, 360 337 bytes
#lang racket(require net/url net/uri-codec)(λ(t)(cddr(sort(map list t(map(lambda(a)(string->number(string-replace(list-ref(string-split(car(regexp-match#px"s\">About [\\d,]+ res"(call/input-url(string->url(string-append"http://google.com/search?nfpr=1&q="(uri-encode a)))(curry get-pure-port)port->string)))" ")1)",""")))))#:key cdr <)))

0.o
There's a reason they call it Lost In a Sea of Parentheses.
Ungolfed:
#lang racket
(require net/url)
(require net/uri-codec)

(define (open-url term)
  (call/input-url
   (string->url (string-append "http://" term))
   (curry get-pure-port #:redirections 5)
   port->string))

(define (get-result term)
  (string->number
   (string-replace
    (list-ref
     (string-split
      (car (regexp-match #px"s\">About [\\d,]+ results" (open-url (string-append "google.com/search?nfpr=1&q=" (uri-encode term)))))
      " ")
     1)
    "," "")))

(define (zip a b) (map list a b))

(define (google-fite terms) (cddr (sort (zip terms (map get-result terms))) #:key cdr <))

source: Stack Exchange

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

sort: votes


text:
Multidimensional array
This is a code-golf, so keep your code small!
The objective is to create a function that receives 3 arguments:

Rows(int): The max number of an item in each array;

Cols(int): The max number of dimensions (sub-arrays);

Val(*): The starting value in each item;

This function should return a multidimensional array with the proper size and with the items containing the value specified.
It should be able to return any number of dimensions.
Example:
var multiArray = createMultiArray(2, 4,'empty');

multiArray[0][0][0][0] === 'empty' //true
multiArray[0][0][0][1] === 'empty' //true
multiArray[0][0][0][2] === 'empty' //true
multiArray[0][0][1][0] === 'empty' //true
...
multiArray[2][2][2][2] === 'empty' //true

I'd recommend at the very least a different challenge type than a [tag:popularity-contest]. I'm having a tough time thinking what would make a recursive array initialization exercise popular. [tag:code-golf] would be better.

This feels homework-y, and even if I'm wrong it's not a particularly interesting challenge.

You guys gotta be kidding me ... If this was about balls, trolls or dwarves people would be interested ... what a shame. I'm gonna put my solution to this and try to find my faith in humanity again...

No reason to freak out. The point they are making is that this is quite a simple question which doesn't leave a lot of flexibility in the solutions (especially if you are prescribing recursive approachs), and hence it not very well suited for popularity contests. Also even if you leave it as a popularity contest, there is no incentive to keep the code small. So you may want to think about changing the winning criterion or lifting the recursion constraint to allow for creative approaches.

@rafaelcastrocouto Please don't take it personally. Just look at these comments as recommendations for asking a better question, they are not personal attacks. I see this is your first question attempt -- that makes you braver than I, and kudos for that, but there's no shame in taking the suggestions you have been giving, acting on them, and coming up with a better question.

I'm not sure why you think a question on a different site is an indication of what would be received well here, and I can assure you that although some people may be interested in troll questions they attract a lot of negativity.

for the greater good I changed the contest type .. although i don't agree at all with you guys ... there are lots of ways to solve this ... and keeping the readability would make this much more informative ... well whatever ...

Meh, I was hoping you'd lift the recursion requirement. :D (then again "should" is not such a strong word)

"Informative" is subjective. If you want useful, clearly written ways to do things, a general QA site might be more appropriate than a puzzle site.

"Informative" is as subjective as "useful ... removed the recursive req ... still praying for those down votes to go away... god I hate this golfscript language .... whatever again

I also assume you have an off-by-one error in the number of items?

I just don't care anymore Howard ...

GolfScript
This is pretty trivial, so there's no need to over-complicate it:
{[1$({2$@(@A}{\;}if]*}:A;

Online demo

@ProgramFOX, until they add syntax highlighting for GolfScript, I think it's best to leave it unhighlit. I don't know any other language with the same tokens.

@ProgramFOX You can even see in this short example that the @ is coloured differently in two places as is the A.

Ok, I'll keep it in mind.

Where is the byte count?

@Zacharý, when I wrote the answer it wasn't golf.

GolfScript, 17 characters
A non-recursive approach in GolfScript.
{\{\[.;]*}+@*}:A;

Online demo

JavaScript, 132 characters
function m(e,t,n){var r=0,i=[];var s=function(i){r++;for(var o=0;o<=e;o++){if(r==t)i[o]=n;else i[o]=s([])}r--;return i};return s(i)}

UnGolfed:

function multiArray(maxRows, maxCols, val){
  var c = 0, farray = [];
  var recursive = function(array){
    c++;
    for(var r = 0; r <= maxRows; r++){
      if(c == maxCols) array[r] = val;
      else array[r] = recursive([]);
    }
    c--;
    return array;
  };
  return recursive(farray);
}

Mathematica, 32 bytes
Within reach of GolfScript for once! Scrap that, I didn't see Howard's answer.
f=ConstantArray[#3,#+0Range@#2]&

APL, 19 bytes
{(¯1↑⍵)⍴⍨⊃(//)⌽2↑⍵}

Sample:
    {(¯1↑⍵)⍴⍨⊃(//)⌽2↑⍵} 2 4 'empty'
┌─────┬─────┐
│empty│empty│
├─────┼─────┤
│empty│empty│
└─────┴─────┘
┌─────┬─────┐
│empty│empty│
├─────┼─────┤
│empty│empty│
└─────┴─────┘

┌─────┬─────┐
│empty│empty│
├─────┼─────┤
│empty│empty│
└─────┴─────┘
┌─────┬─────┐
│empty│empty│
├─────┼─────┤
│empty│empty│
└─────┴─────┘

Unneeded commute, you can change it to{(⊃(//)⌽2↑⍵)⍴¯1↑⍵}, and maybe even {(⊃(//)⌽2↑⍵)⍴⊃⌽⍵}

The commute is unneeded (and its absence would save us one character), but the second suggestion is wrong: "minus one take" returns a one element vector, whereas "first reverse" opens the box. Try it online.

Yeah, I don't do well with stuff like that in APL (which is probably bad).

Python 3, 36 bytes
lambda a,b,x:eval("["*b+"x"+"]*a"*b)

Try it online!

J, 8 bytes
$/@]$<@[

Try it online!

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


text:
Merge two sorted lists
Merge Sort
In this challenge, you will implement the merge subroutine of merge sort. Specifically, you must create a function or program or verb or similar which takes two lists, each sorted in increasing order, and combines them into one list sorted in increasing order.
Requirements:
 - Your algorithm must take an asymptotically linear amount of time in the size of the input. Please stop giving O(n^2) solutions.

You may not use any built-in functions capable of sorting a list, or merging a list, or anything like that. Author's discretion.
The code should be able to handle repeated elements.
Don't worry about empty lists.

Examples:
merge([1],[0,2,3,4])
[0,1,2,3,4]

merge([1,5,10,17,19],[2,5,9,11,13,20])
[1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20]

This is code-golf, so may the shortest code win!

Do we have to handle repeated elements within a list, or only between the two lists?

Let's say both. The idea is that you should be able to use this to do merge sort.

Is it kosher to clobber the input arrays?

Sure, go ahead.

Hmm, would using min comply to the rules?

Solutions using min are unlikely to be O(n). However, if you can do it, go ahead.

About the output: 1. A program will necessarily output a string. Does it matter how the list elements are separated (spaces, newlines, etc.)? 2. Does a function have to output an array or can it output something else (string, elements ordered on the stack, etc.) as well?

Anything with the right informational content is fine. In other words, all of the above.

Can we assume that the elements will be non-negative integers?

@Dennis No. All you can assume is that they are comparable by > and the like.

I'm not sure how to interpret algorithm must take an asymptotically linear amount of time. Algorithms do not take any time, implementations do. The execution time of my Golfscript answer is O(scary) with the Ruby interpreter, but the Online Golfscript Tester behaves much better and could in fact be linear (no real way of telling without the source code though). My point is: b=a;b=b.length might duplicate the entire array a (and result in O(n^2) time if executed for every element) or duplicate just the reference to the array (O(n) time). Which one counts?

I guess in cases like these, just do your best to figure it out, but if you honestly can't tell, you can assume things work nicely, like the second alternative you mentioned. You can assume that the interpreter works nicely if your language doesn't have a standard interpreter.

Rebmu (35 32 chars)
u[iG^aNXa[rvA]apGtkFaM?fA]apGscA

Test
>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[1 5 10 17 19] [2 5 9 11 13 20]]
== [1 2 5 5 9 10 11 13 17 19 20]

>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[2 5 9 11 13 20] [1 5 10 17 19]]
== [1 2 5 5 9 10 11 13 17 19 20]

About
Rebmu is a dialect of Rebol that permits 'mushing' of regular code for situations that require brevity. Unmushed, the code works somewhat like:
u [                     ; until
    i g^ a nx a [       ; if greater? args next args
       rv a             ; reverse args
    ]                   ; (we want the block containing the next value first)

    ap g tk f a         ; append output take first args
    m? f a              ; empty? first args
]                       ; (first block is now empty)

ap g sc a               ; append output second args
                        ; (add the remainder of the second)

I believe this satisfies the O(n) requirement as the until block is at most looped as many times as the length of the input (and the reverse only switches the order of the container of the input blocks, not the blocks themselves). Using take is perhaps a liberty, but is still a minor efficiency hit.
Rebol (83 75 chars)
Just a wee bit different: in Rebol, paths are a shorter expression than first or second. a is the input block containing the two blocks:
until[if a/2/1 =q=q:k%s|0<1=l%k
a%_=a

Python 131 105 101 99 93
With thanks to @Evpok:

f=lambda u,v:v and(v[-1]<u[-1]and f(v,u)or[b.append(a)for a,b in[(v.pop(),f(u,v))]]and b)or u

You can write a%b=a++b after the main pattern matching to handle empty lists, that will shave off couple of characters.

doesn't the Haskell solution fail if the first list runs out of content first?

If you look at the first function, it recursively calls the function with the shortened list as the second argument, and the lengthened list as the first argument, or else swaps the arguments. Therefore, the first argument never gets shorter. Since by the OP it does not start empty, it will never empty.

Python (79)
from itertools import*
def m(*a):
 while any(a):yield min(compress(a,a)).pop(0)

Python (95, if we're not allowed to return a generator)
from itertools import*
def m(*a):
 r=[]
 while any(a):r+=[min(compress(a,a)).pop(0)]
 return r

Itertools is the solution for all worldy problems.
Bonus: the two of these work on an arbitrary number of lists, and DO worry about empty lists (as in, they'll happily take 2 empty lists, and return an empty list, or take 1 empty and 1 non-empty list, and they'll return the non-empty one. Another added feature of the 2 non-yielded ones: they'll also run with no arguments, and just return an empty list.)
Ungolfed:
from itertools import *  # Import all items from itertools
def m(*a):               # Define the function m, that takes any number of arguments,
                         #  and stores those arguments in list a
    r=[]                 # Create an empty list r
    while any(a):        # While any element in a returns True as value:
        b=compress(a,a)  # Remove any element from a that isn't True (empty lists)
                         #  The example in the official documentation is this one:
                         #  compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
        c=min(b)         # Sort the lists by first value, and take the first one of these.
        d=c.pop(0)       # Take the first element from c
        r.append(d)      # Append this first element to r
    return r             # Gives back r

In your solutions without generator, use r+=[...] instead of r.append(...) (saves 4 chars every time)

I don't mean any offense by this, but if your answer contains code in a language that's just another language with modifications made specifically for golfing, I'm going to downvote it. It's a shame, the real python answers are good.

If you split them into different posts I'll upvote the python one.

@undergroundmonorail Sure thing.

@undergroundmonorail Do you downvote all the GolfScript answers?

@evp As far as I'm aware, GolfScript commands don't map 1-to-1 with another language. If I'm incorrect I'll absolutely start.

Your solution is quite nice. That being said, it doesn't satisfy the O(n) criterion. Both the r+=[...] and the .pop(0) pieces take linear time per element, for a total runtime of O(n^2). I hope the answer can be fixed, though.

@isaacg I could've sworn that wasn't there before. I'll look into it, but I'm no CS expert.

@undergroundmonorail There is nothing in https://codegolf.stackexchange.com/tags/code-golf/info or http://meta.codegolf.stackexchange.com/search?q=language referring to your no 1→1 rule, so it is not valid.

@Evpok Now that you mention it, might as well throw it on meta, and see what they have to say there.

@evp I never claimed it was a rule, it just falls under my personal criteria for "low quality answer".

@Synthetica: .pop(0) on a list is linear in the size of the list because it has to move all the elements (from 1:n to 0:n-1).

C - 75
This operates on NULL terminated arrays of int *, though it would work equally well for pointers to other types by substituting the appropriate comparison function for **b < **a (e.g., strcmp(*b, *a) < 0).
void m(int**a,int**b,int**c){while(*a||*b)*c++=!*a||*b&&**b<**a?*b++:*a++;}

Ungolfed:
void merge(int **a, int **b, int **c)
{
    while(*a || *b)
        *c++ = !*a || *b && **b < **a
            ? *b++
            : *a++;
}

Golfscript, 29 27 30 29 26 bytes
~{.0=@.0=@<{}{\}if(@@.}do;~]p

or
~{.0=@.0=@>{\}*(@@.}do;~]p

How it works
The command
golfscript merge.gs <<< '[2 3] [1 4]'

will get processed as follows:
~            # Interpret the input string.
             #
             # STACK: [2 3] [1 4]
{            #
    .@=0.@=0 # Duplicate the two topmost arrays of the stack and extract their first
             # elements. This reverses the original order of the first copy.
             #
             # STACK: [1 4] [2 3] 2 1
             #
    >        # Check if the respective first elements of the arrays are ordered.
             #
             # STACK: [1 4] [2 3] 1
             #
    {\}*     # If they are not, swap the arrays. This brings the array with the smallest
             # element to the top of the stack.
             #
             # STACK: [2 3] [1 4]
             #
    (@@      # Shift the first element of the array on top of the stack and rotate it
             # behind the arrays.
             #
             # STACK: 1 [2 3] [4]
             #
    .        # Duplicate the topmost array.
             #
             # STACK: 1 [2 3] [4] [4]
             #
}do          # Repeat this process if the array is non-empty.
             #
             # STACK: 1 [2 3] [4] -> 1 2 [4] [3] -> 1 2 3 [4] []
             #
;~           # Delete the empty array from the stack and dump the non-empty array.
             #
             # STACK: 1 2 3 4
             #
]p           # Combine all elements on the stack into a single array, the to a string and
             # print.

The output is:
[1 2 3 4]

Does duplication of arrays in stack makes it O(n^2)?

@swish: I'm no computer scientist, but I'd say it depends on the implementation. If the interpreter actually duplicates the entire arrays, I guess it does.

The previous version was O(n^2) for very similar arrays (e. g., [1 1 1 ... 2] and [1 1 1 ... 3]), since comparing the arrays (rather than their first elements) would be very slow in this case.

The only array operations that take place in the new version are duplication, swapping and rotation on the stack. Since the duplicated arrays are only used to extract single elements and test the arrays for non-emptiness (both destructive operations in Golfscript), the above code can be run in O(n) time (by duplicating, swapping and rotating the references to the arrays). Actual performance depends on the interpreter.

Python (63)(69)(71)
def m(a,b):
 if a[0]>b[0]:a,b=b,a
 return[a.pop(0)]+(m(a,b)if a else b)

I wrote this before seeing OP's comments on runtimes of other answers, so this is another solution that's O(n) in algorithm but not implementation.

What algorithms have extracts from the front of arrays as O(1)? What algorithms have list comparisons take O(1)? Also, you can golf it further by changing ... if ... else ... to ... and  ... or ...

@isaacg Shoot, I'd forgotten about repetitions possibly making the list comparison O(n). So, I've taken out that optimization for 6 more characters. You can extract from and append to the front in O(1) in a linked list. I don't see how you can make ...and...or... play nice with returning the value.

OK, I see now how to do ...and...or..., but it doesn't save chars due to the parens needed. return[a.pop(0)]+(a and m(a,b)or b)

@isaacg: To extract the front of an array in O(1), just increase the array pointer such that it points to the second element and release the memory consumed by the first element.

@Wrzlprmft I couldn't get the array trick to work because both elements of the array are evaluated regardless of the boolean value, which throws an error when a is the empty list. Is there a short way to make a "lazy array"?

@xnor: Argh, I should have thought of that.

@Wrzlprmft: I don't think this function works. Once it has recursed down to an empty list, it tries to take the empty list's 0th element and crashes. For instance, when running m([1],[2]) I get error: list index out of range

@isaacg:Indeed, there are some brackets missing in the last line (return[a.pop(0)]+(m(a,b)if a else b) works). But why are you addressing this at me?

@Wrzlprmft: Sorry, I was looking at the comments and thought you submitted this answer.

@isaacg: Thanks, looks like I need the parens.

@xnor: And while we're on the subject: a golfing tip - using and + or is shorter than using if + else. (m(a,b)if a else b) is identical in function to (a and m(a,b)or b).

JavaScript (ES6), 69 79 bytes
f=(a,b,c=[])=>(x=a[0]          // `f' is a function that takes arguments `a', `b' and `c' -
                               // `c' defaults to `[]' - which returns the following
                               // expression:
                               //
 (x = a[0] < b[0] ? a : b)     // Store the array among `a' and `b' with the smaller first
                               // element in `x'.
                               //
 .length ?                     // If it's non-empty,
                               //
  f(a, b, c.concat(x.shift())) // append the first element of array `x' to array `c' and run
                               // `f' again;
                               //
  : c.concat(a,b)              // otherwise, append the arrays `a' and `b' to `c'.
                               //
)

Comparing the arrays with the < operator isn't valid as it does a string comparison: f([123, 456, 789], [1, 2, 3, 4, 5]) => [1, 123, 2, 3, 4, 456, 5, 789]

@nderscore: Right. It wouldn't have worked anyway, since comparing the whole arrays might not be O(n). The same seems to be true for the non-emptiness test, which has to convert the entire array to a string.

Yeah, I'm not sure what the big-o for array->string type conversion is.

Concatenating an array with [] and then converting it into a string requires O(n) time. Doing so once for all n elements of the array takes O(n^2) time.

Makes sense. Got it.

J - 42 33
Modified version from here + the comment of @algorithmshark
k=:(m}.),~0{]
m=:k~`k@.(>&{.) ::,

k prepends the head of the right array to the merged tails of both arrays. k~ is the same, but with arrays flipped. (>&{.) is comparing the heads. The code will throw an error if one of the arrays is empty, in that case we return just their concatenation ,.

I'm presuming that since /:~ a,b is the forbidden answer (along with [:/:~,), that you're shooting for the shortest answer that does not include /:, right?

I will point out that the question states, "Don't worry about empty lists."

@Dane The test for emptiness required for recursion to stop.

m=:k~`k@.(>&{.)`,@.(0=*&#) saves 2 char.

In fact, you can get the whole thing down to 33 char: k=:(m}.),~0{] and m=:k~`k@.(>&{.) ::,. We use 0{ to throw an error when the list is empty, and then catch that error and exit with ,.

Haskell, 35 bytes
a#b@(c:d)|a<[c]=b#a|0<1=c:a#d
a#_=a

Haskell, 30 bytes (non-competing)
This non-competing version only guarantees linear runtime if a and b have disjoint elements; otherwise it still runs correctly but may use quadratic time.
a#b|a<b=b#a|c:d<-b=c:a#d
a#_=a

PHP 91 98 91 bytes
edit #1: Empty $b requires an addional condition in the curly braces (+7).
edit #2: minor golfings
edit #3: added second version
pretty straight forward. The nicest part is the ternary inside the array_shift
(which fails if you try it without the curlys)
function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a&(!$b|$a[0]<$b[0])?a:b});return$c;}

or
function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a?!$b|$a[0]<$b[0]?a:b:b});return$c;}

ungolfed
function m($a,$b)
{
    $c=[];
    while($a||$b)
    {
        $c[] = array_shift(${
            $a&&(!$b||$a[0]<$b[0])
                ?a
                :b
        });
#       echo '
', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    }
    return $c;
}

test
$cases = array (
    [1],[0,2,3,4], [0,1,2,3,4],
    [1,5,10,17,19],[2,5,9,11,13,20], [1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20],
    [1,2,3],[], [1,2,3],
    [],[4,5,6], [4,5,6],
);
function outA($a) { return '['. implode(',',$a). ']'; }
echo '

A	B	expected	actual result
';
while ($cases)
{
    $a = array_shift($cases);
    $b = array_shift($cases);
#   echo '
', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    $expect = array_shift($cases);
    $result=m($a,$b);
    echo '
',outA($a),'	',outA($b),'	', outA($expect), '	', outA($result),'
';
}
echo '
';

I could not understand why you make it not simple $a&(!$b|$a[0]<$b[0])?$a:$binstead of ${$a&(!$b|$a[0]<$b[0])?a:b}

@JörgHülsermann The array_shift parameter is used by reference. It has to be a variable; an expression won´t work.

Go, 124 chars
func m(a,b[]int)(r[]int){for len(a)>0{if len(b)==0||a[0]>b[0]{a,b=b,a}else{r=append(r,a[0]);a=a[1:]}};return append(r,b...)}

JavaScript - 133
function m(a,b){c=[];for(i=j=0;i<a.length&j<b.length;)c.push(a[i]$$y[0]?shift@$y:shift@$x while@$x&&@$y;@o,@$x,@$y}

Using perl 5.14.0 and its newfangled arrayref shift: 78 chars + 1 char penalty = 79 chars:
sub M{($x,$y,@o)=@_;push@o,shift($$x[0]>$$y[0]?$y:$x)while@$x&&@$y;@o,@$x,@$y}

* instead of && will save a byte. And even more if sub M{map{shift(!@$x+@$y*($$y[0]<$$x[0])?$y:$x)}map@$_,($x,$y)=@_}

@VadimR, wow. nice work. Go ahead and post that if you like - I never would have thought to do the double map trick instead of pushing on an array.

Java: 144
This is pretty straightforward. A function that takes two arrays and returns one, the merged version, golfed and without compilation wrapper:
int[]m(int[]a,int[]b){int A=a.length,B=b.length,i,j;int[]c=new int[A+B];for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);return c;}

Ungolfed (with compile-able and runnable wrapper):
class M{
    public static void main(String[]args){
        int[]a=new int[args[0].split(",").length];
        int i=0;
        for(String arg:args[0].split(","))
            a[i++]=Integer.valueOf(arg);
        int[]b=new int[args[1].split(",").length];
        int j=0;
        for(String arg:args[1].split(","))
            b[j++]=Integer.valueOf(arg);
        int[]c=(new M()).m(a,b);
        for(int d:c)
            System.out.printf(" %d",d);
        System.out.println();
    }
    int[]m(int[]a,int[]b){
        int A=a.length,B=b.length,i,j;
        int[]c=new int[A+B];
        for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);
        return c;
    }
}

Example executions:
$ javac M.java
$ java M 10,11,12 0,1,2,20,30
 0 1 2 10 11 12 20 30
$ java M 10,11,12,25,26 0,1,2,20,30
 0 1 2 10 11 12 20 25 26 30

Any tips to shorten would be appreciated.

Scala, 97 bytes
Recursive solution with O(n). To shorten the code, sometimes an operation is done by switching the 2 interchangeable parameters, i.e. f(a,b) calls f(b,a).
type L=List[Int];def f(a:L,b:L):L=if(a==Nil)b else if(a(0)<=b(0))a(0)::f(a.drop(1),b) else f(b,a)

Ungolfed:
type L=List[Int]

def f(a:L, b:L) : L =
  if (a == Nil)
    b
  else
    if (a(0) <= b(0))
      a(0) :: f(a.drop(1), b)
    else
      f(b,a)

Exception if a is non empty, but b is empty

APL (32)
{⍺⍵∊⍨⊂⍬:⍺,⍵⋄g[⍋g←⊃¨⍺⍵],⊃∇/1↓¨⍺⍵}

Explanation:
{⍺⍵∊⍨⊂⍬                               if one or both of the arrays are empty
        :⍺,⍵                           then return the concatenation of the arrays
             ⋄g[⍋g←⊃¨⍺⍵]              otherwise return the sorted first elements of both arrays
                          ,⊃∇/        followed by the result of running the function with
                               1↓¨⍺⍵}  both arrays minus their first element

LISP, 117 bytes
The algorithm ends in n + 1 iterations, where n is the length of the shortest list in input.
(defun o(a b)(let((c(car a))(d(car b)))(if(null a)b(if(null b)a(if(< c d)(cons c(o(cdr a)b))(cons d(o a(cdr b))))))))

PYG (50)
def m(*a):
 while An(a):yield Mn(ItCo(a,a)).pop(0)

PYG (64, again, if no generators are allowed.):
def m(*a):
 r=[]
 while An(a):r+=[(Mn(ItCo(a,a)).pop(0)]
 return r

An adaptation of my Python answer.

JavaScript (ES5) 90 86 90 bytes
function f(a,b){for(o=[];(x=a[0]86) Moved the ternary into the for loop condition. Idea stolen from Dennis.
edit: (86 -> 90) Removed Array to String cast, as it breaks the O(n) requirement.

Python – 69 bytes
def m(A,B):
    C=[]
    while A and B:C+=[[A,B][A>B].pop(0)]
    return C+A+B

If the order of input and output were descending, this could be shortened to 61 bytes:
def m(A,B):
    C=[]
    while A+B:C+=[[A,B][A<B].pop(0)]
    return C

And further down to 45 bytes if generators are allowed:
def m(A,B):
    while A+B:yield[A,B][A<B].pop(0)

This is definitely not O(n). .pop(0) and += are both O(n) operations you do O(n) times.

I didn’t even know until now that lists aren’t implemented as lists in Python and even then pop(0) can be implemented in O(1) and += can at least be implemented better than O(n) (see the link). By the way, your solution uses += (i.e., append and extend) as often as mine. Anyway, all that is an implementation question (as far as I know), so in a (fictional) Python implementation, where lists are implemented as lists, my function is O(n). Finally your question required the algorithm to be O(n), and mine is.

Actually, append and extend are implemented differently in python than += is. += creates a new list, while .append and .extend modify an existing one.

Perl 6: 53 characters
sub M(\a,\b){{shift a[0]>b[0]??b!!a}...{a^b},a[],b[]}

Shift from whichever of a or b has the smaller value, until a XOR b (a^b) is true. Then return whatever is left, flattening ([]) the arrays into the list (a[],b[]).
Assuming shifting from the start of an array is O(n), the worst case is two comparisons and one shift per element, so the algorithm is O(n).

Mathematica, 137 135
m[a_,b_]:=(l=a;Do[Do[If[b[[f]]<=l[[s]],(l=Insert[l,b[[f]],s];Break[]),If[s==Length@l,l=l~Append~b[[f]]]],{s,Length@l}],{f,Length@b}];l)

Input:
m[{2,2,4,6,7,11},{1,2,3,3,3,3,7}]

Output:
{1, 2, 2, 2, 3, 3, 3, 3, 4, 6, 7, 7, 11}

Ungolfed:
mergeList[a_, b_] := (
    list = a;
    Do[
        Do[(
            If[
                b[[f]] <= list[[s]],
                (list = Insert[list, b[[f]], s]; Break[]),
                If[
                    s == Length@list,
                    list = list~Append~b[[f]]
                ]
        ]),
        {s, Length@list}
    ],
    {f, Length@b}
    ];
    list
)

Could probably do better.

m[a:{x___,y_},b:{___,z_}]:=If[y<z,b~m~a,{x}~m~b~Join~{y}];{}~m~b_=b;

R, 80
Same solution as in Scala and other languages. I am not so sure about x[-1] is O(1).
f=function(a,b)if(length(a)){if(a[1]<=b[1])c(a[1],f(a[-1],b))else f(b,a)}else b

Mathematica, 104 bytes
Reap[{m,n}=Length/@{##};i=k=1;Do[If[k>n||TrueQ[#[[i]]<#2[[k]]],Sow@#[[i++]],Sow@#2[[k++]]],n+m]][[2,1]]&

Anonymous function, stores the length of the two input lists in the variables m and n, then each iteration of the Do loop Sows an element of one the lists incrementing the counter for that list (i for the first, k for the second) by one. If one of the counters exceeds the length of the list, the If statement will always Sow the element from the other list. After n+m operations, all the elements have been taken care of. Reap or rather part [[2,1]] of its output is a list of elements in the order they have been Sown.
I'm not sure of the internals (is accessing a part of a list a O(1) operation or not), but timings looked quite linear on my machine with respect to input list length.


text:
Shortest code to generate 2D coordinates
I'm looking for the shortest code to generate the following sequences:
Sequence A
i | y x
0 | 0 0
1 | 0 1
2 | 1 0
3 | 1 1

The best I have is x = i % 2, y = i / 2, there is probably no beating that. Those are coordinates of corners of a box in 2D, but they are not in a good order for drawing. To draw a box as line loop, one needs those coordinates:
Sequence B
i | y x
0 | 0 0
1 | 0 1
2 | 1 1
3 | 1 0

So far, I have x = (i ^ i / 2) % 2, y = i / 2. There is likely space for improvement there. Finally, how to generate directions towards the box edges (where the order does not matter, but i still must be 0 to 3):
Sequence C
i |  y  x
? |  0 -1
? |  0  1
? | -1  0
? |  1  0

So far I have rather ugly x = (1 | -(i % 2)) * (i / 2), y = (1 | -(i % 2)) * (1 - i / 2).
Shortest code in any programming language wins (I actually plan to use these). The best solution will be used in a closed-source project, no attribution can be paid other than source code comment, so post only if you're ok with it. Submit solutions to any of the above sequences. Don't bother writing code that generates all of them, think of it like competition with three categories (and tree possible winners).

@ProgramFOX alright, I have changed rules and explicitly mentioned licensing. Fair enough?

Are people seriously getting offended by the closed source thing? What if I work in a company and want to use the knowledge from code golf in a commercial project? Not all software is open-source linux stuff. I imagine I'd be having a hard time convincing my boss to add attribution / license to the distribution of the final product. I thought the purpose of these sites is to provide knowledge. What good is it, if it can't be used by companies? Alternately I could just ignore the licensing and then use the answers anyway - who will ever know, right? I though I was being fair.

Why do you think people are offended? Because you get downvotes? People also downvote challenges they don't like, it's not because of the closed source.

Well I was just making sure, I'm new to this site.

I'm curious: why do you need golfed production code? In a similar vein: it's only four pairs of numbers; why can't you store them in an array and look them up?

@m.buettner Simple answer: I don't, it is absolutely worthless to me. I could easily use an array and be done with it. But if I see a solution I like, I want to be able to use it. If I'm not able to use it, what good is it? Better if I don't see it at all, maybe I can figure it out by myself.

I can't speak for anyone else, but I'm certainly not going to do your job for you.

@KyleKanos but why not? I've written online programming tutorials absolutely for free. I have never asked anyone to not use the code or to mention me in anything they write in the future. What about programming textbook authors? Imagine they would enforce license on everything you learn. We all do it for free and it is absolutely fine. Why is it a problem here? My point was to ask for solutions so others may see / use them as well.

Tutorials & textbooks have a solution already in mind in order to teach future programmers. You do not have such a solution already and are not actually teaching anyone anything. Instead, you are hoping to take other people's solutions to your own problems and get paid for someone else's work. Good luck.

@KyleKanos I have provided two solutions already, one using table and one using x = (1 | -(i % 2)) * (i / 2), y = (1 | -(i % 2)) * (1 - i / 2). Am I supposed to come up with the best answer myself? Wouldn't that take the challenge of the code golf out, though? Have you been recently sacked? Why all that bitterness about me getting paid? Aren't you paid? And as I already said, the solution to this problem is worthless. I already have good enough solutions for my implementation. It is code golf. It is fun. I'm just being honest with how would I use a better answer, that's all.

If your job requires a better solution then what you've given, then you must certainly should give the best solution. Doing your work isn't much of a challenge. I have not been sacked, but I am also not a professional programmer (a physicist, if you want to know). I am not bitter about your job, just think it's wrong to ask people to do your work for you knowing they won't be credited for their work.

@KyleKanos but saying that up front is the fairness of it. Textbooks or free tutorials are written and the people who write them know they will not be credited, ever, only in extremely rare exceptional cases.

Short sequence C (20 characters):
x=1==i^-!i,y=i%3-!!i

This generates a permutation of the original sequence (as I said, the order does not matter):
x -1  1  0  0
y  0  0  1 -1

Short sequence B (14 characters):
x=i>>~-i,y=i/2

So how about that? I'd say it is not possible to do better than that. Anyone to prove me wrong?
And yes, this answer is free. Use it as you want, sell it, no attribution needed.
EDIT:
Shorter sequence C (17 characters):
x=~-i%2,y=~-~-i%2

This generates a permutation of the original sequence (as I said, the order does not matter):
x -1  0  1  0
y  0 -1  0  1

Some other interesting solutions to short sequences:
was solving for {0, 0, 1, 1} in 1D {4 x 1 x 1} domain
solution: '1 < i': score 3
solution: 'i > 1': score 3
solution: 'i / 2': score 3

was solving for {0, 1, 0, 1} in 1D {4 x 1 x 1} domain
solution: '1 & i': score 3
solution: 'i & 1': score 3
solution: 'i % 2': score 3

was solving for {0, 1, 1, 0} in 1D {4 x 1 x 1} domain
solution: 'i >> ~-i': score 6
solution: '!!(i % 3)': score 7
solution: 'i >> ~(-i)': score 8

was solving for {-1, 1, 0, 0} in 1D {4 x 1 x 1} domain
solution: '!~-i - !i': score 7
solution: '!~-i + -!i': score 8
solution: '!~-i | -!i': score 8

was solving for {1, -1, 0, 0} in 1D {4 x 1 x 1} domain
solution: '!i - !~-i': score 7
solution: '!i - !(~-i)': score 9
solution: '-!(~-i) + !i': score 10

was solving for {1, 0, 0, -1} in 1D {4 x 1 x 1} domain
solution: '-~(~i / 2)': score 8
solution: '-~(-i >> 1)': score 9
solution: '-(~-i >> 1)': score 9

was solving for {-1, 0, 0, 1} in 1D {4 x 1 x 1} domain
solution: '~-i >> 1': score 6
solution: '~(~i / 2)': score 7
solution: '~-i >> !!i': score 8

was solving for {0, 1, -1, 0} in 1D {4 x 1 x 1} domain
solution: '~(~i % 3)': score 7
solution: '~(~i % ~2)': score 8
solution: '~(~i % -3)': score 8

was solving for {0, -1, 1, 0} in 1D {4 x 1 x 1} domain
solution: '-~(~i % 3)': score 8
solution: '-~(~i % ~2)': score 9
solution: '-~(~i % -3)': score 9


text:
Build a bit-counting comparator using NAND logic gates
A bit-counting comparator (BCC) is a logic circuit that takes some number of counting inputs A1, A2, A3, ..., An as well as inputs B1, B2, B4, B8, ... representing a number. It then returns 1 if the total number of A inputs that are on is greater than the number represented in binary by the B inputs (e.g. B1, B2, and B8 would make the number 11), and 0 otherwise.
For example, for a bit-counting comparator that takes 5 inputs, of which A2, A4, A5, and B2 are set to 1, will return 1 because there are 3 A inputs that are on, which is greater than 2 (the number represented by only B2 being on).
Your task is to create a bit-counting comparator that takes a total of 16 A inputs and 4 B inputs (representing bits from 1 to 8), using only two-input NAND gates, and using as few NAND gates as possible. To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

NOT: 1
AND: 2
OR: 3
XOR: 4

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.
The logic circuit that uses the fewest NAND gates to produce a correct construction wins.

So any answer that uses no NAND gates at all will win? That should be easy. Am I allowed to use AND gates with 16 inputs?

@squeamishossifrage Did you read the question? AND gates add 2 to your score.

@squeamishossifrage One AND == two NAND

@Timtech Then why the requirement to use "as few NAND gates as possible"?

@squeamishossifrage, "using only NAND gates". The scores for other gates are the minimum number of NAND gates required to build them; essentially it's defining some convenience macros.

@PeterTaylor Aaaah, I see. So gates with 16 inputs are fine, then?

@squeamishossifrage None of the gates listed take 16 inputs.

@Rusher Here's a 13-Input NAND gate: http://www.classiccmp.org/rtellason/chipdata/dm74als133.pdf

"...16 A inputs and 4 B inputs (representing bits from 1 to 8)..." How come there are 8 bits from only 4 B inputs?

@user80551 How many base ten digits do you need to represent the numbers zero through nine? Only one I hope.

"because there are 3 lights on" -- where do lights come into the problem ?

@Rusher I'm assuming each input is one bit. Oh wait, is it sum(total number of A-bits on)>int_representation(B) ? Then the question is a bit unclear

@PaulR Lights are commonly used analogies for things that can be OFF or ON.

@user80551 You need 16 bits to tell if 16 bits are ON or OFF. You need 4 bits to represent a 4 bit number. The number of ON bits must be greater than the 4 bit number. I don't really understand why that is so difficult. See the part of the question that says "total number of A inputs that are on is greater than the number represented by the B inputs."?

@user80551 It is indeed.

@PaulR I tend to think of light switches when designing these logic gate problems. Sorry if I made a mental typo that made it incomprehensible.

169 nands
Adds up the A's to get A{1,2,4,8,16}.  Then does a binary comparison with the Bs.
I use a few more building blocks:

FA = full adder, 9 nands (from here)
HA = half adder, 7 nands (same ref)
EQ = equality, 5 gates (a.k.a. xnor)

The half and full adders have 2 outputs - they are distinguished with an r for result and c for carry.
The A{1,2,4,8,16} are the outputs from the half adders.

Wow. Just wow. Note that a half adder can be made in just 5 gates:http://codegolf.stackexchange.com/a/10848/9498 , 4 for xor, and 1 to invert the first nand in the xor. So we get an xor and an and. Picture: http://i.stack.imgur.com/qCFxa.png

@Quincunx: thanks, the better half adder lowers the count to 161.  I don't think we need a quartus diagram, but if you'd like to I can update the answer with it.

751 nand gates
module BitCountingComparator(A, B, O);
    input [15:0] A;
    input [3:0] B;
    output O;

    wire [15:1] is;
    assign is[1] = A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] | A[8] | A[9] | A[10] | A[11] | A[12] | A[13] | A[14] | A[15];

    wire [14:0] and2;
    assign and2[0] = A[0] & A[1];
    assign and2[1] = A[1] & A[2];
    assign and2[2] = A[2] & A[3];
    assign and2[3] = A[3] & A[4];
    assign and2[4] = A[4] & A[5];
    assign and2[5] = A[5] & A[6];
    assign and2[6] = A[6] & A[7];
    assign and2[7] = A[7] & A[8];
    assign and2[8] = A[8] & A[9];
    assign and2[9] = A[9] & A[10];
    assign and2[10] = A[10] & A[11];
    assign and2[11] = A[11] & A[12];
    assign and2[12] = A[12] & A[13];
    assign and2[13] = A[13] & A[14];
    assign and2[14] = A[14] & A[15];

    wire [13:0] and3;
    assign and3[0] = and2[0] & A[2];
    assign and3[1] = and2[1] & A[3];
    assign and3[2] = and2[2] & A[4];
    assign and3[3] = and2[3] & A[5];
    assign and3[4] = and2[4] & A[6];
    assign and3[5] = and2[5] & A[7];
    assign and3[6] = and2[6] & A[8];
    assign and3[7] = and2[7] & A[9];
    assign and3[8] = and2[8] & A[10];
    assign and3[9] = and2[9] & A[11];
    assign and3[10] = and2[10] & A[12];
    assign and3[11] = and2[11] & A[13];
    assign and3[12] = and2[12] & A[14];
    assign and3[13] = and2[13] & A[15];

    wire [12:0] and4;
    assign and4[0] = and3[0] & A[3];
    assign and4[1] = and3[1] & A[4];
    assign and4[2] = and3[2] & A[5];
    assign and4[3] = and3[3] & A[6];
    assign and4[4] = and3[4] & A[7];
    assign and4[5] = and3[5] & A[8];
    assign and4[6] = and3[6] & A[9];
    assign and4[7] = and3[7] & A[10];
    assign and4[8] = and3[8] & A[11];
    assign and4[9] = and3[9] & A[12];
    assign and4[10] = and3[10] & A[13];
    assign and4[11] = and3[11] & A[14];
    assign and4[12] = and3[12] & A[15];

    wire [11:0] and5;
    assign and5[0] = and4[0] & A[4];
    assign and5[1] = and4[1] & A[5];
    assign and5[2] = and4[2] & A[6];
    assign and5[3] = and4[3] & A[7];
    assign and5[4] = and4[4] & A[8];
    assign and5[5] = and4[5] & A[9];
    assign and5[6] = and4[6] & A[10];
    assign and5[7] = and4[7] & A[11];
    assign and5[8] = and4[8] & A[12];
    assign and5[9] = and4[9] & A[13];
    assign and5[10] = and4[10] & A[14];
    assign and5[11] = and4[11] & A[15];

    wire [10:0] and6;
    assign and6[0] = and5[0] & A[5];
    assign and6[1] = and5[1] & A[6];
    assign and6[2] = and5[2] & A[7];
    assign and6[3] = and5[3] & A[8];
    assign and6[4] = and5[4] & A[9];
    assign and6[5] = and5[5] & A[10];
    assign and6[6] = and5[6] & A[11];
    assign and6[7] = and5[7] & A[12];
    assign and6[8] = and5[8] & A[13];
    assign and6[9] = and5[9] & A[14];
    assign and6[10] = and5[10] & A[15];

    wire [9:0] and7;
    assign and7[0] = and6[0] & A[6];
    assign and7[1] = and6[1] & A[7];
    assign and7[2] = and6[2] & A[8];
    assign and7[3] = and6[3] & A[9];
    assign and7[4] = and6[4] & A[10];
    assign and7[5] = and6[5] & A[11];
    assign and7[6] = and6[6] & A[12];
    assign and7[7] = and6[7] & A[13];
    assign and7[8] = and6[8] & A[14];
    assign and7[9] = and6[9] & A[15];

    wire [8:0] and8;
    assign and8[0] = and7[0] & A[7];
    assign and8[1] = and7[1] & A[8];
    assign and8[2] = and7[2] & A[9];
    assign and8[3] = and7[3] & A[10];
    assign and8[4] = and7[4] & A[11];
    assign and8[5] = and7[5] & A[12];
    assign and8[6] = and7[6] & A[13];
    assign and8[7] = and7[7] & A[14];
    assign and8[8] = and7[8] & A[15];

    wire [7:0] and9;
    assign and9[0] = and8[0] & A[8];
    assign and9[1] = and8[1] & A[9];
    assign and9[2] = and8[2] & A[10];
    assign and9[3] = and8[3] & A[11];
    assign and9[4] = and8[4] & A[12];
    assign and9[5] = and8[5] & A[13];
    assign and9[6] = and8[6] & A[14];
    assign and9[7] = and8[7] & A[15];

    wire [6:0] and10;
    assign and10[0] = and9[0] & A[9];
    assign and10[1] = and9[1] & A[10];
    assign and10[2] = and9[2] & A[11];
    assign and10[3] = and9[3] & A[12];
    assign and10[4] = and9[4] & A[13];
    assign and10[5] = and9[5] & A[14];
    assign and10[6] = and9[6] & A[15];

    wire [5:0] and11;
    assign and11[0] = and10[0] & A[10];
    assign and11[1] = and10[1] & A[11];
    assign and11[2] = and10[2] & A[12];
    assign and11[3] = and10[3] & A[13];
    assign and11[4] = and10[4] & A[14];
    assign and11[5] = and10[5] & A[15];

    wire [4:0] and12;
    assign and12[0] = and11[0] & A[11];
    assign and12[1] = and11[1] & A[12];
    assign and12[2] = and11[2] & A[13];
    assign and12[3] = and11[3] & A[14];
    assign and12[4] = and11[4] & A[15];

    wire [3:0] and13;
    assign and13[0] = and12[0] & A[12];
    assign and13[1] = and12[1] & A[13];
    assign and13[2] = and12[2] & A[14];
    assign and13[3] = and12[3] & A[15];

    wire [2:0] and14;
    assign and14[0] = and13[0] & A[13];
    assign and14[1] = and13[1] & A[14];
    assign and14[2] = and13[2] & A[15];

    wire [1:0] and15;
    assign and15[0] = and14[0] & A[14];
    assign and15[1] = and14[1] & A[15];

    wire and16;
    assign and16 = and15[0] & A[15];

    assign is[2] = and2[0] | and2[1] | and2[2] | and2[3] | and2[4] | and2[5] | and2[6] | and2[7] | and2[8] | and2[9] | and2[10] | and2[11] | and2[12] | and2[13] | and2[15];

    assign is[3] = and3[0] | and3[1] | and3[2] | and3[3] | and3[4] | and3[5] | and3[6] | and3[7] | and3[8] | and3[9] | and3[10] | and3[11] | and3[12] | and3[14];

    assign is[4] = and4[0] | and4[1] | and4[2] | and4[3] | and4[4] | and4[5] | and4[6] | and4[7] | and4[8] | and4[9] | and4[10] | and4[11] | and4[13];

    assign is[5] = and5[0] | and5[1] | and5[2] | and5[3] | and5[4] | and5[5] | and5[6] | and5[7] | and5[8] | and5[9] | and5[10] | and5[12];

    assign is[6] = and6[0] | and6[1] | and6[2] | and6[3] | and6[4] | and6[5] | and6[6] | and6[7] | and6[8] | and6[9] | and6[11];

    assign is[7] = and7[0] | and7[1] | and7[2] | and7[3] | and7[4] | and7[5] | and7[6] | and7[7] | and7[8] | and7[10];

    assign is[8] = and8[0] | and8[1] | and8[2] | and8[3] | and8[4] | and8[5] | and8[6] | and8[7] | and8[9];

    assign is[9] = and9[0] | and9[1] | and9[2] | and9[3] | and9[4] | and9[5] | and9[6] | and9[8];

    assign is[10] = and10[0] | and10[1] | and10[2] | and10[3] | and10[4] | and10[5] | and10[7];

    assign is[11] = and11[0] | and11[1] | and11[2] | and11[3] | and11[4] | and11[6];

    assign is[12] = and12[0] | and12[1] | and12[2] | and12[3] | and12[5];

    assign is[13] = and13[0] | and13[1] | and13[2] | and13[4];

    assign is[14] = and14[0] | and14[1] | and14[3];

    assign is[15] = and15[0] | and15[2];

    assign is[16] = and16;

    wire [15:1] eB;
    eB[1] = B[0];
    eB[2] = B[1];
    eB[3] = B[1] & B[0];
    eB[4] = B[2];
    eB[5] = B[2] & B[0];
    eB[6] = B[2] & B[1];
    eB[7] = eB[6] & B[0];
    eB[8] = B[3];
    eB[9] = B[3] & B[0];
    eB[10] = B[3] & B[1];
    eB[11] = eB[10] & B[0];
    eB[12] = B[3] & B[2];
    eB[13] = eB[12] & B[0];
    eB[14] = eB[12] & B[1];
    eB[15] = eB[14] & B[0];

    assign O = is[1] & ~is[2] & ~eB[1] |
        is[2] & ~is[3] & ~eB[2] |
        is[3] & ~is[4] & ~eB[3] |
        is[4] & ~is[5] & ~eB[4] |
        is[5] & ~is[6] & ~eB[5] |
        is[6] & ~is[7] & ~eB[6] |
        is[7] & ~is[8] & ~eB[7] |
        is[8] & ~is[9] & ~eB[8] |
        is[9] & ~is[10] & ~eB[9] |
        is[10] & ~is[11] & ~eB[10] |
        is[11] & ~is[12] & ~eB[11] |
        is[12] & ~is[13] & ~eB[12] |
        is[13] & ~is[14] & ~eB[13] |
        is[14] & ~is[15] & ~eB[14] |
        is[15] & ~eB[15];
endmodule

This is not fully golfed yet. I gave the answer in Verilog because this way, I was able to write a program to output each section. If it is mandatory to answer with a diagram, please let me know. They are equivalent. & is and, ~ is not, and | is or.
My strategy:

take A and put move all the 1s to the low numbers, store in is. (this is the majority of the program)
take B and unpack it into 16 bits (I called it eB for expanded B)
do a simple check.


text:
8 adjacent squares
List the coordinates of 8 squares adjacent to (0, 0) in a 2d grid. Namely,
[(1,-1),(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1)]
Order does not matter. The goal is to store the points into a list. Shortest answer wins.

Formatted exactly like the string in your question, or listed in the native/natural format for your language?

@DigitalTrauma, listed in natural format.

Can you just clarify if the (0, 0) has to be omitted from the output?

@Gareth, yes, it has to be omitted. It would be 9 squares with (0,0), after all.

Does the list need to be output to stdout, or is simply storing it in a list/array sufficient?

@DigitalTrauma, store only.

J - 12 char
The most natural representation of a list of pairs is a list of boxes containing each pair.
   }.4|.,{;~i:1
+---+----+---+---+-----+----+----+----+
|0 1|1 _1|1 0|1 1|_1 _1|_1 0|_1 1|0 _1|
+---+----+---+---+-----+----+----+----+

The magic happens in {, called Catalogue. It is essentially a generalized Cartesian product. The }.4|. part is for removing the 0 0 pair.

Bash + grep  35
eval echo\ {-1..1},{-1..1}\;|grep 1

I know this doesn't beat the other bash answer but someone had to think of grep

Ruby 29 28 26
(a=-1,1,0).product(a)[0,8]

Bonus solution:
Ruby has many nice builtin array operators, but some of them have ridiculously long names.
[*[-1,1,0].repeated_permutation(2)].take 8

Doesn't this include the 0,0?

You don't actually need the square brackets in your first answer.

@DigitalTrauma + Gareth Yup. So do other answers here I suspect. Fixed it anyways.

I FIXED IT!!!! give a poor guy a little breathing room before downvoting, eh?

@DigitalTrauma :P

You can go further: (a=-1,1,0).product(a)[0,8] is 26 chars.

@algorithmshark you're right -- thanks!

Python 43 32
l=zip([1,-1,0]*3,[-1,1]*3+[0]*2)

Inspired by @primo

I don't think this is 43 bytes anymore :)

It looks like 43 characters to me - am I missing something? Oh wow, that solution above is sweet.

@issacg I had miscounted earlier, my mistake. Nice improvement, though.

I like it. Nice improvement on my 40.

GolfScript (17 chars)
9,4-{[.3/(\3%(]}%

Since the question calls for the points to be "listed in natural format", this leaves an array on the stack. To pretty-print it, append p, as in the online demo.

Haskell 32
c=[0,1,-1]
_:l=[(a,b)|a<-c,b<-c]

The list is l (L).

You could do _:l=(,)<$>c<*>c to save 6 characters, although it requires import Control.Applicative.

Yeah, having free import statements would be pretty cool. It'd be interesting to specify free imports on a challenge, and see what sort of different responses you'ld get.

Brainfuck, 1093 characters.
++++++++[>+>++>+++>++++>+++++>++++++>+++++++>++++++++>+++++++++>++++++++++>+++++++++++>++++++++++++>+++++++++++++>++++++++++++++>+++++++++++++++>++++++++++++++++<<<<<<<<<<<<<<<<-]>>>>>>>>>>>+++.---<<<<<<<<<<<>>>>>.<<<<<>>>>>>+.-<<<<<<>>>>>>----.++++<<<<<<>>>>>>---.+++<<<<<<>>>>>>+.-<<<<<<>>>>>+.-<<<<<>>>>>>----.++++<<<<<<>>>>>.<<<<<>>>>>>+.-<<<<<<>>>>>>----.++++<<<<<<>>>>>>.<<<<<<>>>>>+.-<<<<<>>>>>>----.++++<<<<<<>>>>>.<<<<<>>>>>>+.-<<<<<<>>>>>>----.++++<<<<<<>>>>>>+.-<<<<<<>>>>>+.-<<<<<>>>>>>----.++++<<<<<<>>>>>.<<<<<>>>>>>.<<<<<<>>>>>>----.++++<<<<<<>>>>>>+.-<<<<<<>>>>>+.-<<<<<>>>>>>----.++++<<<<<<>>>>>.<<<<<>>>>>>---.+++<<<<<<>>>>>>+.-<<<<<<>>>>>>----.++++<<<<<<>>>>>>+.-<<<<<<>>>>>+.-<<<<<>>>>>>----.++++<<<<<<>>>>>.<<<<<>>>>>>---.+++<<<<<<>>>>>>+.-<<<<<<>>>>>>----.++++<<<<<<>>>>>>.<<<<<<>>>>>+.-<<<<<>>>>>>----.++++<<<<<<>>>>>.<<<<<>>>>>>---.+++<<<<<<>>>>>>+.-<<<<<<>>>>>>----.++++<<<<<<>>>>>>---.+++<<<<<<>>>>>>+.-<<<<<<>>>>>+.-<<<<<>>>>>>----.++++<<<<<<>>>>>.<<<<<>>>>>>.<<<<<<>>>>>>----.++++<<<<<<>>>>>>---.+++<<<<<<>>>>>>+.-<<<<<<>>>>>+.-<<<<<>>>>>>>>>>>>---.+++<<<<<<<<<<<<.

EDIT 209 characters
++++++++++[>+++++++++>++++>+++++>++++<<<<-]>+.>.>-.>++++.<.<+.>>.<<-.>.>.<-.<+.>>.<<-.>+.>.+.-<.<+.>>.<<-.>-.>.<+.<+.>>.<<-.>-.>.+.<+.<+.>>-.<<-.>>+.<.>-.<.<+.>>.<<-.>>+.<.>-.<-.<+.>>.<<-.>>+.<+.>-.+.<.<+.<++.

Original by Benjamin - i gave it another shot as well and got to 209 characters as well.

Someday, Brainfuck will win a code-golf contest !

@Michael : it did, once: http://codegolf.stackexchange.com/questions/8915/write-a-program-that-uses-all-printable-non-alphanumeric-ascii-symbols/8926#8926

My solution is 5 times more concise :) http://codegolf.stackexchange.com/a/25666/20279

Perl, 43 bytes
for$x(-1..1){$x|$_&&push@r,[$x,$_]for-1..1}

The result is stored in array @r. Explicitly it can be defined with 58 bytes:
@r=([-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1])

J, 16 characters
   }.4|.,<@,"0/~i:1

Usage:
   }.4|.,<@,"0/~i:1
┌───┬────┬───┬───┬─────┬────┬────┬────┐
│0 1│1 _1│1 0│1 1│_1 _1│_1 0│_1 1│0 _1│
└───┴────┴───┴───┴─────┴────┴────┴────┘

Pretty ugly - especially dropping the (0, 0). There's probably a better way.

Mathematica 23
Most@Tuples[{-1,1,0},2]
(*
{{-1, -1}, {-1, 1}, {-1, 0}, {1, -1}, {1, 1}, {1, 0}, {0, -1}, {0, 1}}
*)

Cheeky. :) Very nice idea! I think precedence rules should allow you to replace Tuples[{...},2] with {...}~Tuples~2 to save another byte.

@m.buettner Thanks. That byte is lost afterwards when trying to apply Most[] (or I can't find a way around it). BTW I never  saw you around http://mathematica.stackexchange.com  Any particular reason?

Can you explain how this works?

Ah, I thought ~..~ had higher precedence than @. I think that means I can save a byte in quite a few of my mathematica-answers :D. No particular reason why I haven't been around mathematica stackexchange, but I haven't used other SE sites other than SO much until recently. And I don't really consider myself an expert in Mathematica to be answering interesting questions. And I also don't use it for more than some casual stuff like here in code golf and the odd physics problem.

@DigitalTrauma Tuples[{a,b,c ...}, n] generates all possible lists of length n containing {a,b,c ...} as elements. Then Most[] discards the last one (which is {0,0} )

Brainfuck, 217 209 characters.
Only a bit worse than Java!
5x less than the other BF solution.
++++++++++[>+++++++++>++++>+++++>++++<<<<-]>+.>.>-.>++++.+.<.<+.>>-.<<-.>.>.<-.<+.>>.<<-.>+.>.<.<+.>>.<<-.>-.>.<+.<+.>>.<<-.>>+.<.>-.<.<+.>>.<<-.>>+.<.>-.<-.<+.>>.<<-.>>+.<+.>-.+.<.<+.>>-.<<-.>-.>.+.<+.<+.<++.

You mean 1/5th of the other solution :D But i accept your challlenge. Allthough i think i can not get it any smaller than this.

Hah.. I gave it a shot as well and came to the same amount of characters... Coincidence?

Mathematica, 44 characters
Outer[List,d=Range@3-2,d]~Flatten~1~Drop~{5}

Well. Generates all 9 coordinates, flattens the list and drops the centre.

Very nice use of common functions, Outer and Range, but they should not return the point {0,0}.

@m.buettner Good. Thanks.  +1

Python 50:
l=[(a,b)for a in[1,0,-1]for b in[1,0,-1]];l.pop(4)

Bash, 25 characters
Storing the list of coordinates as a bash array a:
a=({-1..1},{-1..1});a[4]=

Output:

$ a=({-1..1},{-1..1});a[4]=
$ echo ${a[@]}
-1,-1 -1,0 -1,1 0,-1 0,1 1,-1 1,0 1,1
$

F# - 41 36 bytes
[for i in 0..7->i*2/5-1,(i*5/4)%3-1]

Python - 57 54 56
r=range(-1,2);list({(i,j) for i in r for j in r}-{(0,0)})

Improved to
r=[-1,0,1];list({(i,j) for i in r for j in r}-{(0,0)})

with storage of the variable
r=[-1,0,1];l=list({(i,j) for i in r for j in r}-{(0,0)})

r=[-1,0,1] is shorter!

You're right- nice one

Um, you need to print it.

Only storing is needed according to the instructions, so perhaps its necessary to add l= before list at a price of 2 chars

C++, 60
Let's do this an interesting way. Hint: "2" is ASCII 50.
char x[]="11123332",y[8],i;for(i=8;i--;)y[(i+2)%8]=x[i]-=50;

Can you do char *x="11123332" to save a char?

or just auto x="11123332" to save another

@DigitalTrauma you can, but only once the array has been declared, otherwise it throws an exception. Eliminating declarations my code becomes char*x="11123332";for(i=8;i--;)y[(i+2)%8]=x[i]-=50; saving 8 bytes. You have to include the type specifier char so it knows what to store in *x.

or char*x="11123332" if you're not so comfortable with auto.

You can save another byte with i=8;while(i--) I believe. Combine with char*x= and you're looking at only 57 bytes.

(i+2)%8 -> i+2&7

Perl 6: 27 characters
Most simply:
$/=(-1..1 X -1..1)[^4,5..*]

Get the permutations of -1, 0, and 1 with itself, and hard-code skipping (0, 0). But that's no fun! I prefer things to be more complex: (50 characters)
$/=map {[.re,.im]},grep *.abs>0,(-1..1 X+ -i,0i,i)

Python - 37 bytes
a=[(i*2/5-1,-i%3-1)for i in range(8)]

An alternative at 40:
a=zip([0,1,-1]*3,[0]*3+[1]*3+[-1]*3)[1:]

And a 42 that's also interesting:
a=0,1,-1;a=zip(sum(zip(a,a,a),()),a*3)[1:]

Java 207 204
Way too much, I know, but its the best I could do right now...
I might think of something better...
class A{public static void main(String...a){int[][] l=new int[8][2];for(int x=-1,y,i=0;x<2;x++){for(y=-1;y<2;y++){if(x!=0||y!=0){l[i][0]=x;l[i][1]=y;System.out.print("("+l[i][0]+","+l[i][1]+")");i++;}}}}}

Sensibly:
class A {
    public static void main(String...a) {
        int[][] l = new int[8][2];
        for (int x = -1, y, i = 0; x < 2; x++) {
            for (y = -1; y < 2; y++) {
                if (x != 0 || y != 0) {
                    l[i][0] = x;
                    l[i][1] = y;
                    System.out.print("("+l[i][0]+","+l[i][1]+")");
                    i++;
                }
            }
        }
    }
}

main(String[] args) -> main(String...s) Saves 3 characters.

I bet String[]a is better than String...a

APL (13 characters)
1↓,∘.,⍨0 1 ¯1

Explanation:
1↓           ⍝ Drop the first element of
  ,          ⍝ an array that comes from the matrix formed by
   ∘.,⍨      ⍝ concatenating each element with every other element
       0 1 ¯1⍝ in this array [0,1,-1]

PYG (27):
P(*ItPr((-1,0,1),repeat=2))

Nothing all that special, really.
In regular python:
from itertools import product
for i in product((-1,0,1),repeat=2): print i

This prints (0, 0). I think this is not supposed to be included

The OP has clarified (0,0) should not be included.  Let me know when you fix this and I'll remove my downvote :)

What is this "PYG", you speak of? (Presumably not a Pig Latin program or yet another package manager.)

C, 73
main(i){for(i=0;i<9;i++)if(i-4)printf("%s(%d,%d)",i?",":"",i%3-1,i/3-1);}

SQL 109 (that far)
create table a(x int);insert into a values(-1),(0),(1);select a.x,b.x y from a,a b where not(a.x=0 and b.x=0)

if you want to retest it, you can prepend drop table if exists a;

Mathematica: 41
This works most of the time ;)
Union[RandomInteger[2,{99,2}]-1]~Drop~{5}

Equivalently:
Drop[Union@RandomInteger[2,{99,2}]-1,{5}]

In the first case you can lose another character, by using infix notation for RandomInteger.

Matlab: 53
Similar to my other answer:
unique(round(2*rand(99,2))-1,'rows');ans([1:4,6:9],:)

I couldn't index on the output of unique directly, and I couldn't find a way around that...

Haskell 97
Too much for Haskell and definitely not as good as the other Haskell answer, but here's a different, albeit sucky, approach:
take 8 (zip (replicate 3 (-1) ++ replicate 3 1 ++ replicate 3 0) (concat (replicate 3 [-1,1,0])))

:D

Scala, 56
Self-explanatory.
def x=List(-1,0,1);for{i<-x;j<-x;if i!=0|j!=0}yield(i,j)

Ungolfed:
def x=List(-1,0,1)
for{
  i <- x
  j <- x
  if i!=0 | j!=0
} yield(i,j)

Perl, 42 characters:
@r=map[split","],grep/1/,glob"{-1,0,1},"x2

Uses the shell-like glob functionality to generate the list of strings ("-1,-1","-1,0","-1,1","0,-1","0,0","0,1","1,-1","1,0","1,1"), discards strings that don't contain the character "1" (i.e. drop "0,0"), then splits the strings on comma to get the desired data structure.
41 characters:
@r=map[split x],grep/1/,glob"{-1,0,1}x"x2

abuses barewords: the strings are ("-1x-1","-1x0", etc.) and the split is done on the letter x instead.

JavaScript (ES5) 52 bytes
[[n=-1,n],[n,0],[n,1],[0,n],[0,1],[1,n],[1,0],[1,1]]

Javascript (ES5) (algorithmic) 57 bytes
for(a=-2,x=[];++a<2;)for(b=-2;++b<2;)a|b&&x.push([a,b]);x

Fortran: 101 96
Fortran supports complex variables, so we just store the 8 values as a set of complex numbers and get ourselves a list of tuples.
complex x(8);x=reshape([(1,-1),(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1)],[8]);print*,x;end

Printing this to look nice might be a pain in the butt because printing the real and aimag components adds a lot of bytes. But we can deal with floats.

Old answer:
complex x(8);k=1;do i=-1,1;do j=-1,1;if((j==0).and.(i==0))cycle;x(k)=cmplx(i,j);k=k+1;enddo;enddo;end

This abuses implicit typing (as usual).

C# 140 chars
Shorter version:
List<string> a=new List<string>();for(int i=0,m=-1;i<3;i++,m++){for(int j=0,n=-1;j<3;j++,n++){if(m==0 && n==0)continue;array.Add(m+","+n);}}

Easy to read version:
List<string> array = new List<string>();
for (int i = 0, m = -1; i < 3; i++, m++)
{
    for(int j = 0, n = -1; j < 3; j++, n++)
    {
         if (m == 0 && n == 0) continue;
         array.Add(m + "," + n);
    }
}