text:
Golomb's sequence to 1000000
This used to be an old Computer Olympiad Question, not sure what the actual source was.
Assume function f:

f(1) = 1
This f(1), f(2), f(3), f(4), ... sequence of numbers are in ascending order.
Number n has been repeated f(n) times

Here is the sequence up to the fifteenth number:
n :     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
f(n) :  1 2 2 3 3 4 4 4 5  5  5  6  6  6  6

for example number 4 has been repeated f(4) = 3 times.
So what you should do is to print out the sequence till f(1000000). There are no inputs.
Also you can run out of memory, not an issue! Code with less bytes wins.
So this is how to output will look like:
1 2 2 3 3 4 4 4 5 ...

CJam (22 bytes)
1{_~$(~$-)~$)}A6#(/]S*

Online demo for only 15 terms
This relies on one of the formulae given in the entry for OEIS A001462, and the use of ~$ to index the stack from the bottom.

Thanks for the link! Now I know what it's called! Golomb's sequence!

Welp!! I searched "Golomb's sequence" and this is a duplicate i think.

@aliqandil, I thought it rang a bell, but I searched for A001462 and found nothing so I went ahead and wrote an answer. Obviously we weren't as consistent in adding OEIS references back in 2012. I probably shouldn't use my binding vote to close as a dupe given that I've got rep from an answer.

Ruby, 55 bytes
Dynamic programming-style solution. Generates the table iteratively, and then prints the needed terms.
f,i=[0],0
f+=[i+=1]*(f[i]||i)while f.size<1e6
p f[1,1e6]

MATL, 25 22 bytes
FTTQ`@2+yy)1X"!htn1e7<

Try it online replacing 1e7 in the code by a more manageable number, such as 1e2
This initiallizes the sequence as [1 2 2], and from that builds the rest of the sequence applying its definition.


text:
Print out a shape in printable ASCII art based on a specific number of sides provided by the user
The Challenge:
Just as the title says, your challenge is to use the printable ASCII characters to create a program that prints out a random polygon in the terminal based on the number of sides, n provided by the user, where n is an integer in the range 3 -> 10 including 3 and 10, in as few bytes as possible.
For example:
If n = 4 it should print out a 4 sided shape. For instance, it may print out a square, like so:
 ______
|      |
|      |
|______|

However, if the program is called again with the same attribute of n=4, it should print out a different polygon based on the same number of sides. For instance, maybe a plain, old parallelogram this time, like so:
    ______________
   /             /
  /             /
 /_____________/

As another example, consider n=6. At least once, it should print out a 6-sided polygon, such as the convex hexagon shown below:
    ________
   /        \
  /          \
 /            \
 \            /
  \          /
   \________/

But another time, it should print out a visually different polygon with 6 sides, for instance, maybe a concave hexagon like the following:
________
\      /
 \    /
  \  /
  /  \
 /    \
/______\

Finally, as a last example, if n=3, it may print out an isosceles triangle:
    / \
   /   \
  /_____\

However, another call with the same attribute should print out another kind of triangle, maybe like the following right triangle:
    /|
   / |
  /__|

EDIT: To fulfill @CatsAreFluffy's request, here is an example of an ASCII nine-sided polygon:
    ___
   /   \
  /     \
 /       \
 \       /
  \     /
   \   /
   /   \
  /     \
 /       \
 \       /
  \     /
   \   /
    \ /
     v

NOTE: These are all just examples. Your polygons can be drawn in any style, as long as they meet the guidelines shown below.
Guidelines:

Each number of sides, from 3-10, should have at least 2 different shapes associated with it.

The program should print out a random shape from the shapes associated with each number of sides each time the program is executed with a specific number of visually distinguishable sides in the range 3 -> 10 given as an argument.

The sides of the each polygon can be any length, such that every shape able to be drawn by the entire program has at least one side with the same length as all the others. For instance, a triangle should have at least one side with the same length as one of the sides of a parallelogram. So should the square, pentagons, rectangles, etc. with the parallelogram, and also with each other. As a reference, in the examples given in the challenge sections, each shape has at least one side with a length of 3 slashes.

Standard loopholes apply.

For your square and hourglass, you have the top overhanging the sides, but for the parallelogram and hexagon the top is "inside" the sides. Is that intentional? Can submissions choose either style, as fits their design?

@TimmyD Those are just examples. Submissions can choose any style they want, as long as the submissions meet the guidelines given.

I think you mean hexagon, not pentagon for your n = 6 example.

@DoctorHeckle Yes, you're right. I meant hexagon.

Can the sides overlap themselves?

@Blue Actually, now that I think about it, yes they can. Like I said in my post, they can be any style as long as the program follows the guidelines given.

Can we take # of program runs from input? Would make testing on online interpreters easier (as persistent data requires file io)

@CatsAreFluffy For testing you can do whatever you want, as long as in the final version of the code, the input is a specific number of sides in the range 3 => 10 including 3 and 10. With that said, I wish you good luck! :)

Can I have an example of a 9-sided ASCII polygon?

@CatsAreFluffy Okay. Please look at the edit.

@R.Kap That last example isn't ascii.

@CᴏɴᴏʀO'Bʀɪᴇɴ Now it should be. :)

Can I print a filled polygon instead of a wireframe? If I can, then I may be able to do it eith resterization.

@Bálint Yeah, sure, that's fine, as long as I can distinguish between different sides.

Java, 1887 1866 bytes
Try in on Ideone
Saved 21 bytes due to unneeded "public" headers (Thanks to @Bálint!)
Not exactly a golfing challenge, but hey, why not?
I feel Java might actually be the best language for this challenge because no esolang could handle this, and many others don't have as good list manipulation (although Java's takes way more bytes).
Golfed:
import java.util.*;public class A{public static void main(String[]args){System.out.print((new P()).b(Integer.parseInt((new Scanner(System.in)).next())).s());}}class P{S p;public S b(int w){p=new S(w);int j=-1,k=-1,f=(w%2)*2,t,y,x;for(x=0;x<w/2-2+w%2;x++){t=r();y=r();if(j==t|k==y|t==y){x--;continue;}g(t,true,2);g(y,false,2-f);f=0;j=t;k=y;}while(1>0){t=r();y=r();if(w<4&t<1&y<1)continue;if(j==t|k==y|t==y|j==y){x--;continue;}g(t,true,3);g(y,false,3+(w<4?0:(w%2)*2));break;}return p;}void g(int w,boolean b,int h){if(w<1)p.u(h,b);else if(w<2)p.r(h,b);else p.l(h,b);}int r(){return (int)(Math.random()*3);}}class S{List<List<Character>>q,a;int h,s,u,o,e,r,b,t,g,n,m,x,y;public S(int d){s=d;h=s+s%2-1;u=h;o=h;b=s>3?(int)(Math.random()*3*s)+1:0;q=new ArrayList<List<Character>>();a=new ArrayList<List<Character>>();for(x=0;x<h;x++){q.add(new ArrayList<Character>());a.add(new ArrayList<Character>());}i(0,q);i(0,a);e=1;r=1;t=0;g=0;n=0;m=0;}public String s(){String p="";for(x=0;x<e+b+r;x++)p+=x>t+(s<4?1:0)&x<e+b+g?'_':' ';p+="\n";for(y=0;y<h;y++){for(x=0;x<e;x++)p+=y>h-2&x>n?'_':q.get(y).get(x);for(x=0;x<b;x++)p+=y>h-2?'_':' ';for(x=0;x<r;x++)p+=y>h-2&x<m-1?'_':a.get(y).get(x);p+="\n";}return p;}void i(int i,List<List<Character>>z){for(List<Character>l:z)l.add(i,' ');if(z==q){e++;if(i<=t)t++;if(i<=n)n++;}else{r++;if(i<=g)g++;if(i<=m)m++;}}void u(int v,boolean i){if(i){u-=v;for(y=0;y<v;)q.get(u+y++).set(t,'|');}else{o-=v;for(y=0;y<v;)a.get(o+y++).set(g,'|');}}void l(int v, boolean i){if(i){x=v-t;while(x-->0)i(0,q);t=x>0?0:t-v;u-=v;for(y=0;y<v;)q.get(y+u).set(t+y++,'\\');}else{x=v-g;while(x-->0)i(0,a);g=x>0?0:g-v;o-=v;for(y=0;y<v;)a.get(y+o).set(g+y++,'\\');}}void r(int v,boolean i){if(i){t+=v;y=t;while(e<=y)i(e,q);t=y-1;u-=v;for(y=0;y<v;)q.get(u+y).set(t-y++,'/');}else{g+=v;y=g;while(r<=y)i(r,a);g=v<1?g:y-1;o-=v;for(y=0;y<v;)a.get(o+y).set(g-y++,'/');}}}

Must be in file called A.java (for obvious reasons). To run:

In the terminal, type javac A.java
Then, if it gives you no errors, type java A
Finally, type the number of sides. This program actually supports side lengths up to 65536

As you can see in the example output below, the corners tend to be more open, and the sides not as smooth, as compared to the polygons in the examples. Also, it cannot produce a square, but still follows the official guidelines. If there are any problems I can change the answer to fix them.
Sample output:
3

  / |
 /  |
/___|

4
   ____
  /    \
 /      \
/________\

5
   _________
  /         |
 /          |
/           |
\           |
 \ _________|

6
  ____________
 |            \
 |             \
 |              \
 /               |
/_______________ |

7
 _____________________
\                     /
 \                   /
  \                 /
   |               /
   |              /
   \              \
    \ _____________\

8
 _______________
\               /
 \             /
  \           /
   |          \
   |           \
   /            |
  /____________ |

9
 __________
\          /
 \        /
  \      /
   |    /
   |   /
   /   \
  /     \
  |      |
  |_____ |

10
   ____
  /    \
 /      \
/        \
|         /
|        /
\        |
 \       |
  /      \
 /________\

EDIT: Finally! the ungolfed code is here! It's a bit long, but you probably already guessed that...
I will get to the explanation soon.
import java.util.*;
public class ASCII_Polygon_Driver
{
   public static void main(String[] args)
   {
      System.out.print(P.b(Integer.parseInt((new Scanner(System.in)).next())));
   }
}
class P
{
   static S p;
   public static S b(int w)
   {
      p = new S(w);
      int l1=-1,l2=-1,f=(w%2)*2,r1,r2,x;
      for(x=0;x<w/2-2+w%2;x++)
      {
         r1=r();
         r2=r();
         if(l1==r1){x--;continue;}
         if(l2==r2){x--;continue;}
         if(r1==r2){x--;continue;}
         g(r1,true,2);
         g(r2,false,2-f);
         f=0;
         l1=r1;
         l2=r2;
      }
      while(true)
      {
         r1=r();
         r2=r();
         if(w<4&r1<1&r2<1)continue;
         if(l1==r1|l2==r2|r1==r2|l1==r2){x--;continue;}
         g(r1,true,3);
         g(r2,false,3+(w<4?0:(w%2)*2));
         break;
      }
      return p;
   }
   static void g(int w,boolean b,int h)
   {
      if(w<1)p.goUp(h,b);
      else if(w<2)p.goRight(h,b);
      else p.goLeft(h,b);
   }
   static int r()
   {
      return (int)(Math.random()*3);
   }
}
class S
{
   public List<List<Character>> area1;
   public List<List<Character>> area2;
   private int wid1;
   private int wid2;
   private int spcb;
   public int hght;
   private int top1;
   private int top2;
   private int bot1;
   private int bot2;
   private int mid1;
   private int mid2;
   public int sides;
   private int x;
   private int y;
   public int y1;
   public int y2;
   public S(int numSides)
   {
      sides = numSides;
      hght = sides+sides%2-1;
      y1=hght;
      y2=hght;
      spcb = sides>3?(int)(Math.random()*3*sides)+1:0;
      area1 = new ArrayList<List<Character>>();
      area2 = new ArrayList<List<Character>>();
      for(x=0;x<hght;x++)
      {
         area1.add(new ArrayList<Character>());
         area2.add(new ArrayList<Character>());
      }
      insertCollum1(0);
      insertCollum2(0);
      wid1 = 1;
      wid2 = 1;
      top1 = 0;
      top2 = 0;
      bot1 = 0;
      bot2 = 0;
   }
   public String toString()
   {
      String out ="";

      for(x=0; x<wid1+spcb+wid2; x++)
      {
         out+=x>top1+1&x<wid1+spcb+top2?'_':' ';
      }
      out+="\n";
      for(y=0; y<hght; y++)
      {
         for(x=0; x<wid1; x++)out+=y>hght-2&x>bot1?'_':area1.get(y).get(x);
         for(x=0; x<spcb; x++)out+=y>hght-2?'_':' ';
         for(x=0; x<wid2; x++)out+=y>hght-2&x<bot2-1?'_':area2.get(y).get(x);
         out+="\n";
      }
      return out;
   }
   private void insertCollum1(int index)
   {
      for(List<Character> line : area1)
      {
         line.add(index,' ');
      }
      wid1++;
      if(index<=top1)top1++;
      if(index<=bot1)bot1++;
   }
   private void insertCollum2(int index)
   {
      for(List<Character> line : area2)
      {
         line.add(index,' ');
      }
      wid2++;
      if(index<=top2)top2++;
      if(index<=bot2)bot2++;
   }
   /*private void setChar1(int x, int y, char character, List<List<Character>> which)
   {
      which.get(y).set(x,character);
   }*/
   public void goUp(int howMany, boolean is1)
   {
      if(is1)
      {
         y1-=howMany;
         for(y=0;y<howMany;)
         {
            area1.get(y1+y++).set(top1,'|');
         }
      }
      else
      {
         y2-=howMany;
         for(y=0;y<howMany;)
         {
            area2.get(y2+y++).set(top2,'|');
         }
      }
   }
   public void goLeft(int howMany, boolean is1)
   {
      if(is1)
      {
         x = howMany-top1;
         while(x-->0)insertCollum1(0);
         top1 = Math.max(0,top1-howMany);
         y1-=howMany;
         for(y=0;y<howMany;)
         {
            area1.get(y+y1).set(top1+y++,'\\');
         }
      }
      else
      {
         x = howMany-top2;
         while(x-->0)insertCollum2(0);
         top2 = Math.max(0,top2-howMany);
         y2-=howMany;
         for(y=0;y<howMany;)
         {
            area2.get(y+y2).set(top2+y++,'\\');
         }
      }
   }
   public void goRight(int howMany,boolean is1)
   {
      if(is1)
      {
         top1+=howMany;
         y=top1;
         while(wid1<=y)insertCollum1(wid1);
         top1=y-1;
         y1-=howMany;
         for(y=0;y<howMany;)
         {
            area1.get(y1+y).set(top1-y++,'/');
         }
      }
      else
      {
         top2+=howMany;
         y=top2;
         while(wid2<=y)insertCollum2(wid2);
         top2=howMany<1?top2:y-1;
         y2-=howMany;
         for(y=0;y<howMany;)
         {
            area2.get(y2+y).set(top2-y++,'/');
         }
      }
   }
}

And, to be honest, I am actually not experienced in Java whatsoever. I am more a Python person. With that said, when I ran your code in my Mac's Terminal, I got this error: A.java:1: cannot find symbol symbol  : class Shetring location: class S. Maybe you can fix it soon as I cannot since I am not experienced in that language. At least not yet.

@R.Kap That's a weird error. When I ran it on my computer (Windows) and on Ideone (online compiler, link on answer), it worked fine. What version of Java are you using? EDIT-- oh, I forgot to tell you how to run it. I'll edit my answer.

I finally got it to work in my Terminal, and I have to say, amazing job! It does everything according to the guidelines, and still works perfectly! Great job! :)

Do you need the methods to be public? Default isn't enough?

@Bálint good catch; u, r and l don't need to be public

Also, if you only use  Scanner from java.util, then you can do new java.util.Scanner instead of importing it (I can't really tell, as the code is really, really messy)

@Bálint no, I use ArrayList as well

t=0;g=0;n=0;m=0 can be t=g=n=m=0

@Bálint I didn't know you could do that! (BTW I'm on mobile, so I can't test until I get to my computer)

You can also get the input as arguments, and create a function instead of a whole program.

How many possible shapes would you say this can output for each input integer in the range 3=>10?

@R.Kap there are 3^(n-2) different side patterns for n>3, 6 for n=3

Instead of Integer.parseInt((new Scanner(System.in)).next()) you can do new Scanner(System.in).nextInt()).

And, instead of while(true) you can do for(;;).

source: Stack Exchange

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

sort: votes


text:
Create an ABACABA city
Here is the 3rd ABACABA city:
  _
A|_|
B|__|
A|_|_
C|___|
A|_|
B|__|
A|_|

It is made out of the ABACABA sequence, which is basically:

A (1st iteration)
place B - AB
repeat A - ABA (2nd iteration)
Place C - ABAC
Repeat ABA - ABACABA (3rd iteration)

and you get the idea.
The buildings have a height (corresponded by no. of underscores) equal to the letters converted to numbers as A = 1, B = 2 e.t.c.
Input
An iteration number 1<=n<=26.
Output
The ABACABA city of order n, including the letters at the start of the lines.

@DonMuesli Haha yes. Will hyperlink in question.

What do we need to output when the number gets higher than 26?

Yes please :D (it wasn't going to be easy was it?)

That won't count as valid input.

Can the input be zero, and if so, what should the output be? Also, it wouldn't hurt to list the first, say, 4 inputs and expected outputs.

Are the letters below the buildings part of the output?

@DonMuesli Nice catch. It's fixed now.

Somewhere there's a hole in a window pane, do you think I'm to blame?

Is lowercase ok?

I would like uppercase.

Is there a problem with having trailing whitespace?

Python 2, 82 bytes
f=lambda n,s=1:n*"'"and"  _"*s+f(n-1,0)+"_"*(n-2)+"\n%c|%s|"%(64+n,"_"*n)+f(n-1,0)

I noticed no one had posted the binary recursion method and decided to give it a shot...and now with a trick borrowed from Sherlock9, it is the shortest python answer! (Also, thanks to xnor for one more shortening.) (And then Dennis who shaved a handful more...)
Ungolfed:
def f(n,s=1):
    if n>0:
        strsofar = "  _" if s==1 else ""        #prepend overhang for top-level call
        strsofar += f(n-1,0)                    #build the city above the current line
        strsofar += "_"*(n-2)                   #add the overhang to reach the current tower
        strsofar += "\n%c|%s|" % (64+n, "_"*n)  #write the current (center) line
        strsofar += f(n-1,0)                    #build the city below the current line
        return strsofar
    else:
        return ""                               #only this line will be executed when n==0 (base case)

print "  _"+f(input())

I think I understand this and it's quite clever. I had totally missed this nice recursion. You can save some chars by concatenating onto both sides rather than storing s, and by making the second line an anon function: f=lambda n:n*"?"and f(n-1)+"_"*(n-2)+"\n%c|%s|"%(64+n,"_"*n)+f(n-1);lambda n:"  _"+f(n)

I was thinking about doing that next...

@quintopia f=lambda n,s=1:n*"_"and"  _"*s+f(n-1,0)+"_"*(n-2)+"\n%c|%s|"%(64+n,"_"*n)+f(n-1,0) should work.

@Dennis i suggest implementing the above solution in Pyth. I suspect it could be shorter than 59 bytes... I would do it, but at this point, it's only half mine...

Currently working on a port to CJam. You seem to have introduced a space in the string before and, which should go in the string after it.

The space was missing from your comment entirely, and I accidentally edited it into the wrong string because you made them both underscores...

The space is there, but HTML doesn't render it. :/

81 bytes as program, same length as a function.

MATL, 59 bytes
vi:"t@wv]!-1hPXJtPvX>"'|'@Z"63+h6MJ2+X@)(]XhcJ64+!wh!32H:(!

This uses current release (15.0.0) of the language.
Try it online!

(If the letters didn't have to be included in the output: the following would work, 48 bytes):
vi:"t@wv]!-1hPXJtPvX>"' |'X@1=o)@Z"63+h6MJ2+X@)(

Explanation
v        % vertically concatenate the stack contents: gives an empty array
i:       % input number n. Generate [1,2,...,n]
"        % for each k in [1,2,...n]
  t      %   duplicate
  @      %   push k
  wv     %   swap, vertically concatenate
]        % end. Poduces the numeric ABACABA: [1 2 1 3 1 2 1]: ceiling heights
!        % transpose into a row
-1h      % append -1
PXJ      % reverse array. Copy into clipboard J
tP       % duplicate. Reverse again, so undo the reversing
v        % vertically concatenate reversed and non-reversed row arrays
X>       % max of each column. Gives array of wall heights: [1 2 2 3 3 2 2 1]
"        % for each value in that array
  '|'    %   push "floor" char
  @      %   push height
  Z"     %   create string with that many spaces
  63+    %   transform spaces into "wall" chars, '_'
  h      %   concatenate horizontally
  6M     %   push "floor" char '|' again, to be used as ceiling
  J      %   push array of ceiling heights
  2+X@)  %   index into that to get height of current building
  (      %   at that position, overwrite the string with '|'
]        % end
Xhc      % concatenate all strings into a 2D char array, padding with spaces
J        % push array of ceiling heights (numeric ABACABA sequence)
64+      % add 64 to transform into letters
!        % transpose into column array
wh       % swap, concatenate horizontally. This appends letters below the floor
!        % transpose
32H:(    % overwrite first two positions (in linear order) with spaces
!        % transpose back. Implicitly display

Very nice answer, but you also need to output the letters in front of the buildings :p.

Solved. Waiting for OP clarification anyway

I actually already asked this, but I deleted my comment. This was the response though :p.

A very elegant solution.

Python 2, 99 bytes
b=1;i=2**input('  _\n')-1
while i:i-=1;a=len(bin(i&-i))-2;print'%c|%s|'%(64+b,'_'*b)+'_'*(a+~b);b=a

To find the ith number of the ABACABA sequence, write i in binary, count the number of trailing zeroes, and add one. We use the classic bit trick i&-i to find the greatest power of 2 that divides i, then compute bit length. Actually, we count i down from 2**n-1 to 0, which is fine because the ABACABA sequence is symmetric.
We track both the current and last number of the sequence with the help of a "previous" variable b. This tells us how many underscores to print as the "overhang". The final building is drawn correctly without overhang because 0 is treated as have bit length 1.
The string format for printing is taken from Sp3000, as is the trick of using the input to print the first line.

CJam, 37 35 bytes
SS'_Lri{[H)'_*_2>N@H'A+'|@'|6$]+}fH

This is an iterative implementation of the recursive algorithm from @quintopia's answer.
Try it online!
How it works
SS'_     e# Push two spaces and an underscore.
L        e# Push "".
ri       e# Read an integer I from STDIN.
{        e# For each H in [0 ... I-1]:
  [      e#   Set an array marker.
    H)   e#     Push Push H+1.
    '_*  e#     Push a string of that many underscores.
    _2>  e#   Push a copy and remove the first two underscores.
    N    e#   Push a linefeed.
    @    e#   Rotate the longer string of underscores on top of it.
    h'A+ e#   Add H to the character 'A', pushing the corresponding letter.
    '|  e#    Push a vertical bar.
    @   e#    Rotate the string of underscores on top of it.
    '|  e#    Push another vertical bar.
    6$  e#    Push a copy of the previous iteration (initially "").
  ]     e#   Wrap everything up to the former marker in an array.
}fH     e#

JavaScript (ES6), 162 bytes
n=>(a=[...Array(1<<n)]).map((_,i)=>i?(a[i]=String.fromCharCode(64+(n=1+Math.log2(i&-i)))+`|${"_".repeat(n)}|`,a[i-1]+='_'.repeat(--n&&--n)):a[i]='  _')&&a.join`\n`

Where \n is the literal newline character.

\n is at the end, if anyone was wondering.

Python 2, 123 121 bytes
f=lambda n:n*[n]and f(n-1)+[n]+f(n-1)
L=f(input('  _\n'))
for i,j in zip(L,L[1:]+L):print'%c|%s|'%(64+i,'_'*i)+'_'*(j+~i)

ideone link (-2 bytes thanks to @xsot)
f generates the ABACABA sequence as a list of numbers, e.g. f(3) = [1, 2, 1, 3, 1, 2, 1]. The offset of the input by 1 compared to the ABACABA sequence challenge lets us golf off a byte in f.
The first line is printed separately, after which all other lines are printed using an expression which takes into account the current number and the next number. Just for fun, the first line is printed using input().

You can replace [0] with L.

@xsot Ah thanks, that works out pretty well :) (just as xnor posts an answer!)

Pyth - 64 62 bytes
Probably could be golfed more, but good enough for now.
Lsl.&Jhb_J"  _"Vtt^2Qpr@G=ZyN1p"|_"p*\_Zp\|W<=hZyhNp\_)d)"A|_|

Try it here!
Explanation:
            |Predefined vars: Q = evaluated input, G = lowercase alphabet
L           |Lambda definition. y(b) = return (following code)
   .&       |bitwise and
     Jhb    |J = b + 1, pass b + 1 to the bitwise and
        _J  |-J
  l         | base 2
 s          |̲c̲o̲n̲v̲e̲r̲t̲ ̲t̲o̲ ̲i̲n̲t̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲
          "  _"                              |print "  _" with a trailing newline
               Vtt^2Q                        |For N in 2^Q - 2
                     pr      1               |print in caps
                         =ZyN                |Z = y(N) remember the first lambda?
                       @G                    |G[Z], basically convert 1-26 to A-Z
                              p"|_"          |print "|_", no trailing newline
                                   p*\_Z     |print "_" Z times
                                        p\|  |̲p̲r̲i̲n̲t̲ ̲"̲|̲"̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲ ̲
                                           W<=hZyhN             |While ++Z<y(N+1)
                                                   p\_          |print "_"
                                                      )k        |end while,
                                                                |print newline
                                                        )"A|_|  |end for,
                                                                |print "A|_|"

Python 3.5 - 262 236 220 bytes:
-16 bytes thanks to @CatsAreFluffy! My entire function can now finally be in a single line! :)
from collections import*
def a(v):o=OrderedDict;j=[chr(i+97)for i in range(26)];d=o((j[i],('  '+'_'*(i+1)+'\n'+j[i]+'|'+'_'*(i+1)+'|'))for i in range(26));f=lambda w:'a'[w:]or f(w-1)+j[w]+f(w-1);[print(d[g])for g in f(v)]

It may be a bit long, and it may print new lines in between building, but in does what it needs to. You can test it out yourself to confirm it.
EDIT:
My previous golfed code did not print the right pattern whatsoever. However, now the one shown above does, and it does it good in my opinion. You can also run it for yourself to confirm that.
Note: The program prints all lowercase letters behind every "building". I hope that's okay.
Ungolfed version with Explanation:
from collections import*
def a(v):
    o=OrderedDict # Assign the OrderedSict function to "o"
    j=[chr(i+97)for i in range(26)] # Create a list with all 26 lowercase letters of the alphabet
    d=o((j[i],('  '+'_'*(i+1)+'\n'+j[i]+'|'+'_'*(i+1)+'|'))for i in range(26)) # Create a dict assigning each letter it's corresponding building with its corresponding length
    f=lambda w:'a'[w:]or f(w-1)+j[w]+f(w-1) # Return the ABACABA sequence based on the user input
    [print(d[g])for g in f(v)] # Print out the building according to the sequence returned by the above lambda function (thanks to @CatsAreFluffy for this method to print it! :) )

Basically what I am doing is first importing the collections module's Ordered Dictionary function, and then creating an ordered dictionary, with each lower case letter in the list "j" being assigned to its corresponding building, with its corresponding length in underscores. Then I compute the sequence, based on the user's input, using the f=lambda w:"a"[w:]or f(w-1)+j[w]+f(w-1) function, and then based on the sequence returned by that, the buildings, with each's corresponding letter behind it, are printed out.

Can you import OrderedDict as o instead? And changing op to p and item to j also works.

You can drop the if (all inputs are 1≤v≤26), change range(26) to range(v), and use return"\n".join(f(v)) instead of the for.

-2bytes: use from collections import* and o=OrderedDict instead of from collections import OrderedDict as o

@CatsAreFluffy Actually, changing range(26) to range(v) results in an Index Error. Also, doing return"\n".join(f(v)) will ONLY returns the sequence, but not the buildings themselves. Other than those, your tips were pretty good. Thanks! :)

Well, I don't quite have Python 3.5 (I've got 3.4.1), maybe it's time to upgrade...

Also you should be able to use [print(d[g])for g in f(v)] to output, making it a one-liner and saving about 4 bytes. Also may I ask why you use single quotes everywhere except "a"? Request for consistency!

@CatsAreFluffy I did not know it would print the output without brackets using [print(d[g])for g in f(v)]. Thank you for that information! Also, about the double quotes around the a, I will be honest here, I went on the ABACABA link provided by the OP, and used the lambda function by one of the answers shown there, as I did not even know you could call the lambda function itself within the function! However, I did make some changes to that, all except changing the double quotes, which I did not see, so thanks for pointing that out to me! :)

As for the double-quote problem, was length-checking the last improvement in Mathematica and whenever you paste in something that contains backslashes or double quotes a dialog box slower than {slowthing} pops up.

@CatsAreFluffy Ok, so?

Well, I guess it's not that big a deal. A slightly bigger deal is that I saved 16 bytes, not 14.

@CatsAreFluffy Yeah, sorry. I forgot to change that before. It's fixed now.

Let us continue this discussion in chat.

JavaScript (ES6), 143
There are 2 newline inside the backticks that are significant and counted.
n=>`  _
`+(r=n=>n?[...r(n-1),n,...r(n-1)]:[])(n).map((x,i,t,u=n=>'|'+'_'.repeat(n>0&&n))=>String.fromCharCode(x+64)+u(x)+u(t[i+1]-x-1)).join`
`

... or 138 if the letters can be lowercase.
n=>`  _
`+(r=n=>n?[...r(n-1),n,...r(n-1)]:[])(n).map((x,i,t,u=n=>'|'+'_'.repeat(n>0&&n))=>(x+9).toString(36)+u(x)+u(t[i+1]-x-1)).join`

Less golfed
n=>{
  // recursive function for ABACABA returning an array of integers
  var r=n=>n?[...r(n-1),n,...r(n-1)]:[]
  // function to build "|__..."
  // if argument <=0 just returns the vertical bar
  var u=n=>'|'+'_'.repeat(n>0&&n)
  var t = r(n)
  t = t.map((x,i)=>
    // current building + extension to the len of next building if needed
    String.fromCharCode(x+64)+u(x)+u(t[i+1]-x-1)
  )
  return ' _\n' // the top line is fixed
    + t.join('\n')
}

Test

solution=
n=>`  _
`+(r=n=>n?[...r(n-1),n,...r(n-1)]:[])(n).map((x,i,t,u=n=>'|'+'_'.repeat(n>0&&n))=>String.fromCharCode(x+64)+u(x)+u(t[i+1]-x-1)).join`
`

function update() {
  var n=+N.value
  if (n>=0 && n<=26) O.textContent=solution(n)
}

update()
#N { width: 2em }
N:<input id=N value=4 oninput='update()'>

Powershell, 67 Bytes
1..(Read-Host)|%{'  _'}{$x+=@([char]($_+96)+'|'+'_'*$_+'|')+$x}{$x}

Ruby, 129 bytes
Anonymous function, returns a multiline string.
->x{a=->n{n<1?[]:(b=a[n-1];b+[n]+b)}
r="  _
"
a[x].zip(a[x][1,9**x]<<0).map{|n,m|r+=(64+n).chr+"|#{?_*n}|#{?_*(m+~n)if m>n}
"}
r}

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


text:
Invert png image
Create program or function that takes file name as an argument or reads it from standard input, and completes the following task:

Read image from a png file (name given as argument).
Reverse colors in that image, so that for example dark green (0, 75, 30) would become (255, 180, 225) (because 255-0=255, 255-75=180 and 255-30=225). You should not change alpha channel value.
Output that image to a file called a.png (in png format), or show it in GUI window.

This is code-golf. Standard loopholes apply.

Is it required to support any optional png features? Are built-in png loading/writing functions acceptable?

@Sparr Optional feature support is optional. Built-in functions are not explicitly disallowed, so I'll assume they are allowed.

PNG files can be indexed (each pixel contains a pointer to a color in the colormap) or truecolor (each pixel contains the actual color). Which one do we need to support? Can we choose? In fact, there are five different subformats regarding color. So... ?

@DonMuesli I think any method that provides correct result will be fine. You can assume that the color isn't greyscale, and supporting alpha-channel is optional. I think that using any other mode is acceptable, as long as the task will still be reversing the colors, and colors have (r,g,b)-values.

Can I use just CSS?

ImageMagick display -fx, 3 7 18 24 bytes
1-u

The ImageMagick tool display with the fx parameter can apply the above program to a png given as the parameter and display the results on screen.
Check out my post on meta about ImageMagick as a programming language. I wrote a prime tester over there as a proof of concept.
Re byte counting, display -fx code filename is equivalent to perl -e code filename, where we traditionally count just code for length.

Is this not a standard loophole? It's gotten plenty of upvotes, but it seems like it should be. I guess if Mathematica can have a bunch of these functions built-in, then using any pre-released application (before the asking of the question) to do it for you is fair game, so long as it accepts command-line arguments?

@NateDiamond Give me about 5 minutes to finish my meta post about "is imagemagick a programming language" and I'll cut this down to 7 bytes and address your question at the same time :)

@NateDiamond http://meta.codegolf.stackexchange.com/questions/8828/is-imagemagick-a-programming-language

Pyth, 16 15 13 bytes
.w-LLL255'z\a

Outputs to a.png.
          z    read input
         '     read as RGB triples from file
   LLL         map over rows, then triples, then individual values...
  -   255      ...subtract from 255
.w         \a  write as image to a.png

Thanks to Jakube for 2 bytes!

man, i've gotta learn pyth

Does Pyth not have bitwise negation (~ or similar)?

@PeterTaylor I don't think it does, surprisingly. (In any case, it would have to be restricted to 8 bits.)

is there no way to deeply-map with a pfn?

@ven Nope, I don't think so (or at least not the ways I've tried). You can't nest Ls or Rs.

too bad, that'd be very fun :D. I remember having tried such things.

@ven @Doorknob Actually you can do it: .w-LLL255'z\a. But don't ask me how this works or why you need LLL and not something like LMM.

paging @isaacg, maybe?

@ven Pinging only works for users that have authored, commented  or edited the post

haha, okay, noted :P. (note: to page exists)

@Jakube from looking at the code, it seems to require that because L parses in a kind of odd way with other sugar parsing. The L parse seems to keep the other Ls as part of the body of the map, so after the first parse you get: .wm-LL255d'z\a and so on. I'm not sure what's up with M though, I'll ping isaac in the Pyth chatroom.

@Jakube O_o I have no idea why that works, but thanks!

MATL, 10 bytes
255iYi-IYG

There are five different subformats of PNG, depending on how color is encoded. None of them seems to be more "optional" than the others. I chose the most flexible one, Truecolor, in which each pixel can have an arbitrary color. The above code also supports Truecolor with alpha, ignoring the alpha channel.
To know the color subformat of a PNG file: look for the byte sequence [73 72 68 82] near the beginning of the file; and the tenth byte from there will have one of the five values in the table linked above.
How the code works
Pretty straightforward:
255    % push 255 to the stack
i      % input filename with extension '.png'
Yi     % read contents of that file as (truecolor) image
-      % subtract
IYG    % show image

Example
I couldn't resist seeing myself inverted, so I downloaded this image (which is in subformat Truecolor with alpha), ran the code (second line is user input)
>> matl 255iYi-IYG
> 'C:\Users\Luis\Desktop\me.png'

and got

Your avatar is actually you? I thought it was just your helmet! :P

I thought PNG and all means long code, but 10 bytes? Wow.

Java, 295
import javax.imageio.*;class V{public static void main(String[]a)throws
Exception{java.awt.image.BufferedImage m=ImageIO.read(new
java.io.File(a[0]));for(int
x=m.getWidth(),y;x-->0;)for(y=m.getHeight();y-->0;)m.setRGB(x,y,m.getRGB(x,y)^-1>>>8);ImageIO.write(m,"png",new
java.io.File("a.png"));}}

I like how x-- and x>0 together make a litte arrow showing that x goes up to 0. Why have I never seen/used that before?

Import java.io.File?

@LuWi hehe, I've seen and used it before, some people call it the "goes to" operator, and it's pretty golfy :)

@nickb even if you use the shorter import java.io.*;, it doesn't save any bytes but actually increases the size.

R, 124 bytes
p=png::readPNG(readline());p[,,-4]=1-p[,,-4];png("a.png",h=nrow(p),w=ncol(p));par(mar=rep(0,4));plot(as.raster(p));dev.off()

Reads in file name through stdin (readline()).
p=png::readPNG(readline()) #Reads in png as an RGBA array on range [0,1]
p[,,-4]=1-p[,,-4] #Takes the opposite value except on alpha layer
png("a.png",h=nrow(p),w=ncol(p)) #Prepares output png of same size as input
par(mar=rep(0,4)) #Makes the png take the full space of the figure region
plot(as.raster(p)) #Transforms p as a raster so that it can be plotted as is.
dev.off() #Closes the plotting device.

Example Input/Output using the first png I found on this computer :)

CSS, 19 Bytes
*{filter:invert(1)}

http://output.jsbin.com/suqayudoyu

The two images don't appear to have any change.

Use Firefox, http://caniuse.com/#feat=css-filters

Tcl, 176 bytes
foreach r [[image c photo -file {*}$argv] d] {set x {}
foreach c $r {lappend x [format #%06X [expr "0xFFFFFF-0x[string ra $c 1 end]"]]}
lappend y $x}
image1 p $y
image1 w a.png

Loads the PNG via the photo image type, gets the image data, converting each row and color by subtracting from #FFFFFF, then writes the file back to disk (as "a.png").
For best results, use TrueColor PNGs, since Tk will try to use the same color resolution as the source image data.
To see the image without sampling problems, add
pack [label .i -image image1]

to the end. (Obviously, this is longer than the disk-save option.)

You can ave bytes replacing foreachby lmap

Mathematica, 140 bytes
Export["a.png",SetAlphaChannel[ColorCombine[Most@#],Last@#]&@MapAt[Image[1-ImageData@#]&,ColorSeparate[Import[#],{"R","G","B","A"}],{;;3}]]&

Note that you can save two bytes by changing Import[#] to Import@#, and same for ColorCombine[Most@#].

Why wouldn't a simple ColorNegate@*Import be a complete answer?

cmd + IrfanView, 19 characters
i_view32 %1 /invert

Just the expensive alternative of Sparr's answer.

Julia, 94 79 bytes
using FileIO
save(ARGS[1],map(x->typeof(x)(1-x.r,1-x.g,1-x.b,1),load(ARGS[1])))

This is a full program that takes a file name as a command line argument and overwrites the given file with the inverted image. It requires that the FileIO and Image package be installed. The latter doesn't need to be imported though.
Call the program from the command line like julia filename.jl /path/to/image.png.
Ungolfed:
using FileIO # required for reading and writing image files

# Load the given image into a matrix where each element is an RGBA value
a = load(ARGS[1])

# Construct a new image matrix as the inverse of `a` by, for each element
# `x` in `a`, constructing a new RGBA value as 1 - the RGB portions of
# `x`, but with an alpha of 1 to avoid transparency.
b = map(x -> typeof(x)(1 - x.r, 1 - x.g, 1 - x.b, 1), a)

# Save the image using the same filename
save(ARGS[1], b)

Example:

The magpie (?) looks seriously depressed on the second image.

Python + PIL, 85 bytes
from PIL import Image
lambda a:Image.eval(Image.open(a),lambda x:255-x).save('a.png')

This defines an anonymous function that takes a filename as a string and saves the resultant image to a.png.
Test run:

-3 bytes: from PIL import Image as I, followed by replacing Image in the function with I

I'm fairly sure that simply import Image will work, shaving off a whole load of bytes

save 11 bytes with from PIL.Image import*

I think this accidentally inverts the alpha channel as well. Apparently the eval function runs against all "bands", including the alpha one. Here is what I get when inverting the Firefox logo - https://imgur.com/a/wV3MSQX

@dana Per the OP's comment, supporting alpha channels is optional.

OK - Cool deal :) I might update my answer to reflect this.

C + stb_image + stb_image_write, 175 162 bytes (or +72=247 234)
My first submission on this site ever.
#include"stb_image.h"
#include"stb_image_write.h"
x,y,c,i;f(char*d){d=stbi_load(d,&x,&y,&c,i=0);for(;i<x*y*c;i++)d[i]=255-d[i];stbi_write_png("a.png",x,y,c,d,0);}

Could probably shave off a few bytes. Needs stb_* implementation to either be in a separate library, or at the start of this file with:
#define STB_IMAGE_IMPLEMENTATION
#define STB_IMAGE_WRITE_IMPLEMENTATION

I didn't include it in the count because it's essentially part of the library (esp. if it's compiled separately). +72 bytes to add that if required, however.

Update 1:
Realized only a function (as opposed to an entire program) is acceptable, shaving off 15 bytes. The old implementation (which is an entire program), for reference:
x,y,i;main(int c,char**d){*d=stbi_load(d[1],&x,&y,&c,0);for(;i<x*y*c;i++)i[*d]=255-i[*d];stbi_write_png("a.png",x,y,c,*d,0);}

Java, 300 298 bytes
import javax.swing.*;void c(String f)throws Exception{java.awt.image.BufferedImage r=javax.imageio.ImageIO.read(new java.io.File(f));for(int i=0;i++<r.getWidth();)for(int j=0;j++<r.getHeight();)r.setRGB(i,j,(0xFFFFFF-r.getRGB(i,j))|0xFF000000);JOptionPane.showMessageDialog(null,new ImageIcon(r));}

MATLAB / Octave, 31 bytes
Code:
imshow(imcomplement(imread(x)))

Example:
imshow(imcomplement(imread('balloons.png')))

Explanation:
Read the image, x, from a graphics file, complement the image, and then display the image.

The code assumes that x is predefined, which is not allowed. You can turn it into a lambda function for +4 bytes with @(x).

FFmpeg, 10 bytes
Edit: Taking a cue from @Sparr's answer
-vf negate

(the above when passed to ffplay alongwith the image name, will display the negated image)

ffplay %1 -vf negate

The above is saved as a batch file.

Is FFmpeg a programming language by our standards? I don't know enough about it to be sure. Perhaps ask on meta?

Racket 282 bytes
(λ(fname)(let*((i(make-object bitmap% fname))(w(send i get-width))(h(send i get-height))(pixels(make-bytes(* w h 4)))(i2(make-object bitmap% w h)))
(send i get-argb-pixels 0 0 w h pixels)(send i2 set-argb-pixels 0 0 w h(list->bytes(map(lambda(x)(- 255 x))(bytes->list pixels))))i2))

More readable form:
(define(f fname)
  (let*(
        (i (make-object bitmap% fname))
        (w (send i get-width))
        (h (send i get-height))
        (pixels (make-bytes(* w h 4)))
        (i2 (make-object bitmap% w h)))
    (send i get-argb-pixels 0 0 w h pixels)
    (send i2 set-argb-pixels 0 0 w h
          (list->bytes
           (map
            (lambda(x) (- 255 x))
            (bytes->list pixels))))
    i2))

Usage:
(f "myimg.png")

Golang, 311 bytes
package main
import("image"
."image/png"
."image/color"
."os")
func main(){f,_:=Open(Args[1])
i,_:=Decode(f)
q:=i.Bounds()
n:=image.NewRGBA(q)
s:=q.Size()
for x:=0;x<s.X;x++{for y:=0;y<s.Y;y++{r,g,b,a:=i.At(x,y).RGBA()
n.Set(x,y,RGBA{byte(255-r),byte(255-g),byte(255-b),byte(a)})}}
o,_:=Create("o")
Encode(o,n)}

ungolfed
package main
import(
    "image"
    "image/png"
    "image/color"
    "os"
)

func main(){
    // open a png image.
    f, _ := os.Open(Args[1])

    // decode the png image to a positive image object(PIO).
    p, _ := png.Decode(f)

    // get a rectangle from the PIO.
    q := p.Bounds()

    // create a negative image object(NIO).
    n := image.NewRGBA(q)

    // get the size of the PIO.
    s := q.Size()

    // invert the PIO.
    for x := 0; x < s.X; x++ {
        for y := 0; y < s.Y; y++ {
            // fetch the value of a pixel from the POI.
            r, g, b, a := p.At(x, y).RGBA()

            // set the value of an inverted pixel to the NIO.
            // Note: byte is an alias for uint8 in Golang.
            n.Set(x, y, color.RGBA{uint8(255-r), uint8(255-g), uint8(255-b), uint8(a)})
        }
    }

    // create an output file.
    o, _ := os.Create("out.png")

    // output a png image from the NIO.
    png.Encode(o, n)
}

Python 2 + OpenCV, 55 bytes
import cv2
cv2.imwrite('a.png',255-cv2.imread(input()))

The OpenCV library uses NumPy arrays to read, process, and write images. Below is an example of this script inverting an image found on mozilla.org.

All channels, including the alpha channel, will be inverted. This is problematic for images that have transparency. But as @Mego pointed out, support for the alpha channel is optional.
Below is an 82 byte commented version that property handles the alpha channel.
import cv2                # import OpenCV library
i=cv2.imread(input(),-1)  # image file name is specified from stdin
                          # read with the IMREAD_UNCHANGED option
                          # to preserve transparency
i[:,:,:3]=255-i[:,:,:3]   # invert R,G,B channels
cv2.imwrite('a.png',i)    # output to a file named a.png

As shown below, this properly handles inverting the Firefox logo while preserving the transparent background.

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


text:
All possible ways to interleave two strings
I recently saw this question on stackoverflow. It's a great question, but there's one fatal problem with the question. They are asking for the best way to do it. E.g, easiest to read, most idiomatic, neatest etc. Don't they know that isn't what matters? You're supposed to ask about how to do it with the fewest bytes of code!
Since I doubt that question will be appreciated on stackoverflow, I decided to ask it here.
The challenge
You must write the shortest possible program or function that generates all possible ways to interleave any two arbitrary strings. For example, if the two strings are 'ab' and 'cd', the output is:
['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

As you can see, a is always before b, and c is always before d.
IO can be in any reasonable format. Use this python code to verify to check your output. (credit: JeD)
def shuffle(s,t):
    if s=="":
        return [t]
    elif t=="":
        return [s]
    else:
        leftShuffle=[s[0]+val for val in shuffle(s[1:],t)]
        rightShuffle=[t[0]+val for val in shuffle(s,t[1:])]
        leftShuffle.extend(rightShuffle)
        return leftShuffle

Sample IO:
shuffle("$", "1234"):
['$1234', '1$234', '12$34', '123$4', '1234$']

shuffle("az", "by"):
['azby', 'abzy', 'abyz', 'bazy', 'bayz', 'byaz']

shuffle("code", "golf"):
['codegolf', 'codgeolf', 'codgoelf', 'codgolef', 'codgolfe', 'cogdeolf', 'cogdoelf',
'cogdolef', 'cogdolfe', 'cogodelf', 'cogodlef', 'cogodlfe', 'cogoldef', 'cogoldfe',
'cogolfde', 'cgodeolf', 'cgodoelf', 'cgodolef', 'cgodolfe', 'cgoodelf', 'cgoodlef',
'cgoodlfe', 'cgooldef', 'cgooldfe', 'cgoolfde', 'cgoodelf', 'cgoodlef', 'cgoodlfe',
'cgooldef', 'cgooldfe', 'cgoolfde', 'cgolodef', 'cgolodfe', 'cgolofde', 'cgolfode',
'gcodeolf', 'gcodoelf', 'gcodolef', 'gcodolfe', 'gcoodelf', 'gcoodlef', 'gcoodlfe',
'gcooldef', 'gcooldfe', 'gcoolfde', 'gcoodelf', 'gcoodlef', 'gcoodlfe', 'gcooldef',
'gcooldfe', 'gcoolfde', 'gcolodef', 'gcolodfe', 'gcolofde', 'gcolfode', 'gocodelf',
'gocodlef', 'gocodlfe', 'gocoldef', 'gocoldfe', 'gocolfde', 'goclodef', 'goclodfe',
'goclofde', 'goclfode', 'golcodef', 'golcodfe', 'golcofde', 'golcfode', 'golfcode']

As usual, standard loopholes apply, and the shortest answer in bytes wins. Since the question was originally about python, I'd love to see the shortest python answer. (And no, pyth is not python). However, answers in any language are encouraged.

Fewest bytes of code is the bestest way to do it, every one knows that!* (disclaimer: not CR).

Are all characters distinct? Or not necessarily?

Actually... in your "code", "golf" example you have a duplicate "o" and duplicate results too, e.g. 'gcoodelf'. I'll assume that's what you want.

"I just found this great question. However, there is one fatal flaw: they want it done well!"

You should provide the sample IO for "aabb","bc".

Pyth, 26
M?G?H++LhGgtGH+LhHgGtH]G]H

Try it here
This is a very basic implementation of the given recursive formula. It defines a function g that performs the required task. The link is a modified program that reads the strings from STDIN newline separated, to be more convenient. To call the function do g<string1><string2>.
Expansion:
M                ##  Define a function g taking two arguments: G and H
 ?G?H ... ]G]H   ##  Two ternaries: if G is empty return a list containing H
                 ##  if H is empty return a list containing G
   +             ##  otherwise return these next two lists joined together
   +LhGgtGH      ##  the first letter of G added to each result of a recursive call to g
                 ##  with G missing its first character and H
   +LhHgGtH      ##  the same as above but with G and H swapped

The two recursive calls are very similar, but I haven't been able to find a way to golf them any more.

Haskell, 47
(x:s)#b=(x:)<$>s%b
a#b=[]
[]%b=[b]
a%b=a#b++b#a

% is the operator that solves this challenge.
# is an operator that takes in two lists and finds all the ways to interleave them such that the first character is from the first string (with an edge case - if the first list is empty, then the result is an empty list) by recursing to %.
then, % works by just applying # twice.
Edit:
The previous version had a bug in which ""%"" returned ["",""], so I fixed it up. It was fixed by adding a base case to %, which then allowed to remove a base case of the same length from # (which really, didn't make much sense).

@nimi But the types mismach - (#) :: [a]->[a]->[[a]], so a::[a] and the result should be of type [[a]]

Oops, you're right. Sorry.

Haskell, 53 48 bytes
a%""=[a]
a%b=[x:t|(x:y,z)<-[(a,b),(b,a)],t<-y%z]

Defines a function % for which a%b with strings a,b gives a list of strings.
Given two strings, we choose one of the two to take the first character from. We then recurse on the remainder of two strings, prepending that character to each result.
When one of the string is empty, the only possible result is the other string. ""%""=[""] would also suffice, but's it's longer.

53 bytes:
a@(b:c)%d@(e:f)=((b:)<$>c%d)++((e:)<$>a%f)
a%d=[a++d]

Defines a function % for which a%d with strings a,d gives a list of strings.
The function is defined recursively. If we take a character from the first string, then it must be prepended to each result of the recursive call on the remained of the first string with the second string. Symmetrically for the other string.
For the base case, if one of the strings is empty, the result is a single-element list of their concatenation. This is shorter than two cases for each string being empty.

@aditsu Oops, I meant ""%""=[""].

It's weird to have an answer winning over you by exactly one byte in the exact same language

Python 2, 71 bytes
f=lambda*p:[x[0]+t for x,y in p,p[::-1]for t in x and f(x[1:],y)]or['']

Example run:
>> f('ab','AB')
['abAB', 'aABb', 'aAbB', 'ABab', 'AabB', 'AaBb']

Given two strings x,y we can take the first character of x and prepend it to each result of the recursive call with it missing f(x[1:],y). Or, we can do the same with x and y switched. By taking x,y as either the input p or its reversal `p[::-1], we get both possibilities.
To avoid taking from an empty string x, we logical short-circuit with x and. If both strings are empty, neither string can be x and we get and empty list of possibilities, which we fix with or to the correct base case [''].
A similar generative strategy in Python 3 (73 bytes):
f=lambda p,s='':[f((x[1:],y),s+x[0])for x,y in[p,p[::-1]]if x]or print(s)

What kind of sorcery is this?! (+1)

Python, 80
As requested, here's a python answer:
f=lambda a,b,c='':[c+x for x in[a+b][a>''<b:]or f(a[1:],b,a[0])+f(a,b[1:],b[0])]

Thanks Sp3000 for eating 4 bytes :)

CJam, 38
q~L{_2$e&{_2$(\@jf+@@(@@jf++}{+a}?}2jp

Try it online
Dynamic programming (using memoized recursion).
Explanation:
q~         read and evaluate the input (2 strings)
L{…}2j     calculate with memoized recursion with no initial cache and 2 arguments
  _2$      copy the 2 strings
  e&{…}    if they are both non-empty
    _2$    copy the strings again (they're in reverse order)
    (      take out the first character of the first string
    \@     move the strings after the character
    j      solve recursively
    f+     prepend the character to all results
    @@     bring the other copy of the strings on top (in order)
    (      take out the first character of the second string
    @@     move the strings after the character
    j      solve recursively
    f+     prepend the character to all results
    +      concatenate the 2 sets of results
  {…}      else
    +      concatenate the 2 strings (at least one is empty)
    a      put the result in an array
  ?        end if
p          pretty-print the results for the input strings

JavaScript (Firefox 30-57), 88 84 81 bytes
(s,t,g=(v,w)=>v[1]?f(v.slice(1),w).map(x=>v[0]+x):[v+w])=>[...g(s,t),...g(t,s)]

Edit: Saved 4 bytes by improving my termination condition. Saved 3 bytes thanks to @edc65.

Too close to publish, but have a look - it's shorter: f=(a,b,z=(v,w)=>v[1]?f(v.slice(1),w).map(x=>v[0]+x):[v+w])=>z(a,b).concat(z(b,a))

@edc65 Very nice; I'd tried and failed to use v as the condition, but it never occurred to me to use v[1].

CJam, 32 bytes
qN/_:,eeWf%e~e!\f{\{_2$=(ot}/No}

Test it here.
This feels really golfable, but so far I've only found 4 alternative solutions that all have the same byte count:
qN/_ee{),*~}%e!\f{\{_2$=(ot}/No}
l_:!l_0f>@+])e!\f{\{_2$=(ot}/No}
ll__3$:!+.=])e!\f{\{_2$=(ot}/No}
qN/[_:,2,]ze~e!\f{\{_2$=(ot}/No} (found by Sp3000)

The basic idea is to generate all permutations of 0s and 1s corresponding to which string to take each character in the result from. That's everything up to and including the e!. The rest simply pulls out characters in that order from the two strings then.

Nice, I thought about that idea but didn't think it can golf that well.

@aditsu What we really need is a mix between e* and .* which repeats each element by a different amount. ;) (I.e. an operator to do :a.*:~. I suppose e* could be used for that since it currently errors if given two lists.)

Brachylog, 8 bytes
p~cᵐz₁cc

Try it online!
Takes input as a list of two strings through the input variable, and generates all possible interleavings through the output variable. Since the test cases seem to permit duplicate interleavings where there are shared letters, I haven't taken any care to avoid them, but this generates a lot more duplicates and not just with shared letters. (If this isn't allowed, but the shared letter duplicates aren't necessary, just add three bytes to wrap in {}ᵘ for output as a list with no duplicates.)
p           A permutation of
            the input variable
   ᵐ        with each element
 ~c         arbitrarily partitioned,
    z       zipped
     ₁      without cycling,
      cc    and concatenated twice
            is the output variable.

Essentially, this generates every partition of both strings, then interleaves them in the normal deterministic fashion in either order. The extra duplicate interleavings are due to partition pairs where the difference between the length of the first and the length of the second has some value other than 0 or 1, so that one of them has chunks that get concatenated to each other at the end. So, to produce output with the same multiplicities as the sample output:
Brachylog, 17 bytes
p~cᵐ{lᵐ-ℕ<2&}z₁cc

Try it online!
The extra code, {lᵐ-ℕ<2&}, fails any partition pair where any extraneous divisions are made. (I altered the header on TIO to print with quotes for easier output checking in the Python shell.)

MATL, 34 30 bytes
h1Mgw~hY@Xu!ttYs*w~tYs1Gn+*+!)

This uses an idea from this answer: if the lenghts of the strings are m and n, enumerate all m+n bit patterns with m bits set. One way do that that enumeration is: generate all permutations of a vector with m ones and n zeros and then remove duplicates.
Try it online!
Explanation
h     % implicitly input the two strings of lengths m and n. Concatenate
1M    % push the two strings again
g     % convert the second strings into ones
w~    % swap. Convert the second string into zeros
h     % concatenate: vector of zeros and ones
Y@    % 2D array with all permutations of that vector, each on a row
Xu    % remove duplicate rows
!     % transpose
ttYs  % duplicate twice. Cumulative sum along each column
*     % element-wise product. Produces, in each column, indices for
      % elements of the first string; 1, 2,...,m. The rest are 0
w~    % swap, negate
tYs   % duplicate. Cumulative sum along each column
1Gn+  % add length of first input
*     % element-wise product. Produces, in each column, indices for
      % elements of the second string: m+1,...,m+n. The rest are 0
+     % add. This gives indices into the concatenated string created initially
!     % transpose back
)     % index into concatenated string. Implicitly display

Batch, 154 152 bytes
@if "%~1%~2"=="" echo %3
@set t=%~1
@if not "%t%"=="" call %0 "%t:~1%" "%~2" %3%t:~,1%
@set t=%~2
@if not "%t%"=="" call %0 "%~1" "%t:~1%" %3%t:~,1%

Ruby, 83 bytes
A recursive function that returns [a+b] if either of those strings are empty. Otherwise, it returns a list of strings a[0] + every string in v[a[1..-1],b] added to a list of string b[0] + every string in v[a,b[1..-1]]
v=->a,b{a[0]&&b[0]?v[a[1..-1],b].map{|i|a[0]+i}+v[a,b[1..-1]].map{|i|b[0]+i}:[a+b]}


text:
Evaluate a minimax tree
Alice and Bob are playing a little game. First, they draw a tree from a root node (indicated by a thick dot), with no internal nodes, with numbers at the leaves. Any node may have any number of children.

We start at the root, and first to play is Alice (A). She must select one of the current node's children. Then it's Bob's turn, and he similarly selects a child node. This continues until a leaf node is reached.
When a leaf node is reached, the game is over. It is Alice's goal to end at a node with as large of a value as possible, and Bob's goal to end at a node with as small of a value as possible.
Given a tree in nested array form, return the value of the leaf that will be reached if both Alice and Bob play perfectly.

Examples:
18: [[67, [[100, [[67, 47], [86], 21, 16], [[46, [14], 35, 85], [71, [18, 63, 69], 99, 22], 3]]], [[18, 32, 42, 80]], [[36, 70], [86, 53, 46, 59], [[41], 86, 35]]], 3]
60: [[[84, 35], [44, 60]], [[24, 98], [16, 21]]]
58: [[53, 77], [58, [82, 41]], 52]
59: [[93, [100, 53], 58, 79], [63, 94, 59], [9, [55, 48]], [40, 10, 32]]
56: [[20, 10, [[[89, 22, 77, 10], 55], [24, 28, 30, 63]]], [[49, 31]], 17, 56]
0: [0]

You may assume that the root node never is a leaf node and points to at least one leaf node. You may assume that leafs are nonnegative numbers.

Shortest code in bytes wins.

I recognise this!

Jelly, 7 bytes
Nß€¬¡ṂN

Try it online! or verify all test cases.
This uses the algorithm from @xnor's answer. For comparison purposes, a more straightforward approach that alternately computes minima and maxima weighs 8 bytes:
ß€¬¡€Ṃ€Ṁ

How it works
Nß€¬¡ṂN  Main link. Argument: x (array or integer)

N        Negate. For an array, this negates all integers in it.
   ¬     Logical NOT. For an array, this applies to all integers in it.
    ¡    Apply the second link to the left once if ¬ returned an array or 1, or not
         at all if it returned 0.
 ß€      Recursively call the main link on all elements at depth 1 of -x.
         If -x == 0, € will cast 0 to range before mapping ß over it.
         Since the range of 0 is [], mapping ß over it simply yields [].
     Ṃ   Minimum.
         For an integer, Ṃ simply returns the integer. For [], Ṃ returns 0.
      N  Negate the minimum.

Python 2, 53 bytes
f=lambda l,c=1:c*l if l<[]else-min(f(x,-c)for x in l)

The main question is how to alternate between max and min each layer. Using the fact that max(l) == -min([-x for x in l]), we instead negate every second layer and recurse with -min. To negate every second layer, we pass down a multiplier c that alternates +1 and -1, and when we reach a leaf, we adjust its value by the multiplier. We recognize being at a leaf via the condition l<[], since Python 2 treats numbers as less than lists.
It's hard to shorten the else/if ternary because either branch could give a Truthy (nonzero) or Falsey (zero) value.

JavaScript (ES6), 53 bytes
f=(a,s=1)=>a.map?s*Math.max(...a.map(b=>s*f(b,-s))):a

Uses a similar approach to @xnor's answer. If the numbers are nonzero, then only 49 bytes:
f=(a,s=1)=>+a||s*Math.max(...a.map(b=>s*f(b,-s)))

Pyth, 21 bytes
M?sIG*GH_hSmgd_HGLgb1

My first Pyth answer! Thanks to Dennis for the help :).
M                      # define a binary function (G, H)
 ?sIG                  # if G (first argument) is the same with s applied
                       # (check if it's an integer, so, a leaf node)
     *GH               # in such a case, calculate G*H
        _              # negation
         hS            # take the first element of the sorted list (that's the min)
           mgd_HG      # map over G, applying ourself (g) recursively,
                       # with the current lambda's value (d)
                       # and the negation of H
                 Lgb1  # Define a unary function to call our previous
                       # one with the correct base argument (1)

There's shorter syntax for that map: mgd_H can be gR_H. Also, instead of defining a function you can take input with Q and replace Lgb1 with gQ1.

Mathematica, 13 bytes
-Min[#0/@-#]&

or equivalently
Max[-#0/@-#]&

This evaluates to an unnamed function that takes the tree and returns the result.
This is also essentially the same as xnor's solution: at each level we swap the sign of the list and the result and use Min all the way down. This turned out incredibly golfy in Mathematica, because:

Min can take either individual numbers or lists or even several lists. It just gives you the minimum value across all of its arguments. That means it works both on lists as well as leaves (where it just returns the leaf).
/@ which is short for Map is a very general higher-order function in Mathematica. It doesn't just map a function over lists, it can map them over any expression whatsoever. Numbers are such an expression, but they don't contain any elements to be mapped over. That means we can safely map any function over numbers, which doesn't affect the number at all.

Both of those things together mean we can write the code without any conditionals, since the Min and Map operations are no-ops on numbers, and subsequently the two negations cancel out so that the function becomes the identity when given a number.
Finally, thanks to #0 it is possible to write unnamed recursive functions in Mathematica, which saves a few more bytes.

Ruby, 46 bytes
Used @xnor's trick with min for alternating between max and min.
f=->n,a=1{n==[*n]?-n.map{|c|f[c,-a]}.min: a*n}

Julia, 27 25 bytes
!a=0==0a?a:-minimum(!,-a)

This uses the algorithm from @xnor's answer. Try it online!

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


text:
Unlocking the Secrets to a 1-Dimensional Labyrinth
Background
You awake to find yourself lost in a one dimensional labyrinth! A mystical genie (or something) appears and explains that the exit lies in front of you, but that between you and the exit is a series of challenges. As you wander forward you realize that all of the so-called challenges are merely locked doors. You first see a door with a tee-shaped key-hole, and having no such key yourself, retrace your steps, looking for a key with a T shape.
Frustrated, you find an alphabet soup of keys on the ground, none of which match the door you've come across. By some stroke of genius (or idiocy), you decide that the lower-case t-shaped key might be able to fit in the slot if you jam it in there hard enough. As you approach the door with the lower-case t key in hand, the T hole glows green and the door dissolves in front of you.
One down, many more to go...
Challenge
The goal of this challenge is to mark how many steps it takes you to exit the labyrinth.
The input of this challenge is the labyrinth: one string containing only  characters [A-Za-z^$ ].
Glossary:

^ -- The start space. The input will contain exactly one ^.
$ -- The exit (freedom!). The input will contain exactly one $.
[A-Z] -- Capital letters signify doors. You can only go through this door if you have already collected the requisite key.
[a-z] -- Lower case letters signify keys. You collect these keys by walking onto the space that contains the key.

There will be at most one of each capital letter in the input. This means the total number of doors will be between 0-26 inclusive.
Every locked door [A-Z] will have exactly one corresponding lower case key [a-z]. There may be any number of spaces ( ) in the input.
All of the doors will be to the right of the start, and to the left of the exit. Thus there will be no superfluous doors. All inputs will be solvable.
The output for this challenge will be a number, the number of steps it took to exit the labyrinth.
Algorithm
Your methodical approach to exiting this wretched place is as follows:

Start at the beginning (^) and move forward (right) collecting any keys you come across.
When you come across a door, if you have the correct key, you proceed forward onto the door. If you don't have the correct key, you walk backwards (left) collecting keys you come across until you find the key for the most recent door that you couldn't open.
Once you collect the key for the current troublesome door, you turn back to the right and proceed onward.
Repeat this process until you step on to the exit ($).

Experienced golfers will understand that your code doesn't have to implement this specific algorithm as long as it outputs the same result as if you had run this algorithm.
Counting
Each time you step from one square onto another square, that counts as one step. Turning 180º incurs no additional step. You cannot step forward onto a door without the requisite key. You must step onto a key to pick it up, and must step onto the exit to win. After your first move, the start space (^) behaves just like any other regular space.
Examples
In these examples I've left the spaces as underscores for human-readability.
Input is _a_^_A__$__. The output is 11. You take 1 step forward, notice that you have no key for the A door, and then about face. You walk backward until you occupy the space containing the a (3 steps backward, now 4 total). You then walk forward until you occupy the space containing the exit (7 steps forward, 11 total).
Input is b__j^__a_AJB_$. The output is 41 You make two separate trips to the back of the labyrinth, one to get the j key, and the next one to get the b key.
Input is __m__t_^__x_T_MX_$____. The output is 44. You won't make any extra trip to get the x key, as you picked it up on your way from the start to door T.
Input is g_t_^G_T$. The output is 12. You cannot move onto the G space without a key, and immediately about-face. You're lucky enough to pick up the t key on the way to the g key, and thus open both doors on your way to freedom.
Input is _^_____$. The output is 6. That was easy.
I/O Guidelines and Winning Criterion
Standard I/O rules apply. This is a code-golf challenge.

Apart from the nice challenge, I'd like to remark how good the wording and explanation are

"Thus there will be no superfluous doors." I think A in bA^aB$ wouldn't be superfluous either. ;)

"The goal of this challenge is to mark how many steps it takes you to exit the labyrinth." Then why not require optimality? Always going right first is not an optimal strategy.

@MartinBüttner ;)

@orlp I'm more interested in seeing how people golf this wandering-in-the-dark algorithm. It seems trivial to do the optimal solution of "go get all the keys then go open all the doors".

@orlp, this is more interesting than optimality (for which there would almost certainly be a handful of dupe candidates).

@PeterTaylor and turbulencetoo No it's not, who's to say all the keys are on the left side, and all doors on the right? And superfluous keys/doors would be interesting too. It'd be pretty interesting, as it would mean solving a dependency graph.

@orlp The optimal solution would be interesting, just as the present algorithm is. Maybe a future new challenge about the optimal solution? However, it may be difficult to verify that a solution is indeed optimal

Every door has a key. Does every key have a door?

Wait. Its a  1-Dimensional Labyrinth where you can go left??

@Distjubo - hehe, yes - a single dimension denotes a line.

I wonder if there will be any language solving this with 1 byte built-in this time?

The optimal solution would to just keep going straight collecting every key as you go if it weren't for the algorithm constraint. Good thing there's no inventory constraint as well.

@user2357112 Does it matter if every key has a door or not?

CJam, 45
1q_'$#<'^/~\W%:A;ee{~32+A#)_T>{:T+2*+}&]0=)}/

Try it online
Explanation:
1         initial step count; this 1 is actually for the last step :)
q_'$#<    read the input and only keep the part before the '$'
'^/~      split by '^' and dump the 2 pieces on the stack
\W%:A;    take the first piece, reverse it and store it in A
ee        enumerate the other piece (making [index char] pairs)
{…}/      for each [index char] pair
  ~32+    dump the index and character on the stack, and add 32 to the character;
           uppercase letters become lowercase and other chars become garbage
  A#)     find the index of this character in A and increment it (not found -> 0)
  _T>     check if this index (number of steps from '^' back to the key)
           is greater than T (which is initially 0)
  {…}&    if that's true (we need to go back), then
    :T    store that index in T (keeping track of how far we go back before '^')
    +     add to the other index (from the pair, number of steps we took after '^')
    2*    double the result (going back and forth)
    +     add it to the step count
  ]0=     keep only the first value from the bottom of the stack (step count)
           (if the condition above was false, we'd have 2 extra values)
  )       increment the step count (for the current step)

Pyth, 51 bytes
JxQ"^"K-xQ"$"JVQI&}NrG1>JxQrN0=JxQrN0=+K*2t-xQNJ;pK

sum the distance between the door and its key (doubled, to take the round trip), ignoring the "nested" keys and the distance from the start to the end:
JxQ"^"                                              #Initialize the farther point with the starting position
      K-xQ"$"J                                      #Initialize the step counter with the difference between the exit and the start
              VQ                                    #iterate over the input
                I&}NrG1>JxQrN0                      #check if is upper and if the keys is father than one stored (to eliminate nested keys)
                              =JxQrN0               #update the farther key
                                     =+K*2t-xQNJ;   #update step counter with the round trip door<>key
                                                 pK #print the step counter

same algorythm in python2.7 :
lab=raw_input()
farther_key=lab.index('^')
steps = lab.index('$') - farther_key
for i in lab:
    if i.isupper():
        if farther_key> lab.index(i.lower()):
            farther_key=lab.index(i.lower())
            steps+=((lab.index(i) - farther_key)-1)*2
print steps

Python 2, 155 154 134 128 bytes
Edit:  Thanks to @user2357112 and @loovjo for their comments that helped me shave another 20 26 bytes off my solution!
def f(l):
 i=l.index;b=i('^');t=i('$')-b
 for d in filter(str.isupper,l):
  k=i(d.lower())
  if k<b:b=k;t+=2*(i(d)-k-1)
 print t

You can combine the second and third line with a semicolon, saving one byte. Also, the i variable seems unnecessary in the loop.

Agreed on the 2nd and 3rd line, @Loovjo, but why do you say i is unnecessary?  i tracks the position of the door currently being processed, and is required if its key hasn't been picked up yet (i.e. if k - the position of the key - is less than f - the furthest left we've walked - then we need to add 2*(i-k-1) steps to our total (walking left to get the key, and walking right back to the door) ... ?

But couldn't the i be replaced by l.index(d) on the fifth line and the assignment by removed at the fourth?

The separate e and f variables look redundant. Also, you could save a bunch of characters by saving l.index to a variable.

@loovjo : Yup, you're right ... I misunderstood your comment at first.
@user2357112 :  absolutely correct.  x is redundant as well.
Guess my golf noob-iness is showing. :)  Thanks for the help!

You still have a l.index where an i could be used on line 4.

C, 136 bytes
q,x,p[300],z,c,k;main(i){for(;p[c=getchar()]=++i,c-36;z&&(k+=(x=p[c+32])&&x<q?(q=q>x?x:q,2*i-2*x-1):1))z=p[94],q||(q=z);printf("%d",k);}

PHP 5.3, 123 bytes
This is my first post on Code Golf, hopefully this is of golfing quality high enough for a first post. Definitely a fun challenge and an awesome question!
function n($m){while('$'!=$o=$m[$i++])$o=='^'?$b=$i+$c=0:$o>'Z'||$b<=$k=stripos($m,$o))?$c++:$c+=2*$i-3-2*$b=$k;return$c;}

This program nicely abuses the fact that PHP doesn't need you to pre-declare any variables before you use them.
It also turned out to be a couple bytes shorter in my final solution to start at 0 and reset the step count when the start character is found, rather than starting at the '^'.
Any tips are definitely welcome!

JavaScript (ES6), 110 bytes
s=>(i=c=>s.indexOf(c),p=i`^`,l=i`$`-p,s.replace(/[A-Z]/g,(c,j)=>p>(t=i(c.toLowerCase()))?l+=j-(p=t)-1<<1:0),l)

Port of @Rob's Pyth answer.

Python 2.7, 234 199 179
a=raw_input()
x=a.index
v=x('^')
b=x('$')-v
l=filter(str.islower,a[:v])[::-1]
for i in filter(str.isupper,a):
 k=i.lower()
 if k in l:b+=(x(i)-x(k)-1)*2;l=l[l.index(k)+1:]
print b

C#, 309 bytes
class P{static void Main(string[]a){string m=Console.ReadLine(),k="";var f=true;char b,c=b=' ';int j=m.IndexOf('^'),t=0;for(;m[j]!='$';j+=f?1:-1){c=m[j];if(char.IsUpper(c)){if(k.IndexOf(char.ToLower(c))<0){f=!f;b=c;t--;}}if(char.IsLower(c)){k+=c;if(char.ToUpper(c)==b){f=!f;t--;}}t++;}Console.WriteLine(t);}}

Ungolfed version:
    class P
{
    static void Main(string[] a)
    {
        string m = Console.ReadLine(), k = "";
        var f = true;
        char b, c = b = ' ';
        int j = m.IndexOf('^'), t = 0;
        for (; m[j] != '$'; j += f ? 1 : -1)
        {
            c = m[j];
            if (char.IsUpper(c))
            {
                if (k.IndexOf(char.ToLower(c)) < 0)
                {
                    f = !f; b = c; t--;
                }
            }

            if (char.IsLower(c))
            {
                k += c;
                if (char.ToUpper(c) == b) { f = !f; t--; }
            }

            t++;
        }
        Console.WriteLine(t);
        Console.ReadKey();

    }
}

Nothing fancy here, just iterate through the string and change direction based on the character and whether the key is contained in a keys string.
m = the maze string
k = the keys string
f = the direction (true is forward in the maze)
b = the key to search for when backtracking
c = placeholder for m[j] to save some bytes due to frequent use
j = the char index of the string to look at
t = the count
Still relatively new to golfing so if you see somewhere I can slim it down, let me know!

AWK, 174 Bytes
func f(xmS){x+=S
c=a[x]
if(c~/^[A-Z]/&&!k[c]){C=c
S=-S
s--}else{c=toupper(c)
k[c]=1
s++
if(c==C){S=-S;C=9}}if(c=="$"){print s}else f(x,S)}{split($0,a,"")
f(index($0,"^"),1)}

There's probably a tighter algorithm, but this is what I came up with.
Do note that I'm using gawk.  Some implementations of AWK may not split a string on "" this way.


text:
Print the sum of the squares of some numbers
This is a little codegolf challenge from codingame.com. I was wondering how much Python3 code is necessary (but of course answers are not limited to Python3).
Input
The first line contains one positive integer n. The second line contains n positive integers. Each consecutive integers on the second line are separated by one space. There is no newline at the end of the second line.
Output
One line containing the sum of the squares of the numbers on the second input line, and no white space except an optional newline at the end.
Each entry must be a complete program with input and output, not only a function. Shortest code wins.
For example, input:
5
1 2 5 7 8

and output:
143

Can we take only one input? The first one is unnecessary

You do know you're changing IO allowed by default?  http://meta.codegolf.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods/

Input #1=len(input2.split())

Can I have a link to the original question?

Can we take input as a list of integers? (i.e [1,2,5,7,8])

I'm confused why you've posted both here and in the Sandbox ... http://meta.codegolf.stackexchange.com/a/8827/42963

@CatsAreFluffy - There is no link to the original question, because codingame.com gives the challenges randomly; up to 8 people compete in a randomly selected challenge with a time limit of 10 or 15 minutes, and there is no way to go back and view the question after the time expires.

@DonMuesli -  The code that is submitted there is evaluated automatically, so the first line of input just is there, even though it is unnecessary

@Martin Büttner - It is not a competition, it just a casual time-passer. You may stumble over it multiple times, so I do not think that cheating is a problem. There is no permanent ranking. As to copyright, I do not think that copyright can cover the idea itself, and even if it would, this would be a fair use exception.

@muddyfish and quartata - Sorry about the IO. I stated it the way it was required by the question on codingame, because the first line of input was in the way, and I was wondering how many bytes of code it would take to handle it. input(input()) from CatsAreFluffy's answer saved one byte in this respect, as opposed to my initial code.

@Stewie Griffin - Well, I would prefer if we would stick to the input restrictions of the original problem (input as a list of integers would not be ok in this case) because I am still curious to see if anyone can further improve on the code size of the Python3 and C answers as far as input goes.

We've discussed the situation among the moderators and figured that the copyright is indeed probably not worth worrying about. However, the downvotes on your challenge are likely due to the fact that you've copied the input format verbatim from the source, and cumbersome I/O formats are one of the things to avoid when writing challenges. If you relaxed the rules a little, this challenge would probably blend in more nicely and be more well-received. Sorry about the premature deletion, and welcome to Programming Puzzles & Code Golf!

Jelly, 5 bytes
ṣ⁶V²S

Try it online.
Input format is rather annoying....
Explanation
ṣ⁶V²S
ṣ⁶       split by space
  V      map eval over the resulting list -- the newline in the first element causes the first line to be treated as a separate link and ignored
   ²     map square over the list
    S    sum

You can save three bytes by eliminating the first three bytes.

@Dennis Oh, that's clever. Thanks.

In case it isn't clear, V executes the string just as if it were a complete program. For the first string, the second line is the main link, and the first one isn't referenced, so it is ignored.

05AB1E, 5 bytes
Code:
²ð¡nO

Explanation:
²      # Take the second input, the first input is ignored
 ð¡    # Split on spaces
   n   # Square each element
    O  # Take the sum and implicitly output it

Uses CP-1252 encoding.
Try it online!

Python 3, 52
i=input;print(sum(int(d)**2for d in i(i()).split()))

It is giving an unnecessary output. But that sound fair since there is an unnecessary input!

Yup, going by the rules...

MATL, 6 bytes
xjU2^s

Try it online!
x    % take first input and throw it away
j    % take second input as a string
U    % convert to array with those numbers
2^   % element-wise square
s    % sum of array

Python 3, 54 bytes
-[] thanks to shooqie
print(sum(int(i)**2for i in input(input()).split()))

Takes input as specified in the first version of the question.
So to answer your question: Not a lot.

first version :-D

Stupid me, testing in a REPL...

You don't need the square brackets: print(sum(int(i)**2for i in input(input()).split()))

@CatsAreFluffy and shooqie - Thank you, I was doing it in 56 bytes and was wondering what parts of the code are unnecessary. As opposed to my code, input(input()) saves one byte, 2for another and the square brackets another two.

Pyke, 10 bytes
;\ cFE2^)s

Takes input as requested
Try it here (Yay setup a try-it page!)
Or 5 bytes if allowed a list of ints:
2Rm^s

Or noncompeting (add squared node), 3 bytes
mXs

Minkolang 0.15, 9 bytes
n[n2;+]N.

Try it here!
Explanation
n            Take number from input
 [    ]      Pop top of stack and repeat that many times
  n          Take number from input
   2;        Square it
     +       Add to top of stack
       N.    Output as number and stop.

CJam, 10 bytes
l;l~]2f#1b

Test it here.
Explanation
l;   e# Read first line and discard.
l~   e# Read second line and evaluate, dumping all integers on the stack.
]    e# Wrap them in an array.
2f#  e# Square each.
1b   e# Sum.

1b is a nice trick

@DonMuesli I could probably use :+ here, but 1b became a habit because it also works as expected for empty arrays.

Octave, 45 bytes
Octave is not exactly designed for accepting random input formats. For instance, input over multiple lines is impossible. Also, numbers can't be entered as a list unless you have brackets. For that reason, the input must be taken as a string.
input('');disp((x=str2num(input('','s')))*x')

input('')                                     % Take the first input line and discard
                         input('','s')        % Take the second input as a string
               x=str2num(input('','s'))       % Convert the string to a list of numbers, x
               (x=str2num(input('','s')))*x'  % Multiply x by x transposed
                                              % This is equivalent to sum(x.^2) but shorter
          disp((x=str2num(input('','s')))*x') % Display the result

Call it like this:
input('');disp((x=str2num(input('','s')))*x')
5
1 2 5 7 8
143

R, 22 bytes
Nothing very flash, handles the input as specified
cat(sum(scan()[-1]^2))

Test run
> cat(sum(scan()[-1]^2))
1: 5
2: 1 2 5 7 8
7:
Read 6 items
143
>

Lua, 74 62  Bytes
Edit: saved 8 bytes due to @KennyLau

It's quite straigthforward, skip the first line and iterate over the group of digits in the second.
i,x=io.read,0i()i():gsub("%d+",function(d)x=x+d*d end)print(x)

Ungolfed
x=0
i=io.read
i()
i():gsub("%d+",function(d)
   x=x+d*d
end)
print(x)

Actually, lua can convert from string to number automatically, so you don't have to do it yourself :)

Also, this actually takes up less bytes than this:
x=0i=1print(x..i)
x,i=0,1print(x..i)

Pyth, 10 bytes
sm^sd2ce.z

Try it here!
Takes input in the exact same format as specified in the challenge.
Explanation

sm^sd2ce.z  # .z = input lines

       e.z  # only take the last line
      c     # split on spaces
 m          # map each number d
   sd       # convert to integer
  ^  2      # square
s           # sum all squares

Alterntive solutions with more generous input formats
8 bytes if I may omit the number count:
sm^sd2cz

Try it here!
4 bytes if I may take the input as list of integers:
s^R2

Try it here!

Pyth, 9 bytes
s^R2re.z7

Try it here
Or 7 bytes if allowed to omit line 1
s^R2rz7

You're missing the first line of input.

C,65 bytes
j,k;main(i){for(;scanf("%d",&i)+1;j++&&(k+=i*i));printf("%d",k);}

Haskell, 48 bytes
main=interact$show.sum.map((^2).read).tail.words

How it works:
interact                 read whole input, pass it to a function and
                         print it's return value. The function is:

               words     split at whitespace into words
           tail          drop first element (the number on line #1)
    map(       )         convert each word
           read             to integers
       (^2)                 and square
  sum                    sum all values
show                     convert back to string

J, 4 bytes + 100
+/*:

Try it.
   +/*:1 2 5 7 8
143

A +100 punishment in the byte-count to myself for not having standard input.

Add proper input commands please. For some reason this question is very specific about I/O formats, and even normally you can't assume input is in a variable. (And it might be shorter anyway (if you have a 1 or 2 byte input command))

Thanks for your comment. Does J really have an input command?

Yes, J has I/O.

Batch, 76 bytes
@set/px=
@set/px=
@set t=0
@for %%n in (%x%)do set/at+=%%n*%%n
@echo %t%

Pylongolf2, 8 bytes
c| n²+~

c  - read the input
|  - split by space (note the 1 space after |)
n  - convert all of that in the list to numbers
²  - Square everything in the list
+  - Sum everything in the list
~  - Print it

GS2, 5 bytes
W",Φd

Try it online!
How it works
W      Find all numbers in the input; push a list.
 "     Discard the first number.
  ,    Square.
   Φ   Map the last instruction over the list of numbers.
    d  Compute the sum of all squares.

Japt, 8 bytes
Ns1 mp x

Try it in the Japt Interpreter.
How it works
The code is parsed as
N.s(1).m(p).x()

N is a variable; it contains the parsed input.
s(1) discards the first array element.
m(p) maps p (square) over the remaining array.
x() computes the sum of the array of squares.

GolfScript, 13 bytes
Input is extremely easy for GolfScript.
~](;{.*}%{+}*

Try it online!
Explanation
~             # Take & Evaluate the input
 ]            # Wrap the whole input into a list
  (;          # Remove the first item
    {.*}%     # Map with squaring
         {+}* # Reduce by summation

JavaScript (V8), 38 bytes
x=>Math.hypot(...x.match(/\s\d+/g))**2

Try it online!

Thunno 2 S, 4 bytes
sON²

Attempt This Online!
With normal I/O it would be 1 byte (with S flag):
²

Attempt This Online!
Explanation
sON²  # Implicit input
s     # Discard the first input
 O    # Split the second input on spaces
  N   # Convert each string to a number
   ²  # Square each number
      # Implicit output of the sum