text:
Implement "tac": Print lines from a file in reverse
Between the kitten question and seeing this question at U&L about some sed magic, how about implementing tac?

Objective
Implement a program that will reverse and print the lines in a file.

Input
A file, provided as a name or via standard input

Output
The lines, reversed, to standard out.

Scoring
Bytes of source code.

tac is a bit strange when it comes to trailing linefeeds. It transforms a\nb\n (trailing linefeed) into b\na\n and a\nb (no trailing linefeed) into  ba\n. Is this how our code it supposed to behave?

Related

Also, if we have to replicate tac's behavior, a 3 byte Bash answers that executes tac is only a matter of time...

At the time of writing this had 6 votes but 14 answers... Don't forget to vote for questions if you think they're interesting, folks!

@Dennis at this point probably best to leave undefined.

Would be interesting if the file is bigger than the available memory+swap.

@Dennis Makes sense to me. Visualize the lines of a file as horizontal rows, all ending with \n. tac reverses the order of these rows. If an \n is removed from the middle of the file, the row it terminated is joined to the next row, but in the case of the last line, there is no next row to join to.

What mean the reverse of a line? For "123\n" the reverse is "321\n" or "\n321"?

GS2, 3 bytes
* +

The three bytes are, in order, split lines, reverse, and join lines.

Perl, 11 bytes
$\=$_.$\}{

Behaves exactly like tac. This code requires the -p switch, which I have counted as 1 byte.
Test runs
$ echo -en 'a\nb' | perl -pe'$\=$_.$\}{' | xxd -g 1
0000000: 62 61 0a                                         ba.
$ echo -en 'a\nb\n' | perl -pe'$\=$_.$\}{' | xxd -g 1
0000000: 62 0a 61 0a                                      b.a.

How it works
As explained here, the -p switch basically wraps while (<>) { ... ; print } around the program, so the source code is equivalent to
 while(<>)
 {
   $\ = $_ . $\
 }
 print

For each line of input, we prepend the current line ($_) to $\ (initially undefined), updating the latter with the result.
After all lines have been processed, print prints the value of the local variable $_ (undefined in this scope), followed by the output record separator ($\).

Care to explain how this works?

@xebtl Evilly. Adding the -p switch wraps your code in a loop that begins while(<>){ and ends } continue { print }, which allows filtering input just by modifying $_. $\=$_.$\ prepends each line of input to the output record terminator, and the }{ ends the perl-supplied while block prematurely, so the continue block is no longer attached to it. So all the lines of input are added to $\ in reverse order, then at the end the continue { print } eventually runs, printing "nothing" ($_ will be undef after the end of input), but with a terminator of $\.

@xebtl grr, code formatting in comments seems a bit broken where backslashes and backticks come near each other. Perhaps you can guess at what I was trying to say.

That really is devious.  Thanks for the explanation.

@hobbs I've fixed the formatting. If inline code ends with a backslash, you can use double backticks instead.

@Dennis thank you for the help

You may have a problem if the last line of the input is not terminated with a newline.

@primo The first example shows what happens in this case. The output will be strange, but exactly like tac's.

You seem to have independently arrived at the same solution that Eugene van der Pijll did, in a 2001 Perl golf competition in which this was a question.

@msh210 Interesting. Do you happen to have a link?

@Dennis pages 18 ff of this book

Pyth, 4 bytes
j_.z

.z is the input separated by lines as a list, _ reverses it and j joins it by a character, which by default is \n.

FlogScript, 2 bytes
)"

(Try it on anarchy golf.)
The ) enables --in-out-line-array mode, and the rest of the program is ", reversing the array of lines.

Argh, you beat me to it!

Retina, 7 bytes
!rm`.*$

With a single regex, Retina runs in Match mode. This normally just prints the number of matches, but with ! we configure it to print the actual matches instead (separated by linefeeds).
The actual regex is merely .*$. .* matches any line (potentially empty), because . can match any character except linefeeds. I'll get to the $ in a minute.
How do we make it print the matches in reverse? By making use of .NET's right-to-left matching mode, activated with the r. This means the regex engine starts at the end of the string when looking for matches and works backwards.
Finally, the m makes the $ match the end of a line instead of the end of the string. Why do we even need that? The trouble is that .* generates extraneous matches. Consider the regex substitution
s/a*/$0x/

applied to the input baaababaa. You'd think this would yield baaaxbaxbaax, but it actually gives you baaaxxbaxxbaaxx. Why? Because after matching aaa the engine's cursor is between the a and the b. Now it can't match any more as, but a* is also satisfied with an empty string. This means, after every single match you get another empty match.
We don't want that here, because it would introduce additional empty lines, so we discard those extraneous matches (which are at the beginnings of the lines, due to the right-to-left mode) by requiring that matches include the end of the line.

Haskell, 34 bytes
main=interact$concat.reverse.lines

[edit]
Saved one byte by replacing unlines with concat.

CJam, 7 bytes
qN/W%N*

Reads stdin, prints to stdout.
Explanation:
q       Get input.
N/      Split at newlines.
W%      Reverse list.
N*      Join with newlines.

Pyth, 5 bytes
jb_.z

This reverses the order of the lines with a simple split-reverse-join approach, but not quite like tac.
Try it online.

Python 2, 52 bytes
import sys;print''.join(sys.stdin.readlines()[::-1])

Doesn't input() read one line from stdin?

@Mauris Edited it

What about import sys;print sys.stdin.read()[::-1] ?

@dieter That reverses each character, the challenge asks for just the lines to be reversed

ok my bad - Didn't read it carefully, sorry

This inserts an extra newline between each line and an extra newline at the end.

@AndersKaseorg What? No it doesn't

http://pastebin.com/yCS347pu

Befunge-93, 17 bytes
~:1+!#v_
>:#,_@>$

Nothing fancy here; just put everything on the stack, then pop it off.

Pure Bash (no external utilities), 56
mapfile a
for((i=${#a[@]};i--;));{
printf %s "${a[i]}"
}

This is one of the few answers to do exact tac emulation, as asked about in Dennis' comment:
$ echo -en 'a\nb' | ./tacemu.sh | xxd -g 1
0000000: 62 61 0a                                         ba.
$ echo -en 'a\nb\n' | ./tacemu.sh | xxd -g 1
0000000: 62 0a 61 0a                                      b.a.
$

Nice and inspiring.

Ruby, 16 bytes
puts [*$<].reverse

SNOBOL, 42 bytes
S S =INPUT CHAR(10) S :S(S)
 OUTPUT =S
END

JavaScript (SpiderMonkey Shell), 38 bytes
[...read(readline())].reverse().join``

Pretty simple

read() reads a file
readline() reads a string from STDIN
[...str] will split str into an array of chars
reverse() will reverse the array
join`` will collpase the array into a string

GNU Awk, 27 characters
(Inspired by Ed Morton's GNU Awk answer. CW as I not intended to hijack his solution.)
{s=$0RT s}END{printf"%s",s}

Note that by changing RT → RS this becomes portable standard Awk but looses the ability to preserve the absence of the final newline.
Sample run:
bash-4.3$ echo -en 'a\nb' | awk '{s=$0RT s}END{printf"%s",s}' | xxd -g 1
0000000: 62 61 0a                                         ba.

bash-4.3$ echo -en 'a\nb\n' | awk '{s=$0RT s}END{printf"%s",s}' | xxd -g 1
0000000: 62 0a 61 0a                                      b.a.

You can remove the "%s"

@ninjalj, only if we can assume that the input will never contain “%”.

Perl, 16 bytes
print reverse<>

@Dennis oops, now reverted.

sed, 9 bytes
1!G;h;$!d

No upvote wanted, this is a famous sed one-liner.

If it's not your own work, I suggest making your answer community wiki.

Powershell, 41 bytes
$a=$args|%{gc $_};[array]::Reverse($a);$a

Stores the content of a file line by line in a, reverses a and finally prints it.

GolfScript, 7 bytes
n/-1%n*

Online test here.

Burlesque, 6 bytes
ln<-uN

ln splits lines, <- reverses, uN joins lines and formats for raw output.

C#, 179 171 bytes
using B=System.Console;class A{static void Main(){var a=new System.Collections.Stack();string b;while((b=B.ReadLine())!=null)a.Push(b);foreach(var c in a)B.WriteLine(c);}}

Reads lines, placing them in a stack, and then writes them backwards. I would use Mathematica for this, but it has no sense of EOF.

Bash, 48 43 characters
(Inspired by Digital Trauma's Bash answer. Upvotes for the idea should go to him.)
mapfile -c1 -C's=$2$s;set'
printf %s "$2$s"

Sample run:
bash-4.3$ echo -en 'a\nb' | bash tac.sh | xxd -g 1
0000000: 62 61 0a                                         ba.

bash-4.3$ echo -en 'a\nb\n' | bash tac.sh | xxd -g 1
0000000: 62 0a 61 0a                                      b.a.

I think you can do mapfile -c1 -Cf instead of mapfile -c1 -Cf a.

Correct. I also discovered it in meantime, just tried something around that tricky -C first.

><>, 55 bytes
0i:1+?!v:a=?v}1+!
0.20r}~<    >~}00
oa]~~.?)2l2dor[;!?l

It first counts the length of each line so it can isolate them in a separate stack when it browses back the lines to display them.
It can probably get shorter, I may work on it later.

Gema, 25 characters
*\n=@set{s;$0${s;}}
\Z=$s

Sample run:
bash-4.3$ echo -en 'a\nb' | gema '*\n=@set{s;$0${s;}};\Z=$s'
ba

bash-4.3$ echo -en 'a\nb\n' | gema '*\n=@set{s;$0${s;}};\Z=$s'
b
a

Hassium, 90 Bytes 86 Bytes
use IO;func main(){c=File.readLines(args[0]);for(x=c.length-1;x>=0; println(c[x--]))0;

See expanded here

I you can shorten this a lot by abusing for syntax. See a sample here

Good call @FryAmTheEggman! I added it in.

JavaScript(Node.js), 91 Bytes
console.log(require('fs').readFileSync(process.argv[2])+"".split(d="\n").reverse().join(d))

Did you mean console.log((require('fs').readFileSync(process.argv[2])+"").split(d="\n").reverse().join(d)) (92 bytes)? Your current code does not reverse the lines.

sed, 7 bytes
G;h;$!d

This works for me (and it's the shortest solution elsewhere), but I don't really want to find out why. I just messed around with the famous 9-byte trick until I found this. I guess Ging the first line does nothing?

Actually does something: your code produces an extra newline at the end of output. (G appends a newline and the content of hold space to the pattern space. While appending the content of empty hold space is indeed harmless, the newline is still appended.)

Bash + common utilities, 25
tr \\n ^G|rev|tr ^G \\n|rev

Here the ^G is a literal BEL character.  I'm assuming the input is only printable ascii.
This transforms the entire input to one line by replacing newlines with BELs, then reverses that line, then transforms back to multiline, then reverses each line again, to get the desired output.

MATLAB, 44
@(x) strjoin(fliplr(strsplit(x,'\n')),'\n');

Splits the string at new lines, flips the resulting array, then rejoins with new line characters.

Julia, 65 bytes
open(s->print(join(reverse([l for l=readlines(s)]),"")),ARGS[1])

This takes a file as a command line argument and prints its lines in reverse order. Trailing newlines are moved to the front, unlike tac, which is legit.
Ungolfed:
function p(s::Stream)
    # Create a vector of the lines of the input stream
    L = [l for l in readlines(s)]

    # Reverse the vector and join it back into a string
    j = join(reverse(L), "")

    # Print the string to STDOUT
    print(j)
end

# Open the file specified in the first command line argument
# and apply the function p to its contents
open(p, ARGS[1])

Pip, 3 + 2 = 5 bytes
Uses the r and n flags; reads from stdin.
RVg

The r flag reads stdin and stores it as a list of lines in g (which is normally a list of command-line args). We then reverse that list, and it is auto-printed. The n flag causes lists to be output with newline as a separator.

Jelly, 10 9 bytes
Ḋ;ƈ$ÐLỴṚY

Try it online!
Thanks to Dennis for -1.

Note: I assume that "provided as a name or via standard input" means that we can choose whether our program will take input from a file or STDIN (as other answers do), so, in this case, my program takes input from STDIN.

Addict, 67 bytes
a g
 t _[_]
 p
 o
a p
 i _
 g
 d
a o
 d _
 s
 d
a s
 c _[_]
 o
 d
g

Copy and paste the code here to try it.

q, 35 bytes
-1 each reverse read0 hsym`$.z.x 0;

STATA, 46 bytes
inf str99 v using a.b
g a=-_n
so a
l v,noo noh

Expects input as a file called a.b, with each line no more than 99 characters. Reads in a file and labels the variable v. Makes a new variable called a with the negative index of it. Sort by the negative index (i.e. reverse order) and then list every thing in sorted (i.e. reverse) order.
For a longer length of lines, put quotes around each line and use (42 bytes):
insheet using a.b
g a=-_n
so a
l v,noo noh

Scala, 53 52 bytes
(io.Source.stdin.getLines():\0){(a,b)=>println(a);0}

Bastardizing/side-effecting foldRight (:\) to deal with iterators (as returned by getLines) not having reverse

GNU command line environment, 41 40 37 bytes
cat -n|sort -nr|sed 's/^[^ ]* //'

Python, 80 72 bytes
It isn't the best solution, but I guess it's something.
a=lambda x: f=open(x,'r');l=f.readlines();for o in reversed(l): print(o)

Any tips on golfing it further?

return outside of a def function is a syntax error. If you use a lambda, the return value is the result of the (single) expression.

@NickT Thanks, I'll (try to) fix it.

would l[::-1] instead of reversed(l) work?
Also, you could remove the spaces after the :

C#, 145 bytes
Not as short as I hoped.. But I tried!
Golfed
using System.Linq;class c{static void Main(string[]a){foreach(var s in System.IO.File.ReadAllLines(a[0]).Reverse())System.Console.WriteLine(s);}}

Ungolfed
using System.Linq;
class c
{
    static void Main(string[]a)
    {
        foreach(var s in System.IO.File.ReadAllLines(a[0]).Reverse())
            System.Console.WriteLine(s);
    }
}

Vim, 6 bytes:
!Grev<cr>

Filters every line through the external command: rev. Must be run on linux.
Try it online!

tcl, 52
File is named F
puts [join [lreverse [split [read [open F]] \n]] \n]

demo

Pyth, 4 bytes
j_.z

Try it!
Takes input from STDIN
explanation
j_.z
  .z    # Input as list of lines
 _      # reverse
j       # join on newline

Thunno 2 N, 2 bytes
¤r

Try it online!

¤ - lines of input
r - reverse
N - join on newlines


text:
Save the pilot!
Question
We are captured by robot army on their space station. Our space ship pilot is in the prison which is in level 1. There is only one way how to escape and it's rescuing your space ship pilot. It mean's moving from level N to level 1. However because it's very risky you need to get to the prison in the least number of steps as possible.
Conditions

There are 4 ways how to move:

Move from level N to level N - 1 e.g. from 12 to 11
Move from level N to level N + 1 e.g. from 12 to 13
Use teleport from level 2k to level k e.g. from 12 to 6
Use teleport from level 3k to level k e.g. from 12 to 4

Teleports are only one-way (you can get from 12 to 4 but it's imposible to get from 4 to 12)
Every action takes one step

Input
Input should be read from STDIN, or the closest alternative in your programming language. Input consists of an integer n where 1 <= n <= 10^8.
Output
The output should be the minimum number of steps it takes to go from n to level 1.
Examples
Level         Minimum number of steps
1             0
8             3
10            3
267           7
100,000,000   25

Try to code program that will help us to save our space ship pilot from the prison in the shortest time and return home!
The shortest code will win!

It is advisable (but not obligatory) to wait at least one week before accepting an answer. Even if you intend to change the accepted answer if a shorter one gets posted in the future, others may get the impression that this contest is "over" and refrain from participating.

This challenge reminds me of a game I used to play with my calculator: I would type a number that fills up the screen and try to divide by 2, 3, or 5 as much as I can, then adding/subtracting 1 and continuing.

Pyth, 32 bytes
L?<b3tbhSsmm+h%_Wkbdy/+kbd2tS3yQ

Try it online: Demonstration or Test Suite
Explanation:
I transformed the problem a little bit. I define 4 new operations, that replace the 4 operations of the question.

level / 2 (counts as (level % 2) + 1 steps, because you might need to do move a level down first in order to teleport)
(level + 1) / 2 (counts as (level % 2) + 1 steps)
level / 3 (counts as (level % 3) + 1 steps)
(level + 1) / 3 (counts as (-level % 3) + 1 steps)

By design these operations can be applied to each number, if the number is 0 mod 2, 1 mod 2, 0 mod 3, 1 mod 3 or 2 mod 3.
You can easily think about, why this works. The main idea is, that there is at least one optimal solution, that doesn't have two (move down) or two (move up) motions in a row. Proof: If you have a solution, that has two such motions in a row, than you can replace them and make the solution smaller or equal in length. For instance you could replace (move up, move up, teleport from 2k to k) by (teleport from 2k to k, move up) and similar in all other cases.
L?<b3tbhSsmm+h%_Wkbdy/+kbd2tS3yQ
L                                 define a function y(b), which returns:
 ?<b3                               if b < 3:
     tb                               return b-1
                                    else:
          m                tS3        map each d in [2, 3] to:
           m              2             map each k in [0, 1] to:
              %_Wkbd                      (b mod d) if k == 0 else (-b mod d)
             h                            +1, this gives the additional steps
            +       y/+kbd                + f((b+k)/d) (recursive call)
         s                            combine the two lists
       hS                             and return the minimum element
                               yQ call y with input number

The function y uses implicitly memoization and therefore the runtime doesn't explode.

The main idea is, that there are never two (move down) or two (move up) motions in a row in the optimal solution. - what about  29 -> 28 -> 27 -> 9 -> 3 -> 1 ? If that is an optimal solution, how did you decide that there's always an alternative to the two-up/two-down path, which doesn't lead off into a more awkward region of numbers?

@TessellatingHeckler Maybe I should have be more precise. There is at least one optimal solution, that doesn't have two (move down) or two (move up) motions in a row. E.g. 29 -> 30 -> 10 -> 9 -> 3 ->1

I don't say that it's wrong, only that I can't "easily think about why it works". I was reasoning: the fastest route to room 1 is starting at a power of three, divide by three every move. So the fastest route for numbers near a power of three is repeated subtraction or addition to get to the power of three, then divide repeatedly by 3. If instead they start by moving moving n/2, they get further from the power of three, and therefore past the fastest possible route. I don't see how they will /always/ find another route equally short; it seems they are in a region with 'worse' choices now.

Python, 176 bytes
n=int(1e8);s,f,L=0,input(),[1,0]+[n]*(n-1)
def h(q):
 if 0<=q<=n and L[q]>s:L[q]=s+1
while n in L:
 for i,v in enumerate(L):
  if v==s:map(h,(i-1,i+1,i*2,i*3))
 s+=1
print L[f]

Brute force all the way; a list of all numbers 1 to 100,000,000 on a 64bit computer is ~800Mb of memory.
The list index represents the numbers, values represent the distance from 1 in allowed rescue steps.

Set list[1]=0 meaning "reachable in 0 steps".
for every number in the list which is reachable in 0 steps (i.e. 1)

set number+1, number-1, number*2, number*3 reachable in 1 step

for every number in the list which is reachable in 1 step (i.e 0,2,2,3)

set number+1, number-1, number*2, number*3 reachable in 2 steps

... etc. until every list index is reached.

Runtime is a bit over 10 minutes. *ahem*.
Code comments
n=int(1e8)           # max input limit.
s=0                  # tracks moves from 1 to a given number.
f=input()            # user input.

L=[1,0]+[n]*(n-1)    # A list where 0 can get to room 1 in 1 step,
                     # 1 can get to itself in 0 steps,
                     # all other rooms can get to room 1 in
                     # max-input-limit steps as a huge upper bound.

def helper(q):
    if 0<=q<=n:      # Don't exceed the list boundaries.
      if L[q]>s:     # If we've already got to this room in fewer steps
                     # don't update it with a longer path.
          L[q]=s+1   # Can get between rooms 1 and q in steps+1 actions.

while n in L:        # until there are no values still at the
                     # original huge upper bound

 for i,v in enumerate(L):
  if v==s:                            # only pick out list items
                                      # rechable in current s steps,
      map(helper,(i-1,i+1,i*2,i*3))   # and set the next ones reachable
                                      # in s+1 steps.

 s+=1                                 # Go through the list again to find
                                      # rooms reachable in s+1 steps

print L[f]                            # show answer to the user.

Other

If you run it in PythonWin, you can access the list L in the interpreter afterwards.
Every room has a path to the captain in 30 moves or less.
Only one room is 30 moves away - room 72,559,411 - and there are 244 rooms  which are 29 moves away.
It may have terrible runtime characteristics for the maximum case, but one of the question comments is "@Geobits all programs that should find shortest ways for 20000 test cases in 5 minutes" and it tests 1-20,001 in <6 seconds.

Python 2 ... 1050
poorly written, ungolfed, unoptimal.
Reads the start level on stdin, prints the minimum number of steps on stdout.
def neighbors(l):
    yield l+1
    yield l-1
    if not l%3:yield l/3
    if not l%2:yield l/2

def findpath(start, goal):
    closedset = set([])
    openset = set([start])
    came_from = {}
    g_score = {}
    g_score[start] = 0
    f_score = {}
    f_score[start] = 1
    while len(openset) > 0:
        current = min(f_score, key=f_score.get)
        if current == goal:
            return came_from
        else:
            openset.discard(current)
        del f_score[current]
        closedset.add(current)
        for neighbor in neighbors(current):
            if neighbor in closedset:
                continue
            tentative_g_score = g_score[current] + 1
            if (neighbor not in openset) or (tentative_g_score < g_score[neighbor]):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = tentative_g_score + 1
                openset.add(neighbor)
def min_path(n):
    path = findpath(n,1)
    i,current = 0,1
    while current <> n:
        i+=1
        current = path[current]
    return i
print min_path(input())

32-bit x86 machine code, 59 bytes
In hex:
31c9487435405031d231dbb103f7f14a7c070f94c301d008d353e8e3ffffff5b00c3585331d2b102f7f152e8d2ffffff5a00d05a38d076019240c3

The machine language per se has no concept of standard input. Since the challenge is pure computational, I opted to write a function taking input parameter in EAX and returning result in AL.
The math behind the code is nicely explained by @Jakube: the search is conducted only among the paths having teleports interspersed with no more than one one-level moves. The performance is about 12000 test cases per second in the lower end of input range and 50 cases per second in the upper end. The memory consumption is 12 bytes of stack space per recursion level.
0:  31 c9               xor ecx, ecx
_proc:
2:  48                  dec eax
3:  74 35               je _ret       ;if (EAX==1) return 0;
5:  40                  inc eax       ;Restore EAX
6:  50                  push eax
7:  31 d2               xor edx, edx  ;Prepare EDX for 'div'
9:  31 db               xor ebx, ebx
b:  b1 03               mov cl, 3
d:  f7 f1               div ecx       ;EAX=int(EAX/3); EDX=EAX%3
f:  4a                  dec edx       ;EDX is [-1..1]
10: 7c 07               jl _div3      ;EDX<0 (i.e. EAX%3==0)
12: 0f 94 c3            sete bl       ;BL=EDX==0?1:0
15: 01 d0               add eax, edx  ;If EAX%3==2, we'd go +1 level before teleport
17: 08 d3               or bl, dl     ;BL=EAX%3!=0
_div3:
19: 53                  push ebx      ;Save register before...
1a: e8 e3 ff ff ff      call _proc    ;...recursive call
1f: 5b                  pop ebx
20: 00 c3               add bl, al    ;BL is now # of steps if taken 3n->n route (adjusted) less one
22: 58                  pop eax       ;Restore original input parameter's value
23: 53                  push ebx
24: 31 d2               xor edx, edx
26: b1 02               mov cl, 2
28: f7 f1               div ecx       ;EAX=EAX>>1; EDX=EAX%2
2a: 52                  push edx      ;Save register before...
2b: e8 d2 ff ff ff      call _proc    ;...another recursive call
30: 5a                  pop edx
31: 00 d0               add al, dl    ;AL is now # of steps if using 2n->n route (adjusted) less one
33: 5a                  pop edx
34: 38 d0               cmp al, dl    ;Compare two routes
36: 76 01               jbe _nsw
38: 92                  xchg eax, edx ;EAX=min(EAX,EDX)
_nsw:
39: 40                  inc eax       ;Add one for the teleport itself
_ret:
3a: c3                  ret

source: Stack Exchange

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

sort: votes


text:
Pseudorandom Cellular Automaton
Introduction
In this challenge, we will simulate a certain probabilistic cellular automaton using very bad pseudorandom numbers.
The cellular automaton is defined on binary strings by the following local rule.
Suppose that the left neighbor of a cell and the cell itself have states a and b.

If min(a,b) == 0, then the new state of b is max(a,b).
If min(a,b) == 1, then the new state of b is chosen randomly from {0,1}.

The following picture shows one possible 10-step evolution of a single 1.
1
11
101
1111
11001
101011
1111111
10001001
110011011
1010111101

Note how two adjacent 1s sometimes evolve to 1, and sometimes to 0, and the border-most bits are always 1s.
Your task is to produce a cellular automaton evolution of this form.
Inputs
Your inputs are a positive integer n, denoting the number of rows to display, and a non-empty list of bits L, which we use as a source of randomness.
Output
Your output is a list of lists or 2D array of bits, depicting the evolution of a single 1 for n time steps, as in the above figure.
You can pad the output with 0s to get rows of equal lengths, if desired, but there must not be leading 0s.
The random choices in the cellular automaton must be drawn from the list L, jumping back to the beginning when it is exhausted.
More explicitly, if the output is traversed one row at a time form top to bottom, left to right, then the successive random choices shall form the list L repeated as many times as necessary.
Example
Suppose the inputs are n = 7 and L = [0,1,0].
Then the cellular automaton evolves as follows during the 7 steps, where we have put a v right above every random choice:
[1]

[1,1]
   v
[1,0,1]

[1,1,1,1]
   v v v
[1,1,0,0,1]
   v
[1,1,1,0,1,1]
   v v   v
[1,0,0,1,1,1,1]

If we read all the bits marked with a v, we get 01001001, which is L repeated 2.66 times.
The next random bit would be 0.
Rules and Scoring
You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
The exact format of the inputs and outputs is unimportant (within reason).
Test Cases
Deterministic version, every random bit is 0:
Inputs: 10 [0]
Output:
1
11
101
1111
10001
110011
1010101
11111111
100000001
1100000011

Every random bit is 1:
Inputs: 6 [1,1]
Output:
1
11
111
1111
11111
111111

Pseudorandom versions:
Inputs: 10 [0,0,1]
Output:
1
11
101
1111
10101
111111
1010011
11110101
101011111
1111101001

Inputs: 10 [1,0,0,1]
Output:
1
11
111
1001
11011
111111
1001101
11010111
111111101
1011001111

Inputs: 15 [1,1,1,0,0,0]
Output:
1
11
111
1111
10001
110011
1110111
11011001
111111011
1100011111
11100100011
111101100101
1001111101111
11011000111111
101101001011101

Pyth, 33 bytes
jjLk.u++1m?hSde=.<Q1sd.:N2 1tvz]1

Try it online: Demonstration or Test Suite
Explanation:
jjLk.u++1m?hSde=.<Q1sd.:N2 1tvz]1  implicit: Q = input list
    .u                      tvz]1  reduce N=[1] input-1 times by applying
                      .:N2           all substrings of length 2
         m                           map each d of ^ to:
          ?hSd                         if min(d) = 0 then:
               =.<Q1                     rotate Q by one
              e                          and use the last element
                    sd                 else use sum(d) (=max(d))
      ++1                  1         add a 1 at the front and the back
                                   .u gives all intermediate results
 jLk                               join these lists to strings
j                                  print each string on a line

Retina, 139 bytes
^.
1

 00:0 01:1 10:1 11:
(m`^(..)((\S*)(?<=0) .*)
$1$3#$1!$2
+m`(?<=^(?<-2>.)*(..).*?#(.)*.)\d!(.)(.*\1:)(.)(\d*)
$5$3!$4$6$5
)`!0
0
 .+
<empty>

Where <empty> indicates that there is a trailing empty line. Each line goes in a separate file and the # should be replaced with linefeeds (0x0A).
Expects the input to be n in unary (made of zeroes, as in Unary), followed by a space, followed by the "pseudo-random" string, e.g. 10, [1, 0, 0, 1] would be read as
0000000000 1001

Output is as in the challenge, but padded with zeroes, e.g.
1000000000
1100000000
1110000000
1001000000
1101100000
1111110000
1001101000
1101011100
1111111010
1011001111

This was way trickier than I expected...

Python, 142 135 132 131 bytes
133 132 131 byte version
f=input;n=f();L=f()*n*n;r=[1];i=1
while i<=n:print r;r=[L.pop(0)if r[x-1]&r[x]else r[x-1]+r[x]for x in range(1,i)];r=[1]+r+[1];i+=1

replaced r[x-1]+r[x]>1 by r[x-1]&r[x] were the bitwise operator & yields the minimum value in (r[x-1],r[x])
Thanks @ThomasKwa for suggesting n*n instead of n**2 which saves 1 byte!
Thanks @Shebang for the -1 byte
135 byte version
f=input;n=f();L=f()*n**2;r=[1];i=1
while i<=n:print r;r=[L.pop(0)if r[x-1]+r[x]>1 else r[x-1]+r[x]for x in range(1,i)];r=[1]+r+[1];i+=1

Thanks to @Cole for the -7 bytes:
min(r[x-1],r[x])->r[x-1]+r[x]>1
max(r[x-1],r[x])->r[x-1]+r[x]
142 byte version
f=input;n=f();L=f()*n**2;r=[1];i=1
while i<=n:print r;r=[L.pop(0)if min(r[x-1],r[x])else max(r[x-1],r[x])for x in range(1,i)];r=[1]+r+[1];i+=1

Not even close to @Jakube's answer but I had a lot of fun coding and golfing this one.
Expects two inputs: first input is the number of rows and second input is the pseudorandomness source list. It prints on console one row after another, each on a new line.
As an example:
10 # This is input
[0] # This is input
[1] <- First output row
[1, 1]
[1, 0, 1]
[1, 1, 1, 1]
[1, 0, 0, 0, 1]
[1, 1, 0, 0, 1, 1]
[1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 0, 0, 0, 0, 0, 0, 1, 1]

Now for a short explanation on how it works:
f=input;n=f();L=f()*n*n;r=[1];i=1 First we define the input() function as f
                                   for saving bytes as we have to call it twice.
                                   Then L is defined as a list made of the
                                   pseudorandom numbers in their order *many* times
                                   (were *many* is an upperbound of the canges that
                                   could be done); r as the first row and i as the row
                                   counter.

while i<=n:print r                 A while loop that exits when the nth row has been
                                   calculated and the printing of the actual row.

r=[L.pop(0)if r[x-1]&r[x] else r[x-1]+r[x] for x in range(1,i)];r=[1]+r+[1];i+=1
     ^           ^                 ^                         ^
     |           |                 |Same as max(r[x-1],r[x]) | from 2nd to last element
     |           | Same as min(r[x-1],r[x]) (0->False;1->True)
     | get random bit from pseudorandom list

The trick here is that we know that the bit list will always start and end with a 1 because the first and last elements are never modified due to the specs. of the question. That's the reason for the statement [1]+r+[1].
But if r is initialized as [1], there are no changes on the first row and then we add [1]+r+[1] how come the second row is not [1,1,1]?
This is due to the fact that on the first iteration i=1 so range(1,i) returns an empty list and, as a result of the for in the list comprehension having nothing to iterate over r becomes an empty list so [1]+r+[1]=[1,1]. This just happens on the first iteration which is just ideal for us!
P.S: Feel free to make any suggestions on how to golf it more.

My apologies if I don't understand the challenge correctly, but can't you replace min(a,b) with a+b>1 and max(a,b) with a+b? I realize you'd probably have to do something to handle the very first case of 1 -> 11 (I think you could do L=[1]+f()..., or find some way to insert 1 in the front of L because that would always pop 1 for the second line)

@Cole Luckily no changes have to be made to the rest of the program as the changes only affect the way of knowing the min and max values of a pair of bits.

You missed that you can remove a space here: r[x-1]&r[x] else :)

Would n**2 -> n*n work?

@Thomas You're right!

MATLAB, 146 143 138
(Also works on Octave online, but you need to sign in to save the function in a file).
function o=c(n,L);o=zeros(n);o(:,1)=1;for i=2:n;for j=2:i;a=o(i-1,j-1);b=o(i-1,j);c=a|b;d=a&b;c(d)=L(d);L=circshift(L,-d);o(i,j)=c;end;end

The function takes an input n and L, and returns an array o which contains the output.
For the input values, n is a scalar, and L is a column vector, which can be specified in the format [;;;]. Not quite what you show, but you say it is flexible within reason and this seems so.
The output is formatted as an n x n array containing 0's and 1's.
And an explanation:
function o=c(n,L)
%Create the initial array - an n x n square with the first column made of 1's
o=zeros(n);o(:,1)=1;
%For each row (starting with the second, as the first is done already)
for i=2:n;
    %For each column in that row, again starting with the second as the first is done
    for j=2:i;
        %Extract the current and previous elements in the row above
        a=o(i-1,j-1); %(previous)
        b=o(i-1,j);   %(current)
        %Assume that min()==0, so set c to max();
        c=a|b;
        %Now check if min()==1
        d=a&b;
        %If so, set c to L(1)
        c(d)=L(d);
        %Rotate L around only if min()==1
        L=circshift(L,-d);
        %And store c back to the output matrix
        o(i,j)=c;
    end;
end

Update: I have managed to optimise away the if-else statement to save a few bytes. The input format has once again changed back to column vector.

Haskell, 153 149 bytes
j[_]o l=(l,o)
j(a:u@(b:c))o q@(l:m)|a*b==0=j u(o++[a+b])q|1<2=j u(o++[l])m
k(r,a)=fmap((1:).(++[1]))$j a[]r
n%l=map snd$take n$iterate k(cycle l,[1])

% returns a list of bit lists. Usage example:
> 10 % [1,0,0,1]
[[1],[1,1],[1,1,1],[1,0,0,1],[1,1,0,1,1],[1,1,1,1,1,1],[1,0,0,1,1,0,1],[1,1,0,1,0,1,1,1],[1,1,1,1,1,1,1,0,1],[1,0,1,1,0,0,1,1,1,1]]

Oh dear! Carrying the random list L around is pure pain. Let's see if this can be shorter.

C#, 152 bytes
There's nothing special here.  The function returns a 2D array where the first rank is the line and the second is the column.
Indented and new lines for clarity:
int[,]F(int n,int[]l){
    var o=new int[n,n];
    for(int y=0,x,i=0,m;y<n;y++)
        for(o[y,x=0]=1;x++<y;)
            o[y,x]=(m=o[y-1,x-1]+o[y-1,x])<2?m:l[i++%l.Length];
    return o;
}

TI-BASIC, 106 94 87 86 87 bytes
Prompt N,B
"∟B(1+remainder(,dim(∟B→u
{1
For(I,1,N
Disp Ans
augment({0},Ans)+augment(Ans,{0
Ans and Ans≠2+seq(u(-(Ans(X)<2)+2dim(∟B)),X,1,dim(Ans
End

TI-BASIC doesn't have an increment operator, right? Well, it sort of does. The equation variable u, normally used with sequences, has an obscure feature: when u is called with an argument, the variable  is set to one greater than that argument. The conditional increment depends on this. (I've been waiting to use it for a long time.)
For list indexing to work properly,  must be its default value of 0, and Min should be its default 1, so either clear your calculator's RAM or set those values manually before running this.
augment({0},Ans)+augment(Ans,{0 calculates a list of sums of two adjacent elements, so it will return a list of 0s, 1s, and 2s. Then the magic is on this line:
Ans and Ans≠2+seq(u(-(Ans(X)≠2)+dim(∟B)),X,1,dim(Ans

Ans and                 ;set 0s to 0
Ans≠                    ;set to 0 all sums that equal...
2+
  seq(...,X,1,dim(Ans   ;execute for each element of the list
      u(                ;return this element in list of bits (looping)
                       ;current location in the list
        -(Ans(X)≠2)+    ;subtract 1 if the element isn't 2
        2dim(∟B)        ;Add twice the dimension of the list
                           ;(because n<nMin on the first iteration, it's out of the domain
                           ;this prevents an error)
       )                      ;set n to one greater than that value
                              ;i.e. increment if element≠2
                        ;Will equal Ans(X) iff Ans(X)=2 and the bit read false

The result of this line will be that list elements are 0 if they were 0 or if they were 2 and the bit read was 0.
Result of above line
n \ u |  0  |  1
0        0     0

Test case:
N=?7
B=?{0,1,0
             {1}
           {1 1}
         {1 0 1}
       {1 1 1 1}
     {1 1 0 0 1}
   {1 1 1 0 1 1}
 {1 0 0 1 1 1 1}
            Done

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


text:
A real sausage fest
Since the first weekend of October is drawing near, let's have our own Oktoberfest!
Background
You and some other programmers have been hired by the local sausage guys in Munich, Germany. The sausage guys provide Oktoberfest with all the sausages the giant Volksfest needs. You manage to overhear your boss speaking to the other employees about why you and the others were hired without any previous sausage-related experience. You realize you were hired for your impeccable programming skills - and your boss apparently wants you to code a sausage analyzer.
This year around, the sausage guys have decided to increase the variety of sausages at Oktoberfest - but they have no idea of how much they've imported.
Challenge
You need to help your boss figure out how much sausage of a certain kind they've actually imported. You will have to program a sausage analyzer which outputs the kind and number of every sausage the sausage guys have imported.
Your boss has bought a special floppy drive for this occasion which, given a sausage, pipes it to stdin.
Input
A number of sausages on stdin, each sausage separated by one space.
Sausages are given on the following format:
Prinskorv (P)
 ¤
| |
| |
| |
 ¤

Salchichón (S)
 l
| |
| |
| |
| |
 l

Landjäger (L)
\ /
| |
| |
| |
| |
/ \

Kabanos (K)
.
|
|
|
|
|
.

Cotechino Modena (C)
 ___
|   |
|   |
|   |
|___|

Rød pølse (R)
 ^
| |
| |
| |
| |
 v

Output
The occurrences of a given sausage along with an identifier of which kind of sausage it is, separated by a space. The identifier is the first letter in the name of the sausage. Order is not important.
Output shall be written to stdout, trailing newlines and spaces are allowed.
Examples
Input
 ^   ^   ^   ^  .
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
 v   v   v   v  |
                .

Output
4R 1K

Input
\ /  ___   l   ¤   ¤
| | |   | | | | | | |
| | |   | | | | | | |
| | |   | | | | | | |
| | |___| | |  ¤   ¤
/ \        l

Output
1L 1C 1S 2P

Input
 l   ¤   l
| | | | | |
| | | | | |
| | | | | |
| |  ¤  | |
 l       l

Output
2S 1P

The programmer with the shortest program in bytes gets paid by the sausage guys (wins)!
Sausage trivia

Prinskorv
Prinskorv which directly translates to "prince-sausage" is a small Swedish sausage which is often sold in links. Usually fried in a frying pan and served with a generous helping of mustard.

Salchichón
Salchichón is a Spanish summer sausage often made with pork, although some recipes use other meats including ox, veal or horse. The meat and fat are chopped in thin bits, seasoned with salt, pepper, nutmeg, oregano, and garlic and then inserted in thick natural pork intestines.

Landjäger
Landjäger is a semi-dried sausage traditionally made in Southern Germany, Austria, Switzerland, and Alsace. It is popular as a snack food during activities such as hiking. It also has a history as soldier's food because it keeps without refrigeration and comes in single-meal portions.

Kabanos
Kabanos is a Polish long thin dry sausage made of pork or kosher turkey. They are smoky in flavour, and can be soft or very dry in texture depending on freshness. Kabanosy are often seasoned only with pepper. Unlike other meats, these sausages are typically eaten alone as an appetiser and, except when kosher, often served with cheese.

Cotechino Modena
Cotechino Modena or Cotechino di Modena is a fresh sausage made from pork, fatback, and pork rind, and comes from Modena, Italy, where it has PGI status. Cotechino is often served with lentils or cannellini beans with a sauce alongside mashed potatoes, especially around the New Year.

Rød pølse
Rød pølse (red sausage) is a type of brightly red, boiled pork sausage very common in Denmark. Since hot dog stands are ubiquitous in Denmark, some people regard røde pølser as one of the national dishes.

All sausage information shamelessly copied from Wikipedia

You are writing an Oktoberfest-themed challenge about sausages, and it doesn't include Weißwurst? -1

I blame those dastardly sausage guys!

As the sausages are different heights, are they all aligned to the top (as current examples are)? or may they be bottom aligned? or unaligned?

They're all given on one line (which means they're aligned to the top)

Hey, my mom makes Salchichón for Thanksgiving!

Why did you put the sausage information in a spoiler tag? Is that to keep it from going bad?

@MartinBüttner It's just you can't see the Weisswurst. They're white. :-D

@MartinBüttner Well I guess you could say...that was the wurst idea ever!

Is a trailing space allowed?

Trailing spaces are allowed. I think I meant to write trailing spaces instead of trailing newlines..
Now both are allowed!

Maybe requiring invalid input to print "Wurst" would have made the programs more interesting.

Does the Landjäger have a space at the top?

Landjäger does not have a space at the top :~)!

Pyth, 30 bytes
jdm+hd@"SKLCRP"%Ced45rS-czd\/8

Try it online: Demonstration or Test Suite
Explanation:
As all other participants I only look at the first line of the input. Let's say the first line of the input is \ /  ___   l   ¤   ¤  ____.
At first I split by spaces, which gives me the list
['\\', '/', '', '___', '', '', 'l', '', '', '¤', '', '', '¤', '', '___']

Now we want to get ride of '/'s and ''s and sort the remaining thing.
['\\', '___', '___', 'l', '¤', '¤']

Now I can run-length-encode it.
[[1, '\\'], [2, '___'], [1, 'l'], [2, '¤']]

As it turns out, the order (ascii-value) of these chars or of the string '___'
 can be mapped nicely to the numbers [0, 1, 2, 3, 4, 5].
char/string |  l   .   \    ___    ^   ¤
-------------------------------------------
value       | 108  46  92 6250335  94 164
value%45    |  18   1   2      15   4  29
(value%45)%6|   0   1   2       3   4   5

And this can be used to map them directly to the letters SKLCRP.
jdm+hd@"SKLCRP"%Ced45rS-czd\/8
                        czd     split the input string at spaces
                       -   \/   remove "/"s (and also ""s)
                      S         sort
                     r       8  run-length-encode
  m                             map each pair d of ^ to:
   +hd                            d[0] +
                Ced               convert d[1] to a number
               %   45             mod 45
      @"SKLCRP"                   take the ^th element in the string (mod 6)
jd                              join by spaces

Pyth, 36 34 32 30 bytes
XjdsMrShM-czd\\8"¤_l/^.KRLSCP

Saved yet another 2 bytes thanks to...guess who? :D
Ignores all the input except for the first line, removes all the /s and spaces, translates it to the target identifiers, sorts it, uses run-length encoding, and prints the result.
Live demo.
32-byte version
XjdsMrS-hMfTczd\\8"¤_l/^.KRLSCP

Live demo.
Saved another 2 bytes thanks to @Jakube!
34-byte version
jdsMrSX-hMfTczd\\"¤_l/^.KRLSCP")8

Live demo.
Saved 2 bytes thanks to @Jakube!
36-byte version
jdsMrSX-hMfTczd\/"¤_l\\^.""PCSLRK"8

Live demo.

I gave you a +1 because I love Kirby

I didn't give you a +1 because you're at exactly 4k rep :)

I gave you a -1 to get you back to exactly 4k :D

Another two bytes ;-) hM-czd\\ is the same as -hMfTczd\\

@Jakube Thanks again! You're really good at this...

Isn't this actually 29 bytes?

@sweerpotato See here. The ¤ is two bytes.

Oh yeah, of course. Totally missed that character

Javascript (ES6), 105
a=>[...'¤l/._^'].map((g,h)=>(f=(a.split(g).length-1)/'222261'[h],f?f+'PSLKCR'[h]:0)).filter(b=>b).join` `

It's pretty simple but here's an explanation anyway:
input=>
  // list of all unique characters of the sausages
  [...'¤l/._^'].map((sausage_char, index)=>(
    // find all occurrences of the character in the string
    occurrences = (input.split(sausage_char).length - 1)
      / '222261'[index], // divide by the number of that character in its sausage
      // when dividing and multiplying by numbers in strings, JS automatically casts them
    occurrences ? // is there anything for this sausage?
      occurrences + 'PSLKCR'[index] : // add the sausage's letter and count
      0 // return 0 so it can be filtered out
  ))
  // filter out the 0s
  .filter(b=>b)
  // return a space-separated string
  .join` `

Very clever! Using ES7's array comprehensions to golf this version, I got 91: a=>(h=-1,[for(g of'¤l/._^')if(f=(a.split(g).length-1)/'222261'[++h])f+'PSLKCR'[h]].join` `) If only I could simplify the declaration of h...

@ETHproductions cool! I should learn ES7

CJam, 38 35 33 bytes
l'_%'C*"l¤\^./""SPLRK "erS-$e`S*

Test it here.
Explanation
The first line of each type of sausage is unique, and since the sausages are aligned at the top, it's sufficient to count the relevant characters in that first line. Two types require special treatment:

Landjäger (L) have both \ and /. We want to get rid of one of them, then we can count the other one like all the other characters.
Cotechino Modena (C) have three underscores, so we need to divide the underscore count by 3. However, it's actually shorter to treat underscores individually by simply replacing runs of them in the input (which will always belong to only one sausage) with the target character C right away.

Now for the actual code:
l         e# Read one line from STDIN.
'_%       e# Split on runs of underscores.
'C*       e# Join back together by C's.
"l¤\^./"  e# Push a string with characters corresponding to each type, and a slash.
"SPLRK "  e# Push a string with the corresponding letters and a space.
er        e# Transliterate, turning each identifying character into the correct
          e# letter and all slashes into spaces.
S-        e# Remove spaces (which also gets rid of what used to be slashes).
$         e# Sort the string to group each letter.
e`        e# Run-length encode.
S*        e# Join by spaces.

Whatever you do, don't forget to Splurk.

MATLAB, 113
Assuming that trailing spaces are allowed (yep they are), here is a MATLAB anonymous function:
@(a)arrayfun(@(p,m)fprintf([(m>32&&p)*'%d%c ' ''],p,m),histc(strtok(strrep(a,'___','_'),10),'./\^_l¤'),'K LRCSP')

And an explanation:
@(a) %Anonymous function, with an input a
    arrayfun(@(p,m) %Loop through the two input arrays (see later)
                   fprintf( %Print to console
                           [(m>32&&p)*'%d%c ' ''] %Essentially this means if p>0 and m>' ', print an integer followed by a char, then a space
                                                 ,p,m) %The values from the array input is what is getting printed
                                                      ,histc( %Make an array of how many times
                                                                       strtok(strrep(a,'___','_'),10), %Keep only the first line (as that is where the interesting bit is) and also replace ___ with _ for the 'C'
                                                             './\^_l¤'), %these inputs appear (which will be passed in turn as the 'p' variable to cellfun)
                                                                        'K LRCSP' %These are the characters to be printed with the count representing each sausage (it will be placed in the 'm' input of arrayfun)
             )

Appears to work correctly. Still has the trailing space, but now handles all sausages correctly.

Mathematica 116
Some bytes could probably shaved off, but nothing to approach the golfing languages.
Row[Row/@Reverse/@Tally@ImportString[#,"Table"][[1]]/.{"¤"->"P","l"->"S","/"->"L","___"->"C","."->"K","^"->"R"}," "] &

ImportString[#,"Table"][[1]] returns a list of space-separated strings appearing in the top line of the input. The string may include any of the elements in the list, {"¤","l","/","___",".","^"}, including repeats. Each element is associated with a unique type of sausage.
Tally counts the number of times each such string appears.
/.{"¤"->"P","l"->"S",... replaces ¤ with P, l with S and so on.
Reverse places each tally before the item it is associated with.
The two Rows format the output.

Perl, 84 77 bytes
Someone could probably shave a bit off of this...
84 bytes
($s=<>)=~y|_^\.l\\¤|CRKSLP|d;$$_++for split//,$s;$C/=3;for(A..Z){print"$$_$_ "if$$_}

77 bytes
$$_++for split//,<>=~y|_^\.l\\¤|CRKSLP|dr;$C/=3;for(A..Z){print"$$_$_ "if$$_}

Breakdown:
Take first line of STDIN, transliterate values into letter codes, delete extra garbage. The d modifier shouldn't really be necessary, but I ran into weird unicode issues on the ¤ character without it.
Use symbolic reference to create and/or increment variable for each character found.
$$_++ for split //, <> =~ y|_^\.l\\¤|CRKSLP|dr;

Divide C variable by 3, due to triple-underscore
$C /= 3;

Loop through alphabet and print single-letter capital variables along with letter if they have a value greater than zero
for (A..Z) {
    print "$$_$_ " if $$_;
}

Test result: http://ideone.com/alpUlI
Edit: Chop 7 bytes by having transliterate pass anonymous return value directly into split.

Perl, 172 bytes
Daresay more can be sliced off this sausage still, but here's a starter for ten.
$a=<>;$a=~s/¤/h/g;$a=~s/_+/_/g;$a=~s/(\/| |\n)//g;$a=~s/\\/x/g;$h{$_}++ for split(//,$a);foreach (sort keys %h){print $h{$_};$_=~tr/^.hlx_/RKPSLC/;print "$_ ";}print "\n"

Ungolfed version
$a=<>;              # get 1st line
$a=~s/¤/h/g;        # convert ¤ to h, avoid unicode hassles
$a=~s/_+/_/g;       # multiple consecutive _ to single _
$a=~s/(\/| |\n)//g; # strip / and spaces
$a=~s/\\/x/g;       # convert \\ to x to avoid regexp hassles

# build hash that counts occurences of character
$h{$_}++ for split(//,$a);

# print the answers
foreach (sort keys %h) {
 print $h{$_};
 $_=~tr/^.hlx_/RKPSLC/;
 print "$_ ";
}
print "\n";

Test results
$ perl meaty.pl <test1.txt
1K 4R
$ perl meaty.pl <test2.txt
1C 2P 1S 1L
$ perl meaty.pl <test3.txt
1P 2S
$

Python 3, 120 bytes
I'm pretty sure you can shorten this, but there wasn't already a Python solution so here we go:
x=input()
a={z:x.count(y)for y,z in zip('¤l/.^_','PSLKRC')}
a['C']//=3
print(' '.join(str(a[x])+x for x in a if a[x]))

Explanation
It's pretty simple, some might even say readable, but here's a short explanation anyway:
First one line of input is read, since each sausage can be determined from just the first line.
Now a={z:x.count(y)for y,z in zip('¤l/.^_','PSLKRC')} is a dictionary comprehension that maps the identifier of each type of sausage (z) to the count of each type of sausage (x.count(y), where y is the sausage defining character).
We then divide the count of Cotechino Modena (C) sausages by 3 because of the triple underscore.
Finally we print out the result: print(' '.join(str(a[x])+x for x in a if a[x])). This creates the output count of each sausage one at a time, but only if that sausage was seen at least once (a[x] is not zero => Truthy). Each count string is joined by a space and printed out.

print ’a[x]’+' '+a[x] for ... Should work (not tested) and saves 5 bytes. With ’ being a backtick.


text:
Math in manhattan
I define the following operators:
Manhattan Addition a +M b, for single-digit numbers, is the result of concatenating b onto a. So, a +M b = 10a + b. Therefore, the general operator +M is defined as thus:
a +M b = 10a + b
Manhattan Subtraction a –M b, for single-digit numbers, is the result of removing the last b from a. Therefore, the operator –M is defined as thus in pseudocode:
a –M b = a remove last b
Manhattan Multiplication a ×M b is the result of replacing all instances of b in a with b instances of b. Ergo, ×M is defined in pseudocode as:
a ×M b = a -> s/b//g
Manhattan Division a ÷M b is defined in terms of ×M:
1 ÷M b = the first character of b
a ÷M b = a ×M (1 ÷M b)
With all this in mind, create an interpreter that will evaluate infix expressions that use the following operators (i.e., a + b, not a b + or + a b)
+    Addition
-    Subtraction
/    Division
*    Multiplication
*M   Manhattan Multiplication
/M   Manhattan Division
+M   Manhattan Addition
-M   Manhattan Subtraction

Each Manhattan operator has a higher order precedence than their normal counterpart.
Test cases:
> 5 +M 10 + 3
63      // 5*10 + 10 + 3 => 60 + 3
> 10 *M 2
10      // no 2s in 10
> 10 *M 1
10      // one 1 in 10 replaced once
> 23 *M 3
2333    // 23 has one 3, which is replaced with three 3s
> 23 *M 2
223     // 23 has one 2, which is replaced with two 2s
> 232 *M 2
22322   // 232 has two 2s, which are replaced with two 2s
> 232 *M 23
23...(23 times)...232   // ...
> 123 *M 2 * 3
3669    // 1223 * 3 => 3669
> 5 + 3 +M 2
37      // 5 + (3 +M 2) => 5 + 32 => 37
> 150 /M 3
150     // 150 ÷M 3 => 150 ×M 3 => 150
> 150 /M 53
1555550 // 150 ÷M 53 => 150 ×M 5 => 1555550
> 50 -M 0
5
> 500 -M 0
50
> 5234 -M 5
234
> 12 +M 633 *M 3
6333453 // = 12 +M 6333333 = 120 + 6333333 = 6333453

This is a code-golf, so the shortest program in bytes wins.
Leaderboards
Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.
To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:
# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:
# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:
# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:
# [><>](http://esolangs.org/wiki/Fish), 121 bytes

var QUESTION_ID=59299,OVERRIDE_USER=8478;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 commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
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

Winners by Language

Language	User	Score

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

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

Why are you using the Unicode symbols × and ÷ instead of ASCII * and /?

Why does 232 ×M 23 equal 23232? Shouldn't it equal 23 copies of 23 followed by a 2?

@senshin Sorry, yes. right.

@ASCIIThenANSI I can see why you asked that. The choice is arbitrary. Unless if there is some pressing issue with my choice, I don't think I'll change it.

It makes it arbitrarily harder for languages without good Unicode support to participate, which is not very fun, if the challenge isn't about Unicode.

@Mauris Ah. kay then.

So $a -M b = a$ if $a ≠ b$, $0$ otherwise? Or are $a +M b$ and $a -M b$ defined for arbitrary $a$ and single-digit $b$? Also, should we suppose base 10?

Your definition of subtraction is not related to single digit numbers. Maybe b is single digit but not a

This question has not received enough attention because is not well specified. You define addition for sngle digit numbers, then your first example have 2 digits numbers. I give up...

@edc65 I clearly defined (fine, specified) what each operator should do. Feel free to give up.

Do * and / have higher precedence than + and -? What about *M and /M vs +M and -M?

How much flexibility do we need in our handling of whitespace?

@ThomasKwa I didn't specify it, so whatever works best for your program is fine by me.

@edc65 He clearly states a +M b = 10a + b. This is in general, not just for single-digit numbers. The concatenation method was the one that was only for single digit numbers.

Can we assume that -M will always be called with an a that contains at least one b?

@ThomasKwa Yes.

You need some better test cases that test operator precedence, and also a test more than one or two operations at once.

@mbomb007 I should, and will do so when the time becomes available.

Which comes first in order of operations? *M or /M? Same question with +M and -M. They aren't inverses of each other, so I think they need to have a fixed order. Or is it just going to be left-to-right?

The same as normal: As * and / are evaluated first, from left-to-right, so are *M and /M.

@CᴏɴᴏʀO'Bʀɪᴇɴ You’ve left several questions about your specs unanswered. First of all, your operations are not defined on numbers, but on their representations. I suppose that you want us to use base 10 representations at all time, but it’s not in the specs. If I get it right, 2 -M 1 = 2 if we suppose base 10, but 1 if we suppose base 2.

@CᴏɴᴏʀO'Bʀɪᴇɴ Second, you define +M and -M for single digits, then you say “in general”. Does that mean “for any integer”? Because, then, I’m not sure whether 123 -M 12 = 3 and I have no idea what 123 -M 13 is.

@Édouard Yes, in general applies to all integers. 123 -M 12 = 3 and 123 -M 13 = 123. If there is no instance of b in a, then a remains unchanged.

You should add 4342343 -M 34 → 43423 as a test case.

Dyalog APL, 104 81 79 93 75 bytes
Edit: Now handles 4342343 -M 34 → 43423 correctly.
M←{⍎(5|⌊⍺⍺2)⊃'⍺×M⍣(⍺≠1)⍎⊃b'(b⎕R(⍵⍴'&')⊢a)'10⊥⍺⍵'(('(.*)',b←⍕⍵)⎕R'\1'⊢a←⍕⍺)}

Background
This extends APL to include the Manhattan operator. An operator in APL terminology is a modifier of functions (e.g. ÷). An example of an operator is ⍨ which modifies functions to swap their arguments so 3 = 2 ÷⍨ 6. So too, M modifies the basic arithmetic functions to be their Manhattan relatives. Note that since the resulting language is an extension of APL, APL's strict right-to-left precedence remains.
Explanation
The overarching structure is M←{⍎(5|⌊⍺⍺2)⊃…} which applies the function (+ or - or × or ÷) to 2 and uses the result to chose which string to evaluate. The strings are:
3 for -M: (('(.*)',b←⍕⍵)⎕R'\1'⊢a←⍕⍺)
 regex remove the last occurrence of b (string rep. of right arg.) in a (string rep. of left arg.)
2 for +M: '10⊥⍺⍵'
 evaluate the arguments as base-10 digits
1 for ×M: (b⎕R(⍵⍴'&')⊢a)
 replace occurrences of b with b ampersands (i.e. regex for the
0 for ÷M: '⍺×M⍣(⍺≠1)⍎⊃b'
 ⍎⊃b first digit of b
 ⍺×M⍣(⍺≠1) apply ⍺ ×M if ⍺ ≠ 1
⊃ out of of the above four strings, pick number:
(5|⌊⍺⍺2) mod-5 of the floor of the function applied to 2, namely:
 3 = 5 | ⌊-2
 2 = 5 | ⌊+2
 1 = 5 | ⌊×2 because ×2 ⇔ sgn(2) ⇔ 1
 0 = 5 | ⌊÷2 because ÷2 ⇔ 1 ÷ 2 ⇔ 0.5
Lots of thanks to my dear friend ngn for amazing shavings.

This is fine. It fits what I had desired.

Great, I'll edit the post then.

@CᴏɴᴏʀO'Bʀɪᴇɴ I might have lost out on the bonus, but it sure is the shortest now.

oops, forgot about this one.

@CᴏɴᴏʀO'Bʀɪᴇɴ Forgot? I just edited today, making it shorter than the accepted one.

Oops again. I thought you were reminding me to accept

Perl, 100 99 98 bytes
97 bytes code + 1 byte command line
s/ |.*\K(\d)(\d*)-M\1|\+M/\2/g+s/(\d+)\*M(.)/$1=~s@$2@$&x$&@erg/e+s#/(M.)\d+#*\1#&&redo,$\=eval}{

Usage example:
echo "123 *M 2 * 3 + 150 /M 53" | perl -p entry.pl

If it makes your code shorter, you only have to use *M for xM and /M for
M.

Congrats on the bounty!

Python, 644 bytes
import operator as o,re
x,q,t,r,w='*/+-M';mm,md,ma,ms='*M /M +M -M'.split()
n=lambda x:x
a=lambda a,b:str(10*int(a)+int(b))
v=lambda a,b:a[::-1].replace(b,'',1)[::-1]
m=lambda a,b:a.replace(b,b*int(b))
d=lambda a,b:m(a,b[0])if a>0 else b[0]
def p(s):s=s.group();ss=s.split();l=s.split(ss[1]);h={mm:m,md:d,ma:a,ms:v,x:o.mul,q:o.div,t:o.add,r:o.sub}.get(ss[1],n);return str(h(*map(int if h in[o.mul,o.div,o.add,o.sub]else n,map(u,map(str.strip,l)))))
def u(s):z=r'\d+ (?:\{0}{2}|\{1}{2}) \d+';return re.sub(z.format(t,r,''),p,re.sub(z.format(t,r,w),p,re.sub(z.format(x,q,''),p,re.sub(z.format(x,q,w),p,re.sub(r'\((.*)\)',u,s)))))
print u(input())

Accepts input on STDIN (wrapped in quotes). Uses regex to match and parse operations. All work is done on strings, and casting to and from ints is only used when doing normal mathematical operations.
I'm pretty sure this could be golfed further, so I'll be working on that over the next few days.

I don't see a c or f.


text:
"Fill the Grid" Problem
A challenge with simple rules but non-trivial algorithms. :-)
Task
Take input in the form of space-separated integers:
N A B S

Where N is the side length of a 2D square matrix filled with unique numbers (integers) between A and B inclusive. For each row and column in this matrix, the sum is always the same: S. (In other words, the matrix is a semi-magic square).
Note:
All numbers are positive. Exception is A, which can be 0.
Examples
For
3 1 10000 2015

a valid solution would be

For
8 1 300 500

a valid solution would be

Output
You output should be an ASCII table. Example for the first example above:
 384  159 1472
1174  499  342
 457 1357  201

Right-aligned integers padded by spaces. The width of each column is the width of the largest integer in that column.
Scoring
This is code-golf, so shortest code in bytes wins. Standard loopholes apply (especially about built-ins to solve this problem). You don't have to care about wrong or otherwise impossible inputs (including negative numbers). Please provide a sample output in your answer (mandatory) for the second example above.

Are we allowed to generate random numbers between A and B  until they sum correctly and are unique?

Just to check, A, B, and N can be negative?

@xnor No. That would be an invalid input and as I said, you don't have to care about invalid inputs.

@minxomat You should clarify then, you say "integers", which includes negatives.

@ThomasKwa If that is the best solution you can come up with, sure. (Lame! :P)

@minxomat What about 0 inputs? Are those valid?

@xnor Added a clarification in the header.

minxomat, I'm not saying it's the best solution I can come up with, I'm saying it may be the shortest possible.

@ThomasKwa Yes, it would technically win. But clever answers are usually more popular than easy answers :)

A simple random algorithm would find the solution in a finite (albeit very large) time almost surely. This should probably be ruled out explicitly in the challenge

@LuisMendo You have to generate a sample output according to the task. If you can manage this within your lifetime with a brute-force approach, I'd be impressed. :-). I could rule it out, but it would be too fuzzy, since the most popular solution (which is GA) still involves randomness. Also I don't want to change the rules when someone might work on a solution already.

@minxomat All your three arguments are very good points :-)

CJam, 119 91 bytes
q~:M;),>:R;(:L{{R{ML)d/-Y#)mr}$L/L<2{{M1$:+-+}%z}*:U:+__O|=R*-}gU{:s_:,:e>f{Se[}}%zSf*N*}M?

This is a provably correct, non-deterministic approach.
On my desktop, the second test case generally finishes in less than 10 minutes.
The first case finishes instantly. Try it online in the CJam interpreter.
Sample run
$ cjam grid.cjam <<< '8 1 300 500'
77  66  37 47  56  46 86  85
63 102  70 72  49  54 81   9
62  69  58 57  71  17 48 118
64  65  67 87  53  44 80  40
73  60  55 89  51  76 84  12
68  59  28 78  74  38 50 105
61  75  52 43 125  83 42  19
32   4 133 27  21 142 29 112

Idea
Without time limits, we could just randomly generate squares until finding a valid square. This approach builds on that idea, adding two optimizations:

Instead of pseudo-randomly generating square of side length N, we generate squares of side length N-1, add one column to form a N × (N-1) rectangle whose rows have sum S, then one row to form a square of side length N whose columns have sum S.
Since the sum of the elements of all columns will be NS and the sum of the elements of the first N-1 rows is (N-1)S, the last row will also have sum S.
However, this process may generate an invalid matrix, since there's no guarantee that all elements of the last row and column will be unique or fall in the range [A ... B].
Picking a square of unique integers in [A ... B] and side length N-1 uniformly at random would take way too long. We somehow have to prioritize squares that have a higher chance of resulting in a valid square of side length N after applying the process detailed in the previous bullet point.
Given that each row and column has to have a sum of S, its elements have an average of S/N. Thus, picking more elements close to that average should increase our chances.
For each I in [A ... B], we pseudo-randomly pick a float between 0 and (I - S/N)2 + 1 and sort the elements of [A ... B] by the picked floats. We keep the first N2 numbers and place them in reading order in a square.
Assuming a perfectly uniform distribution of all real numbers between 0 and (I - S/N)2 + 1 in each step, all squares have a non-zero probability of being picked, meaning that the process will finish eventually.

Code
q~          e# Read all input from STDIN and evaluate it.
:M;         e# Save "S" in M and discard it from the stack.
),>:R;      e# Transform "A B" into [A ... B], save in R and discard.
(:L         e# Save "N - 1" in L and keep it on the stack.
{           e# If L is non-zero:
  {         e#   Do:
    R{      e#     For each I in R:
      ML)d/ e#       Compute M/Double(L+1).
      -Y#   e#       Subtract the result from I and square the difference.
      )mr   e#       Add 1 and pick a non-negative Double below the result.
    }$      e#     Sort the values of I according to the picks.
    L/      e#     Split the shuffled R into chunks of length L.
    L<      e#     Keep only the first L chunks.
    2{      e#     Do twice:
      {     e#       For each row of the  L x L array.
        M1$ e#       Push M and a copy of the row.
        :+- e#       Add the integers of the row and subtract their sum from M.
        +   e#       Append the difference to the row.
      }%    e#
      z     e#       Transpose rows and columns.
    }*      e#
    :U:+    e#     Save the result in U and concatenate its rows.
    __O|    e#     Push two copies. Deduplicate the second copy.
    =R*     e#     Push R if all elements are unique, an empty array otherwise.
    -       e#     Remove the result's elements from U's elements.
  }g        e#   If the resulting array is non-empty, repeat the loop.
  U{        e#   For each row in U:
    :s      e#     Convert its integers into strings.
    _:,     e#     Copy and replace each string with its length.
    :e>     e#     Compute the maximum length.
    f{      e#     For each integer, push the maximum length; then
      Se[   e#       Left-pad the integer with spaces to that length.
    }       e#
  }%        e#
  z         e#   Transpose rows with columns.
  Sf*N*     e#   Join columns by spaces, rows by linefeeds.
}M?         e# Else, push M.

Jelly, 19 18 bytes
S;§f⁵
r/œ!²}s€ÇÞṪG

Try it online!
Takes input via the command-line in the form A, B N S. Outputs the lexicographic ally first grid that fits
-1 byte thanks to Jonathan Allan!
On the one hand, it's short. On the other hand, it's incredibly inefficient. This generates
$$\frac {(B-A+1)!} {(B-A-N^2+1)!}$$
\$N\times N\$ squares to check. For example, if \$A = 1, B = 9, N = 3\$ (the example in TIO), this generates \$362880\$ \$3\times3\$ matrices to check are semi-magic. For the second test case, it generates 243427020732724848691170301000009788596908895057539171134817782742659530443034291592046861179091424965386457564096330026488754281163364761600000000000000000 \$8\times8\$ matrices.
Given enough time and memory, this would work on any input. However, on my computer, it runs out of memory for the second test case after 5 minutes
How it works
S;§f⁵ - Helper link. Takes a matrix M and outputs if it's semi-magic to S
S     - Column sums of M
  §   - Row sums of M
 ;    - Concatenate
   f⁵ - Keep only S

r/œ!²}s€ÇÞṪG - Main link. Takes [A, B] on the left and N on the right
r/           - Reduce [A, B] by range, yielding [A, A+1, ..., B-1, B]
     }       - To N:
    ²        -   Square
  œ!         - Generate all permutations of range(A, B) of length N²
       €     - Over each:
      s      -   Slice into NxN matrices
        ÇÞ   - Sort the matrices by the helper link
          ṪG - Take the last and format as a grid

Impossible inputs do not need to be handled so save two using filter-keep and sort to save one, which then allows a four-link dyad, which saves one more TIO. (The spec does say we must take space-separated integers, so that might cost a little unless we're just allowed to ignore that nowadays?)

@JonathanAllan Thanks, that's really clever! For older challenges, I typically ignore the "space separated" inputs rule if they have them, unless the OP complains, because it just seems unnecessary and outdated. But I suppose you could argue that they are space separated on the command line when provided locally rather than on TIO, if someone really insisted on space separated input

I don't think the 17-byter solves the challenge, as 9 8 7 / 6 5 4 / 3 2 1 is pretty far from semi-magic.

@Bubbler Good point, I've reverted the edit. Can't believe I didn't noticed that

@Bubbler oh, yeah the four cannot be combined with a hyper, so 18 it is.

@JonathanAllan A good catch on the sorting and f either way, thanks!

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


text:
Reduced Row-Echelon Form of a Matrix
The goal of this challenge is to create a program that takes in a matrix and outputs its reduced row-echelon form.

A matrix is in reduced row-echelon form if it meets all of the
  following conditions:

If there is a row where every entry is zero,
  then this row lies below any other row that contains a nonzero entry.
The leftmost nonzero entry of a row is equal to 1.
The leftmost nonzero entry of a row is the only nonzero entry in its column.
Consider any two different leftmost nonzero entries, one located in
  row i, column j and the other located in row s, column t. If s>i, then
  t>j.

Source

The general process to transform the matrix is:

Deal with each row i from 1 to n in turn, and work across the columns j from 1 to m skipping any column of all zero entries.
Find the next column j with a nonzero entry.
Interchange rows, if necessary, so that the pivot element A(i,j) is nonzero.
Make the pivot equal to 1 by dividing each element in the pivot row by the value of the pivot.
Make all elements above and below the pivot equal to 0 by subtracting a suitable multiple of the pivot row from each other row.
Repeat for all rows.

If you want to read more on this type of matrix, view the Wikipedia article on it and a tool and article(steps above) that shows the steps to transform the matrix.
As for the actual challenge, here it goes:
The input can be given in any way you wish through STDIN or equivalent, just please explain it in your answer. The output will be the reduced row-echelon form of the input in the same form as the input through STDOUT or equivalent. Standard loopholes are not allowed and external libraries or functions that do this task are also not allowed (TI-BASIC's rref( command, for example). You may write a full program or function. This is code golf, lowest BYTES wins. Good luck!
Example Input: [[2,1,1,14][-1,-3,2,-2][4,-6,3,-5]]
Example Output: [[1,0,0,1][0,1,0,5][0,0,1,7]]

You need to give some explanation of the reduction process here, so this question still makes sense when those links go bad.

Added an explanation. Hope its detailed enough.

Are we allowed to use `ref()``, linear equation solvers, or any other builtins that almost solve the problem?

As long as there is a more complex step that just something like method(ref(matrix)), then I would say go ahead

R, 232 bytes
function(M){p=1;R=nrow(M);C=ncol(M);for(r in 1:R){if(C<=p)break;i=r;while(M[i,p]==0){i=i+1;if(R==i){i=r;p=p+1;if(C==p)return(M)}};t=M[i,];M[i,]=M[r,];M[r,]=t;M[r,]=M[r,]/M[r,p];for(i in 1:R)if(i!=r)M[i,]=M[i,]-M[r,]*M[i,p];p=p+1};M}

This is just an implementation of the usual Gaussian elimination algorithm.
Ungolfed:
rref <- function(M) {
    p <- 1
    R <- nrow(M)
    C <- ncol(M)
    for (r in 1:R) {
        if (C <= p)
            break
        i <- r
        while (M[i, p] == 0) {
            i <- i + 1
            if (R == i) {
                i <- r
                p <- p + 1
                if (C == p)
                    return(M)
            }
        }
        t <- M[i, ]
        M[i, ] <- M[r, ]
        M[r, ] <- t
        M[r, ] <- M[r, ] / M[r, p]
        for (i in 1:R)
            if (i != r)
                M[i, ] <- M[i, ] - M[r, ] * M[i, p]
        p <- p + 1
    }
    M
}

I think you may be able to get away with M[c(i,r),]=M[c(r,i),] rather than t=M[i,];M[i,]=M[r,];M[r,]=t

Vyxal, 29 23 bytes
(ƛh/;ḣ„D"„-‟wJƛǓ:h±*]ƛǓ

it's so complex that I forget how it works, but it does work I guess...?
29 bytes by me
24 bytes by @emanresu A
23 bytes(current) by great god @lyxal
Try it Online!

you forgot to update the tio link to reflect 23 bytes.


text:
Construct a companion matrix
You have a number of polynomials who are lonely, so make them some companions (who won’t threaten to stab)!
For a polynomial of degree n,  there is an n by n companion cube matrix for it. You need to make a function that accepts a list of coefficients for a polynomial in either ascending (a + bx +cx^2 + …) or descending (ax^n + bx^(n-1) + cx^(n-2)+…) order (but not both) and output the companion matrix.
for a polynomial c0 + c1x + c2x^2 + ... + cn-1x^(n-1) + x^n,
its companion matrix is
     (0, 0, 0, ..., -c0  ),
     (1, 0, 0, ..., -c1  ),
     (0, 1, 0, ..., -c2  ),
     (...................),
     (0, 0, ..., 1, -cn-1)

note that the coefficient for x^n is 1. For any other value, divide all the rest of the coefficients by x^n's. Additionally, the 1's are offset from the diagonal.
If the language you’re using already contains a function or module that does this, you can’t use it – you must write your own.
For instance, if you had 4x^2 – 7x + 12, the coefficients in ascending order are (12, -7, 4) and descending order (4, -7, 12). The function or program should output [(0, -3.0), (1, 1.75)] for either order. Specify which order your code accepts. Minimum polynomial should be a quadratic. Coefficients are restricted to real numbers.
Below are examples – your output does not have to match the pretty formatting but it should output the rows (in the ()) of the matrix in order.
Ascending order:
input:
    [3., 7., -5., 4., 1.]
output:
    [(0, 0, 0, -3.),
     (1, 0, 0, -7.),
     (0, 1, 0,  5.),
     (0, 0, 1, -4.)]

input:
    [-4., -7., 13.]
output:
    [(0, 0.30769231),
     (1, 0.53846154)]

input:
    [23., 1., 92., 8., -45., 88., 88.]
output:
    [(0, 0, 0, 0, 0, -0.26136364),
     (1, 0, 0, 0, 0, -0.01136364),
     (0, 1, 0, 0, 0, -1.04545455),
     (0, 0, 1, 0, 0, -0.09090909),
     (0, 0, 0, 1, 0,  0.51136364),
     (0, 0, 0, 0, 1, -1.        )]

Descending order:
input:
    [1., 4., -5., 7., 3.]
output:
    [(0, 0, 0, -3.),
     (1, 0, 0, -7.),
     (0, 1, 0,  5.),
     (0, 0, 1, -4.)]

input:
    [13., -7., -4.]
output:
    [(0, 0.30769231),
     (1, 0.53846154)]

input:
    [88., 88., -45., 8., 92.,1., 23.]
output:
    [(0, 0, 0, 0, 0, -0.26136364),
     (1, 0, 0, 0, 0, -0.01136364),
     (0, 1, 0, 0, 0, -1.04545455),
     (0, 0, 1, 0, 0, -0.09090909),
     (0, 0, 0, 1, 0,  0.51136364),
     (0, 0, 0, 0, 1, -1.        )]

Dennis wins with 20 bytes!

Coefficients are real (not complex), right?

Are programs valid, or is it functions only? (Keep in mind that restricting the contest to functions disallows interesting langauges without functions.)

What's the minimum degree polynomial we have to account for?

CJam, 23 20 bytes
{)W*f/_,,_ff=1f>\.+}

This is a function that pops the input (ascending order) from the stack and pushes the output in return.
Try it online in the CJam interpreter.
How it works
)   e# Pop the last element from the input array.
W*  e# Multiply it by -1.
f/  e# Divide the remaining array elements by this product.
_,  e# Push a copy of the array and compute its length (L).
,_  e# Push [0 ... L-1] twice.
ff= e# For each I in [0 ... L-1]:
    e#   For each J in [0 ... L-1]:
    e#     Push (I==J).
    e# This pushes the L x L identity matrix.
1f> e# Discard the first element of each row, i.e., the first column.
\   e# Swap the result with the modified input.
.+  e# Vectorized append; append the input as a new column.

CJam, 32 31 28 bytes
0q~)f/f-_,(_,\0a*1+fm<~]W%z

Try it online
This takes the input in ascending order, using the CJam list format. Sample input:
[-4.0 -7.0 13.0]

Explanation:
0     Push a 0 for later sign inversion.
q~    Get and interpret input.
)     Pop off last value.
f/    Divide all other values by it.
f-    Invert sign of values.
_,    Get count of values, which corresponds to n.
(     Decrement by 1.
_,    Create list of offsets [0 1 ... n-1] for later.
\     Swap n-1 back to top.
0a*   Create list of n-1 zeros.
1+    Append a 1. This is the second-but-last column [0 0 ... 0 1].
fm<   Apply rotation with all offsets [0 1 ... n-1] to column.
~     Unwrap the list of 0/1 columns.
]     Wrap all columns
W%    Invert their order from last-to-first to first-to last.
z     Transpose to get final matrix.
`     Convert to string for output.

APL, 40 30 bytes
{(-n↑⍵÷⊃⊖⍵),⍨⍉1↓⍉∘.=⍨⍳n←1-⍨≢⍵}

Accepts input in ascending order.
Explanation:
{
                        n←1-⍨≢⍵    ⍝ Define n = length(input)-1
                   ∘.=⍨⍳           ⍝ Create an n×n identity matrix
               ⍉1↓⍉                ⍝ Drop the leftmost column
            ,⍨                     ⍝ Append on the right:
  (-n↑⍵                            ⍝ n negated coefficients,
       ÷⊃⊖⍵)                       ⍝ divided by the n+1st
}

Try it online

Julia, 43 bytes
c->rot180([-c[2:(n=end)]/c[] eye(n-1,n-2)])

This uses descending order for the input. It constructs the matrix rotated 180 degrees, in order to enable more efficient use of "eye", then rotates the matrix into the right orientation.

Julia, 64 44 bytes
c->(k=c[n=end];[eye(n-=1)[:,2:n] -c[1:n]/k])

Accepts a vector of the coefficients in ascending order.
Ungolfed:
function f(c::Array)
    # Simultaneously define k = the last element of c and
    # n = the length of c
    k = c[n = end]

    # Decrement n, create an n×n identity matrix, and exclude the
    # first column. Horizontally append the negated coefficients.
    [eye(n-=1)[:,2:n] -c[1:n]/k]
end

Try it online
Saved 20 bytes thanks to Glen O!

R, 71 59 bytes
Takes input in ascending order.
function(x)cbind(diag(n<-length(x)-1)[,2:n],-x[1:n]/x[n+1])

Ungolfed:
f <- function(x) {
    # Get the length of the input
    n <- length(x)-1

    # Create an identity matrix and exclude the first column
    i <- diag(n)[, 2:n]

    # Horizontally append the negated coefficients divided
    # by the last one
    cbind(i, -x[1:n]/x[n+1])
}

Matlab, 66 bytes
function y=f(c)
n=numel(c);y=[[0*(3:n);eye(n-2)] -c(1:n-1)'/c(n)];

It uses ascending order for the input, with format [3., 7., -5., 4., 1.] or [3. 7. -5. 4. 1.].
Try it online (in Octave).
Example (in Matlab):
>> f([23., 1., 92., 8., -45., 88., 88.])
ans =
                   0                   0                   0                   0                   0  -0.261363636363636
   1.000000000000000                   0                   0                   0                   0  -0.011363636363636
                   0   1.000000000000000                   0                   0                   0  -1.045454545454545
                   0                   0   1.000000000000000                   0                   0  -0.090909090909091
                   0                   0                   0   1.000000000000000                   0   0.511363636363636
                   0                   0                   0                   0   1.000000000000000  -1.000000000000000

If a program is valid (instead of a function), with stdin and stdout:
Matlab, 59 bytes
c=input('');n=numel(c);[[0*(3:n);eye(n-2)] -c(1:n-1)'/c(n)]

I think you can do n=numel(c=input(''));

@ThomasKwa Thanks! However, that's not valid syntax in Matlab. n=numel(input('')) would be valid, but I need to use c again later

Sorry; it worked in Octave where I tested it.

Octave, 45 44 bytes
Assuming c is a column vector with the coefficient of the highest power of x at the end.
@(c)[eye(n=rows(c)-1)(:,2:n),-c(1:n)/c(end)]

Old version:
@(c)[eye(n=numel(c)-1)(:,2:n),-c(1:n)/c(end)]

High five, Julia!

Python 2, 141 bytes
My own attempt:
def C(p):
 c,r=p.pop(0),range;d=[-i/c for i in p];n=len(d);m=[[0]*n for i in r(n)]
 for i in r(n-1):m[i][i+1]=1
 m[-1]=d[::-1];return zip(*m)

Takes a list of the coefficients in descending order and first builds the transpose of the companion matrix - known for stabbing and being talkative. The return uses zip to produce the transpose of this transpose to get the actual matrix.
>>> C([1., 4., -5., 7., 3.])
[(0, 0, 0, -3.0), (1, 0, 0, -7.0), (0, 1, 0, 5.0), (0, 0, 1, -4.0)]

JavaScript (ES6) 85
Ascending order.
Test running the snippet below in any EcmaScript 6 compliant browser.

f=c=>alert(c.map((v,i)=>c.map((x,j)=>++j-i?j-c.length?0:-v/m:1),m=c.pop()).join(`
`))

// test
// redefine alert to write into the snippet body
alert=x=>O.innerHTML+=x+'\n'

function test() {
  v=I.value.match(/\d+/g)
  I.value=v+''
  alert(v)
  f(v)
}

test()
<input value='23.,1.,92.,8.,-45.,88.,88.' id=I><button onclick="test()">-></button>

TI-BASIC, 50 bytes
Ans→X
List▶matr(ΔList(Ans-cumSum(Ans)),[A]
dim(Ans
augment(augment(0randM(Ans-2,1),identity(Ans-2))ᵀ,[A]∟X(Ans)⁻¹

Takes input in ascending order. Note that this will not work for polynomials of degree <2, because TI-BASIC does not support empty matrices or lists. Pending a ruling from OP, I can fix this at the cost of a few bytes.
First, we store the list into ∟X to use the last element later; then, we calculate ΔList(Ans-cumSum(Ans)), which is just the negated list with the last element chopped off, and convert it to a column vector. Since List▶matr( doesn't modify Ans, we can use the next line to take the dimension of the list, which we use thrice. TI-BASIC doesn't have vertical concatenation, so we need to take transposes and horizontally concatenate. In the last line, [A]/∟X(Ans wouldn't work because matrices can be multiplied by scalars but not divided.
An aside: To generate the row vector of zeros, we take advantage of the rarely useful randM( command. randM( creates a random matrix, but its entries are always random integers between -9 and 9 (!), so it's really only useful to create zero matrices.

Pari/GP, 42 bytes
p->concat(matid(#p-1),-p[^#p]~/p[#p])[,^1]

Try it online!


text:
Four steps to the left: vipers. Four steps to the right: a cliff. Don't die!
Introduction
Suppose for a moment that the vipers and cliff are only two steps away, instead of three.
            o
           ---
Hsss!       |
 ';;' ___  /_\  ___  _
                      |

You are, unfortunately, a captive of a sadistic torturer. You must take a step either to the left or to the right every turn. If you don't, they shoot you dead instantly. You are allowed to plan out your steps beforehand, but once you take your first step, you can't change your plan. (And no dawdling either; they'll shoot you.)
Suddenly, a bright idea comes to mind...

Ah! I can just alternate stepping right and left! Step right, step left, step right, step left, and so on...

Ah ah ah, not so fast. Like I said, the torturer is sadistic. They get to choose whether you take every step, or every second step, or every third step, and so on. So if you naively choose the sequence RLRLRL... then they can force you to take every second step, which starts with LL. Uh oh! You've been bitten by vipers! Blackness swoops over you and all else fades away...
Actually no, you're not dead yet. You still have to come up with your plan. After thinking about it for a few minutes, you realize you are doomed. There is no way to plan out a series of steps that will guarantee your survival. The best you can come up with is RLLRLRRLLRR.1 Eleven safe steps and no more. If the twelfth step is R, then the Torturer will make you take every step and then the last three steps send you off the cliff. If the twelfth step is L, then the Torturer will make you take every third step (LRLL), which puts you right in the brood of vipers and their lethal bites.
You pick R as the twelfth step, hoping to delay your demise as long as possible. With the wind roaring in your ears, you wonder to yourself...

What if I had three steps?

Spoiler alert!
You would still die. As it turns out, no matter how many steps you have, there will be some point where no matter what choice you make, there is a sequence of steps your Torturer can pick to ensure you meet your deadly fate.2 However, when the vipers and cliff are three steps away, you can take a total of 1160 safe steps and when they're four steps away, there are at least 13,000 safe steps!3
The challenge
Given a single integer n < 13000, output a sequence of n safe steps, assuming the cliff and the vipers are four steps away.
Rules

Can be either a full program or a function.
Input can be taken through STDIN or equivalent, or as a function argument.
Output must have two distinct characters (which can be +/-, R/L, 1/0, etc.).
Any whitespace in the output doesn't matter.
Hard-coding a solution is not allowed. That would trivialize this challenge.
Your program should (in theory) finish in a decent amount of time. As in, n=13000 might take like a month, but it shouldn't take a thousand years or more. That is, no brute force. (Well, at least try to avoid it.)
Life bonus: provide a series of 2000 safe steps. If you do this, the Torturer will be so impressed by your tenacity, perseverance, and forethought that they'll let you live. This one time. (Treat this sequence as a binary number and provide the decimal equivalent for verification. This is intended to reward answers that finish quickly as answers are allowed to take a very long time.)
Score: bytes, unless you qualify for the bonus - multiply by 0.75.

1 There is a good explanation of this problem and "solution" by one of the stars of Numberphile, James Grime, over on his YouTube channel here: https://www.youtube.com/watch?v=pFHsrCNtJu4 .
2 This 80-year-old conjecture, known as Erdos' discrepancy problem, was proved very recently by Terence Tao. Here is a very nice article on Quanta Magazine about this: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .
3 Source: A SAT Attack on the Erdos Discrepancy Conjecture, by Boris Konev and Alexei Lisitsa. Retrieved from here: http://arxiv.org/pdf/1402.2184v2.pdf .

So, if I make a solution for n=13000, will the first 2000 instructions of it win a bonus? Seems pointless, so you probably meant something else?

@anatolyg: All solutions should theoretically be able to handle n=13000 within like, a year, maybe ten. Are you going to wait a month for n=2000? Probably not. And if you do, then you deserve the bonus anyway.

Java, 915 * 0.75 = 686.25
import java.util.*;class E implements Comparable<E>{static
int n,m,t,u;byte[]a;int k=2,b,d;E(){a=new byte[5];a[1]=13;}E(E
x){a=Arrays.copyOf(x.a,n+1);k=x.k;d=x.d;b=x.b;}int
g(int x){return(a[x]+1)%3-1;}void s(int x,int y){a[x]=(byte)(a[x]/3*3+(y+3)%3);}void
S(int x,int y){a[x]=(byte)(a[x]%3+(y+3)*3);}E
w(int x){if(g(k)==-x)return null;E e=new E(this);e.s(k,x);e.S(e.k++,x);for(m=0;++m<k;)if(k%m<1){u=e.a[m]/3-3+x;if(u==(k<9?2:4)*x)return
null;e.S(m,u);if(u==3*x){e.b++;if(k+m<=n){if(e.g(k+m)==x)return
null;e.s(k+m,-x);}}}return e;}public int compareTo(E o){m=d-o.d+(b-o.b)/60+(o.k-k)/150;return
m==0?o.k-k:m;}public static void main(String[]a){n=Integer.valueOf(a[0]);Queue<E>q=new PriorityQueue<>();q.add(new
E());for(;;){E x=q.remove(),y;if(x.k>n){for(t=0;++t<x.k;)System.out.print((x.g(t)+1)/2);return;}t=x.g(x.k<9?1:x.k%9==0?x.k/9:x.k%9);y=x.w(t);if(y!=null)q.add(y);y=x.w(-t);if(y!=null){y.d++;q.add(y);}}}}

Input is taken as a command-line argument.
This tries almost all possibilities (the only restriction is that the first 8 steps should only go within -1..1), going step by step, using a magic voodoo heuristic to choose which way to try first.
It solves 2000 and even 4000 within 1 second on my (fairly fast) computer. Needs more RAM for bigger numbers; the largest input I solved within 8GB is 5023 and it took about 30 seconds.
Decimal representation of the solution for 2000 steps, as requesed for the bonus:
67629177464446960798008264442022667063957880432486338092706841703491740570274032860458934082821213021464065304260003487277917407152662394728833698812373924467640518368465012204980858438160127647802572983143425507448999967241207186701518207195015015739598846687434709056793597015487555707466358473564611432637890414593517116857771284711814076853125419306285869381974622557155019992727242896503018802441210966188045211779436703341152749688824296759097963388158731237092792251164105828728858516951458791084595247591674731645830905744761534078963607725435881491831508342871545788662307953494333833994658998

Append Yb to it in CJam to convert back to binary.
About the heuristic: first, there is a pattern I'm using: every 9 steps try to repeat the first 9, except every (9*x)th step tries to repeat the x'th step. This is inspired from the solution I downloaded and used (hardcoded) in my python answer.
I'm keeping track of the number of times I deviated from the pattern, and also the number of times I got to an "edge" (1 step from dying). The heuristic function is basically a weighted combination of those 2 numbers and the number of steps taken so far.
The heuristic could be further tweaked to improve the speed, and there are several ways to add a random factor into it too.
In fact, I've just read about multiplicative functions in relation to this problem, and it looks like that can provide a significant improvement (TODO: implement this later).
Ungolfed and commented:
import java.util.*;

public class Erdos implements Comparable<Erdos> {
    static int n; // input (requested number of steps)
    static int m, t, u; // auxiliary variables

    byte[] a; // keeps each step and sum combined into 1 byte
    int k = 2; // number of steps + 1 (steps are 1-based)
    int edge; // number of times we got to an edge
    int diff; // number of differences from the expected pattern

    // start with one step
    Erdos() {
        a = new byte[5];
        set(1, 1);
        setSum(1, 1);
    }

    // copy constructor
    Erdos(Erdos x) {
        a = Arrays.copyOf(x.a, n + 1);
        k = x.k;
        diff = x.diff;
        edge = x.edge;
    }

    // get the x'th step (can be -1, 0 or 1)
    int get(int x) {
        return (a[x] + 1) % 3 - 1;
    }

    // set the x'th step
    void set(int x, int y) {
        a[x] = (byte) (a[x] / 3 * 3 + (y + 3) % 3);
    }

    // get the sum of every x'th step (should be within -3..3)
    int getSum(int x) {
        return a[x] / 3 - 3;
    }

    // set the sum of every x'th step
    void setSum(int x, int y) {
        a[x] = (byte) (a[x] % 3 + (y + 3) * 3);
    }

    // try to add a step with value x (1 or -1)
    Erdos grow(int x) {
        if (get(k) == -x) // predetermined step doesn't match
            return null;
        Erdos e = new Erdos(this);
        e.set(k, x);
        e.setSum(e.k++, x);
        for (m = 0; ++m < k;)
            if (k % m < 1) { // check all divisors of k
                u = e.getSum(m) + x; // updated sum
                if (u == (k < 9 ? 2 : 4) * x) // use limit 2 for the first 8 steps, 4 for the rest
                    return null; // dead
                e.setSum(m, u);
                if (u == 3 * x) { // we're at an edge
                    e.edge++;
                    if (k + m <= n) { // predetermine future step - should be going back
                        if (e.get(k + m) == x) // conflict
                            return null;
                        e.set(k + m, -x);
                    }
                }
            }
        return e;
    }

    public int compareTo(Erdos o) { // heuristic function
        m = diff - o.diff + (edge - o.edge) / 60 + (o.k - k) / 150;
        return m == 0 ? o.k - k : m;
    }

    public static void main(String[] a) {
        n = Integer.valueOf(a[0]);
        Queue<Erdos> q = new PriorityQueue<>();
        q.add(new Erdos());
        for (;;) {
            Erdos x = q.remove(), y;
            if (x.k > n) { // we made it
                for (t = 0; ++t < x.k;)
                    System.out.print((x.get(t) + 1) / 2);
                return;
            }
            t = x.get(x.k < 9 ? 1 : x.k % 9 == 0 ? x.k / 9 : x.k % 9); // next step based on the pattern
            y = x.grow(t);
            if (y != null)
                q.add(y);
            y = x.grow(-t);
            if (y != null) {
                y.diff++;
                q.add(y);
            }
        }
    }
}

"later" waits over a year

Python 2, 236 bytes
n=input();r=len;u=[("",[0]*(n//4))]
while n>r(u[-1][0]):
 y,t=u.pop()
 for c in 0,1:
  s=t[:];u+=(y+"LR"[c],s),
  for i in range(r(s)):
   if-~r(y)//-~i*-~i==-~r(y):s[i]+=2*c-1;
   if abs(s[i])>3:u.pop();break;
print(u[-1][0])

This is fairly fast, for a brute-force-ish method, only taking a few seconds for n=223, but much longer for n>=224.
Explanation:
Keep track of a list of string-list pairs (s,u), where the list u is such that u[i] is the current position after following every ith step in the string. For each string in the list, try to add "L" or "R", then change the values in the list that intersect. (i.e. if the resulting string has length 10, add or subtract 1 from positions 1,2,5 and 10, according to the directions you moved). If you exceed 3 or -3 throw the new pair away, otherwise keep it in the list. The longest strings are kept at the end. Once you have a string of length n, return it.

Why python 2/3?

It works the same in either one. Should I specify one of them?

Probably you should.  I was just wondering because I didn't know that // was availible in python 2.

Python 2, 729 bytes
n=0
for x in"eJytVU2LwyAQPWzTvZjjspcsxFYTBdNuQSEF+///1jp+p5o0hYVSBl9nfOObNz1MlAgqzMcEEwQkDyIkFpDYCW0UnChbyZJiK2sfhDcYmu9hT0GdIPQvLduAmoCvvqEssvq84CVCpLzrNcOOspLhY6/KswB6FmoSxGPBcWts7lsMp/0q83da1hgC6k7GoqBir1ruAFIVvWIdTi++oGIAyZw8mkuG03uDDc+rEsSWTmFBwbLgtTF8hl1e/lpCigR7+pM5V9lIqVJBjStzKNRRQDp6UOrvwga6VFrGcWz6YHwLNYWUYeZfWO/DQTq7i4dAxixeszmtFEw7Cr5v9R3lRVF55TDzY6QRrSfzF9NLE7lAZ+vLnGgYLZ/FlCuoRcOugeFduHTqRWmyh1J91XpIndIbEk8jifL8hs8qQ8vjAVoGqhK5Tm/O5svpXd82QH4Azq05kYnhj93PzLbcTisFzXWfDqIC5zsq3jU7UUhSh1R3L4+i4HCXKlrGyywSBttPr2zpL4gCDPtk2HPN5tgZFomzSDPfGAlASus+e4KlLcjS0vPQ0f5/mR/r1s4PcxsgMLRSMp617AveCuup2OCAPBT6yltWrPO9azsbp6fphR87Lc7VzcbEt5F4Ydg/NzhXTA==".decode("base64").decode("zip"):n=n*64+ord(x)
print bin(n)[2:input()+2]

I think this qualifies for the bonus too if the idea is "to reward answers that finish quickly".
However, this is a hard-coded answer, which is not in the spirit of the challenge (although not explicitly disallowed when I wrote it).

Finally, an answer! d;-)

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