text:
Let's see some action!
Who doesn't love action movies with fast noisy cars, especially those with a lot of crashes? Who doesn't love action shots in ascii art?
The scene is:
Two cars are starting at opposite sides of a straight road (with 60 spaces between). They start driving towards each other at constant speeds. The car to the left drives at 1 space per second, and the one to the right drives at 2 spaces per second.
Obviously, the cars can't pass through each other, so for n ≥ 20, the scene will be two crashed cars with bonnets up at the position where the crash occurred.
As a movie lover, I want to pause the scene now and then, just to enjoy the beauty of it.
Given an integer n (function argument or STDIN), representing the number of seconds from the start of the scene, show the scene at that moment.
This is the starting scene, with 60 spaces between the front wheels:
  __                                                                __
_/  \_                                                            _/  \_
o    o                                                            o    o

this is the scene after 11 seconds:
             __                               __
           _/  \_                           _/  \_
           o    o                           o    o

and this is what it looks like after the crash (note that the bonnets are up after the crash):
                      __    __
                    _/  \/\/  \_
                    o    oo    o

I'm only interested in watching two cars crashing, so spaces, newlines, ++ doesn't matter.
This is code golf, so the shortest code in bytes wins. Answers added later can still win if they are shorter than the current accepted answer.

It's implied, but is the crash (20s?) the only time the bonnets are up / \  as opposed to down _ _ ?

@StewieGriffin Nice one!!

CJam, 68 66 bytes
liKe<:M"  __  _/  \_o    o"6/f{\S*1$+60M3*-S*@N}:+MK={58'/t59'\t}&

Try it online
Anybody who sees the start of the code will be sure to liKe it!
Explanation:
li      Get input n and convert to integer.
Ke<     Cap n at 20.
:M      Save in variable M for multiple use later.
"  __  _/  \_o    o"
        Car (18 characters).
6/      Split into 3 lines of 6 characters.
f{      Map lines with parameter.
  \       Swap n to top.
  S*      Create string with n spaces for left margin.
  1$      Copy one car line to top. Keep original for second car
  +       Concatenate the spaces and car.
  60M3*-  Calculate 60-3*n, which is the amount of space between cars.
  S*      Create string with 60-3*n spaces.
  N       Add a newline.
}       End of line mapping.
:+      Concatenate all output pieces into single string.
MK=     Check if capped n is equal to 20.
{       If equal, replace hoods with crashed versions.
  58'/t   '/ at position 58.
  59'\t   '\ at position 59.
}&      End of conditional block for crashed hoods.

Are the first four characters a subliminal message for the voters?

@JanDvorak Absolutely! :) Well, it wasn't completely subliminal anymore because I pointed it out. No original intention, but I noticed it immediately when I pasted the code into the answer.

Labyrinth, 394 386 bytes
I proudly introduce...
<}74}}:23}29}59}}}}}}}:111_}}}}:::::::23_}:111
?                        @
:" }}_47}_95    3""""""""(
 _ :       }    _   }    {=}
 2 23_}29_ _    ;   :      \
 0       ; 3  +_( 3_"  60{ .{.{.
"-_95:}}"" 2  0 ) 2 "  _ _ {
""       _ :  2 _ ."(; } 3 .{
 ;_92}_47} :  _ 0    = : *  ;
           : "" 2 {.{{ . -""(
}}:59_}}:::: "";_ .    {  _ "
}             "   {.{.{.  32.
}}}_95:}}}}_20-

...my new two-dimensional esolang Labyrinth! The code above isn't incredibly well golfed (there are 161 spaces and 25 NOPs, so a better layout could shorten this a lot), but at least I managed to show that the language is usable for non-trivial tasks. :)
How it works
First, a quick overview of the language:

Labyrinth operates on two stacks, main and auxiliary, which can hold arbitrary signed integers. At the bottom of both stacks there is an infinite amount of zeroes.
Commands are individual characters on a 2D grid and they form a maze (that is unknown characters, particularly spaces, are walls). " is a NOP which is not a wall and can be helpful for padding certain paths in the code. As opposed to many other 2D languages, the edges do not wrap around.
The instruction pointer (IP) starts at the first non-wall character (in reading order) moving to the right. @ terminates the program.
If possible, the IP follows corridors (also around bends). If the IP has multiple cells to move to, it will generally turn left if the top of the main stack is negative, move straight ahead if it's zero, or turn right if it's positive. When the IP hits a wall it reverses direction. (There are a few more subtleties, but they shouldn't matter for this code.) This is the only way to implement control flow.
Apart from arithmetic and stack manipulation commands, the source code can be modified at runtime with the four commands >v<^ which will shift a row or column of the source code cyclically by one cell. Which row or column is affected depends on the top of the stack. If the IP's own row or column is shifted, it will move with the shift. This makes it possible to jump from one edge of the source code to the other.

Now for this particular challenge, here is the general idea of the algorithm:

Push the ends of the cars up to the bonnets (i.e. /  \_o    oo    o) onto the auxiliary stack.
Read the input and determine whether to push __ or /\ next.
Push the remainder of the cars (i.e. __    __  _/  \ and two leading spaces) onto the auxiliary stack.
Clamp the input to a maximum value of 20, let's call this N.
Now do the following 3 times:

Print N spaces.
Print 6 stored characters.
Print 60 - 3*N spaces.
Print 6 stored characters.
Print a newline.

Finally, let's look at some parts of the code. The IP starts in the top left corner, on a grid shifting command. The top of the main stack is 0 (which is used as a relative index), so the first row is shifted to the left, which also moves the IP to the right end of the grid. Now the first row is simply executed from right to left, which pushes the first set of fixed characters onto the auxiliary stack:
}74}}:23}29}59}}}}}}}:111_}}}}:::::::23_}:111<

This row shifting is useful for golfing when you want to start with a large amount of linear code.
Next we read the input and push the correct bonnets:
?
:"
 _
 2
 0       ;
"-_95:}}""
""       _
 ;_92}_47}

The bit on the left with the three NOPs sends negative results along the top branch and non-negative results along the bottom branch. At the right they are joined back together.
Now follows another large linear section (which could probably be golfed a lot with another row-shifting trick):
   }}_47}_95
   :       }
   23_}29_ _
           3
           2
           :
           :
           :
}}:59_}}::::
}
}}}_95:}}}}

This pushes the remainder of the cars onto the auxiliary stack.
Next, we compute min(20, input), which is similar to first branch:
                ;
              +_(
              0 )
              2 _
              _ 0
             "" 2
             "";_
              "
           _20-

Finally, we have the loop which runs three times to print the lines. Each iteration of the loop contains two small (3x3) loops to print the spaces, as well as two sections to print 6 characters from the auxiliary stack:
                         @
                3""""""""(
                _   }    {=}
                    :      \
                  3_"  60{ .{.{.
                  2 "  _ _ {
                  ."(; } 3 .{
                     = : *  ;
                  {.{{ . -""(
                  .    {  _ "
                  {.{.{.  32.

One nifty trick I'd like to draw attention to is the .{.{. at the right edge. This is a dead end, so apart from the . at the end the code is executed twice, once forward and once backward. This gives a neat way to shorten palindromic code (the catch is that you need to make sure the IP takes the correct turn when exiting the dead end again).

Challenge: Write a program in Labyrinth without a monospaced font ;)

@BetaDecay That sounds painful in any language. ;)

Python 2.7, 167 164 159 Bytes
n=input();s,x=60-3*n,min(n,20)
for e in['  _',"_/ ","o  "]:p=e+(e[::-1],(' \_',' \/')[s<1])['/'in e];print" "*x+p+" "*s+(p[-1]+p[1:-1]+p[0]).replace("//","\/")

This takes input from stdin.
Demo here
Testing this -
$ ./cars.py
0
  __                                                                __
_/  \_                                                            _/  \_
o    o                                                            o    o

$ ./cars.py
11
             __                               __
           _/  \_                           _/  \_
           o    o                           o    o

$ ./cars.py
20
                      __    __
                    _/  \/\/  \_
                    o    oo    o

(n,20)[n>20] is simply min(n,20).

You can save a byte by replacing (' \_',' \/')[s<1] with '  \\\\_/'[s<1::2].

Also, is l necessary? Could you just do for e in ['  _',"_/ ","o  "]: and remove l altogether?

@kirbyfan64sos Yes, l is not necessary now. I had to used it in an earlier version. Thanks :)

@kirbyfan64sos and regarding ' \\\\_/'[s<1::2], i think it has to be '  \\\\_/'[s<1::2](notice the 2 starting spaces rather than the one) which is the same length as the original expr, but thanks for that, didn't know i could do that :)

@Kamehameha Actually, mine is shorter: I just mistyped it! :/ It should be r'  \\_/'[s<1::2].

R, 191 Bytes
About as good as I can get it now.  Takes the seconds from STDIN and cats to STDOUT.
n=scan();p=paste0;formals(p)$collapse='';cat(sprintf(c('%s  __  %s  __  ','%s_/  \\_%s_/  \\_','%s_/  \\/%s\\/  \\_','%so    o%so    o')[-3+(n<21)],p(rep(' ',n)),p(rep(' ',60-n*3))),sep='\n')

Explanation
# Get the input from STDIN.  Requires a single number 0-20
n=scan();
# alias paste0 and set collapse default to ''
p=paste0;
formals(p)$collapse='';
# output
cat(
    # sprintf to format the strings
    sprintf(
        # vector of strings to format                                                      picks which bonnet to remove
        c('%s  __  %s  __  ','%s_/  \\_%s_/  \\_','%s_/  \\/%s\\/  \\_','%so    o%so    o')[-3+(n<21)]
        # move left car by 1
        ,p(rep(' ',n))
        # move right car by 2
        ,p(rep(' ',60-n*3))
    )
,sep='\n')

Tests
> n=scan();p=paste0;formals(p)$collapse='';cat(sprintf(c('%s  __  %s  __  ','%s_/  \\_%s_/  \\_','%s_/  \\/%s\\/  \\_','%so    o%so    o')[-3+(n==20)],p(rep(' ',n)),p(rep(' ',60-n*3))),sep='\n')
1: 0
2:
Read 1 item
  __                                                                __
_/  \_                                                            _/  \_
o    o                                                            o    o
> n=scan();p=paste0;formals(p)$collapse='';cat(sprintf(c('%s  __  %s  __  ','%s_/  \\_%s_/  \\_','%s_/  \\/%s\\/  \\_','%so    o%so    o')[-3+(n==20)],p(rep(' ',n)),p(rep(' ',60-n*3))),sep='\n')
1: 5
2:
Read 1 item
       __                                                 __
     _/  \_                                             _/  \_
     o    o                                             o    o
> n=scan();p=paste0;formals(p)$collapse='';cat(sprintf(c('%s  __  %s  __  ','%s_/  \\_%s_/  \\_','%s_/  \\/%s\\/  \\_','%so    o%so    o')[-3+(n==20)],p(rep(' ',n)),p(rep(' ',60-n*3))),sep='\n')
1: 20
2:
Read 1 item
                      __    __
                    _/  \/\/  \_
                    o    oo    o
>

Nice work! And clever use of formals(). :)

@AlexA it only saved me one in the end, but seeing the two collapses was a bit offensive

You and I have very different definitions of "offensive."

PHP, 160 155 bytes
$f=str_repeat;echo$l=$f(' ',$s=min(max($argv[1],0),20)),"  __  ",
$m=$f(' ',$r=60-3*$s),"  __\n{$l}_/  \\",$r?_.$m._:'/\\',
"/  \\_\n{$l}o    o{$m}o    o\n";

The code is displayed here on 3 lines to fit the layout of the code box. Those newlines are not needed.
The ungolfed code:
// The number of seconds, between (and including) 0 and 20
$sec  = min(max($argv[1], 0), 20);
$rest = 60 - 3 * $sec;

$left = str_repeat(' ', $sec);      // left padding
$mid  = str_repeat(' ', $rest);     // space in the middle
$c = $rest ? '_'.$mid.'_' : '/\\';

echo($left.'  __  '.$mid."  __\n");
echo($left.'_/  \\'. $c ."/  \\_\n");
echo($left.'o    o'.$mid."o    o\n");

It gets the number of seconds from the command line (first argument):
$ php -d error_reporting=0 action.php 11
             __                               __
           _/  \_                           _/  \_
           o    o                           o    o

The PHP CLI option -d error_reporting=0 is needed to hide some notices PHP displays about undefined constants (str_repeat, _) that it converts to strings (2 bytes saved for each notice).
One additional byte can be saved on PHP 7 by squeezing the initialization of $f into its first use ($m=($f=str_repeat)(...)); it doesn't compile on PHP 5.
The test case and some of the techniques used to shrink the code can be found on github.
Update:
@ismail-miguel squeezed the initialization of $left and inlined $c into the arguments of echo saving 4 bytes (see comment below).
By swapping the order the variables $m and s are initialized I got rid of a pair of parentheses and saved 1 byte more.

156 bytes: $f=str_repeat;$m=$f(' ',$r=60-3*($s=min(max($argv[1],0),20)));echo$l=$f(' ',$s),"  __  $m  __\n{$l}_/  \\",$r?_.$m._:'/\\',"/  \\_\n{$l}o    o{$m}o    o\n";

@IsmaelMiguel 155 bytes: $f=str_repeat;echo$l=$f(' ',$s=min(max($argv[1],0),20)),"  __  ",$m=$f(' ',$r=60-3*$s),"  __\n{$l}_/  \\",$r?_.$m._:'/\\',"/  \\_\n{$l}o    o{$m}o    o\n";

I tried a variation of your finding and I actually got longer code. You can edit your answer and update the byte count

I also tried to extract o    o into a variable but got the same length or worse.

You can replace the \n with real newlines. I forgot about it. And it counts as 1 byte each

@IsmaelMiguel Yes, I know that. I can also remove the trailing \n altogether, save 4 bytes in total this way.

CJam, 120 bytes
q~20e<_["   "]*\[" _o"]\[" / " "_  " "_  " " \ " ]\[19>" /o"" _o"?]60 3 5$,*-["   "]*[0$," _o"" \o"?]3$[" _o"]+++++++zN*

Demo
Ungolfed:
q~        e# Read the input
20e<      e# min(20, input) (let's call it N)
_         e# Duplicate the value on the stack
["   "]   e# Push 3 blank spaces
*         e# Create N arrays of 3 blank spaces
\         e# Swap the top two stack elements
[" _o"]   e# Push the " _o" string to stack
\         e# Swap the top two stack elements
[" / " "_  " "_  " " \ " ]
\         e#
[         e# If N is greater than 20 then push the array [" /o"],
  19      e# otherwise [" _o"]
  >
  " /o"
  " _o"
  ?
]
60        e# 60 is the maximum space between the two cars
3         e# 3 is the number of blocks covered per move
5$,       e# Take the 6th element from the stack (an array of size N)
*-        e# Compute the remaining blocks (60 - 3 * N)
["   "]   e# Add an array of 3 blank spaces
*         e# Multiply it to fit the remaining blocks
[0$," _o"" \o"?] e# Add the (broken?) front part of the second car
3$        e# Copy the middle part of the car
[" _o"]   e# Append the right side of the car
+++++++   e# Concatenate all arrays
z         e# Transpose the array
N*        e# Join the array using new lines

Demo

You should be able to save quite a bit of code by not having separate strings for the left and right car, since they are basically the same (except for the crash case). A couple of local improvements: Variable J has value 19, K has value 20, saving a character each for those constants. If you need an array with one element, you can use the a operator to wrap the element, instead of using a pair of brackets.

Thanks for the tips and for the posted CJam code. It actually helps a lot to see many other possible improvements.

JavaScript (ES6), 121 bytes
Using template string, the 2 newlines inside the string are signficant and counted.
To save bytes, output with alert, even if the proportional font used in alert is not well suited for ASCII art and the result is ugly for n>=20 (crash).
Test running the snippet in FireFox

F=n=>alert(`  __
_/  \\_
o    o`.replace(/.+/g,v=>(Z=x=>' '.repeat(x)+v)(n<20?n:n=20)+Z(60-3*n)).replace('__/','/\\/'))
<input id=I value=10><button onclick='F(I.value)'>go</button>

C, 180 191 168 bytes
#define S(x,y)"  __  ",#x"/  \\"#y,"o    o",
char*s[][3]={S(_,_)S(_,/)S(\\,_)};i;l;f(n){l=n>19&&(n=20);for(i=0;i<3;i++)printf("%*s%*s\n",n+6,s[l][i],60-3*n,s[l*2][i]);}

ungolfed:
// make a map of possible car parts
#define S(x, y) { "  __  ", #x "/  \\" #y, "o    o" }
char * s[4][3]= {
    S(_,_),
    S(_,/),
    S(\\,_)
};
i,l;
f(n){
    i = 0;
    l = n>19 && (n = 20); // l = 1, if crash happend
    for(; i < 3; i++) {
        // '*' means length (padding) is given as an int argument
        printf("%*s%*s\n", n + 6, s[l][i], 60 - 3 * n, s[l*2][i]);
    }
}

test program:

main() {
    f( 0);f( 5);f(10);
    f(15);f(20);f(21);
    return 0;
}

output:
  __                                                          __
_/  \_                                                      _/  \_
o    o                                                      o    o
       __                                           __
     _/  \_                                       _/  \_
     o    o                                       o    o
            __                            __
          _/  \_                        _/  \_
          o    o                        o    o
                 __             __
               _/  \_         _/  \_
               o    o         o    o
                      __    __
                    _/  \/\/  \_
                    o    oo    o
                      __    __
                    _/  \/\/  \_
                    o    oo    o

I was able to golf this one pretty hard. I think I started with almost 300 bytes.
But I don't know if this still fulfills all the requirements. As you can see after 21 seconds, the first car pushes the second car over to the right. I would need to add a few bytes if this isn't allowed.
Edit: fixed it. This should be more realistic than Sharknado ;-)
Edit: I could significantly shorten my solution by taking a second look at the printf man-page. If you use '*' you can supply the field length directly to printf, without the need to create a format-string with sprintf beforehand.

The faster car should compensate for the heaviness of the other car. They shouldn't move after hitting, or would maybe even move to the left a bit, since twice the speed on the right, but probably not twice the weight on the left.

I agree with @mbomb007,but, Sharknado 3 has an IMDB-rating of 4.5, so even though your answer is obviously defying physics, it might still deserve some positive recognition =)

I think the expected behavior is clearly defined in the question (emphasis added): "for any large enough n, the scene will be two crashed cars at the position where the crash occurred". The way I read this, they should stay at the same position indefinitely after the crash.

Python 2, 148 bytes
This uses ANSI escape codes to position the cursor in the right place to draw the cars. It then checks to see if the input was 20, if it was, it goes back and draws on the bonnets of the car.
Takes an int from stdin, output to stdout.
p=lambda x:"u  __u_/  \_uo    o".replace("u","\n\033[%dC")%(x,x,x)+"\033[4A";i=min(20,input());print p(i)+"\n"+p(66-i*2)+"\n\n\n\033[25C/\\"*(i==20)

Ungolfed:
def get_car(x):
    return "\n  __\n_/  \_\no    o".replace("\n","\n\033[%dC")%(x,x,x)+"\033[4A"

i=min(20,input())
print get_car(i)
print get_car(66-i*2)
if i==20:
    print"\n\n\033[25C/\\"

Pyth, 67 bytes
Kjbm+++*\ JhS,Q20d*\ -60*3Jdc3"  __  _/  \_o    o"?nJ20KXXK58\/59\\

Try it out here.
                                                                       Implicit: Q=eval(input())
          JhS,Q20                                                      Set J=min(Q,20)
                              "  __  _/  \_o    o"                     Concatenated car string
                            c3                                         Split into 3
   m                                                                   For d in the above
       *\ J                                                            J spaces before 1st car
                  *\ -60*3                                             60-3J spaces in between them
    +++          d         d                                           Concatenate spaces and car string
Kjb                                                                    Join on newlines, store in K
                                                  ?nJ20                If J != 20...
                                                       K               ... print K
                                                         XK58\/        ... else put / in position 58
                                                        X      59\\        and \ in position 59 (implicit print)

Python 2, 102 bytes
n=input()
for r in"  __  ","_/  \_","o    o":print((n*' ')[:20]+r+(60-3*n)*' '+r).replace('__/','/\/')

Pretty straightforward. For each row of the car, we print n spaces, that row, 60-3*n spaces, and the row again. To stop the cars, rather than doing min(n,20), it was one char shorter to limit the first run of spaces with [:20], and the second is fine because a negative times a string is the empty string.
To move up the fenders, we just do a replace. Since __ also appears on the roof, we need a bit of context to identify the fenders, so we check for a / following.

><>, 538 276 bytes
 :3*a6*$-:0)?v~~a2*0c4*1-e2*1+6pa9*2+b7p04.
  v          >04.
 >>1[>:0)  ?v~].
  ^  ^-1o" "<
\$:&94&12." ":oo"_":oo" ":oo
\$:&95&12." ":oo"_":oo" ":ooao
\$:&96&12."_"o"/"o" ":oo"\"o"_"o
\$:&97&12."_"o"/"o" ":oo"\"o"_"oao
\$:&98&12."o"o" ":::oooo"o"o
\$:&99&12."o"o" ":::oooo"o"o;

I've dropped the size a LOT, I'm amazed that I managed to drop the size by half.  The old one is below.  This one is not as efficient performance wise due to the width of the grid, mostly from the very first line.
You can test it out here.  Put the amount of time passed in the "Initial Stack", not "Input"!
Here's the old version.
:3*a6*$-:0)  ?v~~a2*0c4*1-c3*1-4p^
v~v?)0:  <[1:$/$:1[ >:0)  ?v~]" ":oo"_":oo" ":ooaov
] >" "o1-^    ^    <^-1o" "/"/"o"_"<]~v?)0:  <[1:$<
>" ":oo"_":oo" ":oo^       \o" ":oo"\"\" "o1-^
/o"\"oo:" "o"/"o"_"]~v?)0:  <[1:$o"_"o/
\"_"oaov   hi there  >" "o1-^
       >$:1[ >:0)  ?v~]"o"o" ":::oooo"o"o>$:1[ >:0)  ?v~]v
       ^    <^-1o" "<                    ^    <^-1o" "<
              v      p4-1*29+2*9a<    ;o"o"oooo:::" "o"o"<

Java, 258 Chars
class M{public static void main(String[]a){String l="",m=l,r="  __  ",w="o    o",x="_/  \\_";int p=Integer.parseInt(a[0]),i=20;p=p>i?i:p;for(i=-1;++i<p;)l+=" ";for(;++i<21;)m+="   ";System.out.print(l+r+m+r+"\n"+l+(x+m+x).replace("__","/\\")+"\n"+l+w+m+w);}}

Un-Golfed
  class M {
     public static void main(String[] a) {
        String l = "", m = l, r = "  __  ", w = "o    o", x = "_/  \\_";
        int p = Integer.parseInt(a[0]), i = 20;
        p = p > i ? i : p;
        for (i = -1; ++i < p;)
           l += " ";
        for (; ++i < 21;)
           m += "   ";
        System.out.print(l + r + m + r + "\n"
              + l + (x + m + x).replace("__", "/\\") + "\n"
              + l + w + m + w);
     }
  }

Results
0
  __                                                                __
_/  \_                                                            _/  \_
o    o                                                            o    o

1
   __                                                             __
 _/  \_                                                         _/  \_
 o    o                                                         o    o

...

19
                     __       __
                   _/  \_   _/  \_
                   o    o   o    o

20
                      __    __
                    _/  \/\/  \_
                    o    oo    o

21
                      __    __
                    _/  \/\/  \_
                    o    oo    o

Java, 270 267 bytes
Pretty sure there's a better/shorter way of doing this, but my brain isn't properly engaged.
class C{public static void main(String[]a){String l="",m="",r="  __  ",w="o    o";int p=Math.min(Integer.parseInt(a[0]),20),i;for(i=0;++i<p;)l+=" ";for(i=0;++i<60-3*p;)m+=" ";System.out.print(l+r+m+r+"\n"+l+"_/  \\"+(p==20?"/"+m+"\\":"_"+m+"_")+"/  \\_\n"+l+w+m+w);}}

For n=19:
                    __      __
                  _/  \_  _/  \_
                  o    o  o    o

For n=20:
                     __    __
                   _/  \/\/  \_
                   o    oo    o

Ungolfed

public class Crash {
public static void main(String[] args) {
    String left="", mid="", r="  __  ", w="o    o";
    int pos = Math.min(Integer.parseInt(args[0]),20),i;
    for (i=0; ++i<pos;){
        left+=" ";
    }
    for (i=0; ++i<60-3*pos;){
        mid+=" ";
    }
    System.out.print(
            left + r + mid + r + "\n" +
            left + "_/  \\" + (pos==20 ? "/" + mid + "\\" : "_" + mid + "_") + "/  \\_\n" +
            left + w + mid + w);
}
}

The results of this are slightly incorrect. Your cars start only 59 chars apart. My solution fixes this and Golfs yours a bit harder :)

Good catch & well done :)

Javascript, 193 bytes
It's not a winner, but it's something
http://jsfiddle.net/yb703y0p/2/
function f(n){
c = ["  __  A", "_/  \\_A", "o    oA"]
for(i=0;i<3;i++)c[i]=c[i].replace('A',' '.repeat(n))+c[i].replace('A','')
if(n==0)c[1]=c[1].replace('__','/\\')
console.log(c.join("\n"))
}

PHP 7, 140 bytes
<?$s=$argv[1];$r=($f=str_repeat)(~ß,60-3*$s);echo$l=$f(~ß,min(20,$s)),"  __  $r  __
${l}_/  \\",$r?_.$r._:~Ð£,"/  \_
$l",$o=~ßßßß,$r,$o;

Usage:
Save as ANSI in file.php (there should be zero-width characters in $o) and run:
php -derror_reporting=~E_NOTICE -dshort_open_tag=1 file.php x

with x as the number of seconds.
And a version that works without changing the error reporting (148 bytes):
<?$s=$argv[1];$r=($f=@str_repeat)(' ',60-3*$s);echo$l=$f(' ',min(20,$s)),"  __  $r  __
${l}_/  \\",$r?"_${r}_":"/\\","/  \_
$l",$o="o    o",$r,$o;


text:
A backwards relationship
Write a program or function that, given two ASCII strings A and B, will produce strings A' and B' where the common substrings are reversed in their place. The process for finding A' is as follows:

A' is initially empty.
If the first character of A is in B, find the longest prefix of A which is a substring of B. Remove this prefix from A and add its reversal to A'.
Otherwise, remove this first character from A and add it to A'.
Repeat steps 2-3 until A is empty.

Finding B' is done similarly.
Example
Let's consider the strings A = "abc bab" and B = "abdabc". For A', this is what happens:

A = "abc bab": The first character "a" is in B and the longest prefix of A found in B is "abc". We remove this prefix from A and add its reversal "cba" to A'.
A = " bab": The first character " " is not in B, so we remove this character from A and add it to A'.
A = "bab": The first character "b" is in B and the longest prefix of A found in B is "b". We remove this prefix from A and add its reversal (which is still "b") to A'.
A = "ab": The first character "a" is in B and the longest prefix of A found in B is "ab". We remove this prefix from A and add its reversal "ba" to A'.
A = "": A is empty, so we stop.

Thus we get A' = "cba" + " " + "b" + "ba" = "cba bba". For B', the process is similar:
B = "abdabc"  ->  "a" in A, remove prefix "ab"
B = "dabc"    ->  "d" not in A, remove "d"
B = "abc"     ->  "a" in A, remove prefix "abc"

Thus we get B' = "ba" + "d" + "cba" = "badcba".
Finally, we return the two strings, i.e.
(A', B') = ("cba bba", "badcba")

Test cases
"abc bab", "abdabc" -> "cba bba", "badcba"
"abcde", "abcd bcde" -> "dcbae", "dcba edcb"
"hello test", "test banana" -> "hello tset", "tset banana"
"birds flying high", "whistling high nerds" -> "bisdr flyhgih gni", "wihstlhgih gni nesdr"

Shortest code in bytes wins.

Do we presume all input is lowercase ASCII? Is the exact output expected to be akin to "cba bba", "badcba" including quotes and comma?

@TimmyD The exact input/output format is your choice. You may not presume the input is lowercase ASCII - it could be any printable ASCII.

Is the empty string a legal input?

@MtnViewMark Yes.

Pyth, 29 bytes
M&G+_Je|f}TH._GhGg.-GJHgzQgQz

Test Harness.
Input format is:
abc bab
"abdabc"

Output is:
cba bba
badcba

Haskell, 120 111 bytes
import Data.List
a&b=(a#b,b#a)
[]#_=[]
(a:y)#b=[a]%y where p%(i:w)|reverse(i:p)`isInfixOf`b=(i:p)%w;p%x=p++x#b

Test runs:
λ: "abc bab"&"abdabc"
("cba bba","badcba")

λ: "abcde"&"abcd bcde"
("dcbae","dcba edcb")

λ: "hello test"&"test banana"
("hello tset","tset banana")

λ: "birds flying high"&"whistling high nerds"
("bisdr flyhgih gni","wihstlhgih gni nesdr")

SWI-Prolog, 312 bytes
a(A,B,X,Y):-b(A,B,"",X),b(B,A,"",Y).
b(A,B,R,Z):-A="",R=Z;sub_string(A,0,1,_,C),(sub_string(B,_,1,_,C),(string_length(A,J),I is J-1,between(0,I,K),L is J-K,sub_string(A,0,L,_,S),sub_string(B,_,L,_,S),string_codes(S,E),reverse(E,F),string_codes(Y,F));S=C,Y=C),string_concat(S,V,A),string_concat(R,Y,X),b(V,B,X,Z).

Example: a("birds flying high","whistling high nerds",X,Y). outputs
X = "bisdr flyhgih gni",
Y = "wihstlhgih gni nesdr" .

A way, way too long solution that goes too show how verbose Prolog is when dealing with strings. It might be possible to shorten this thing using codes arrays (`birds flying high`) instead of strings ("birds flying high").

Python 2.7, 169 156 152 141 Bytes
m=lambda A,B:(b(A,B),b(B,A))
def b(A,B,C=''):
 while A:j=next((j for j in range(len(A),0,-1)if A[:j]in B),1);C+=A[:j][::-1];A=A[j:]
 return C

The function m takes the 2 strings as input.It calls the b function twice which does the actual processing according to the specs.
Demo here.
Testing it -

l=[("abc bab", "abdabc"),
("abcde", "abcd bcde"),
("hello test", "test banana"),
("birds flying high", "whistling high nerds")]
for e in l:
    print m(*e)

OUTPUTS:
('cba bba', 'badcba')
('dcbae', 'dcba edcb')
('hello tset', 'tset banana')
('bisdr flyhgih gni', 'wihstlhgih gni nesdr')

PS: Thanks to orlp for the solution using next()

m=lambda A,B:(b(A,B),b(B,A))

Also you can replace while len(A)>0 with just while A. Similarly if len(p)>0 becomes if p.

if len(p) can also be if p. (Already said above, but you missed it.)

@mbomb007 Didn't read it properly. Just replaced len(p)>0 to len(p). Thanks for that :)

Even shorter: while A:j=next((j for j in range(len(A),0,-1)if A[:j]in B),1);C+=A[:j][::-1];A=A[j:].

@orlp Nice. Didn't know about much about generator expressions and next() function. Thanks for that :)

source: Stack Exchange

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

sort: votes


text:
Enumerate valid Brainf**k programs
Golunar/Unary is a way to encode all valid Brainfuck programs, but it is not an enumeration, since most natural numbers do not correspond to a valid program.
For the purpose of this challenge, assume a doubly infinite tape and no comments, i.e., a Brainfuck program is valid if and only if it consists solely of the characters <>+-.,[] and all left and right brackets match.
For example, the empty program, ,[+][-]., [>+<[--].] and +[+[+][+[+]+]+]+. are valid Brainfuck programs, while ][, and a[] are not.
Task
Write a program or function that accepts a valid Brainfuck program as input and returns a natural number (1, 2, 3, …), with the following constraints:

The generated output must be different for all valid Brainfuck programs.

For every natural number n, there must be a valid Brainfuck program that, when provided as input, generates the output n.

Additional rules

Given a Brainfuck program of 100 or less bytes, your program or function must finish within one minute.
This means that you cannot iterate over all valid Brainfuck programs until you match the input.

Standard code-golf rules apply.

I was thinking to just encode it as octal but the matching brackets are making this tricky.

Is the empty program a valid Brainfuck program? Must it be mapped to a natural integer as well?

Why the close vote? This is a fascinating question and the problem happens to have the size and variety for a great golf.

@orlp Yes, the empty program satisfies the above definition

Still waiting to see an answer written in Brainfuck...

Python 3, 443 158 155 154 134 131 128 124 117 116 115 bytes
c=d=C=D=0
for e in input():v='[<>,.-+]'.find(e);d=d*8+v;c+=c<0<6<v;c-=d>1>v;C,D=(c,C+1,d,D)[v>6::2]
print(-~D*8**C)

Several bytes thanks to Sp3000 and Mitch Schwartz :D
How this works:
This maps all valid BF programs into all possible, valid or invalid, BF programs, that don't start with a [, in a one-to-one ratio. After that, the new program is simply converted into octal.
Here is the mapping formula:

Separate a BF program into 3 parts. The first part is the largest prefix consisting of only [ characters. The third part is the largest postfix consisting of only ] characters. The second part is the middle.
Dispose of the first part. These can be recomputed later.
Remove all ] brackets in the third part that match [ brackets in the second part. These can also be recomputed later.
Concatenate the second and third parts together.

If you don't understand this explanation, you can find an extended explanation in chat starting here.
For reference, here are the first 20 programs:
1 :
2 : <
3 : >
4 : ,
5 : .
6 : -
7 : +
8 : []
9 : <[]
10 : <<
11 : <>
12 : <,
13 : <.
14 : <-
15 : <+
16 : [<]
17 : >[]
18 : ><
19 : >>
20 : >,

Here are the first 1000 programs: http://pastebin.com/qykBWhmD
Here is the program I used to generate them: http://ideone.com/e8oTVl
Here is Hello, World!:
>>> ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
457711481836430915510337664562435564418569135809989841510260388418118348571803953323858180392373

Minor quibble: You cannot map a program to 0.

@Dennis Does an empty program count as a program though?

@BetaDecay Yes: http://codegolf.stackexchange.com/questions/55363/enumerate-valid-brainfk-programs/55368?noredirect=1#comment134529_55363

@Dennis I'll fix that when I golf it.

Your reference output is wrong. When I run >. I get 20. When I run >, I get 19.

This is ingenious

@isaacg Sorry, those reference outputs were handmade and untested. The new ones are computer generated.

Python 2, 157 bytes
def f(s,o=0,d=0,D={}):T=s,o,d;x=D[T]=D[T]if T in D else~o and 0**o+sum(f(s[1:],cmp(c,"[")%-3-~o,d or cmp(c,s[0]))for c in"+,-.<>[]")if s else~d<0==o;return+x

Still looks pretty golfable, but I'm posting this for now. It uses recursion with a bit of caching. Annoyingly, D.get doesn't short circuit for the caching, so I can't save 9 bytes that way...
The mapping prioritises length first, then lexicographical order over the ordering "][><.-,+" (see output examples below). The main idea is to compare prefixes.
The variable o keeps track of the number of [ brackets still open for the current prefix, while the variable d takes one of three values indicating:

d = 1:  The current prefix is lexicographically earlier than s. Add all programs with this prefix and length <= s,
d = -1: The current prefix is lexicographically later than s. Add all programs with this prefix and length < s.
d = 0: The current prefix is a prefix of s, so we might change d to 1 or -1 later.

For example, if we have s = "[-]" and our current prefix is p = "+", since p is later than s lexicographically we know only to add the programs starting with p which are strictly shorter than s.
To give a more detailed example, suppose we have an input program s = "-[]". The first recursive expansion does this:
  (o == 0)               # Adds a program shorter than s if it's valid
                         # For the first expansion, this is 1 for the empty program
+ f(s[1:], o=-1, d=1)    # ']', o goes down by one due to closing bracket
+ f(s[1:], o=1, d=1)     # '[', o goes up by one due to opening bracket
+ f(s[1:], o=0, d=1)     # '>'
+ f(s[1:], o=0, d=1)     # '<'
+ f(s[1:], o=0, d=1)     # '.', d is set to 1 for this and the previous branches
                         # since they are lexicographically earlier than s's first char
+ f(s[1:], o=0, d=0)     # '-', d is still 0 since this is equal to s's first char
+ f(s[1:], o=0, d=-1)    # ',', d is set to -1 for this and the later branches
                         # since they are lexicographically later than s's first char
+ f(s[1:], o=0, d=-1)    # '+'

Note how we don't actually use the prefixes in the recursion - all we care about them is captured through the variables d, o and the shrinking input program s. You'll notice a lot of repetition above - this is where caching comes in, allowing us to process 100-char programs well within the time limit.
When s is empty, we look at (d>=0 and o==0), which decides whether to return 1 (count this program because it's lexicographically early/equal and the program is valid), or 0 (don't count this program).
Any situtation with o < 0 immediately returns 0, since any programs with this prefix have more ]s than [, and are thus invalid.

The first 20 outputs are:
 1
> 2
< 3
. 4
- 5
, 6
+ 7
[] 8
>> 9
>< 10
>. 11
>- 12
>, 13
>+ 14
<> 15
<< 16
<. 17
<- 18
<, 19
<+ 20

Using the same Hello World example as @TheNumberOne's answer:
>>> f("++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.")
3465145076881283052460228065290888888678172704871007535700516169748342312215139431629577335423L

This answer is a formal proof for the answer by TheNumberOne, Enumerate valid Brainf**k programs, where it can be a bit hard to understand the fine points why the enumeration is correct. It's nontrivial to understand why there isn't some invalid program that maps to a number not covered by a valid program.
Throughout this answer capitals are used to denote programs, and lowercase variables are used for functions and integers. ~ is the concatenation operator.
Proposition 1:
Let the function f be the program described in that answer. Then for every program U there exists a valid program V such that f(U) = f(V)
Definition 1:
Let g(X) be the number of [ that appear in the program X, and let h(X) be the number of ] that appear.
Definition 2:
Define P(x) to be this function:
P(x) = "" (the empty program) when x <= 0
P(x) = "]" when x = 1
P(x) = "]]" when x = 2
etcetera

Definition 3:
Given a program X, denote X1 to be it's largest prefix of [ characters, X2 its center, and X3 its largest suffix of ] characters.
Proof of proposition 1:
If g(U) = h(U) then U is a valid program, and we can take V=U. (trivial case).
If g(U) < h(U) then we can create V by prepending n = h(U) - g(U) [ symbols. Obviously f(V) = f(U) as all [ symbols in the prefix are removed.
Now consider g(U) > h(U). Define T = U2 ~ U3. if g(T) <= h(T), then we can construct V by removing n = g(U) - h(U) [ symbols.
So we can assume that h(T) < g(T). Construct V = T ~ P(g(T) - h(T)).
We need three small facts to proceed:
Claim 1: g(U2) = g(T)
U3 does not contain any [ symbols by its definition. As T = U2 ~ U3, its [ symbols are all in the first part.
Claim 2: h(U3) < g(T)
This follows from noting that h(T) < g(T) and h(U3) < h(U3 ~ U2) = h(T).
Claim 3: h(V3) = g(U2) - h(U2)
h(V3) = h(U3) + g(T) - h(T)                           using the construction of V
h(V3) = h(U3) + g(U2) + g(U3) - h(U2) - h(U3)         apply the definition of T
h(V3) = g(U2) - h(U2) *one term cancels, g(U3)        is always zero, as U3 contains only `]` symbols*

Now we show that f(V) = f(U).
f(U) = U2 ~ P(h(U3) - g(U2)) = U2                     claim 2, definition of P

f(V) = U2 ~ P(h(V3) - g(V2))
     = U2 ~ P(h(V3) - g(U2))
     = U2 ~ P(g(U2) - h(U2) - g(U2))                  claim 3
     = U2 ~ P(-h(U2))
     = U2                                             definition P

This completes the proof. Q.E.D.
Let's do uniqueness as well.
Proposition 2:
Let U, V be two diffrent, valid programs. Then f(U) != f(V)
This is fairly straightforward compared to the previous proposition.
Let's assume that U2 = V2. But then the only way U and V can be diffrent is by adding or removing n [ and ] symbols to U1 and U3 respectively. Yet this changes the output of f, since f will count the number of unmatched ] symbols in the suffix.
Thus U2 != V2.
Obviously, this leads to a contradiction. As U2 and V2 are literally contained in the output of f(U) and f(V) respectively, they cannot differ, except at the 'edge', the place where U2 is concatenated with U3. But the first and last symbols of U2 and V2 cannot be [ or ] by definition, while those are the only symbols allowed in U1, U3, V1, V3 respectively and respectively again. Thus we get U2 = V2.  Q.E.D.

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

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


text:
Convert Brainfuck to MarioLANG
MarioLANG is a two-dimensional programming language where the source code resembles a Super Mario Bros. level. Furthermore, its instruction set is very similar to Brainfuck's. This means that MarioLANG is essentially a 2-D Brainfuck where the instruction pointer moves like Mario. So when I wrote my MarioLANG submission for the Programming Language Quiz, I started by converting a Brainfuck "Hello, World!" program to MarioLANG. I noticed that this is possible with a very systematic process, so let's write a Brainfuck-to-MarioLANG compiler!
Note: The MarioLANG spec isn't entirely unambiguous, so I'm assuming the interpretation of the Ruby implementation.
I'll explain the process with the following Brainfuck program:
++[>+++++[>+++++++>++++++++++>+++>+<<<<-]<-]>>++.>+.+++++++..+++.>+++.>.

It prints Hello! and a trailing newline.

Convert < and > to ( and ), respectively:
++[)+++++[)+++++++)++++++++++)+++)+((((-](-]))++.)+.+++++++..+++.)+++.).

Add a floor for Mario to walk on:
++[)+++++[)+++++++)++++++++++)+++)+((((-](-]))++.)+.+++++++..+++.)+++.).
========================================================================

Now the issue is that MarioLANG doesn't have loops like [ and ]. Instead, we have to use elevators and directional instructions to make Mario actually walk in a loop. First, we replace [ with > and change the floor to ". And we also replace ] with [! and change the floor to =#:
++>)+++++>)+++++++)++++++++++)+++)+((((-[!(-[!))++.)+.+++++++..+++.)+++.).
=="======"===============================#===#============================

The " and # can form elevators (starting from #, ending at "), so now all we need are auxiliary floors for Mario to walk back on. The start with ! and end with <:
++>)+++++>)+++++++)++++++++++)+++)+((((-[!(-[!))++.)+.+++++++..+++.)+++.).
=="======"===============================#===#============================
         !                               <
         #==============================="
  !                                          <
  #=========================================="

Note that all lines must be at least as long as the largest enclosing loop, because the interpreter isn't able to connect elevator ends across shorter lines. Therefore, we pad the middle lines with spaces.

And that's it. We've got a fully functional, equivalent MarioLANG program.
The Challenge
Given a valid Brainfuck program, implement the above procedure to compile it into a MarioLANG program.
You may assume that there are only command characters in the input, i.e. no characters except ,.+-<>[].
All auxiliary floor must be as close as possible to the main program floor. You may choose to pad the lines of intermediate floors either as little as possible (up to the width of the largest enclosing loop) or to the end of the main program.
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter. If you don't print the result to STDOUT, it should still be a single newline-separated string.
This is code golf, so the shortest answer (in bytes) wins.
Test Cases
The test cases are formatted as follows: the first line is the Brainfuck program (your input), then there's an empty line, and everything until the next empty line is the expected output in MarioLANG. These examples use the minimal amount of padded spaces. Alternatively, you may pad each line with spaces to the width of the first line of the output.
>,++-.<

),++-.(
=======

,[.,]

,>.,[!
="===#
 !   <
 #==="

>>[-]<<[->>+<<]

))>-[!((>-))+(([!
=="==#=="=======#
  !  <  !       <
  #=="  #======="

++[>+++++[>+++++++>++++++++++>+++>+<<<<-]<-]>>++.>+.+++++++..+++.>+++.>.

++>)+++++>)+++++++)++++++++++)+++)+((((-[!(-[!))++.)+.+++++++..+++.)+++.).
=="======"===============================#===#============================
         !                               <
         #==============================="
  !                                          <
  #=========================================="

[][[[][[]]][]][[]]

>[!>>>[!>>[![![!>[![!>>[![!
"=#"""=#""=#=#=#"=#=#""=#=#
! <  ! < ! <    ! <   ! <
#="  #=" #="    #="   #="
        !    <       !    <
        #===="       #===="
    !          <
    #=========="
   !                <
   #================"

>>+++++++>>++>>++++>>+++++++>>+>>++++>>+>>+++>>+>>+++++>>+>>++>>+>>++++++>>++>>++++>>+++++++>>+>>+++++>>++>>+>>+>>++++>>+++++++>>+>>+++++>>+>>+>>+>>++++>>+++++++>>+>>+++++>>++++++++++++++>>+>>+>>++++>>+++++++>>+>>+++++>>++>>+>>+>>++++>>+++++++>>+>>+++++>>+++++++++++++++++++++++++++++>>+>>+>>++++>>+++++++>>+>>+++++>>++>>+>>+>>+++++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>+>>++>>+>>++++++>>++>>++++>>+++++++>>+>>+++++>>+++++++>>+>>+++++>>+>>+>>+>>++++>>+>>++>>+>>++++++>>+>>+++++>>+++++++>>+>>++++>>+>>+>>++>>+++++>>+>>+++>>+>>++++>>+>>++>>+>>++++++>>+>>+++++>>+++++++++++++++++++>>++>>++>>+++>>++>>+>>++>>++++>>+++++++>>++>>+++++>>++++++++++>>+>>++>>++++>>+>>++>>+>>++++++>>++++++>>+>>+>>+++++>>+>>++++++>>++>>+++++>>+++++++>>++>>++++>>+>>++++++[<<]>>[>++++++[-<<++++++++++>>]<<++..------------------->[-<.>>+<]>[-<+>]>]<<[-[-[-[-[-[-[>++>]<+++++++++++++++++++++++++++++>]<++>]<++++++++++++++>]<+>]<++>]<<[->.<]<<]

))+++++++))++))++++))+++++++))+))++++))+))+++))+))+++++))+))++))+))++++++))++))++++))+++++++))+))+++++))++))+))+))++++))+++++++))+))+++++))+))+))+))++++))+++++++))+))+++++))++++++++++++++))+))+))++++))+++++++))+))+++++))++))+))+))++++))+++++++))+))+++++))+++++++++++++++++++++++++++++))+))+))++++))+++++++))+))+++++))++))+))+))+++++))+))++++++))+))++))+))++++++))+))++))+))++++++))+))++))+))++++++))+))++))+))++++++))+))++))+))++++++))+))++))+))++++++))++))++++))+++++++))+))+++++))+++++++))+))+++++))+))+))+))++++))+))++))+))++++++))+))+++++))+++++++))+))++++))+))+))++))+++++))+))+++))+))++++))+))++))+))++++++))+))+++++))+++++++++++++++++++))++))++))+++))++))+))++))++++))+++++++))++))+++++))++++++++++))+))++))++++))+))++))+))++++++))++++++))+))+))+++++))+))++++++))++))+++++))+++++++))++))++++))+))++++++>(([!))>)++++++>-((++++++++++))[!((++..-------------------)>-(.))+([!)>-(+)[!)[!((>->->->->->->)++)[!(+++++++++++++++++++++++++++++)[!(++)[!(++++++++++++++)[!(+)[!(++)[!((>-).([!(([!
========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================="===#=="======="================#=========================="========#="=====#==#=="="="="="="="=====#================================#=====#=================#====#=====#=="=====#===#
                                                                                !   <          !                <                          !        < !     <                 !     <                                                                      !     <
                                                                                #==="          #================"                          #========" #====="                 #====="                                                                      #====="
                                                                                !                                                                       <            !                                        <
                                                                                #======================================================================="            #========================================"
                                                                                !                                                <
                                                                                #================================================"
                                                                                !                                                                    <
                                                                                #===================================================================="
                                                                                !                                                                           <
                                                                                #==========================================================================="
                                                                                !                                                                                <
                                                                                #==================================================================================="
                                                                                !                                                                                <
                                                                                #=================================================================================================="

CJam, 148 144 bytes
q"<>[""()>"er']/"[!"*_">!"1$|"\"#=":Cer:FF,[{SF,*L{'=t}/FI>(C#"['=-{_'##}{_CW</s}w],2*(:M'#tM('!tLM+ ;LW=34ctLW=('<tLW< ;L"S/=~:L;}fI]z~]{S-},N*

Try it online in the CJam interpreter.

Python, 707 chars
def b(c):
 c,l,o,x,j,m=list(c.replace(">",")").replace("<","(")),[list("="*len(c))],[],[],0,0
 for i,z in enumerate(c):
  i+=j
  if"["==z:
   c[i],l[0][i]=">",'"'
   x.append(i)
  if"]"==z:
   c[i],l[0][i]="[!","=#"
   c,l[0],m,d,b=list("".join(c)),list("".join(l[0])),max(m,len(x)),0,x.pop()
   for a in o:d+=b<a[0]and-~i>a[0]or b<a[1]and-~i>a[1]
   o.append((b,i+1,d))
   j+=1
 for q in o:
  d=q[2]*2+1
  while len(l)<=d+1:l.append(list(" "*len(c)))
  l[d][q[0]],l[d+1][q[0]],l[d][q[1]],l[d+1][q[1]]="!","#","<",'"'
  for i in range(q[0]+1,q[1]):l[d+1][i]="="
 g="\n".join(l.rstrip()for l in("".join(c)+"\n"+"\n".join("".join(f)for f in l)).split("\n"))
 while"\n\n"in g:g=g.replace("\n\n","\n")
 return g

There's probably a lot of space to be golfed. Doesn't work for the last test case.
Example usage:
>>> print b("++[>+++<-]>[<+++>-]<.")
=="=======#="=======#==
  !       < !       <
  #=======" #======="

No lines in the output contains trailing spaces.

If it doesn't work, it's not a solution (imo).


text:
Golfing strings in Fourier
Challenge
Given a string as input, golf down the Fourier program which outputs that string.
In Fourier there is no easy way to output a string: you have to go through each character code and output that as a character.
Fourier
The language is based upon an accumulator, a global variable which is initialised to 0 at the start of the program. This is used by almost every operator in the language. Only some do not change the value of the accumulator.
Character out
a

Takes the value of the accumulator as the ASCII code and outputs the character. Does not change the value of the accumulator.
If the accumulator is greater than 255, the program will return an error. Likewise if the accumulator is less than 0.
Number out
o

Outputs the value of the accumulator. Does not change the value of the accumulator.
Increase
^

Increase the accumulator by one.
Decrease
v

Decrease the accumulator by one.
Add
+x

Sets the accumulator to the value of the accumulator plus the value of x.
Subtract
-x

Sets the accumulator to the value of the accumulator minus the value of x.
Multiply
*x

Sets the accumulator to the value of the accumulator multiplied by the value of x.
Divide
/x

Sets the accumulator to the value of the accumulator divided by the value of x. (Note that this is integer division, so 1/6 results in 0)
Number
n

Set the accumulator to the integer n.
Note
Here, x and n can be any integer from 0 to 2^32-1 inclusive.
More information
You must only use the operators described above. Therefore your outputted Fourier program is invalid if it uses any of the following (note that the following operators are allowed for the bounty):

Repeat loops
If statements
Variables
Random
Modulo
User Input
Greater/Less than operators
Equality operators
Clear screen
Time delay
Date functions

Your program can either be a full program or a function, taking in input via STDIN, a file or function arguments. You may also take input straight from the Internet.
Note that if there is a vv in your code, you should replace it with -2. The same goes for ^^, replacing it with +2.
Examples
If the input is 7n, then the expected program is:
55a110a

But you can save one byte with
55a*2a

Another way is
7o110a

Using number out.

Similarly if the input is Hello, then the expected program is:
72a101a108a108a111a

You can golf it down by 3 bytes (because outputting doesn't change the accumulator):
72a101a108aa111a

But wait, we can use the addition operator, saving 2 bytes:
72a101a+7aa+3a

Formatting
Because I'll be using Martin Büttner's Stack Snippet leaderboard, please could you format the title like so:
# <Language name>, <length of total output> bytes

Then, you can put anything you wish below the title.
Winning
You should post the length of Fourier programs (produced by your code) to output this text file and this text file. Your score is the combined length of both Fourier programs in bytes (non-ASCII characters aren't used in Fourier so it doesn't really make a difference).
The person with the lowest scores wins. If there is a tie, the shortest program in bytes wins.
Bounty
This 500 rep bounty is for a new answer which golfs the strings using any of Fourier's functions. That includes variables, loops and if statements etc. This new answer will not be accepted.
Leaderboard
Refer to formatting section above:

var QUESTION_ID=55384;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

I don't think having to output all optimal solutions is very fair/interesting. It rules out all implementations except brute force...

The real problem with having to output all optimal solutions is that for a long input, there will be more optimal solutions then there are atoms in the universe.

@orlp Edited out outputting all optimal solutions

Should it only be printable ASCII, or any sort of ASCII? And only 7-bit ASCII, or full bytes?

@orlp You mean for output or in the source code?

Does the accumulator start at 0?

@ASCIIThenANSI Yes, it does.

How does a behave if the accumulator is > 255?

Is the accumulator bound to the same limits as x and n, and if it overflows, does it wrap?  Likewise, if my accumulator is greater than 256 (or 128 per orlp's question), does it throw an exception, output multiple ascii values (which would greatly change this problem), or output acc % 256 (or acc % 128)

@Mauris From the Fourier interpreter: elif code[position] == "a": print(chr(accumulator), end=""); position += 1. It does not wrap.

@Foon refer to my comment above.

@Mauris It will fail, as the interpreter does

@BetaDecay I mean for the string that we're supposed to generate. Is the input string only 7-bit printable ASCII?

@orlp Nope. It is any character in the range 0 to 255

Python, 14307118 bytes
601216 for Hamlet + 13705902 for Genesis = 14307118
There are definitely some senarios under which this solution is not optimal, such as for 1111, where it will output 1111o as opposed to 11oo. However, I think it is nearly optimal.
Edit: Saved a few bytes by improving 0o0o to 0oo.
The name of the file containing the input is received on STDIN, output to STDOUT.
Results verified with the official interpreter.
def opt_str(char, acc):
    opts = []
    char_num = ord(char)
    opts.append(str(char_num))
    if 0 < char_num - acc < 10:
        opts.append('+' + str(char_num - acc))
    if 0 < acc - char_num < 10:
        opts.append('-' + str(acc - char_num))
    if char_num - acc == 1:
        opts.append('^')
    if acc - char_num == 1:
        opts.append('v')
    if acc == char_num:
        opts.append('')
    if acc and char_num % acc == 0:
        opts.append('*' + str(char_num//acc))
    try:
        if acc // (acc // char_num) == char_num:
            opts.append('/' + str(acc // char_num))
    except:
        pass
    return [opt for opt in opts if len(opt) == len(min(opts, key=len))]

acc = 0
result = []
pos = 0
with open(input(), "r") as myfile:
        in_str = myfile.read()
while pos < len(in_str):
    i = in_str[pos]
    pos += 1
    if i in '0123456789':
        if i != '0':
            while pos < len(in_str) and in_str[pos] in '0123456789':
                i += in_str[pos]
                pos += 1
        if i == str(acc):
            result.append('o')
        else:
            result.append(i + 'o')
        acc = int(i)
    else:
        opts = opt_str(i, acc)
        result.append(opts[0] + 'a')
        acc = ord(i)
print(''.join(result))

@Shebang Well, I'm pretty sure Geobit's result is wrong, see my comments there.

There was very little in it, but you won by a mere 5 characters (you and Razvan tied so I used your code length as the tiebreaker)

@BetaDecay I've never seen the length tiebreaker be relevant between a pair of ungolfed programs before.

Yeah... Me neither :P

><>, 14310665 bytes
601398 for hamlet + 13709267 for genesis
This is still a work in progress and takes a lot of time to complete.
v
0
>i:0(?;:r-:?!v:0a-)?v     v
  >~:v       ~      >:a(?v>
 :1+?v~'v'o  v      o'^'~\:0)?v
     >n      vno'+'      ^?=1:<
^        o'a'<

That's crazy small, shame it's not optimal though.

I'm working on using /, * and o, but it's starting to take some more place.

That's okay, fish normally grow with each telling of the story ;)

Well, this is a brilliant choice of language :D

Your program didn't fit the criteria for the bounty (none of the posted answers did), so I have awarded this to you because I love that you used <><.

Wow, you increased my rep by half, thanks a lot ! What was that bounty about? I'm thinking about updating this answer to make it (at least a little bit more) optimal, maybe I could implement the bounty as well.

Java, 14307140 bytes
Hamlet - 601,218
Genesis - 13,705,922
The idea here is to do all the work upfront, by making a character->character map. Then you can just loop through and grab the shortest strings.
A bit of an exception has to be made for numerals, so I check for them in the main loop. It's still fast, though, and handles the larger test case in a few seconds. I may be able to tweak this section for a couple more bytes, but I'm fairly sure it's close to optimum.
Input is a filename as argument. Output is written to a file inputFilename_out.4, and the character count is sent to STDOUT.
This is 1737 bytes for the tiebreaker, completely ungolfed. I can golf it a lot if needed, but it's still going to be a bit big.
import java.nio.file.Files;
import java.nio.file.OpenOption;
import java.nio.file.Paths;
import java.text.NumberFormat;

public class FourierMapper {
    public static void main(String[] args) throws Exception {
        FourierMapper fm = new FourierMapper();
        fm.createMap();
        String filename = args.length>0? args[0]:"bible.txt";
        String out = fm.fourierize(filename);
        System.out.println(out.length());
        Files.write(Paths.get(filename + "_out.4"), out.getBytes(), new OpenOption[]{});
    }

    String[][] map = new String[9999][256];
    void createMap(){
        for(int from=0;from<9999;from++){
            for(int to=0;to<256;to++){
                if(to<10||from<1){
                    map[from][to] = ""+to;
                } else if(to==from){
                    map[from][to] = "";
                } else if(to-from==1){
                    map[from][to] = "^";
                } else if(to-from==-1){
                    map[from][to] = "v";
                } else if(to>99){
                    if(to%from<1){
                        map[from][to] = "*"+(to/from);
                    } else if(to>from&&to-from<10){
                        map[from][to] = "+"+(to-from);
                    } else if(from>to&&from-to<10){
                        map[from][to] = "-"+(from-to);
                    } else {
                        map[from][to] = ""+to;
                    }
                } else {
                    map[from][to] = ""+to;
                }
            }
        }
    }

    String fourierize(String filename) throws Exception{
        StringBuilder out = new StringBuilder();
        byte[] in = Files.readAllBytes(Paths.get(filename));
        String whole = new String(in);
        out.append(in[0] + "a");
        int number = -1;
        for(int i=1;i<in.length;){
            if(in[i]<58&&in[i]>47){
                number = in[i]==48?0:((Number)NumberFormat.getInstance().parse(whole.substring(i,i+4))).intValue();
                out.append(""+number+"o");
                i += (""+number).length();
            } else {
                if(number<0)
                    out.append(map[in[i-1]][in[i]]+"a");
                else
                    out.append(map[number][in[i]]+"a");
                number = -1;
                i++;
            }
        }
        return out.toString();
    }

}

I think this doesn't handle strings of digits with leading zeroes correctly. For instance, on the input 01, I believe it outputs 01o, which is not correct.

Also, I think you're misusing the accumulator. In the else clause of the main loop, you choose between using the actual value of the accumulator and the character value of the previous character. You cannot make the latter choice if the two are different, because that means you used o the time before, and the accumulator does not contain the previous character's value.

Right, both should be fixed now. Thanks!

When I run this on my machinge, I get 625474 for Hamlet and 13705922 for Genesis.

@isaacg Are you running it on the same file (with same line endings)? I ran into a problem with line endings earlier. When I run mine and yours on the same file, they both show the posted scores.

When I run your answer on Genesis, I get 13705922, no trailing newline, no linebreak issues. Moreover, when I diff it against my answer, it's character for character identical, except for a stylistic 100a vs. *10a where the previous accumulator was 10.

@isaacg I don't know what the issue you're seeing is then. Here's the output it gives me, saved straight to a file with size 13705921 in both the text editor and file->properties dialog.

Let us continue this discussion in chat.

PHP, 14307118 bytes
601,216 (Hamlet) + 13,705,902 (Bible)
function f($file) {
    $text = file_get_contents($file);

    $a = 0;

    for ($i = 0; $i < strlen($text); $i++) {
        $chr = $text[$i];

        if (ctype_digit($chr)) {
            while ($chr && isset($text[$i + 1]) && ctype_digit($text[$i + 1])) {
                $chr .= $text[$i + 1];
                $i++;
            }

            if ($a == (int)$chr) {
                print "o";
            }
            else {
                $a = (int)$chr;
                print $chr . "o";
            }

            continue;
        }

        $ord = ord($chr);

        $mapping = array(
            '' => $a,
            '^' => $a + 1,
            'v' => $a - 1
        );

        for ($j = 2; $j <= 9; $j++) {
            $mapping["+$j"] = $a + $j;
            $mapping["-$j"] = $a - $j;
            $mapping["*$j"] = $a * $j;
            $mapping["/$j"] = $a / $j;
        }

        foreach ($mapping as $op => $value) {
            if ($value === $ord) {
                $a = $value;
                print $op . "a";
                continue 2;
            }
            else if ($value . '' === $chr) {
                $a = $value;
                print $op . "o";
                continue 2;
            }
        }

        $a = $ord;
        print $ord . "a";
    }
}

Fourier output for Hamlet
It works as follows:

Iterates over each character in the input;
If there is a sequence of non 0 leading digits it will set the accumulator to that number and output it as number. It also checks for similar digits;
Otherwise, checks if there is shorter way of outputting the current character (rather than the ASCII code + "a" symbol = 4 characters) by performing a basic operation (+-*/) on the accumulator with a number between 2 and 9; obviously, it also tries to compare/increment/decrement;


text:
Who is the rightful ruler?
Who will rule the realm?
You are given a family tree which contains: name, sex, date of birth, date of death and a list of heirs, for each family member. You may use any convenient (nested) list format to represent the tree. The following examples will use JSON. Determine who will rule the realm and in which order.
The succession rules are the following:

When a king dies the realm goes to its oldest legit male child.
If there is none it passes to the oldest legit female child.
In case the king had no heirs the realm goes to the oldest legit king's brother
If there are no male brothers the realm will go to the oldest legit king's sister
If all legit relatives are dead the realm goes to the closest bastard, applying the above rules
If no legit nor bastard relatives are alive print LINE EXTINCT

We define a legit son as one who has the same "house" name as its father.
Examples:
Input
{}
Output
LINE EXTINCT
Input
{
    "name" : "Maegor",
    "house" : "Targaryen",
    "birth" : 12,
    "death" : 48,
    "sex" : "male",
    "heirs" : []
}

Output 12-48: Maegor, LINE EXTINCT
Input
{
    "name" : "Jaehaerys",
    "house" : "Targaryen",
    "birth" : 34,
    "death" : 103,
    "sex" : "male",
    "heirs" : [
        {
        "name" : "Viserys",
        "house" : "Targaryen",
        "birth" : 77,
        "death" : 129,
        "sex" : "male",
        "heirs" : []
        }
    ]
}

Output 34-103: Jaehaerys, 103-129: Viserys, LINE EXTINCT
Input
{
        "name" : "Eddard",
        "house" : "Stark",
        "birth" : 263,
        "death" : 299,
        "sex" : "male",
        "heirs" : [
            {
            "name" : "Robb",
            "house" : "Stark",
            "birth" : 283,
            "death" : 300,
            "sex" : "male",
            "heirs" : []
            },
            {
             "name" : "Jon",
             "house" : "Snow",
             "birth" : 284,
             "death" : 384,
             "sex" : "male",
             "heirs" : []
            },
            {
             "name" : "Sansa",
             "house" : "Stark",
             "birth" : 286,
             "death" : 320,
             "sex" : "female",
             "heirs" : []
            },
            {
             "name" : "Arya",
             "house" : "Stark",
             "birth" : 289,
             "death" : 350,
             "sex" : "female",
             "heirs" : []
            },

            {
             "name" : "Brann",
             "house" : "Stark",
             "birth" : 290,
             "death" : 315,
             "sex" : "male",
             "heirs" : []
            },
            {
             "name" : "Rickon",
             "house" : "Stark",
             "birth" : 295,
             "death" : 319,
             "sex" : "male",
             "heirs" : []
            }

        ]
    }

Output: 263-299: Eddard, 299-300: Robb, 300-315: Brann, 315-319: Rickon, 319-320: Sansa, 320-350: Arya, 350-384: Jon, LINE EXTINCT
Note that the output can be formatted in any way you wish, its only requirements is that it contains the time of reign and the name of the reigning king during those years.
I've used kings from the ASOIAF as demonstrative example, however the code needs to be valid for all input.
You may assume that no twins will be born.
This is a code golf challenge, so the shortest code in bytes wins
Good luck!!!

How are "bastards" represented?

In itself they are not indicated as an attribute, one would need to check if their family name is different from the father's.

@WizardOfMenlo So is their house name their family name?

@ASCIIThenANSI yes

Also, are we allowed to use JSON processing libraries (such as Python's json module?)

@ASCIIThenANSI I think it's good, so you can abstract the problem

@WizardOfMenlo In your last example, shouldn't Arya follow Robb? I see that you put Brann after Robb, but Arya is older than Brann (as per your JSON, both are males).

No because arya is a girl (even if in the book the mistake is common)

Ok, so I guess you should correct the JSON then, right?

@Razvan I forgot to update the json sorry, I copy and pasted it too quick

Also: after Sansa shouldn't there be Arya? (because she is family and Jon is bastard). And after Brann shouldn't there be Rickon? (as he is male and is still alive). I see it like this: 263-299: Eddard, 299-300: Robb, 300-315: Brann, 315-319: Rickon, 319-320: Sansa, 320-350: Arya, 350-384: Jon, LINE EXTINCT

@Razvan you're right, my mind failed me :)

@Celeo I think it's my wording, it should be the king's brother/sister, I'll change it now (I've just checked and discovered sibling means something completely different to what I thought)

Your second example shows Maegor where I believe it should be Jaehaerys.

@Geobits you're 100% right

Does this have to work with infinite amounts of heirs? For example Robb has a son, would it go to John or Robb's son?

@SpeedyNinja yes, if Rood had a son/daughter the realm would go to the son/daughter , and if this heir had a heir of its own the realm would go down that line

@WizardOfMenlo Point 3 is a bit unclear - In case the king had no sons the realm goes to the oldest legit king's brother. It seems to conflict with point 2(If no legit son, then oldest legit daughter is crowned). Do you mean heirs instead of sons in point 3?

@kamehameha yes, I'll edit it now

What about aunts/uncles of the current ruler?

What about them?

@WizardOfMenlo Can you provide an example case where it will reach the king's brother/sister's realm?

PHP, 664 bytes
I'm not sure if 664 bytes fit for code golfing, but here it is:
$k=json_decode($argv[1]);$s=[];$f='array_shift';$r='heirs';$e='death';$y='year';function s
($k,&$e){uasort($e,function($a,$b)use($k){$c=$a->{$h='house'};$d=$b->$h;$e=$k->$h;if($c==$e
&&$d!=$e)return-1;elseif($c!=$e&&$d==$e)return 1;elseif($a->sex<$b->sex)return 1;elseif($a
->sex>$b->sex)return -1;else return$a->birth-$b->birth;});}function d(&$e,$y){foreach($e
as$i=>$h)if($h->death<=$y)unset($e[$i]);};($x=(array)$k)&&$k->$y=$k->birth;$l=[];while($x)
{$l[]=$k;$z=$k->$e;s($k,$k->$r);d($k->$r,$k->$e);if($k->$r){$s=$k->$r;$k=$f($s);}else{s($k
,$s);d($s,$k->$e);$k=$f($s);}if(!$k)break;$k->$y=$z;}foreach($l as$k)
echo"{$k->$y}-{$k->$e}: $k->name, ";echo"LINE EXTINCT";

It receives the JSON string input as the first command line argument.
The algorithm follows the steps described in the challenge (starts from the king, then sorts the heirs and then the siblings to find the next king).
Demo

That was quick!

while loop are prohibited when golfing in PHP :).

I think there is a mistake, I've tested it here and it link goes correctly down the line, however after it doesn't go back up to give Jon Snow it's rightful throne

It's not a mistake. It actually follows the rules that were defined in the challange. As you can see, the last king is Tyrion which is the son of Arya. This means that the next king should be among the heirs of Tyrion or one of his brothers. But he has no brothers, nor heirs. Please note that, as per the JSON in your example, Jon Snow is the uncle of Tyrion.

You are absolutely right, my fanboysm got the best of me

You could golf a bit if you replace fields death, sex etc. with shorter names. The OP allowed any format you like, so one could even try with a format given by the "var_export" function

Storing readable version: Try it online!

jq, 429..410 392bytes
def s(x;y):sort_by(.sex,-.birth)[]|select(.death>x.death and(.house==x.house|y));def i:index([[.[1:][]|select(.!=[])][0]]);def b(z;x;y):[.[i+z][:z+length-1]|s(x;y)];def h(x;y):[x.heirs|s(x;y)];[[],[],[],[],sort_by(-.birth)?]|until(i|not;.[i][-1]as$r|[.[0]+[$r+{t:(.[0][-1].death//$r.birth)}],h($r;.),h($r;not),b(0;$r;.),b(i%2;$r;not)])|[.[0][]|"\(.t)-\(.death):\(.name)"]+["LINE EXTINCT"]|.[]

Try it online!
Explanation:
def s(x;y):sort_by(.sex,-.birth)[]                          #Function: sorts by sex lexicographically, then by birth date in descending order [youngest female -> oldest male]
            |select(                                        and selects those who
                .death > x.death                            did not die before the previous ruler
                and (.house == x.house|y)                   and have the same house (if y := not, selects those with a different house)
            );
def i:index([[.[1:][]|select(.!=[])][0]]);                  #Function: returns index of the first not-empty array (ignoring first array)
def b(z;x;y):[.[i+z][:z+length-1]|s(x;y)];                  #Function: drops the last z (0 or 1) elements of the (i+z)th array and applies s on the resulting array
def h(x;y):[x.heirs|s(x;y)];                                #Function: takes the heirs of x and applies s

[                                                           An array containing five bins:
    [],                                                         0. Result
    [],                                                         1. Heirs from same house
    [],                                                         2. Heirs from another house
    [],                                                         3. Siblings from same house
    sort_by(-.birth)?                                           4. Siblings from another house (initial: sorted input (The ? is necessary for empty inputs))

|until(                                                     Until
        i|not                                               there is no such index i
    ;
        .[i][-1]as$r                                        set the last element of the ith array as the current ruler
        |[                                                  Update the array:
            .[0]+[$r+{t:(.[0][-1].death//$r.birth)}],       Add the current ruler + new attribute (the beginning time of reign) to the result array
            h($r;.),                                        Heirs from same house
            h($r;not),                                      Heirs from another house
            b(0;$r;.),                                      Siblings from same house
            b(i%2;$r;not)                                   If the ruler is heir from the same house as the previous one, store the heirs from a different house here
                                                            else siblings from a different house
        ]
)
|
    [
        .[0][]                                              Takes the result array
        |"\(.t)-\(.death):\(.name)"                         Writes time of reign and ruler
    ]
    +["LINE EXTINCT"]                                       Writes "LINE EXTINCT"
|.[]                                                        Prints on seperated lines

amazing! I chickened out of trying to do this since the spec was a bit wordy. very nicely done!

@Razetime thank you very much!

You can save 53 bytes by using one character names for the keys, "N": "Eddard", "H" : "Stark"...

@JohanduToit can I? It says I can choose the data format but nothing about the content or even the naming of the keys.

This part is a bit vague: You may use any convenient(nested) list format to represent the tree. I'm assuming that something like this will also be valid input TIO

@JohanduToit sounds good. Thanks for the tip! I will change it later.

JavaScript (Node.js), 294 248 244 245 bytes
t=>{for(s(t),o(t.b,t);t;)o(t.d,t=n(t,0))}
s=(r,p)=>r.c.sort((a,b)=>a.s-b.s||a.b-b.b,r.g=p?(r.u=p.h!=r.h,p.c):[]).map(h=>s(h,r))
n=(k,b,j)=>[...k.c,...k.g].map(h=>j=j||h.u==b&h.d>k.d&&h)&&j||b?j:n(k,1)
o=(f,h)=>alert(h?[f,h.d,h.n]:'LINE EXTINCT')

Try it online!
-82 bytes thanks to Shaggy!

A few quick golfs to get you down to 300 bytes

@Shaggy Thanks, I had to add +r.b else it does not sort correctly by age.

260

I think that works, at least; with so few test cases it's hard to tell.

255

248

@Shaggy, wow I should go back to golfing school :-)

PPCG is golfing school! ;)

244

nice! I was playing around with using reduce instead of sorting the arrays but did not get very far, do you think it could work?

or concatenating the siblings to the child array and sorting by bastard, relationship, sex, age.

I think this might work for sorting by all 3 criteria simultaneously.

Actually, we'd need a logical OR rather than a bitwise one. And our current sort suffers from a similar bug; a.s*a.b-b.s*b.b needs to be a.s-b.s||a.b-b.b.

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


text:
Is the pizza fair?
This question is inspired by, and is the inverse of this one.
Dennis (E), Doorknob (D), Martin (M) and Chris (C) have ordered a pizza. The rectangular pizza is divided into square pieces, each marked with their intended eater.
Write a program or function that given a rectangular pizza consisting of 0 or more of each letter determines whether:

Each slice for each person is path-connected. This means that all letters that are the same should be directly adjacent to eachother (no diagonal connections).

The number of slices per person is the same for all.

You must output a truthy/falsy value with an optional trailing newline that indicates whether or not the given pizza is fair.
Valid testcases:

DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEDMMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC
DEMC
DD
EE
MC
MC
EEDDMMMCCC
EEEDDDMMCC
Invalid testcases:
EDM
EDMCCMDE
DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEMDMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC
DDMMEECC
DMMEECCC

Shortest code in bytes wins.

What forms of input are acceptable to a function? string with newlines? array with one string for each line? 2D array of characters? All of the above?   2. I understand that output is truthy for fair, falsy for unfair, or can they be reversed?

Valid test cases: DDDDDDDDDDDDD <-- a fair pizza

@steveverrill For this challenge only a string with newlines is acceptable input. You must return truthy for fair, and falsy for unfair.

Beside newlines, only CDEM in input?

@edc65 Correct.

Pyth, 53 bytes
!f-lJs.z*4lu&G{smfqT@JY@UJ+Ld[Z1_1Klh.z_K)G]xJT)"CDEM

Demonstration
This is essentially a flood fill for each letter, followed by a check that all of the resulting sets are of the appropriate size.
To flood-fill, it starts with the upper-left-most occurence of each letter, then generates all neighbors of locations found so far, filters for locations with the right letter, and repeats until the set stops changing.

Snails, 129
Prints 1 for a fair pizza and 0 for an unfair pizza.
&
={(t\Dt\Et\Ct\M),!(t.}{(o\D)+l^D,=~u{^D=(r^D,~},~|o\E`+l^E,=~u{^E=(r^E,~},~|o\C`+l^C,=~u{^C=(r^C,~},~|o\M`+l^M,=~u{^M=(r^M,~},~

Expanded version:
&
={ (t\Dt\Et\Ct\M), !(t.)}   {
(o\D)+ l^D,=~ u{^D=(r^D,~)}, ~ |
(o\E)+ l^E,=~ u{^E=(r^E,~)}, ~ |
(o\C)+ l^C,=~ u{^C=(r^C,~)}, ~ |
(o\M)+ l^M,=~ u{^M=(r^M,~)}, ~

& means that the pattern must match at all locations on the grid. The first line checks for an equal number of each of E, D, M, C. it uses the teleport instruction t, which is a great way to make programs with factorial complexity. If an input has unequally sized slices with several units for each of the 4 mods, the program will more or less hang forever. After that, there is a check for a contiguous path to the top-left instance of whichever letter the pattern started on.

CJam, 93
qN/_z,:W;s:A,,:B_{{{_B=_@-}g}%$}:F;{a+_Af=)#{F~B\@t:B}|;}:U;W>{_W-U}/{W%},{_(U}/BFe`0f=_1<4*=

Try it online
This is ridiculously long because CJam doesn't (yet) have built-in flood-fill or union-find. I implemented union-find in the program.
Explanation:
qN/_         read input, split into lines and duplicate
z,:W;        transpose, get length (original width) and store in W
s:A          convert to string (without newlines) and store in A
,,           make an array [0..n-1] (n = pizza size)
:B_          store in B (initial structure) and duplicate (will be used in 2 loops)
{…}:F;       define function F ("Find" for multiple indices and sort)
  {…}%       for each value (x)
    {…}g     do…while
      _B=    duplicate x and get B[x]
      _@-    leave a B[x] on the stack and calculate B[x] - x
              if non-zero, repeat the loop with B[x]
  $          sort the results
{…}:U;       define function U ("Union" for 2 indices)
  a+         make an array of the 2 indices
  _Af=       get the corresponding letters from A
  )#         check if the letters are different
  {…}|       if not, execute…
    F~       call F on the array and dump the 2 results on the stack
    B\@t     join the sets - B[bigger index] = smaller index
    :B       store back in B
  ;          pop the last value (either array if indices or B)
W>           remove the first row of indices
{…}/         for each index
  _W-        duplicate and subtract W ("go up")
  U          call U to join sets if they match
{W%},        remove the first column of indices
{…}/         for each index
  _(         duplicate and decrement ("go left")
  U          call U to join sets if they match
BF           call F on B, to get the final sets and sort
e`           RLE encoding
0f=          keep only the repetition counts
_1<4*=       check if it's the first value (if any) repeated 4 times

JavaScript (ES6), 153 166
Using template strings, there is a newline that is significant and counted
Test running the snippet in FireFox.

f=z=>![...'CDEM'].some(c=>((l=p=>z[p]==c&&[-1,1,w,-w].map(o=>l(p+o),z[p]='',++k))(z.indexOf(c),h=k,k=0),~h&&h-k),w=~z.search`
`,z=[...z],k=-1)&z.join``-1

// Ungolfed
U=z=>{
  w = ~z.search`\n`
  z = [...z]
  fill = p=>(
    c = z[p],
    z[p] = '',
    [-1,1,w,-w].forEach(o=>z[o+=p] == c && fill(o)),
    ++k
  )
  h = -1
  r = ['C','D','E','M'].every( c =>(
    k = 0,
    y = z.indexOf(c),
    y >= 0 && fill(y),
    v = h >= 0 ? h == k : true,
    h = k,
    v
  ))
  return r & 1-z.join``
}

// Test
out=x=>O.innerHTML+=x+'\n';

// Valid test cases
valid=[`DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEDMMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC`,
`DEMC`,
`DD
EE
MC
MC`,
`EEDDMMMCCC
EEEDDDMMCC`];
out('Valid')
valid.forEach(t=>out(t+'\n'+f(t)+'\n'));
invalid=[`EDM`,
`EDMCCMDE`,
`DDDDDDDDDDDDDD`,
`DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEMDMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC`,
`DDMMEECC
DMMEECCC`
];
out('Invalid')
invalid.forEach(t=>out(t+'\n'+f(t)+'\n'))

Javascript ES6, 360
Checks for equal numbers of C, D, E, M, then flood fills and checks for any orphaned letters. Not a winner, but I had to try.
i=>(I=i.split`
`.map(e=>e.split``),c=(i[m='match'](/C/g)||[])[l='length'],a=(x,y,z)=>{if(I[x][y]!=z)return;I[x][y]=0;x>0&&a(x-1,y,z);x0&&a(x,y-1,z);y{if((i[m](eval(`/${k}/g`))||[])[l]!=c)return 1;I.some((w,x)=>(g=-1<(y=w.indexOf(k)),g&&a(x,y,k),g));})&&!I.map(e=>e.join``).join``[m](/[CDEM]/))

Fiddle

JavaScript ES6, 328 318 316 269 178
l=>(d=[0,0,0,0],s=[...l.split`
`.join``].map(i=>(d["EDMC".search(i)]++,i)),!l||d.every(i=>i==d[0])&&(s.every((r,i)=>[1,-1,X=l.split`
`[0].length,-X].some(o=>s[o+i]==r))||d[0]<2))

Explanation:
l => (
  d = [0,0,0,0],          // array containing each letter count
  s = [...l.split`
`.join``]                 // removes newlines from input and converts it into array
  .map(i => (             // loops through the array
    d["EDMC".search(i)]++ // increases letter count
    ,i)),                 // returns unchanged value in order to preserve original array
  !l                      // input is empty
  || d.every(i=>i==d[0])  // each letter count is equal
  && (
    s.every((r, i) =>     // there is no orphaned letters
      [1,-1,X=l.split`
`[0].length,-X]           // letters on respectively: right, left, bottom, top
      .some               // at least one of them
        (o=>s[o+i]==r))   // equals original letter
    || d[0] < 2           // count of each letter equals 1
  )
)

Interesting code (you beat mine!) Suggestion: use es6 arrow functions (as in my answer) to save a few bytes. Afaik you don't need to assign it to a variable, using a plain function declaration eg l=>{...} is fine.

Also remove the parentheses on k=(o)=> to save 2 more bytes. Single parameter arrow functions don't need parentheses.


text:
Possible Tetris sequences
Write code to figure out whether a run of Tetris pieces could be generated by the official Tetris algorithm. Fewest bytes wins.

Official Tetris games generate the sequence of falling pieces in a special way. The seven pieces IJLOSTZ are dropped in a random order, then another random permutation is dropped, and so on.
JTLOISZ STJOLIZ LISJOTZ ...

This example contains the contiguous run of pieces
SZSTJOLIZLIS

Note that it cuts across the boundaries of a group of 7. But, the run of pieces
SZOTLZSOJSIT

cannot be a substring of any Tetris sequence, so it can never be seen in an official Tetris game.

Input: A non-empty string of letters IJLOSTZ.
Output: A Truthy or Falsey value for whether the input is a substring of a sequence that can be generated by the official Tetris Random Generator, i.e. of a concatenation of permutations of the seven letters.
Test cases:
True:
T
JJ                        (unique breakdown: J J)
JTJ                     (possible breakdown: JT J)
LTOZIJS
SZSTJOLIZLIS            (possible breakdown: SZ STJOLIZ LIS)
JTLOISZSTJOLIZLISJOTZ   (possible breakdown: JTLOISZ STJOLIZ LISJOTZ)
LIJZTSLIJZTS              (unique breakdown: LIJZTS LIJZTS)

False:
SZOTLZSOJSIT
ZZZ
ZIZJLJ
ZJLJLZITSOTLISOJT
JTLOISZSTJOLIZLISJOTZLJTSZLI
IOJZSITOJZST
LIJZTSLIJZTSL

Leaderboard
Courtesy of Martin Büttner.

function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/55689/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);i=i.replace("{{PLACE}}",t++ +".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=45497;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*((?:[^,\s]|\s+[^-,\s])*)/
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	AuthorLanguageSize

Winners by Language

LanguageUserScore

{{PLACE}}	{{NAME}}{{LANGUAGE}}{{SIZE}}Link

{{LANGUAGE}}{{NAME}}{{SIZE}}Link

CJam, 23 20 16 bytes
q7{\+_7/_Lf|=},&

Credits to Sp3000 for shaving off 4 bytes!
It prints a bunch of digits as a truthy value or nothing as a falsy value (before printing these are actually a non-empty or empty list, which are indeed truthy and falsy in CJam).
Test it here.
Explanation
This just checks all 7 possible partitions of the input into chunks.
q      e# Read the input
7{     e# Select the numbers from 0 to 6 for which the following block is true.
  \+   e#   Prepend the number to the input. This shifts the string by one cell
       e#   without adding non-unique elements.
  _7/  e#   Make a copy and split into chunks of 7.
  _Lf| e#   Remove duplicates from each chunk.
  =    e#   Check if the last operation was a no-op, i.e. that there were no duplicates.
},
&      e# The stack now contains the input with [6 5 ... 1 0] prepended as well as a list
       e# of all possible splittings. We want to get rid of the former. To do this in one
       e# byte we take the set intersection of the two: since we've prepended all the
       e# integers to the list, this will always yield the list of splittings.

Pyth, 16 15 bytes
sm*F.{Mc+>Gdz7T

Prints 0 for false, a positive integer for true.

Retina, 61 55 bytes
^((.)(?<!\2.+))*((){7}((?<-4>)(.)(?!(?<-4>.)*\4\6))*)*$

Since this is just a single regex, Retina will run in Match mode and report the number of matches it found, which will be 1 for valid sequences and 0 otherwise. This isn't competitive compared with the golfing languages, but I'm quite happy with it, seeing I started out with a monster of 260 bytes.
Explanation
^((.)(?<!\2.+))*

This bit consumes a prefix of unique letters of variable length, i.e. it matches the potentially incomplete leading chunk. The lookbehind ensures that any character matched in this bit has not appeared in the string before.
Now for the rest of the input, we want to match chunks of 7 without repeating characters. We could match such a chunk like this:
(.)(?!.{0,5}\1)(.)(?!.{0,4}\2)(.)(?!.{0,3}\3)...(.)(?!.?\5).

I.e. we match a character that doesn't appear for another 6 characters, then one which doesn't appear for another 5 characters and so on. But this requires fairly horrible code repetition, and we'd have to match a trailing (potentially incomplete) chunk separately.
Balancing groups to the rescue! A different way to match
(.)(?!.{0,5}\1)

is to push 5 empty matches onto a capture stack and try emptying it:
(){5}(.)(?!(?<-1>.)*\2)

The * allows a minimum of zero repetitions, just like {0,5}, and because we've pushed five captures, it won't be able to pop more than 5 times either. This is longer for a single instance of this pattern, but this is much more reusable. Since we're doing the popping in a negative lookahead, this doesn't affect the actual stack once the lookahead has completed. So after the lookahead, we've still got 5 elements on the stack, no matter what happened inside. Furthermore, we can simply pop one element from the stack before each lookahead, and run the code in a loop, to automatically decrement the lookahead width from 5 down to 0. So that really long bit up there can actually be shortened to
(){7}((?<-1>)(.)(?!(?<-1>.)*\1\3))*

(You may notice two differences: we're pushing 7 instead of 5. One additional capture is because we pop before each iteration, not after it. The other is actually necessary so that we can pop from the stack 7 times (since we want the loop to run 7 times), we can fix that off-by-one error inside the lookahead by ensuring with the \1 that there is still at least one element left on the stack.)
The beauty of this is that it can also match the trailing incomplete chunk, because we never required it to repeat 7 times (that's just the necessary maximum, because we can't pop from the stack more often than that). So all we need to do is wrap this in another loop and ensure we've reached the end of the string to get
^((.)(?<!\2.+))*((){7}((?<-4>)(.)(?!(?<-4>.)*\4\6))*)*$

JavaScript (Node.js), 75 bytes
f=(n,i=7)=>(n+{}).match(/.{7}/g).some(x=>/(.).*\1/.test(x))?i&&f(i+n,i-1):1

Try it online!
Try 1234567<input>[object Object] so that

digits are inserted one by one, so starting anywhere is tested
Tested length is large enough, match never return null
connected string doesn't break the property