text:
64 bit ASCII weaving
Input
Two integers:

A non-negative integer W in the range 0 to 2^64-1, specifying the weave.
A positive integer S in the range 1 to 255, specifying the side length.

These can be taken in whichever order suits you.
Output
An S by S ASCII representation of the requested weave (S newline separated strings of S characters with an optional trailing newline). The weave is defined by the weave number W as follows:
Convert W to binary and split into 8 bytes. The first (most significant) byte defines the top row, from left (most significant bit) to right. The next byte defines the next row, and so on for 8 rows. The weave number defines an 8 by 8 square which should be tiled over the required area starting from the top left. That is, its top left corner should correspond to the top left corner of the area to be covered.
Every 0 should be displayed as a | and every 1 should be displayed as a -
Examples
Input: 0 8
Ouput:
||||||||
||||||||
||||||||
||||||||
||||||||
||||||||
||||||||
||||||||

Input: 3703872701923249305 8
Output:
||--||--
|--||--|
--||--||
-||--||-
||--||--
|--||--|
--||--||
-||--||-

Input: 3732582711467756595 10
Output:
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--

Input: 16141147355100479488 3
Output:
---
|||
---

Leaderboard Snippet
(using Martin's template)

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

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

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

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

K, 20
{y#y#'"|-"8 8#0b\:x}

.
             0b\:x    // convert to binary
         8 8#         // reshape into an 8x8 boolean matrix
     "|-"             // index into this char vector using the booleans as indices
  y#'                 // extend horizontally
y#                    // extend vertically

.
k){y#y#'"|-"8 8#0b\:x}[3703872701923249305j;10]
"||--||--||"
"|--||--||-"
"--||--||--"
"-||--||--|"
"||--||--||"
"|--||--||-"
"--||--||--"
"-||--||--|"
"||--||--||"
"|--||--||-"

k){y#y#'"|-"8 8#0b\:x}[3703872701923249305j;8]
"||--||--"
"|--||--|"
"--||--||"
"-||--||-"
"||--||--"
"|--||--|"
"--||--||"
"-||--||-"

It really doesn't get simpler or more straightforward than this!

@JohnE That's only true for people who understand K. ;)

CJam, 33 31 bytes
q~:X;2b64Te["|-"f=8/{X*X<z}2*N*

Test it here.
Explanation
q~      e# Read and eval input.
:X;     e# Store the side length in X and discard it.
2b      e# Convert to base 2.
64Te[   e# Left-pad to length 64 with zeroes.
"|-"f=  e# Select '|' for 0 and '=' for 1.
8/      e# Split into chunks of 8 bits.
{       e# Do the following twice:
  X*    e#   Repeat lines X times (to ensure we have enough of them).
  X<    e#   Truncate them to exactly X lines.
  z     e#   Transpose the grid.
        e#   The transpose ensures that the second pass tiles the columns, and that the
        e#   grid is oriented correctly again after both passes are done.
}2*
N*      e# Join lines by newline characters.

I applaud you :). This is probably the quickest answer in PPCG history

@BetaDecay The benefit of golfing languages is that you have less to type, so you can code faster. :P

Geez, even went to the trouble of editing the tags before answering! Somebody spends too much time golfing ;P

Is this intended output: link

@Kenzie that input number is bigger than 2^64-1.

Java, 110 109  107 Bytes
My code is in the form of an anonymous lambda function that takes a long and an int then returns a String.
(w,s)->{String b="";for(int j,i=s--;i-->0;b+='\n')for(j=s;j>=0;)b+=(w>>8*(i%8)+j--%8)%2<1?'|':45;return b;}

Complete testable class
import java.util.function.BiFunction;
public class AsciiWeave {
    public static void main(String[] args){
        BiFunction<Long,Integer,String> weave =
            (w,s)->{String b="";for(int j,i=s--;i-->0;b+='\n')for(j=s;j>=0;)b+=(w>>8*(i%8)+j--%8)%2<1?'|':45;return b;}}
        ;
        System.out.println(weave.apply(Long.valueOf(args[0]),Integer.valueOf(args[1])));
    }
}

I must say, I'm not used to being beaten by Java. :P Nice work.

Thanks @AlexA.! Lambdas really make java more usable for golfing: (w,s)-> instead of String w(long w,int s) is a big save right off the bat.

@Ypnypn that should definitely work

Wow, this is impressive. Good job.

105 bytes

Matlab, 86 80 bytes
function f(W,S)
a='|-';x=de2bi(typecast(W,'uint8'))+1;s=8-mod(0:S-1,8);a(x(s,s))

Thanks to Hoki for his suggestion, which led me to save me 6 bytes.
Example:
>> W = uint64(3732582711467756595)
W =
  3732582711467756595
>> S = uint8(10)
S =
   10
>> f(W,S)
ans =
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--

de2bi will save you a few more characters ;-)

@Hoki! Thanks! I thought about it... but it gives a different order of the result

yep, you have to reverse a='|-' to a='-|'. And use x=de2bi(typecast(W,'uint8'))+1;

@Hoki I managed to fit de2bi just moving the 9- term (used for reversal). Thanks again!

J, 28 bytes
'|-'{~]$"1]$8 8$_64{.#.inv@[

Usage:
   3732582711467756595 ('|-'{~]$"1]$8 8$_64{.#.inv@[) 10
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--
--||--||--
||--||--||
||--||--||
--||--||--

Explanation (right to left):
#.inv@[   binary representation vector of S
_64{.     padded with 0-s from the right to length 64
8 8$      reshaped in an 8 by 8 matrix
]$"1]$    tiled to a W by W size
'|-'{~    select | or - based on matrix element values

Try it online here.

Julia, 145 bytes
f(w,s)=(A=map(i->i=="1"?"-":"|",reshape(split(lpad(bin(w),64,0),""),8,8))';for i=1:s A=hcat(A,A)end;for i=1:s println(join(A[i>8?i%8:i,1:s]))end)

This creates a function that accepts two integers and prints to stdout.
Ungolfed + explanation:
function f(w,s)
    # Convert w to binary, left-padded with zeros to length 64
    b = lpad(bin(w), 64, 0)

    # Create an 8x8 array of | and -
    A = transpose(map(i -> i == "1" ? "-" : "|", reshape(split(b, ""), 8, 8)))

    # Horizontally concatenate A to itself s times
    for i = 1:s
        A = hcat(A, A)
    end

    # Print the rows of A, recycling as necessary
    for i = 1:s
        println(join(A[i > 8 ? i % 8 : i, 1:s]))
    end
end

This is pretty long and I'm sure it can be made much shorter. Working on it.

CJam, 30 28 27 bytes
q~_2m*W%/ff{8f%8bm>"|-"=}N*

Try it online in the CJam interpreter.

Python, 77
lambda w,s:''.join('|-'[w>>~n/s%8*8+~n%s%8&1]+'\n'[~n%s:]for n in range(s*s))

For each of the s*s values of n:

Compute the coordinates via divmod (i,j)=(n/s,n%s)
Compute the location in the tiling as (i%8,j%8)
Compute the appropriate bit position as 8*(i%8)+(j%8)
Extract that bit of w by shifting w that many spaces with right and take the last bit with &1.
Join one of '|-' at that position
Add the newline at the end of every row whenever n%s==0

Actually, all that ends up getting the tiling backwards, since it reads w from the end. We fix this by using ~n in place of n. I tried a recursive approach instead, but it turned out slightly longer.
The expression w>>~n/s%8*8+~n%s%8&1 is a miracle of operator precedence.

C, 160 135 bytes
i;main(s,v)char**v;{s=atoi(v[2]);for(;i++<s*s+s;)putchar(i%(s+1)?strtoull(v[1],0,10)&1ull<<63-(i/(s+1)*8+(i%(s+1)-1)%8)%64?45:'|':10);}

Some more golfing can be done here and need an explanation, but I don't have time at the moment :)
Ungolfed:
i;

main(s,v)
char**v;
{
    s=atoi(v[2]);
    for(;i++<s*s+s;)
        putchar(i%(s+1) ? /* print dash or pipe, unless at end of row, then print newline */
            /* Calculating which bit to check based on the position is the tough part */
            strtoull(v[1],0,10) & 1ull << 63-(i/(s+1)*8+(i%(s+1)-1)%8)%64 ? /* If bit at correct index is set, print dash, otherwise pipe */
                45 /* dash */
                : '|' /* pipe */
            : 10); /* newline */
}

Could you format the title like "C, 100 bytes"? That way it'll show up in the leaderboard better.

Yes, sorry about that.

I'm having trouble getting your code to run correctly on my environment. Are you compiling with any specific options?

@dohaqatar7 It looks like some Linux environments require stdlib.h to be included explicitly. I wasn't forced to include it earlier when I tested on CentOS (I believe that's what I was on). Now on Ubuntu, I can't get it to run without compiling like so: gcc -include stdlib.h w.c

Makes sense I tested on Ubuntu

Python 2, 132 Bytes
Certainly not the most elegant solution, and it's barely shorter than C, but it's a start.. Input is taken comma-separated.
k,n=input()
k=[`['|-'[int(x)]for x in'{0:064b}'.format(k)]`[2::5][i*8:i*8+8]*n for i in range(8)]*n
for j in range(n):print k[j][:n]

Pyth, 31 30 bytes
L<*QbQjbyyMcs@L"|-".[Z64jvz2 8

The input should be on two lines, W then S.
Try it here
Explanation
L                              # define y(b):
  *Qb                          #   b, repeated Q (the second input) times
 <   Q                         #   cut to length Q

                        jvz2   # convert the first input to binary
                   .[Z64       # pad with 0's to length 64
             @L"|-"            # map the digits to the appropriate character
            s                  # convert the list of characters to a string
           c                 8 # chop into 8 strings
         yM                    # extend each string to the correct size
        y                      # extend the list of strings to the correct size
      jb                       # join with newlines


text:
Avoid the Bullet Bills
In 2D Mario, Bullet Bill cannons are two units tall. The Bullet Bill is fired out of the upper unit and travels in a straight line (parallel to the x axis).
Mario is two units tall when standing up and one unit tall when ducking. His jump height is three units. It takes him 0.5 seconds to reach the full height and 0.5 seconds to come back down.
Challenge
Write a program that helps Mario avoid an incoming Bullet Bill. He may have to jump, duck, or do nothing.
Input
The input will come in the format [bullet_bill_position] [direction] [speed] [mario_position].

bullet_bill_position consists of two space-separated integers, x and y. This represents the coordinates of the upper unit of the cannon. The bullet bill will fire from this location.
direction will either be left or right (string).
speed is the speed of the Bullet Bill in units per second.
mario_position consists of x and y and represents the coordinates that Mario is standing on.

Output
[action] [wait_time]

action will be one of three strings: duck, jump, or nothing.
wait_time only applies to jump. It represents how long Mario should wait before jumping over the Bullet Bill. If action is not jump, this will be left blank.

Notes

The ground will always be right underneath Mario's feet.
Bullet Bills are only one unit tall and one unit wide. Mario will be safe if it passes one unit above his head.
Mario will be safe if he lands on the Bullet Bill. Hitting the side or bottom will kill him.
There will often be more than one solution. You only have to output one of them.
Numerical input will always be integers. However, output may sometimes need to have floats/doubles.

Test Cases

Input: 5 1 left 2.5 0 0
Possible Output: jump 1.5
Explanation: The Bullet Bill will be at Mario's feet in 2 seconds. Mario will jump at 1.5 and touch back down at 2.5. The Bullet Bill passed safely underneath him.
Another Possible Output: jump 1
Explanation: If Mario jumps at 1, he will touch back down at 2 and land on the Bullet Bill.

Input: 0 3 right 100 5 0
Possible Output: nothing
Explanation: The Bullet Bill will pass very quickly over Mario's head. He will be safe.

Input: 0 2 right 1 5 0
Output: duck
Explanation: The Bullet Bill will go where Mario's head would've been.

Rules

You can write a full program or function.
I/O should be to stdin and stdout.

Scoring
This is code-golf. Your score is the number of bytes. The solution with the lowest score in one week will win. Good luck!

Just want to make sure I'm interpreting everything, in a 2x1 column where a Bullet Bill is on top and Mario is ducking on the bottom, Mario still stays alive in this scenario, correct?

@Vioz, That's correct, Mario is only one unit tall when ducking.

May we change the order the input is given?

@Vioz, I don't see anything wrong with that, as long as you mention it in your submission.

Is jumping linear speed upwards followed by linear speed downwards, or are we to assume quadratic speed?

@orlp, Physics are a bit simplified for this challenge. In 0.5 seconds, Mario rises up 3 blocks at a constant rate. Then, without stopping, he does the same thing back down.

@NickB. One of your examples uses non-integer input, which you said earlier was impossible. Also, do we have to use this exact input format, or can we use something convenient for our language?

@orlp I meant it as all numerical input will be integers. I'll make it more clear. Also, you can change the input format as long as you mention it in the submission.

@NickB. No, one of your examples uses 2.5 as input.

If a situation where nothing is a valid action, does that mean we can print anything? As duck or jump x would all keep Mario alive too.

@Vioz- Nothing in the challenge prohibits that, so yes. However jump wouldn't always be safe - you can accidently jump into a bullet bill.

@orlp, You're right, I shouldn't have done that. Will roll back the edit. You can output duck or jump when nothing would also work. Sorry!

You say that input will always consist of integers, but the very first test case has a non-integer speed. 2. What point of Mario/Bullet Bill do the coordinates specify? I'm struggling to understand how a Bullet Bill (y=1) could be at Mario's feet (y=0) in the first test case.

Can you provide some program for verifying output?

I think you mean "Bullets Bill".

CJam, 84 80 61 bytes
This is my first program for this, literally just learned CJam last night, for this purpose only. I'm also new to this site's formatting, help would be great with that.
ri:Xri:Yrri:Sri:Ari:B];BY={"jump"XA<{AX)-S/}{X(A-S/}?}"duck"?

It's no longer longer than the previous answer, but I'm still posting it because I'd like tips and stuff.
Explanation
ri:X    - Sets Bullet X to X.
ri:Y    - Sets Bullet Y to Y.
r       - Omits direction.
ri:S    - Sets speed to S.
ri:A    - Sets Mario X to A.
ri:B    - Sets Mario Y to B.
];      - Clears the stack.
BY=     - Due to the ? at the end, executes the first block if true (if B=Y) or the second block (in this case "duck") if false.
{"jump" - Outputs jump.
XA<     - Due to the ? after the next two blocks, executes the first block if true (if X<A) or the second block if false.
{AX)-S/}- Solves and outputs (A-(X+1))/S.
{X(A-S/}- Solves and outputs ((X-1)-A)/S.
?}      - Executes block A if the condition before it is true, or block B if not.
"duck"  - Outputs duck.
?       - Executes block A if the condition before it is true, or block B if not.

There's an online interpreter here if needed.

Nevermind. The question contradicts itself.

@Dennis Not exactly sure what that means, not good with terminology and stuff. I'm not too far into coding yet.

Python, 72 68 66 bytes
We can ignore left/right - if we assume it's always pointed at us we'll always take the right action. Then if our assumption was wrong we did a useless jump/duck, but that doesn't matter - we'll still be safe.
Similarly, there is no incentive to do nothing. Rather, it's shorter code to always duck, and jump when necessary. Ducking will only be unsafe if the bullet bill is exactly one above the block we're standing on. In that case we will take our x position, bullet bill's y position, take the absolute difference, divide by bullet bill's speed and jump 0.2 seconds before that.
lambda a,b,_,s,x,y:["duck","jump "+`max(0,abs(a-x)/s-.2)`][y+1==b]

Call like this:
f=lambda a,b,_,s,x,y:["duck","jump "+`max(0,abs(a-x)/s-.2)`][y+1==b]
f(5, 1, "left", 2.5, 0, 0)

Beat me by 20 seconds and 5 bytes :P Nice work!

Good job! I like your reasoning for what is necessary and what is unnecessary.

@Vioz, You're still welcome to post your solution, even if it's longer. I'd like to see what you came up with.

@NickB. We have pretty much the exact same line of reasoning :P Had I remembered to implement absolute values and stack rotating in the language I'm working on I would have posted it

Surely it's shorter to use a lambda?

@xnor Ah, forgot that you could also submit a function.

I believe that function submission can be anonymous.

Haskell, 61 Bytes
I found that there's no point in doing nothing. Jump if Bill is at or bellow Mario's feet, otherwise duck.
f a b _ c d e|b<e+2="Jump "++(show$abs(a-d)/c-0.5)|1<2="Duck"

source: Stack Exchange

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

sort: votes


text:
A fiercer four-square cipher
Background
One-hundred and thirteen years ago, amateur cryptographer Félix Delastelle published his work on the four-square cipher, a digraphic substitution cipher that accepts two permutations of a 25-letter alphabet as keys and encodes messages consisting of those letters.
Like most pen-and-paper ciphers, the four-square cipher does not have any cryptographic value today, but at the time of its invention, it had a significant advantage over its monographic counterparts.
One-hundred and thirteen years later, Alice Delastelle decides to improve the four-square cipher by increasing the alphabet's size and the number of keys.[citation needed]
Key setup
The alphabet contains the following characters (starting with space):
 !"#$%&'()*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ

Given a pass phrase, we construct a permutation of this alphabet as follows:

Keep only the first occurrence of each character.
Append the unused characters from the alphabet, in their natural order.

After turning four pass phrases into four keys, we split each key into a square of side length 7 and arrange the four resulting squares so that they form one big square.
For example, if the pass phrases were
PROGRAMMING PUZZLES & CODE GOLF
POPULARITY CONTESTS & CODE BOWLING
CORRECT HORSE BATTERY STAPLE
DON'T TELL EVE!!!

the keys would be constructed and arranged like this:
PROGAMI  POULARI
N UZLES  TY CNES
&CDF!"#  &DBWG!"
$%'()*+  #$%'()*
,-./:;<  +,-./:;
=>?@BHJ  <=>?@FH
KQTVWXY  JKMQVXZ

CORET H  DON'T E
SBAYPL!  LV!"#$%
"#$%&'(  &()*+,-
)*+,-./  ./:;<=>
:;<=>?@  ?@ABCFG
DFGIJKM  HIJKMPQ
NQUVWXZ  RSUWXYZ

Encryption
Given a plaintext message such as
ALICE LOVES BOB.

we append 0 or 1 spaces to make its length even and split it into character pairs:
["AL" "IC" "E " "LO" "VE" "S " "BO" "B."]

For each character pair, we locate the the first character in the first square (reading order) and the second in the fourth.
Then, we choose the characters in the remaining squares such that the four selected characters form a rectangle whose sides are parallel to the sides of the squares.
Finally, we replace the character pair by the selected characters of the second and third square.
For our example string, this yields
["PP" "A@" "E " "YT" "ZE" "EH" "=T" "<-"]

resulting in the following ciphertext:
PPA@E YTZEEH=T<-

Task
Write a program or function that accepts four pass phrases and a plaintext, uses the above variant of the four-square cipher to encrypt it and returns the resulting ciphertext.
Details:

The five input strings will consist solely of characters of the mentioned alphabet.
The five input strings can be read in any order, as such, a single string delimited by newlines or as an array of five strings.
You may assume that none of the strings is empty.
The output must be a single string.
If you choose to print the output to STDOUT, you may print only the characters of the ciphertext and (optionally) a trailing newline.
Standard code-golf rules apply.

Test cases
In all test cases, the first four strings correspond to the key squares in reading order and the last input string to the plaintext.
Input
PROGRAMMING PUZZLES & CODE GOLF
POPULARITY CONTESTS & CODE BOWLING
CORRECT HORSE BATTERY STAPLE
DON'T TELL EVE!!!
ALICE LOVES BOB.

Output
PPA@E YTZEEH=T<-

Input
 !"#$%&'()*+,-./:;<=>
 !"#$%&'()*+,-./:;<=>?@ABCDE
 !"#$%&'()*+,-./:;<=>?@ABCDEFGHIJKL
 !"#$%&'()*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRS
HELLO, WORLD!

Output
LALLR)#TROKE !

Input
,'K AB-Q=?@("W$>XM).C#<I:G!OLP*+;SZJTU%NED/&VFHRY
:,-D$C<SU=IYHFVA;! JG/M&L+WT%#.Q@(N*R")EZOBKX?'>P
L()JX,BND?Z<>P*FU%=O@&KIC+A!Y:;$SWHR.EMG'/T"QV #-
<->CI")AP Q:+U;O/F(KH&ER!MW?X'VJLZ#.$,BSGN@TD%*Y=
SPIN THE PPCG WHEEL OF BLAME!

Output
#>TE,VK+,ZQ(&<F@RA.NL@DM%NAC&>

Input
& %(,-#)$@?/=>'*"<:;!.+
=/$- ?;',@#!(&<")%.:>+*
&%-/<?.;$'#:=!( ,>"+*)@
=,<-*?#.'@/;>%!+:(& ")$
HNRA#JX$H %JAV+"GTS,

Output
GOOD LUCK, HAVE FUN.

CJam, 52 50 49 47 46 44 bytes
l2/qN/'[,32>A,s-f|2/f{~@S+2<.#_7f%_W%.m.m.=}

The input order is lines 5, 2, 3, 1, 4. Try it online.
(-1 byte thanks to @MartinBüttner, -2 bytes thanks to @Dennis)
Explanation
l2/           Read the message and split into chunks of 2
qN/           Read rest of input and split by newlines (pass phrases)
'[,32>        Generate " !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ"
A,s-          Remove digits 0123456789
f|            Setwise OR with each pass phrase to remove duplicates, giving keys
2/            Split keys into two pairs
f{ ... }      For each message chunk...
  ~             Unwrap key pairs
  @S+2<         Add a space to the message chunk then cap to length 2
  .#            Find the two chars in keys 1, 4
  _7f%          Copy indices and perform modulo 7 on both
  _W%           Copy and reverse
  .m.m          Vectorised subtraction twice
  .=            Apply both indices to keys 2, 3

For the indices, we want to swap the least significant digits, base 7. For instance, for the first example AL are indices 4 and 7 in keys 1 and 4 respectively. In base 7, this is [0 4] and [1 0]. Swapping the least significant digits gives [0 0] and [1 4], i.e. 0 and 11, and this corresponds to P and P in keys 2 and 3 respectively.
However, instead of base converting, the code does the following:
[4 7]     A: Initial indices
[4 0]     B: Indices mod 7
[0 4]     C: Reverse of B

[4 -4]    B-C
[0 11]    A-(B-C)

Pyth, 74 71 bytes
L+%eb7*7/hb7Jcms+oxdN{d--CMr33 91`MTd.z2ssm@VeJ,ydy_dCmxLhdedC,hJ.tcz2d

Could probably be optimized a lot. I use a lot of zipping.
Takes input in the following order:
ALICE LOVES BOB.
PROGRAMMING PUZZLES & CODE GOLF
DON'T TELL EVE!!!
POPULARITY CONTESTS & CODE BOWLING
CORRECT HORSE BATTERY STAPLE

Can I steal your input order idea?

@Maltysen Sure.

Pyth - 88 86 83 78 76 75 72 bytes
8 bytes saved thanks to @orlp.
Waaay too long, I'm pretty unhappy with this, but just posting it while I look for a better way to handle the squares.
Jm+oxdN{d-+d-CMr33 91`MTd.zsms@VtPJ,+*7hKs.DR7xV,hJeJdeK+*7@K2@K1C.tcz2d

Try it online here.

You can replace c+e.z*%le.z2d2 with C.tce.z2d. Don't ask :)

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


text:
Take It or Leave It: A Game Show for Computers
Context:

A reclusive billionaire has created a game show to attract the world's best and brightest programmers. On Mondays at the stroke of midnight, he chooses one person from a pool of applicants to be the contestant of the week, and provides them with a game. You are this week's lucky contestant!

This week's game:

The host provides you with API access to a stack of 10,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $10,000 (no two envelopes contain the same dollar value).
You have 3 commands at your disposal:

Read(): Read the dollar figure in the envelope at the top of the stack.

Take(): Add the dollar figure in the envelope to your game show wallet, and pop the envelope off the stack.

Pass(): Pop off the envelope on the top of the stack.

The Rules:

If you use Pass() on an envelope, the money within is lost forever.

If you use Take() on an envelope containing $X, from that point forward, you may never use Take() on an envelope containing < $X. Take() on one of these envelopes will add $0 to your wallet.

Write an algorithm that finishes the game with the maximal amount of money.
If you're writing a solution in Python, feel free to use this controller to test out algorithms, courtesy of @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca
If you use the controller, you cannot access globals, you can only use the 3 provided API commands, and local scoped variables. (@Beta Decay)
Notes: "Maximal" in this case means the median value in your wallet after N > 50 runs. I expect, though I would love to be proven wrong, that the median value for a given algorithm will converge as N increases to infinity. Feel free to try to maximize the mean instead, but I have a feeling that the mean is more likely to be thrown off by a small N than the median is.
Edit: changed the number of envelopes to 10k for easier processing, and made Take() more explicit.
Edit 2: The prize condition has been removed, in light of this post on meta.
Current high scores:
PhiNotPi    - $805,479
Reto Koradi - $803,960
Dennis      - $770,272 (Revised)
Alex L.     - $714,962 (Revised)

I implemented in a way that it just returns False. Since you can read it there is no real point of failing the entire game on a failed take()

though I find 100000 kinda high since it takes a long time to do a single iteration

In case anyone wants to use it, here is the controller that i've been using to test my algorithms: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

P.S. Nice question and welcome to Programming Puzzles and Code Golf :)

@Maltysen I put your controller into the OP, thanks for the contribution!

I couldn't find an explicit rule on bitcoin prizes, but there is some meta discussion on real world prizes which people can contribute to.

CJam, $87,143 $700,424 $720,327 $727,580 $770,272
{0:T:M;1e4:E,:)mr{RM>{RR(*MM)*-E0.032*220+R*<{ERM--:E;R:MT+:T;}{E(:E;}?}&}fRT}
[easi*]$easi2/=N

This program simulates the entire game multiple times and calculates the median.
How to run
I've scored my submission by doing 100,001 test runs:
$ time java -jar cjam-0.6.5.jar take-it-or-leave-it.cjam 100001
770272

real    5m7.721s
user    5m15.334s
sys     0m0.570s

Approach
For each envelope, we do the following:

Estimate the amount of money that will inevitably be lost by taking the envelope.
If R is the content and M is the maximum that has been taken, the amount can be estimated as R(R-1)/2 - M(M+1)/2, which gives the money all envelopes with contents X in the interval (M,R) contain.
If no envelopes had been passed yet, the estimation would be perfect.
Calculate the amount of money that will inevitably be lost by passing the envelope.
This is simply the money the envelope contains.
Check if the quotient of both is less than 110 + 0.016E, where E is the number of remaining envelopes (not counting envelopes that cannot be taken anymore).
If so, take. Otherwise, pass.

Because using a golfing language helps in any way whatsoever. ;P +1 for the algo.

Interesting solution, thanks Dennis! This is a game show, and game shows tend to have prizes...Do you have a bitcoin address, by any chance?

@LivingInformation I do, but I'm not sure if accepting real money for a code golf answer violates the TOS.

@Dennis I searched around before adding the prize conditions, and found nothing explicit about giving prizes. Some posts indicated that it could be a bad idea unless the prize terms were very specific, but there doesn't seem to be any rule against it.

I can't replicate your results using a Python clone: https://gist.github.com/orlp/f9b949d60c766430fe9c. You score around $50,000. That's an order of magnitude off.

@orlp I had pretty much everything backwards. Turns out that my algorithm is pretty terrible...

@orlp thanks for that, the score in the main post has been updated.

@Dennis where did the 139 come from? I love the idea of calculating the amount gained versus the amount potentially lost by passing that envelope, and think statistical analysis of both of those numbers could go pretty far in terms of calculating the perfectly optimal choice at each point, but 139 feels like a stab in the dark from there.

@LivingInformation Trial and error. I'm currently looking at using the exact amount instead of estimations, but the resulting code is very slow.

This answer needs more upvotes than mine! It's more clever, scores higher, and is even golfed!

@LivingInformation This is my address: 17uLHRfdD5JZ2QjSqPGQ1B12LoX4CgLGuV

Two confirmations and counting. Thanks, @LivingInformation!

Python, $680,646 $714,962
f = (float(len(stack)) / 10000)
step = 160
if f<0.5: step = 125
if f>0.9: step = 190
if read() < max_taken + step:
    take()
else:
    passe()

Takes larger and larger amounts in steps of size between $125 and $190. Ran with N=10,000 and got a median of $714962. These step sizes came from trial and error and are certainly not optimal.
The full code, including a modified version of @Maltysen's controller which prints a bar chart while it runs:
import random
N = 10000

def init_game():
    global stack, wallet, max_taken
    stack = list(range(1, 10001))
    random.shuffle(stack)
    wallet = max_taken = 0

def read():
    return stack[0]

def take():
    global wallet, max_taken
    amount = stack.pop(0)
    if amount > max_taken:
        wallet += amount
        max_taken = amount

def passe():
    stack.pop(0)

def test(algo):
    results = []
    for _ in range(N):
        init_game()
        for i in range(10000):
            algo()
        results += [wallet]
        output(wallet)
    import numpy
    print 'max: '
    output(max(results))
    print 'median: '
    output(numpy.median(results))
    print 'min: '
    output(min(results))

def output(n):
    print n
    result = ''
    for _ in range(int(n/20000)):
        result += '-'
    print result+'|'

def alg():
    f = (float(len(stack)) / 10000)
    step = 160
    if f<0.5: step = 125
    if f>0.9: step = 190
    if read() < max_taken + step:
        #if read()>max_taken: print read(), step, f
        take()
    else:
        passe()

test(alg)

BitCoin address: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7
Wow OP delivered! Thanks @LivingInformation!

The controller is Maltysen's, not mine.

Confirmed. I had just set up a controller, and get very similar numbers for your solution. Strictly speaking, I think you have to maintain the value of max_taken in your own code, since it's not part of the official game API. But that's trivial to do.

Yeah, max_taken is in @Maltysen's controller. If it is useful I can post the entire solution (controller + algorithm) in one block.

It's really no big deal. But I think the cleanest approach would be to only use the read(), take() and pass() methods in the posted code, since those are the "3 commands at your disposal" based on the definition in the question.

@Reto I'm willing to revise the question to whatever commands make the most sense. Read, Take, and Pass were all 4 characters, and felt fitting, but i'm open to suggestions (for example, i've considered changing "pass" to "leave", because I titled the post "take it or leave it").

Just noticed I was calculating mean instead of median! Will post new score soon. Ok, updated with median score.

step = 160
if f<0.2: step = 75
if f<0.5: step = 125
if f>0.9: step = 190
f <0.2: step = 75 always gets overwritten by f<.5: step = 125. Bug? @Alex L.

@LivingInformation yup! removed the useless line.

How long does this take for you to run 10001 iterations?

C++, $803,960
for (int iVal = 0; iVal < 10000; ++iVal)
{
    int val = game.read();
    if (val > maxVal &&
        val < 466.7f + 0.9352f * maxVal + 0.0275f * iVal)
    {
        maxVal = val;
        game.take();
    }
    else
    {
        game.pass();
    }
}

Reported result is the median from 10,001 games.

Guess and check, I take it? Or did you use some kind of input fuzzer for the constants?

I ran an optimization algorithm to determine the constants.

Do you think that a dynamic calculation at each point would be more effective, or do you think this is approaching the maximum value you can receive?

I have no reason to believe that it's the ideal strategy. I hope it's the maximum for a linear function with these parameters. I've been trying to allow various kinds of non-linear terms, but so far haven't found anything significantly better.

At turn N, given two choices (take or pass), you simulate M "Perfect games" using the remaining unchosen dollar values. That is, randomly shuffle all the remaining elements M times, and each time calculate the maximum amount you could gain if you played perfectly, for the case of taking the money and for leaving it. Whichever choice resulted in the highest average "perfect game" is the choice you make in that turn.
It wouldn't be CPU optimal, of course... O(Envelopes * M * O(perfect game calculation))

I can confirm that simulating this gives the reported score of slightly more than $800,000.

Java, $806,899
This is from a trial of 2501 rounds.  I am still working on optimizing it.  I wrote two classes, a wrapper and a player.  The wrapper instantiates the player with the number of envelopes (always 10000 for the real thing), and then calls the method takeQ with the top envelope's value.  The player then returns true if they take it, false if they pass it.
Player
import java.lang.Math;

public class Player {
  public int[] V;

  public Player(int s) {
    V = new int[s];
    for (int i = 0; i < V.length; i++) {
      V[i] = i + 1;
    }
    // System.out.println();
  }

  public boolean takeQ(int x) {

    // System.out.println("look " + x);

    // http://www.programmingsimplified.com/java/source-code/java-program-for-binary-search
    int first = 0;
    int last = V.length - 1;
    int middle = (first + last) / 2;
    int search = x;

    while (first <= last) {
      if (V[middle] < search)
        first = middle + 1;
      else if (V[middle] == search)
        break;
      else
        last = middle - 1;

      middle = (first + last) / 2;
    }

    int i = middle;

    if (first > last) {
      // System.out.println(" PASS");
      return false; // value not found, so the envelope must not be in the list
                    // of acceptable ones
    }

    int[] newVp = new int[V.length - 1];
    for (int j = 0; j < i; j++) {
      newVp[j] = V[j];
    }
    for (int j = i + 1; j < V.length; j++) {
      newVp[j - 1] = V[j];
    }
    double pass = calcVal(newVp);
    int[] newVt = new int[V.length - i - 1];
    for (int j = i + 1; j < V.length; j++) {
      newVt[j - i - 1] = V[j];
    }
    double take = V[i] + calcVal(newVt);
    // System.out.println(" take " + take);
    // System.out.println(" pass " + pass);

    if (take > pass) {
      V = newVt;
      // System.out.println(" TAKE");
      return true;
    } else {
      V = newVp;
      // System.out.println(" PASS");
      return false;
    }
  }

  public double calcVal(int[] list) {
    double total = 0;
    for (int i : list) {
      total += i;
    }
    double ent = 0;
    for (int i : list) {
      if (i > 0) {
        ent -= i / total * Math.log(i / total);
      }
    }
    // System.out.println(" total " + total);
    // System.out.println(" entro " + Math.exp(ent));
    // System.out.println(" count " + list.length);
    return total * (Math.pow(Math.exp(ent), -0.5) * 4.0 / 3);
  }
}

Wrapper
import java.lang.Math;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;

public class Controller {
  public static void main(String[] args) {
    int size = 10000;
    int rounds = 2501;
    ArrayList<Integer> results = new ArrayList<Integer>();
    int[] envelopes = new int[size];
    for (int i = 0; i < envelopes.length; i++) {
      envelopes[i] = i + 1;
    }
    for (int round = 0; round < rounds; round++) {
      shuffleArray(envelopes);

      Player p = new Player(size);
      int cutoff = 0;
      int winnings = 0;
      for (int i = 0; i < envelopes.length; i++) {
        boolean take = p.takeQ(envelopes[i]);
        if (take && envelopes[i] >= cutoff) {
          winnings += envelopes[i];
          cutoff = envelopes[i];
        }
      }
      results.add(winnings);
    }
    Collections.sort(results);
    System.out.println(
        rounds + " rounds, median is " + results.get(results.size() / 2));
  }

  // stol... I mean borrowed from
  // http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array
  static Random rnd = new Random();

  static void shuffleArray(int[] ar) {
    for (int i = ar.length - 1; i > 0; i--) {
      int index = rnd.nextInt(i + 1);
      // Simple swap
      int a = ar[index];
      ar[index] = ar[i];
      ar[i] = a;
    }
  }
}

A more detailed explanation is coming soon, after I finish optimizations.
The core idea is to be able to estimate the reward from playing a game from a given set of envelopes. If the current set of envelopes is {2,4,5,7,8,9}, and the top envelope is the 5, then there are two possibilities:

Take the 5 and play a game with {7,8,9}
Pass the 5 and play a game of {2,4,7,8,9}

If we calculate the expected reward of {7,8,9} and compare it to the expected reward of {2,4,7,8,9}, we will be able to tell if taking the 5 is worth it.
Now the question is, given a set of envelopes like {2,4,7,8,9} what is the expected value?  I found the the expected value seems to be proportional to the total amount of money in the set, but inversely proportional to the square root of the number of envelopes that the money is divided into.  This came from "perfectly" playing several small games in which all of the envelopes have almost identical value.
The next problem is how to determine the "effective number of envelopes."  In all cases, the number of envelopes is known exactly by keeping track of what you've seen and done.  Something like {234,235,236} is definitely three envelopes, {231,232,233,234,235} is definitely 5, but {1,2,234,235,236} should really count as 3 and not 5 envelopes because the 1 and 2 are nearly worthless, and you would never PASS on a 234 so you could later pick up a 1 or 2.  I had the idea of using Shannon entropy to determine the effective number of envelopes.
I targeted my calculations to situations where the envelope's values are uniformly distributed over some interval, which is what happens during the game.  If I take {2,4,7,8,9} and treat that as a probability distribution, its entropy is 1.50242.  Then I do exp() to get 4.49254 as the effective number of envelopes.
The estimated reward from {2,4,7,8,9} is 30 * 4.4925^-0.5 * 4/3 = 18.87
The exact number is 18.1167.
This isn't an exact estimate, but I am actually really proud of how well this fits the data when the envelopes are uniformly distributed over an interval.  I'm not sure of the correct multiplier (I am using 4/3 for now) but here is a data table excluding the multiplier.
Set of Envelopes                    Total * (e^entropy)^-0.5      Actual Score

{1,2,3,4,5,6,7,8,9,10}              18.759                        25.473
{2,3,4,5,6,7,8,9,10,11}             21.657                        29.279
{3,4,5,6,7,8,9,10,11,12}            24.648                        33.125
{4,5,6,7,8,9,10,11,12,13}           27.687                        37.002
{5,6,7,8,9,10,11,12,13,14}          30.757                        40.945
{6,7,8,9,10,11,12,13,14,15}         33.846                        44.900
{7,8,9,10,11,12,13,14,15,16}        36.949                        48.871
{8,9,10,11,12,13,14,15,16,17}       40.062                        52.857
{9,10,11,12,13,14,15,16,17,18}      43.183                        56.848
{10,11,12,13,14,15,16,17,18,19}     46.311                        60.857

Linear regression between expected and actual gives an R^2 value of 0.999994.
My next step to improve this answer is to improve estimation when the number of envelopes starts to get small, which is when the envelopes are not approximately uniformly distributed and when the problem starts to get granular.

Edit:  If this is deemed worthy of bitcoins, I just got an address at 1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg.  Thanks! (This was here from when the challenge author was handing out prizes.)

Accidentally sent you 20k satoshi over 805,479. For reference, the amount was supposed to be your score. Enjoy my mistake :)

Will you be running numbers with more rounds? Based on what I'm seeing, there is quite a bit of variation, and 500 is not enough to get a stable median. My score is very close to yours if I run only 500 rounds, but it all depends on how the random numbers happen to fall. If I used a variable seed, and did 500 runs a few times, I could probably get a higher score.

@RetoKoradi I'm definitely going to do more rounds.

C++, ~$815,000
Based on Reto Koradi's solution, but switches to a more sophisticated algorithm once there's 100 (valid) envelopes left, shuffling random permutations and computing the heaviest increasing subsequence of them. It will compare the results of taking and not taking the envelope, and will greedily select the best choice.
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

void setmax(std::vector<int>& h, int i, int v) {
    while (i < h.size()) { h[i] = std::max(v, h[i]); i |= i + 1; }
}

int getmax(std::vector<int>& h, int n) {
    int m = 0;
    while (n > 0) { m = std::max(m, h[n-1]); n &= n - 1; }
    return m;
}

int his(const std::vector<int>& l, const std::vector<int>& rank) {
    std::vector<int> h(l.size());
    for (int i = 0; i < l.size(); ++i) {
        int r = rank[i];
        setmax(h, r, l[i] + getmax(h, r));
    }

    return getmax(h, l.size());
}

template<class RNG>
void shuffle(std::vector<int>& l, std::vector<int>& rank, RNG& rng) {
    for (int i = l.size() - 1; i > 0; --i) {
        int j = std::uniform_int_distribution<int>(0, i)(rng);
        std::swap(l[i], l[j]);
        std::swap(rank[i], rank[j]);
    }
}

std::random_device rnd;
std::mt19937_64 rng(rnd());

struct Algo {
    Algo(int N) {
        for (int i = 1; i < N + 1; ++i) left.insert(i);
        ival = maxval = 0;
    }

    static double get_p(int n) { return 1.2 / std::sqrt(8 + n) + 0.71; }

    bool should_take(int val) {
        ival++;
        auto it = left.find(val);
        if (it == left.end()) return false;

        if (left.size() > 100) {
            if (val > maxval && val < 466.7f + 0.9352f * maxval + 0.0275f * (ival - 1)) {
                maxval = val;
                left.erase(left.begin(), std::next(it));
                return true;
            }

            left.erase(it);
            return false;
        }

        take.assign(std::next(it), left.end());
        no_take.assign(left.begin(), it);
        no_take.insert(no_take.end(), std::next(it), left.end());
        take_rank.resize(take.size());
        no_take_rank.resize(no_take.size());
        for (int i = 0; i < take.size(); ++i) take_rank[i] = i;
        for (int i = 0; i < no_take.size(); ++i) no_take_rank[i] = i;

        double take_score, no_take_score;
        take_score = no_take_score = 0;
        for (int i = 0; i < 1000; ++i) {
            shuffle(take, take_rank, rng);
            shuffle(no_take, no_take_rank, rng);
            take_score += val + his(take, take_rank) * get_p(take.size());
            no_take_score += his(no_take, no_take_rank) * get_p(no_take.size());
        }

        if (take_score > no_take_score) {
            left.erase(left.begin(), std::next(it));
            return true;
        }

        left.erase(it);
        return false;
    }

    std::set<int> left;
    int ival, maxval;
    std::vector<int> take, no_take, take_rank, no_take_rank;
};

struct Game {
    Game(int N) : score_(0), max_taken(0) {
        for (int i = 1; i < N + 1; ++i) envelopes.push_back(i);
        std::shuffle(envelopes.begin(), envelopes.end(), rng);
    }

    int read() { return envelopes.back(); }
    bool done() { return envelopes.empty(); }
    int score() { return score_; }
    void pass() { envelopes.pop_back(); }

    void take() {
        if (read() > max_taken) {
            score_ += read();
            max_taken = read();
        }
        envelopes.pop_back();
    }

    int score_;
    int max_taken;
    std::vector<int> envelopes;
};

int main(int argc, char** argv) {
    std::vector<int> results;
    std::vector<int> max_results;
    int N = 10000;
    for (int i = 0; i < 1000; ++i) {
        std::cout << "Simulating game " << (i+1) << ".\n";
        Game game(N);
        Algo algo(N);

        while (!game.done()) {
            if (algo.should_take(game.read())) game.take();
            else game.pass();
        }
        results.push_back(game.score());
    }

    std::sort(results.begin(), results.end());
    std::cout << results[results.size()/2] << "\n";

    return 0;
}

Interesting. It had crossed my mind that it should be possible to improve by looking at the values left for the last few envelopes. I figure you played with the cutoff point where you switch strategies? Is it just getting too slow if you switch earlier? Or are the results actually getting worse?

@RetoKoradi I did play with the cutoff point, and earlier cutoffs both got too slow and worse. Not too surprising honestly, at 100 envelopes we're already sampling a mere 1000 permutations out of a possible 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.

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


text:
Heaviest increasing subsequence
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A strictly increasing subsequence is a subsequence in which every element is bigger than the preceding one.
The heaviest increasing subsequence of a sequence is the strictly increasing subsequence that has the biggest element sum.
Implement a program or function in your language of choice that finds the element sum of the heaviest increasing subsequence of a given list of non-negative integers.
Examples:
                    [] ->  0 ([])
                   [3] ->  3 ([3])
             [3, 2, 1] ->  3 ([3])
          [3, 2, 5, 6] -> 14 ([3, 5, 6])
       [9, 3, 2, 1, 4] ->  9 ([9])
       [3, 4, 1, 4, 1] ->  7 ([3, 4])
       [9, 1, 2, 3, 4] -> 10 ([1, 2, 3, 4])
       [1, 2, 4, 3, 4] -> 10 ([1, 2, 3, 4])
[9, 1, 2, 3, 4, 5, 10] -> 25 ([1, 2, 3, 4, 5, 10])
       [3, 2, 1, 2, 3] ->  6 ([1, 2, 3])

Note that you only have to give the element sum of the heaviest increasing subsequence, not the subsequence itself.

The asymptotically fastest code wins, with smaller code size in bytes as a tiebreaker.

How do you plan to deal with incomparable asymptotics? There are potentially two important variables: the length of the sequence, and the size of the largest element in the sequence.

@PeterTaylor I choose length of the sequence as the asymptotic. Your solution must not assume any bound on the integers, and in particular not loop or allocate memory based on the size of the numbers involved. You are forgiven if your language choice has bounded integers, but you must not make use of this fact in your solution. Does that satisfy your concerns?

Partially. It's still theoretically possible (although probably unlikely) that the fact that comparison of two unbounded integers takes size proportional to their log could be relevant. You might want to allow basic operations (addition, comparison, maybe multiplication) on the integers to be assumed to be O(1) time.

@PeterTaylor Is the transdichotomous model of computation specific enough?

Seems reasonable.

How do we measure asymptotic fastness? Do you mean big O?

@LuisMendo Yes, worst case performance.

What should [1, 2, 4, 3, 4] return? 7 as in  [1, 2, 4] or  [3, 4], or 10 as in [1, 2, 3, 4]?

@AlexanderVogt 10.

@PeterTaylor I'm not certain why you removed the code-golf tag, it's the secondary scoring requirement (and once O(n log n) answers start streaming in, the only one that matters).

Because it's only really appropriate where it's the primary scoring criterion. I did also consider removing both [tag:code-golf] and [tag:fastest-algorithm] and replacing them with [tag:code-challenge] since it's a bit of a hybrid.

javascript (ES6) O(n log n) 253 characters
function f(l){l=l.map((x,i)=>[x,i+1]).sort((a,b)=>a[0]-b[0]||1)
a=[0]
m=(x,y)=>x>a[y]?x:a[y]
for(t in l)a.push(0)
t|=0
for(j in l){for(i=(r=l[j])[1],x=0;i;i&=i-1)x=m(x,i)
x+=r[0]
for(i=r[1];i<t+2;i+=i&-i)a[i]=m(x,i)}for(i=t+1;i;i&=i-1)x=m(x,i)
return x}

this uses fenwick trees (a maximum fenwick tree) to find maxima of certain subsequences.
basically, in the underlying array of the datatype, each place is matched with an element from the input list, in the same order. the fenwick tree is initialized with 0 everywhere.
from the smallest to the biggest, we take an element from the input list, and look for the maximum of the elements to the left. they are the elements that may be before this one in the subsequence, because they are to the left in the input sequence, and are smaller, because they entered the tree earlier.
so the maximum we found is the heaviest sequence that can get to this element, and so we add to this the weight of this element, and set it in the tree.
then, we simply return the maximum of the whole tree is the result.
tested on firefox

Python, O(n log n)
I didn't golf this, because I'm competing primarily on the fastest code side of things. My solution is the heaviest_subseq function, and a test harness is also included at the bottom.
import bisect
import blist

def heaviest_subseq(in_list):
    best_subseq = blist.blist([(0, 0)])
    for new_elem in in_list:

        insert_loc = bisect.bisect_left(best_subseq, (new_elem, 0))

        best_pred_subseq_val = best_subseq[insert_loc - 1][1]

        new_subseq_val = new_elem + best_pred_subseq_val

        list_len = len(best_subseq)
        num_deleted = 0

        while (num_deleted + insert_loc < list_len
               and best_subseq[insert_loc][1] <= new_subseq_val):
            del best_subseq[insert_loc]
            num_deleted += 1

        best_subseq.insert(insert_loc, (new_elem, new_subseq_val))

    return max(val for key, val in best_subseq)

tests = [eval(line) for line in """[]
[3]
[3, 2, 1]
[3, 2, 5, 6]
[9, 3, 2, 1, 4]
[3, 4, 1, 4, 1]
[9, 1, 2, 3, 4]
[1, 2, 4, 3, 4]
[9, 1, 2, 3, 4, 5, 10]
[3, 2, 1, 2, 3]""".split('\n')]

for test in tests:
    print(test, heaviest_subseq(test))

Runtime analysis:
Each element has its insertion position looked up once, is inserted once, and is possibly deleted once, in addition to a constant number of value lookups per loop. Since I am using the built-in bisect package and the blist package, each of those operations are O(log n). Thus, the overall runtime is O(n log n).
The program works by maintaining a sorted list of best possible increasing subsequences, represented as a tuple of ending value and sequence sum. An increasing subsequence is in that list if there are no other subsequences found so far whose ending value is smaller and sum is at least as large. These are maintained in increasing order of ending value, and necessarily also in increasing order of sum. This property is maintained by checking the successor of each newly found subsequence, and deleting it if its sum is not large enough, and repeating until a subsequence with a larger sum is reached, or the end of the list is reached.

Interesting, a very different solution from mine.

Python, O(n log n)
I used an index transform and a nifty data structure (binary indexed tree) to trivialize the problem.
def setmax(a, i, v):
    while i < len(a):
        a[i] = max(a[i], v)
        i |= i + 1

def getmax(a, i):
    r = 0
    while i > 0:
        r = max(r, a[i-1])
        i &= i - 1
    return r

def his(l):
    maxbit = [0] * len(l)
    rank = [0] * len(l)
    for i, j in enumerate(sorted(range(len(l)), key=lambda i: l[i])):
        rank[j] = i

    for i, x in enumerate(l):
        r = rank[i]
        s = getmax(maxbit, r)
        setmax(maxbit, r, x + s)

    return getmax(maxbit, len(l))

The binary indexed tree can do two operations in log(n): increase a value at index i and get the maximum value in [0, i). We initialize every value in the tree to 0. We index the tree using the rank of elements, not their index. This means that if we index the tree at index i, all elements [0, i) are the elements smaller than the one with rank i. This means that we get the maximum from [0, i), add the current value to it, and update it at i. The only issue is that this will include values which are less than the current value, but come later in the sequence. But since we move through the sequence from left-to-right and we initialized all values in the tree to 0, those will have a value of 0 and thus not affect the maximum.

Python 2 - O(n^2) - 114 bytes
def h(l):
 w=0;e=[]
 for i in l:
    s=0
    for j,b in e:
     if i>j:s=max(s,b)
    e.append((i,s+i));w=max(w,s+i)
 return w

C++ - O(n log n) - 261 bytes
Should be fixed now:
#include <set>
#include <vector>
int h(std::vector<int>l){int W=0,y;std::set<std::pair<int,int>>S{{-1,0}};for(w:l){auto a=S.lower_bound({w,-1}),b=a;y=prev(a)->second+w;for(;b!=S.end()&&b->second<=y;b++){}a!=b?S.erase(a,b):a;W=y>W?y:W;S.insert({w,y});}return W;}

auto S=set<pair<I,I>>(); is longer than simply set<pair<I,I>> S;. #define I int is longer than using I=int;. There's no need to assign n to anything, you can replace auto n=*prev(S.lower_bound({w,-1}));I y=n.second with I y=prev(S.lower_bound({w,-1}))->second+w;.

Oh, and the initialization of S is very convoluted, you can just forego the insert and use std::set<std::pair<int,int>>S{{-1,0}};.

@orlp thanks! It shows that I don't use c++ ;)

Here's a much shorter version (still needs the set and vector include): using namespace std;using I=int;I h(vector<I>l){I W=0;set<pair<I,I>>S{{-1,0}};for(I w:l){I y=prev(S.lower_bound({w,-1}))->second+w;W=max(W,y);S.insert({w,y});}return W;}

Oh and dump the std::max, use W=y>W?y:W;.

Then you can also dump the using namespace std and just use std:: a couple of times, if I'm counting correctly.

@orlp Thanks. Just using int instead of I was also better now.

Actually, this solution is incorrect. It gives the wrong result (19) for [9, 1, 2, 3, 4, 5, 10] , the correct result is 25.

@orlp fixed it for that example, but I'm still not sure that it works for all valid inputs

I'm fairly certain it doesn't - try implementing a simpler O(n^2) solution and generating random sequences, comparing between the two.

@orlp Yeah it doesn't work for 3, 2, 1, 2, 3.

A n log n algorithm exists (I have an implementation), but it's surprisingly complex.

Let us continue this discussion in chat.

could you explain what algorithm you used?

@proudhaskeller It's the same algorithm as isaacg's answer.

Python, O(2n), 91 bytes
This is more for fun than to be competitive. An arcane recursive solution:
h=lambda l,m=0:l and(h(l[1:],m)if l[0]<=m else max(h(l[1:],m),l[0]+h(l[1:],l[0])))or 0

max(m,l[0]) given that not(l[0]<m) is just l[0], surely?

@PeterTaylor Derp.

This answer does not appear to be a serious contender.

Matlab, O(n 2n), 90 bytes
function m=f(x)
m=0;for k=dec2bin(1:2^numel(x)-1)'==49
m=max(m,all(diff(x(k))>0)*x*k);end

Examples:
>> f([])
ans =
     0
>> f([3])
ans =
     3
>> f([3, 2, 5, 6])
ans =
    14

Rust ,\$\mathcal{O}(n \log n)\$
Port of @isaacg's answer
run it on Rust Playground!
use std::cmp::Ordering;

fn heaviest_subseq(in_list: &[i32]) -> i32 {
    let mut best_subseq = vec![(0, 0)];

    for new_elem in in_list {
        let insert_loc = match best_subseq
            .binary_search_by(|&(key, _)| if key < *new_elem { Ordering::Less } else { Ordering::Greater })
        {
            Ok(index) => index,
            Err(index) => index,
        };

        let best_pred_subseq_val = best_subseq[insert_loc - 1].1;

        let new_subseq_val = new_elem + best_pred_subseq_val;

        let mut num_deleted = 0;

        while num_deleted + insert_loc < best_subseq.len() && best_subseq[insert_loc].1 <= new_subseq_val {
            best_subseq.remove(insert_loc);
            num_deleted += 1;
        }

        best_subseq.insert(insert_loc, (*new_elem, new_subseq_val));
    }

    best_subseq.into_iter().map(|(_, val)| val).max().unwrap()
}

fn main() {
    let tests = [
        &[][..],
        &[3][..],
        &[3, 2, 1][..],
        &[3, 2, 5, 6][..],
        &[9, 3, 2, 1, 4][..],
        &[3, 4, 1, 4, 1][..],
        &[9, 1, 2, 3, 4][..],
        &[1, 2, 4, 3, 4][..],
        &[9, 1, 2, 3, 4, 5, 10][..],
        &[3, 2, 1, 2, 3][..],
    ];

    for test in &tests {
        println!("{:?} {:?}", test, heaviest_subseq(test));
    }
}


text:
Symbolic Differentiation of Polynomials
Symbolic Differentiation 1: Gone Coefishin'
Task
Write a program that takes in a polynomial in x from stdin (1 < deg(p) < 128) and differentiates it. The input polynomial will be a string of the following form:
"a + bx + cx^2 + dx^3 +" ...

where the coefficient of each term is an integer (-128 < a < 128). Each term is separated by one space, a +, and another space; linear and constant terms appear as above (i.e., no x^0 or x^1). Terms will appear in order of increasing degree, and those powers with zero coefficient are omitted. All terms with coefficient 1 or -1 display that coefficient explicitly.
Your output must have precisely the same form. Note that coefficients in the output might be as big as 127*127 == 16129.
Examples
"3 + 1x + 2x^2" ==> "1 + 4x"
"1 + 2x + -3x^2 + 17x^17 + -1x^107" ==> "2 + -6x + 289x^16 + -107x^106"
"17x + 1x^2" ==> "17 + 2x"

Scoring
Your score is the length of your program in bytes, multiplied by three if you use a built-in or a library that does symbolic algebra.

I can't believe that we haven't already had this challenge here!

@flawr We sort of did. (Although that one required other functions as well and didn't have as strict rules on the output format.)

@flawr I thought the same thing... and yet I didn't find Martin's linked post searching. Ah well.

Retina, 53 43 42 41 40 35 bytes
^[^x]+ |(\^1)?\w(?=1*x.(1+)| |$)
$2

For counting purposes each line goes in a separate file, but you can run the above as a single file by invoking Retina with the -s flag.
This expects the numbers in the input string to be given in unary and will yield output in the same format. E.g.
1 + 11x + -111x^11 + 11x^111 + -1x^11111
-->
11 + -111111x + 111111x^11 + -11111x^1111

instead of
1 + 2x + -3x^2 + 2x^3 + -1x^5
-->
2 + -6x + 6x^2 + -5x^4

Explanation
The code describes a single regex substitution, which is basically 4 substitutions compressed into one. Note that only one of the branches will fill group $2 so if any of the other three match, the match will simply be deleted from the string. So we can look at the four different cases separately:
^[^x]+<space>
<empty>

If it's possible to reach a space from the beginning of the string without encountering an x that means the first term is the constant term and we delete it. Due to the greediness of +, this will also match the plus and the second space after the constant term. If there is no constant term, this part will simply never match.
x(?= )
<empty>

This matches an x which is followed by a space, i.e. the x of the linear term (if it exists), and removes it. We can be sure that there's a space after it, because the degree of the polynomial is always at least 2.
1(?=1*x.(1+))
$1

This performs the multiplication of the coefficient by the exponent. This matches a single 1 in the coefficient and replaces it by the entire corresponding exponent via the lookahead.
(\^1)?1(?= |$)
<empty>

This reduces all remaining exponents by matching the trailing 1 (ensured by the lookahead). If it's possible to match ^11 (and a word boundary) we remove that instead, which takes care of displaying the linear term correctly.
For the compression, we notice that most of the conditions don't affect each other. (\^1)? won't match if the lookahead in the third case is true, so we can put those two together as
(\^1)?1(?=1*x.(1+)| |$)
$2

Now we already have the lookahead needed for the second case and the others can never be true when matching x, so we can simply generalise the 1 to a \w:
(\^1)?\w(?=1*x.(1+)| |$)
$2

The first case doesn't really have anything in common with the others, so we keep it separate.

CJam, 43 41 bytes
Qleu'^/';*'+/{~:E[*'x['^E(]]E<}/]1>" + "*

Thanks to @jimmy23013 for pointing out one bug and golfing off two bytes!
Try it online in the CJam interpreter.
How it works
Q           e# Leave an empty array on the bottom of the stack.
l           e# Read a line from STDIN.
eu'^/';*    e# Convert to uppercase and replace carets with semicolons.
'+/         e# Split at plus signs.

{           e# For each resulting chunk:
  ~         e#   Evaluate it. "X" pushes 1 and ";" discards.
            e#   For example, "3X" pushes (3 1) and "3X;2" (3 2).
   :E       e#   Save the rightmost integer (usually the exponent) in E.
   [        e#
     *      e#   Multiply both integers.
            e#   For a constant term c, this repeats the empty string (Q) c times.
     'x     e#   Push the character 'x'.
     ['^E(] e#   Push ['^' E-1].
   ]        e#
   E<       e#  Keep at most E elements of this array.
            e#  If E == 1, 'x' and ['^' E-1] are discarded.
            e#  If E == 2, ['^' E-1] is discarded.
            e#  If E >= 3, nothing is discarded.
}/          e#

]           e# Wrap the entire stack in an array.
1>          e# Discard its first element.
            e# If the first term was constant, this discards [""]. ["" 'x']
            e# or ["" 'x' ['^' E-1]], depending on the constant.
            e# In all other cases, it discards the untouched empty array (Q).
" + "*      e# Join all kept array elements, separating by " + ".

Julia, 220 bytes
No regular expressions!
y->(A=Any[];for i=parse(y).args[2:end] T=typeof(i);T<:Int&&continue;T==Symbol?push!(A,1):(a=i.args;c=a[2];typeof(a[3])!=Expr?push!(A,c):(x=a[3].args[3];push!(A,string(c*x,"x",x>2?string("^",ex-1):""))))end;join(A," + "))

This creates a lambda function that accepts a string and returns a string. The innards mimic what happens when Julia code is evaluated: a string is parsed into  symbols, expressions, and calls. I might actually try writing a full Julia symbolic differentiation function and submit it to be part of Julia.
Ungolfed + explanation:
function polyderiv{T<:AbstractString}(y::T)

    # Start by parsing the string into an expression
    p = parse(y)

    # Define an output vector to hold each differentiated term
    A = Any[]

    # Loop through the elements of p, skipping the operand
    for i in p.args[2:end]

        T = typeof(i)

        # Each element will be an integer, symbol, or expression.
        # Integers are constants and thus integrate to 0. Symbols
        # represent x alone, i.e. "x" with no coefficient or
        # exponent, so they integrate to 1. The difficulty here
        # stems from parsing out the expressions.

        # Omit zero derivatives
        T <: Int && continue

        if T == Symbol
            # This term will integrate to 1
            push!(A, 1)
        else
            # Get the vector of parsed out expression components.
            # The first will be a symbol indicating the operand,
            # e.g. :+, :*, or :^. The second element is the
            # coefficient.
            a = i.args

            # Coefficient
            c = a[2]

            # If the third element is an expression, we have an
            # exponent, otherwise we simply have cx, where c is
            # the coefficient.
            if typeof(a[3]) != Expr
                push!(A, c)
            else
                # Exponent
                x = a[3].args[3]

                # String representation of the differentiated term
                s = string(c*x, "x", x > 2 ? string("^", x-1) : "")

                push!(A, s)
            end
        end
    end

    # Return the elements of A joined into a string
    join(A, " + ")
end

Perl, 64 63 bytes
62b code + 1 command line (-p)
s/(\d+)x.(\d+)/$1*$2."x^".($2-1)/eg;s/\^1\b|^\d+ . |x(?!\^)//g

Usage example:
echo "1 + 2x + 3x^2" | perl -pe 's/(\d+)x.(\d+)/$1*$2."x^".($2-1)/eg;s/\^1\b|^\d+ . |x(?!\^)//g'

Thanks Denis for -1b

C, 204 162 bytes
#define g getchar()^10
h,e;main(c){for(;!h&&scanf("%dx%n^%d",&c,&h,&e);h=g?g?e?printf(" + "):0,0:1:1)e=e?e:h?1:0,e?printf(e>2?"%dx^%d":e>1?"%dx":"%d",c*e,e-1):0;}

Basically parse each term and print out the differentiated term in sequence. Fairly straightforward.

CJam, 62 57 55 49 bytes
Well, Dennis put this to shame before I even noticed that the site was back up. But here is my creation anyway:
lS/{'x/:T,({T~1>:T{~T~*'xT~(:T({'^T}&}&" + "}&}/;

Latest version saves a few bytes with shortcuts suggested by @Dennis (use variables, and split at space instead of +).
Try it online

Saving in a variable is shorter than popping in the else block. For example, _({'^a\}{;}? is 1 byte longer than :T({T'^a\}&.

If you split at spaces instead of plus signs, you don't need the ~ in the remaining else block and can eliminate that one as well.

@Dennis That works, thanks. I originally wanted to eliminate the plus signs, but they drop out anyway when I test for the presence of x. I found some more improvements while I was at it. Mostly, because I have the values in variables now, I can recall them where I really need them, saving some stack manipulation. I also had a stray a that should have been deleted when I optimized the output generation earlier.

JavaScript ES6, 108 bytes
f=s=>s.replace(/([-\d]+)(x)?\^?(\d+)?( \+ )?/g,(m,c,x,e,p)=>x?(c*e||c)+(--e?x+(e>1?'^'+e:''):'')+(p||''):'')

ES5 Snippet:

// ES5 version, the only difference is no use of arrow functions.
function f(s) {
  return s.replace(/([-\d]+)(x)?\^?(\d+)?( \+ )?/g, function(m,c,x,e,p) {
    return x ? (c*e||c) + (--e?x+(e>1?'^'+e:''):'') + (p||'') : '';
  });
}

[
  '3 + 1x + 2x^2',
  '1 + 2x + -3x^2 + 17x^17 + -1x^107',
  '17x + 1x^2'
].forEach(function(preset) {
  var presetOption = new Option(preset, preset);
  presetSelect.appendChild(presetOption);
});

function loadPreset() {
  var value = presetSelect.value;
  polynomialInput.value = value;
  polynomialInput.disabled = !!value;
  showDifferential();
}

function showDifferential() {
  var value = polynomialInput.value;
  output.innerHTML = value ? f(value) : '';
}
code {
  display: block;
  margin: 1em 0;
}
Preset:
<select id="presetSelect" onChange="loadPreset()">
  <option value="">None</option>
</select>
<input type="text" id="polynomialInput"/>
<button id="go" onclick="showDifferential()">Differentiate!</button>

Python 2, 166 bytes
Boy, this seems longer than it should be.
S=str.split
def d(t):e="^"in t and int(S(t,"^")[1])-1;return`int(S(t,"x")[0])*(e+1)`+"x"[:e]+"^%d"%e*(e>1)
print" + ".join(d(t)for t in S(raw_input()," + ")if"x"in t)

The function d takes a non-constant term t and returns its derivative. The reason I def the function instead of using a lambda is so I can assign the exponent minus 1 to e, which then gets used another four times. The main annoying thing is having to cast back and forth between strings and ints, although Python 2's backtick operator helps with that.
We then split the input into terms and call d on each one that has "x" in it, thereby eliminating the constant term. The results are joined back together and printed.

Pyth, 62 bytes
jJ" + "m::j"x^",*Fdted"x.1$"\x"x.0"kftTmvMcd"x^"c:z"x ""x^1 "J

Pretty ugly solution, using some regex substitutions.

Python 3, 176 bytes
s=input().split(' + ')
y='x'in s[0]
L=map(lambda x:map(int,x.split('x^')),s[2-y:])
print(' + '.join([s[1-y][:-1]]+['x^'.join(map(str,[a*b,b-1])).rstrip('^1')for a,b in L]))

Indeed, the main annoyance is having to convert between strings and ints. Also, if a constant term was required, the code would only be 153 bytes.

First answer, was shooting for beating DLosc, didn't quite get there.

Python 2, 229 bytes
import os
print' + '.join([i,i[:-2]][i[-2:]=='^1'].replace('x^0','')for i in[`a*b`+'x^'+`b-1`for a,b in[map(int,a.split('x^'))for a in[[[i+'x^0',i+'^1'][i[-1]=='x'],i]['^'in i]for i in os.read(0,9**9).split(' + ')]]]if i[0]!='0')

Python 2, 174 bytes
print' + '.join(['%d%s%s'%(b[0]*b[1],'x'*(b[1]>1),'^%d'%(b[1]-1)*(b[1]>2))for b in[map(int,a.split('x^')if 'x^'in a else[a[:-1],1])for a in input().split(' + ')if 'x'in a]])

Unfortunately, DLosc's trick to rename the split method and perform the differentiation in a specific function does not shorten my code...

Swift 5.9, 218 bytes
let f={{$0.split(separator:" + ").flatMap{let h=$0.contains,d=h("^") ?Int($0.split{$0=="^"}[1])!:h("x") ?1:0,c=d*Int($0.prefix{$0<"x"})!
return c==0 ?nil:"\(c)\(d<2 ?"":"x")\(d<3 ?"":"^\(d-1)")"}.joined}($0+"")(" + ")}


text:
Golfing with Python Import
When is it beneficial to use inline, single use importing in Python?
For example:
__import__("x").doSomething()

Is the above ever shorter than the below?
import x
x.doSomething()

Or
from x import*
doSomething()

This can be useful if you want to use a module just once in an anonymous lambda function, as it allows you to avoid writing a separate statement:
lambda x:__import__('SomeModule').foo(x,123)

is one byte shorter than
from SomeModule import*;f=lambda x:foo(x,123)

If the code is a named function or program, then __import__ is unlikely to help except in the most extreme or contrived circumstances.

__import__ would help inside of a named function since it would be inside of an indented block. An import would cost extra since it's on two lines and indented. (That's assuming that imports aren't allowed outside of the function.)

@AlexA I see no problem with placing imports outside of a named function.

Then would there ever be a time when import would be called inside of an indented block? Probably not.

placing imports outside of the named function won't work for challenges where you're writing just one function.

The second example doesn't require the f= because anonymous functions are allowed and can have content outside the function.

@xnor Nowhere in the 2nd question or its answers are anonymous functions mentioned. I wouldn't call a block of code a function literal unless the entire code is a single expression.

This is not true, because imports are allowed preceding a function literal. Here, from SomeModule import*;lambda x:foo(x,123) would be the shortest.

@Challenger5 I don't agree that from SomeModule import*;lambda x:foo(x,123) is a valid answer. It is not a program, does not define a named function, and is not a function expression.

@feersum Here's a random example I found.

When importing multiple modules with sufficiently long names, it can be helpful to assign the __import__ function to a shorter variable and use it for imports
Example:
Regular import statements - 97 bytes

from itertools import*
from datetime import*
print list(permutations("abc"))
print datetime.now()

Assigning __import__ to i - 94 bytes:

i=__import__
print list(i("itertools").permutations("abc"))
print i("datetime").datetime.now()

Almost never.
__import__("x").doSomething() needs 15+x characters to refer to a module with a name of length x.
import x\nx.doSomething() needs 9+2*x characters. These functions overlap at x=6, so compared to this way any module with a longer name is better off using __import__, anything shorter benefits from normal imports:

However, from x import*\ndoSomething() needs only 14+x characters, so compared to the normal import it is not worth it unless the module name is longer than 5 characters:

This all assumes that you are referring to a function/class/whatever only once. If you refer to it more than once, the formulas change, and the latter version might become the winner. In case you use something long from an imported module several times, yet another version wins:
from x import y as z nets you 18+x+y+z*(n+1) characters for n uses of z, which is a large improvement if y is big, because z can be made 1.

Can you check your math? I find __import__("x").doSomething() to be one char shorter than from x import*;doSomething(). Maybe you're counting the newline as two chars? And I recall the break-even point being 5, falling between time and random.

@xnor I didn't count newlines twice, but I missed that you don't need the dot in that version. Give me a minute, I'll update.

z=__import__("x").y is a byte shorter than from x import y as z

@negativeseven Shorter: from x import*;z=y.


text:
Take It or Leave It II: A Game Show for Computers
This is the second in a series of puzzles that I will be posting every Monday at Midnight PST. The first puzzle is located Here.
Context:

A reclusive billionaire has created a game show to attract the world's best and brightest programmers. On Mondays at the stroke of midnight, he chooses one person from a pool of applicants to be the contestant of the week, and provides them with a game. You are this week's lucky contestant!

This week's game:

The host provides you with API access to a stack of 10,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $10,000 (no two envelopes contain the same dollar value).
You have 4 commands at your disposal:

Read(): Read the dollar figure in the envelope at the top of the stack.

Take(): Add the dollar figure in the envelope to your game show wallet, and pop the envelope off the stack.

Pass(): Pop off the envelope on the top of the stack.

Oracle(M): Returns the mean value of the next M envelopes in the stack, not including the one you can currently Read().

The Rules:

If you use Pass() on an envelope, the money within is lost forever.

If you use Take() on an envelope containing $X, from that point forward, you may never use Take() on an envelope containing < $X. Take() on one of these envelopes will add $0 to your wallet.

If you use Oracle(M) on turn T, envelopes T+1 through T+M's mean will be returned. Oracle() is disabled until turn T+M.

Write an algorithm that finishes the game with the maximal amount of money.
If you're writing your algorithm in Python, feel free to use this controller provided by @Maltysen: https://gist.github.com/livinginformation/70ae3f2a57ecba4387b5
Notes 1: "Maximal" in this case means the median value in your wallet after N >= 1000 runs. I expect, though I would love to be proven wrong, that the median value for a given algorithm will converge as N increases to infinity. Feel free to try to maximize the mean instead, but I have a feeling that the mean is more likely to be thrown off by a small N than the median is.
Note 2: as all solutions to the previous part of this puzzle are valid here, reposting them has little value. Only algorithmic improvements of previous puzzles will be considered for part II.
Edit: The prize condition has been removed, in light of this post on meta.

Wow, I can't believe I overslept :O

@Beta Decay clock is ticking! :)

What's the sense of the rracle? You could build your own free oracle by just keeping a tally of all previously read envelopes. What am I getting wrong?

@LuisMendo With your own tally, you can only know the mean of all remaining values. With the oracle, you can get the mean of the next M values, where you get to choose M.

Since all solutions to your previous challenge are also valid solutions to this challenge, can we consider them implicitly submitted?

@Reto updated the OP with a second note to that effect.

@RetoKoradi Got it. Thanks

Groovy $713337 $817829 $818227
Bootstrap code:
class Instance {
    List values = new ArrayList(1..10000); {
        Collections.shuffle(values)
    }
    int i = 0
    int value = 0
    int max = 0
    int nextOracle = 0

    def pass() {
        if (i >= 10000)
            throw new NoSuchElementException()
        i++
    }

    def take() {
        if (i >= 10000)
            throw new NoSuchElementException()
        int v = values[i]
        if (v > max) {
            max = v
            value += v
        }
        i++
    }

    double oracle(int m) {
        if (m <= 0 || i < nextOracle || i + m >= 10000)
            throw new NoSuchElementException()

        nextOracle = i + m
        values.subList(i + 1, i + m + 1).stream().reduce { l, r -> r+l }.get() / m
    }

    int read() {
        if (i >= 10000)
            throw new NoSuchElementException()
        values[i]
    }
}

Algorithm
double square(double v) { v * v }
final double factor = Math.pow(1.5, 1.1)
int attempts = 5000
(1..attempts).stream().parallel().mapToLong {
    def puzzle = new Instance()

    int[] memory = 1..10000 // We will remember every envelope
    int memStart = 0

    while (memStart < 10000 - 3) {
        int value = puzzle.read()
        int i = Arrays.binarySearch(memory, memStart, 10000, value) - memStart
        if (i < 0) { // We can't use the money
            puzzle.pass()
            continue
        }
        if (i == 0) { // Of course we take the lowest
            puzzle.take()
            memStart++
            continue
        }
        int remaining = Arrays.stream(memory, i + 1 + memStart, 10000).sum() // Money we could win if taken
        int losing = Arrays.stream(memory, memStart, memStart + i).sum() // Money we cna't win if taken
        if (value > losing) { // If we pass, we lose money automatically
            puzzle.take()
            memStart += i + 1
        } else if ((losing - value * 16 / 7) * square(Math.log(i)) > remaining / factor) {
            System.arraycopy(memory, memStart, memory, ++memStart, i)
            puzzle.pass()
        } else {
            puzzle.take()
            memStart += i + 1
        }
    }

    // It's broken down to last three elements
    List values = Arrays.copyOfRange(memory, 10000 - 3, 10000)
    while (!values.contains(puzzle.read())) // Skip values we can't use
        puzzle.pass()
    int value1 = puzzle.read()
    int value2 = puzzle.oracle(1)
    if (value1 == values.max() && (
            values.contains(value2)
            ? (value1 * 2 < values.sum() && values.min() == value2)
            : (value1 < values.min() / 2 + (values - [value1]).max())
            )) {
        puzzle.pass()
    }

    // Finish it
    while (puzzle.i < puzzle.values.size()) {
        puzzle.take()
    }

    puzzle.value as Long
}.sum() / attempts // Sum runs and average

I compare remaining values with possible values. This script is not fast (takes 1-minute per 1000x simulations)... but it will perform the simulations simultaneously.
I have no idea why my algorithm works, but it was just trial and error: lumping mathematical operations together and manipulating the constants. I ran it 5000x for the current score, in an attempt to reduce the score's fluctuations (it's +/- $4000 depending on iteration count).
Even without the oracle at the end, it should still be (barely) beating @orlp's solution for the prior puzzle.

C# - $803.603 now -> $804.760 (with oracle)
Bootstrap Code
public static class ShuffleExtension
{
    private static Random rng = new Random();

    public static void Shuffle<T>(this IList<T> list)
    {
        int n = list.Count;
        while (n > 1) {
            n--;
            int k = rng.Next(n + 1);
            T value = list[k];
            list[k] = list[n];
            list[n] = value;
        }
    }
}

public class Puzzle
{
    public List<int> Values = new List<int>(10000);

    public Puzzle()
    {
        for ( int i = 1; i <= 10000; i++ )
        {
            Values.Add(i);
        }
        Values.Shuffle();
    }

    public int i = 0;
    public int value = 0;
    public int max = 0;
    public int nextOracle = 0;

    public void Pass() {
        if ( i >= Values.Count )
            throw new IndexOutOfRangeException();
        i++;
    }

    public void Take() {
        if (i >= Values.Count )
            throw new IndexOutOfRangeException();
        int v = Values[i];
        if (v > max) {
            max = v;
            value += v;
        }
        i++;
    }

    public double oracle(int m) {
    if (m <= 0) {
        throw new IndexOutOfRangeException();
    }
    if ( i < nextOracle ) {
        throw new IndexOutOfRangeException();
    }
    if ( i + 1 + m > Values.Count ) {
        throw new IndexOutOfRangeException();
    }

    nextOracle = i + m;
    var oracleValues = new List<int>();
    for ( int l = 0; l < m; l++ )
    {
        oracleValues.Add(Values[i + 1 + l]);
    }
    return oracleValues.Average (v => v);
}

    public int Read() {
        if (i >= Values.Count )
            throw new IndexOutOfRangeException();
        return Values[i];
    }
}

Game Code:
    void Main()
{
    var m = 0;
    for ( int l = 0; l < 1000; l++ )
    {
        var game = new Puzzle();
        var maxVal = 0;
        var lastOracle = 0;
        var lastOracleValue = 0.0m;
        var oracleValueForIOf = 0;

        for ( int i = 0; i < 10000; i++ )
        {
            var val = game.Read();
            var oracleStep = 1;
            var canUseOracle = (i - lastOracle >= oracleStep) && i + oracleStep + 1 <= 10000;
            if ( canUseOracle )
            {
                var oracle = game.oracle(oracleStep);
                lastOracle = i;
                lastOracleValue = (decimal)oracle;
                oracleValueForIOf = i + 1;
            }
            if ( TakeTheMoney(val, maxVal, oracleValueForIOf, lastOracleValue, i) )
            {
                maxVal = val;
                game.Take();
            }
            else
            {
                game.Pass();
            }
        }
        m += game.value;
    }
    ((int)(m / 1000)).Dump();
}

private bool TakeTheMoney(int val, int maxVal, int oracleValueForIOf, decimal lastOracleValue, int i)
{
    if ( val > maxVal )
    {
        if ( oracleValueForIOf != i + 1
            &&
            (val < 466.7m + (0.9352m * maxVal) + (0.0275m * i))
            )
        {
            return true;
        }

        if (oracleValueForIOf == i + 1)
        {
            if ( val < 466.7m + (0.9352m * maxVal) + (0.0275m * i) )
            {
                return true;
            }
            if ( lastOracleValue > 466.7m + (0.9352m * val) + (0.0275m * i + 1) )
            {
                if ( val < 466.7m + (0.9352m * maxVal) + (0.0275m * i + 1) )
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Credit belongs to Reto Koradi (https://codegolf.stackexchange.com/a/54181/30910)
Edit: Basic Use of Oracle implemented. If the next oracle is above the threshold to use expand the current envelope to the index of the Oracle Index. This doesn't hit often but IT IS an Improvement ;-)

I don't think it's very productive to repost solutions from the previous challenge. We all recognized that those solutions can be used as a baseline to this challenge, and I had already left a comment for the OP asking how we should handle that. The idea is that you come up with your own solution, which is ideally better than the solutions to the previous challenge.

please stop downvoting :) note number 2 was added after my submission. and as it is more effective than the other solutions - i have posted it here. no need to use oracle to beat the existing solutions.

@StephanSchinkel You have my upvote if you manage to include the Oracle to improve the current score. Even by just $1.

@BetaDecay what it is exactly that is frowned upon by the community again? I just followed the question from the op. Once again Note Number 2 was added AFTER my submission.

To Not use a solution from part I of the quiz.

@Dorus: done ;)

Python - $74112
Only take, if the current value is lower than the next value (i.e. you can take both).
def algo():
  try:
    o=oracle(1)
  except ValueError:
    take()
  r=read()
  if r>o:
    passe()
  else:
    take()

Python - (still calculating the mean)
This answer takes VERY LONG to calculate. It reaches around 670.000$.
I remember each envelope I saw. Every time I have to make a decision, I generate two lists of remaining envelopes that I could potentially add to my wallet if I take the current envelope or leave it respectively.
I did not optimize the code.
def algo_2():
  global max_taken, past
  weight=0.92 #Empirically chosen.
  r=read()
  if len(past)==0:
    past.append(r)
    passe()
    return
  if r<max_taken:
    past.append(r)
    take() #the same as passe
    return
  coming=[x for x in range(1,10001) if x not in past and x>max_taken and x!=r ]
  comingIfTake=[x for x in range(1,10001) if x not in past and x>r ]
  if sum(coming)*weight<=sum(comingIfTake)+r:
    past.append(r)
    take()
  else:
    past.append(r)
    passe()

And init_game starts like this:
def init_game():
    global stack, wallet, max_taken, oracle_turns, past
    past=[]

If you use sets to represent past, coming, and comingIfTake, and use intersections, your code would be much faster.

C# - $780.176
Check if the next value is within the lower 5% of all remaining values. Get more relaxed as we get to the end.
public class Taker
{
    private List<int> remaining;
    private Game game;

    public Taker(Game game)
    {
        this.game = game;
        remaining = Enumerable.Range(1, game.Size + 100).ToList();
    }

    int score = 0;

    public int PlayGame()
    {
        for (int i = 0; i < game.Size; i++)
        {
            if (game.Read() < game.Max ||
                game.Read() > selectThreshold() ||
                doOracle()
                )
            {
                remaining.Remove(game.Read());
                game.Pass();
                continue;
            }
            remaining = remaining.SkipWhile(j => j < game.Read()).ToList();
            score += game.Take();
        }
        return score;
    }

    private bool doOracle()
    {
        return game.Oracle(1) < game.Read() &&
            game.Oracle(1) > game.Max;
    }

    private int selectThreshold()
    {
        int selector = (int)(remaining.Count * 0.05);
        return remaining.ElementAt(selector);
    }
}

And my game class, very ugly, game class doesn't even validate if oracle is allowed, but since i only use Oracle(1) that shouldn't be a problem.
public class Game
{
    private int[] list;
    private int position = 0;
    private int max = 0;
    public int Max { get { return max; } }
    public int Size { get { return list.Length; } }

    public Game(int[] list)
    {
        this.list = list;
    }

    public int Read()
    {
        return list[position];
    }

    public int Take()
    {
        if (list[position] < max)
        {
            position++;
            return 0;
        }
        max = list[position];
        return list[position++];
    }

    public void Pass()
    {
        position++;
    }

    public int Oracle(int M)
    {
        int next = position + 1;
        M = Math.Max(0, Math.Min(M, list.Length - next));
        return new ArraySegment<int>(list, next, M).Sum();
    }
}

Java, $804,991
Score is from 1001 rounds.  It is probably too close to call between this answer and Stephan Schinkel's.
This is based on my answer in the previous challenge, in that it uses the same entropy-based calculation to estimate payoffs.  The main difference is that it simply now takes envelopes in pairs (1 & 2, then 3 & 4, so on) and looks at the possible combinations of take-take, take-pass, pass-take, etc.  It also calculates the exact estimated score when the number of valid envelopes is really small.
The "wrapper" I wrote isn't really a true wrapper, it just gives envelopes in pairs instead of calling an Oracle(1) function every other round.
Overall, I would say that, despite the increased complexity, this bot really isn't better than my previous one.
Player
import java.lang.Math;
public class Player2
{
    public int[] V;

    public Player2(int s)
    {
        V = new int[s];
        for(int i = 0; i<V.length; i++)
        {
            V[i] = i+1;
        }
        ////System.out.println();
    }

    public boolean [] takeQ(int x, int y)
    {
        //System.out.println("Look: " + x + " " + y);
        boolean [] move = new boolean[]{false,false};
        double max = 0;
        double val = 0;
        int[] nextV = V;

        ////System.out.println("look " + x);
        int i = find(V,x);
        if(i >= 0)  //if found
        {
            //try taking first envelope
            int[] newVt = takeSlice(V,i);
            //System.out.println("  T: " + ats(newVt));
            int j = find(newVt,y);
            if(j >= 0)
            {
                //try taking first and second
                int[] newVtt = takeSlice(newVt,j);
                val = x + y + calcVal(newVtt);
                //System.out.println("  TT: " + ats(newVtt) + " " + val);
                if(val > max)
                {
                    move = new boolean[]{true,true};
                    max = val;
                    nextV = newVtt;
                }
            }
            //try taking first and passing second
            int[] newVtp = passSlice(newVt,j);

            val = x + calcVal(newVtp);
            //System.out.println("  TP: " + ats(newVtp) + " " + val);
            if(val > max)
            {
                move = new boolean[]{true,false};
                max = val;
                nextV = newVtp;
            }
        }
        int[] newVp = passSlice(V,i);
        //System.out.println("  V: " + ats(V));
        //System.out.println("  P: " + ats(newVp));
        int j = find(newVp,y);
        if(j >= 0)
        {
            //try passing first and taking second
            int[] newVpt = takeSlice(newVp,j);
            val = y + calcVal(newVpt);
            //System.out.println("  PT: " + ats(newVpt) + " " + val);
            if(val > max)
            {
                move = new boolean[]{false,true};
                max = val;
                nextV = newVpt;
            }
        }
        //try taking first and passing second
        int[] newVpp = passSlice(newVp,j);

        val = calcVal(newVpp);
        //System.out.println("  PP: " + ats(newVpp) + " " + val);
        if(val > max)
        {
            move = new boolean[]{false,false};
            max = val;
            nextV = newVpp;
        }
        V = nextV;
        //System.out.println("  NEW: " + ats(V));
        return move;
    }

    public static String ats(int [] a)
    {
        String s = "";
        for(int i = 0; i < a.length; i++)
        {
            s += a[i] + ",";
        }
        return s;
    }

    public static int[] takeSlice (int[] list, int loc)
    {
        int [] newlist = new int[list.length - loc - 1];
        for(int j = loc + 1; j < list.length; j++)
        {
            newlist[j - loc - 1] = list[j];
        }
        return newlist;
    }

    public static int[] passSlice (int[] list, int loc)
    {
        int [] newlist = list;
        if(loc >= 0)
        {
            newlist = new int[list.length-1];
            for(int k = 0; k < loc; k++)
            {
                newlist[k] = list[k];
            }
            for(int k = loc + 1; k < list.length; k++)
            {
                newlist[k-1] = list[k];
            }
        }
        return newlist;
    }

    public static double calcVal(int [] list)
    {
        if(list.length < 8)
        {
            for(int i : list)
            {
                ////System.out.print(i + ",");
            }

                ////System.out.println();
            return computeMean(list);

        }
        return smoothEstimate(list);
    }

    public static double computeMean(int[] V)
    {
        if(V.length == 1)
        {
            return V[0];
        }
        else if(V.length > 1)
        {
            double[] Es = new double[V.length];
            for(int i = 0; i < V.length; i++)
            {
                int[] newVp = new int[V.length - 1];
                for(int j = 0; j < i; j++)
                {
                    newVp[j] = V[j];
                }
                for(int j = i + 1; j < V.length; j++)
                {
                    newVp[j-1] = V[j];
                }
                double pass = computeMean(newVp);
                int[] newVt = new int[V.length - i - 1];
                for(int j = i + 1; j < V.length; j++)
                {
                    newVt[j - i - 1] = V[j];
                }
                double take = V[i] + computeMean(newVt);
                if(take > pass)
                {
                    Es[i] = take;
                }
                else
                {
                    Es[i] = pass;
                }
            }
            double sum = 0;
            for(double d : Es)
            {
                sum += d;
            }
            return sum/V.length;
        }
        else
        {
            return 0;
        }
    }

    public static double smoothEstimate(int [] list)
    {
        double total = 0;
        for(int i : list)
        {
            total+=i;
        }
        double ent = 0;
        for(int i : list)
        {
            if(i > 0)
            {
                ent -= i/total * Math.log(i/total);
            }
        }
        ////System.out.println("      total " + total);
        ////System.out.println("      entro " + Math.exp(ent));
        ////System.out.println("      count " + list.length);
        return total * Math.pow(Math.exp(ent),-0.5) * 4.0/3;// * 1.1287 + 0.05284);
    }

    public static int find(int[] list, int search)
    {
        int first  = 0;
        int last   = list.length - 1;
        int middle = (first + last)/2;

        while( first <= last )
        {
            if ( list[middle] < search )
                first = middle + 1;
            else if ( list[middle] == search )
                break;
            else
                last = middle - 1;

            middle = (first + last)/2;
        }

        if(first > last)
        {
            return -1;
        }
        return middle;
    }
}

Controller
import java.lang.Math;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;
public class Controller2
{
    public static void main(String [] args)
    {
        int size = 10000;
        int rounds = 1001;
        ArrayList<Integer> results = new ArrayList<Integer>();
        for(int round = 0; round < rounds; round++)
        {
            int[] envelopes = new int[size];
            for(int i = 0; i<envelopes.length; i++)
            {
                envelopes[i] = i+1;
            }
            shuffleArray(envelopes);
            Player2 p = new Player2(size);
            int cutoff = 0;
            int winnings = 0;
            for(int i = 0; i<envelopes.length; i+=2)
            {
                boolean [] take = p.takeQ(envelopes[i],envelopes[i+1]);
                if(take[0] && envelopes[i] >= cutoff)
                {
                    winnings += envelopes[i];
                    cutoff = envelopes[i];
                }
                if(take[1] && envelopes[i+1] >= cutoff)
                {
                    winnings += envelopes[i+1];
                    cutoff = envelopes[i+1];
                }
            }
            results.add(winnings);
        }
        Collections.sort(results);
        System.out.println(rounds + " rounds, median is " + results.get(results.size()/2));

    }

    //stol... I mean borrowed from http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array
    static void shuffleArray(int[] ar)
    {
        Random rnd = new Random();
        for (int i = ar.length - 1; i > 0; i--)
        {
            int index = rnd.nextInt(i + 1);
            // Simple swap
            int a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
        }
    }
}

Bitcoin address: 1BVBs9ZEP8YY4EpV868nxi2R23YfL7hdMq

Python 3 - $615570
Doesn't actually use the oracle... Eh :)
def algo():
    global prevs

    try:
        prevs.append(read())
    except NameError:
        prevs = [read()]

    if len(prevs) > 10000:
        prevs = [prevs[-1]]

    if read() < round(len(prevs),-1):
        take()
    else:
        passe()

Builds up a list of all previous envelopes and check if the current envelope is less than the number of previous envelopes in 10 envelope increments.

Python, 87,424
Here's a plain and easy algorithm, the lucky seven.
def LuckyNumber7():
Test = read()
if "7" in str(Test):
    take()
else:
    passe()

test(LuckyNumber7)

Basically what it does is it converts read() to a string and checks if there's a seven in it. If there is, it takes the envelope. If not, it passes it.
It averages around 81,000, I haven't been keeping track.

So this shows that relying on luck is not a successful strategy? ;)

@RetoKoradi Yep :D