text:
Princely Prefix by a Program in Pattern
You should write a program or function which outputs or returns as much of Chapter I of The Little Prince as it can. Your program or function has to be an M-by-N block of code containing only printable ascii characters (codepoint from 32 to 126) and newlines at the end of each row.
You can only use at most 26 characters of your choosing from the 96 printable ascii characters (and the newlines at the end of the rows).
In each row and column every character has to be distinct similar to a sudoku puzzle i.e. there can't be a letter in a row or column twice.
A correct example codeblock with M = 4, N = 3 and alphabet = {a,b,c,d,/,*}:
abcd
bcd*
*/ac

Code details

You can choose the shape of your code-block (i.e. M and N).
The block has to be filled with characters entirely i.e. every row has to have the same length.
A trailing newline at the end of the last row is optional.
As written above in each row and column every character has to be distinct.

Output details

You should output or return a prefix of Chapter I of The Little Prince  without any additional output.
If you reach a newline in the text you can represent it as any common variant (\r,\n,\r\n) but use only one of them and count it as 1 byte to the score.
An extra trailing newline is optional.

Your score is the length of the output text excluding an additional newline if present. Higher score is better.
Example answer
##Python3, score = 6

alphabet = `print('O\ce w)#X` (alphabet element count = 16)

    print('O\
    nce w')#X

You can check the validity of your code with this Python 3 (ideone) program or this CJam program (online) provided by @MartinBüttner.

Doesn't this limit the program size to 26x26 at most?

@marinus Yes it does.

Are you sure this is solvable?

@FUZxxl the question contains a reference solution with score 6. Hopefully the question is designed such that it's not possible to print the entire thing (or it would need a tie breaker).

@MartinBüttner Ah! I forgot about the “a prefix of...” part.

by "prefix" you mean that the words must be in order, starting from the beginning?

I don't think anyone will get the whole thing. There are information density concerns, even if you could use all 626 characters to encode it. I predict someone will do some clever compression into a ~16 character codeset, and get maybe 400 characters of output.

CJam, 47
"Once wh
en Imwas
msix yea
r2s oldm
I "N-'m/
Sc*2s-O"
saw"N/SO
o'aS"m2
a"Oo2s-N
-S/OI*so
'yI-a"nr
wiNadI"c
cel'iaIS
/m2*Oo'x
 I-scel*
Ooel'c 2
2/'e*ON-

Try it online
Alphabet:  "'*-/2INOSacdehilmnorswxy
Explanation:
"Once wh
en Imwas
msix yea
r2s oldm
I "         push this string
N-          remove newlines
'm/Sc*      replace m's with spaces (the c is redundant)
2s-         convert 2 to string and remove 2's
O           push an empty string
"
saw"        push this string
N/          split into lines (effectively removes the newline)
S           push a space
Oo          print empty string (no-op)
'a          push 'a'
S           push a space
"m2
a"          push this string
Oo          print empty string (no-op)
2s-         convert 2 to string and remove 2's
N-          remove newline
S/          split by space (effectively removes the space)
OI*so       print an empty string repeated 18 times (no-op)
'y          push 'y'
I-          subtract 18 -> 'g'
a           wrap in array (string) -> "g"
"nr
wiNadI"     push this string
c           convert to (first) character -> 'n'
c           convert to character (no-op)
el          convert to lowercase (no-op)
'i          push 'i'
a           wrap in array (string) -> "i"
IS/         split " " into slices of length 18 -> [" "]
m           (acting as -) remove space strings from "i" (no-op)
2*          repeat "i" 2 times -> "ii"
Oo          print empty string (no-op)
'x          push 'x'
I-          subtract 18 -> 'f'
sc          convert to string and back to char (no-op)
el          convert to lowercase (no-op)
*           join "ii" with separator 'f' -> "ifi"
Oo          print empty string (no-op)
el          convert to lowercase (no-op)
'c          push 'c'
2 2/        divide 2 by 2 -> 1
'e          push 'e'
*           repeat 'e' 1 time -> "e"
O           push empty string
N-          remove newlines (no-op)

Pip, score = 38
eyli:
"Once
when0
I was
si01x
year5
old I
0sMw1
1M 0"
X1RMh
Rnsxy
iR:'M
'aiR
:5'si

Alphabet:  "'015:IMORXacdehilnorswxy
(I sure would hate to try this in a real programming language.)
Explanation:
eyl      Statements consisting of single variables are no-ops
i:       Assign to i the following:
"Once
when0
I was
si01x
year5
old I
0sMw1
1M 0"    ...this string
X1       ...repeated once (no-op to get alignment right)
RMh      ...with all 1s and 0s removed (h is preinitialized to 100)
Rns      ...and all newlines replaced with spaces.
xy       More no-ops
iR:'M'a  Replace every M with a, assigning result back to i
iR:5's   Replace every 5 with s, assigning result back to i
i        Auto-print i

Python 3, score=11
This is a really tough problem for Python, as the restrictions on repeating characters on a line or column make it nearly impossible to make more than one string literal. The various ways of joining strings together are thus fairly useless, since you can't get the strings to start with in any useful way. Here's my best attempt:
x=chr
print(
"Once\
 when"
,x(73)
)#prin

Note that there is a space at the end of the first line. The alias x for chr is necessary to avoid the same character ending up in more than one column. The comment characters at the end could be almost anything.
The alphabet is 21 printable characters, plus newline (note the space at the start):
 "#(),37=O\cehinprtwx

Output is:

Once when I

Note that this is valid in Python 2 also. Grats on finding a good answer.

CJam, score = 21
"Once wh
en I"N-o
N;S"was
six y"N-

Alphabet: -;INOSacehinoswxy
Just to get the ball rolling; this can probably be beaten easily.

CJam, score = 15
I've had this idea for a while now but I haven't had time to sit down and shuffle things around until I get the needed column uniqueness, so here's a baby version for now:
 79c32"*)+#,105468:;=>Ibef
,:=>Ibcef";7 6)#*219435+80
50I=>;9)6#*127438+ ":,bcfe
),68:>=Ibcef";20 5#*17394+
6)4*b123,97>:c"80f5=+;e# I
"9>+f=e# ),*0481362bI:;5c7

Alphabet (26): " #)*+,0123456789:;=>Ibcef
Try it online.
Explanation
The basic idea is to make use of base encoding so we can print more than 26 types of chars. The core code is
79c                             e#  Push "O"
85032995607801617394 28b        e#  Push array of indices, encoding using base 28
123,97>:c" I                    e#  Push "abcdefghijklmnopqrstuvwxyz I\n"
"+
f=                              e#  Map indices to chars

Note that we treat the first "O" for "Once" separately because including it in our string would take too much of our alphabet. If we wanted to we could try extended our indexing string, but since no more uppercase characters happen for a while apart from "I" I didn't bother too much with this.
We then need to build the big number on the second line somehow. The approach I took was to repeatedly multiply by some power, then add a constant, and repeat, so in the above code 85032995607801617394 is replaced by
32
7 6) # * 219435 +
9) 6 # * 127438 +
20 5 # * 17394 +

where ) is increment and # is exponentiation in CJam.
Then the rest (the most annoying part) is padding each row to fulfill the column criteria. To do this we dump chars in strings and use ; to pop them. Unfortunately, while we would very much like to use e# for comments as well to make things easier, the fact that # is exponentiation forbids this, so this is only done on the last line.
I'm fairly certain this method can be extended up until the comma in the first sentence, but unfortunately shuffling things around to meet the column criteria is proving difficult, so I might need another method of generating the base-encoded integer.

Python 2, score = 13 (invalid)
Python isn't the best language for this.... Upon further inspection, there are two ns in my first line. There is no worthwhile remedy, and I'm going to stop wasting my time with Python. I'm currently working on making a solution in another language, but will not share which one yet.
print"Once wh\
en I",#Oncehtp
chr(0167)#Onwt

Alphabet (22): "#(),0167IOcehinprtw
Output: Once when I w

Your first line is invalid, since it has two ns. This problem is nearly impossible in Python, since you can only use a line continuation backslash once (since the backslash needs to be in the last column) and no line can have two of the same kind of quotation mark.

@Blckknght Ah, I missed that one. Yeah. My answer would probably not be better than the OP's example then...

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


text:
Random Golf of the Day #4: The Bertrand Paradox
About the Series
First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You can find the leaderboard along with some more information about the series in the first post.
Although I have a bunch of ideas lined up for the series, the future challenges are not set in stone yet. If you have any suggestions, please let me know on the relevant sandbox post.
Hole 4: The Bertrand Paradox
The Bertrand paradox is an interesting problem, which shows how different methods for picking random chords in a circle can yield different distributions of chords, their midpoints and their lengths.
In this challenge you are supposed to generate random chords of the unit circle, using the "right" method, i.e. one which produces a distribution of chords which is invariant under scaling and translation. In the linked Wikipedia article, "Method 2" is such a method.
Here are the exact rules:

You should take one positive integer N which specifies how many chords should be returned. The output should be a list of N chords, each specified as two points on the unit circle, given by their polar angle in radians.
Your code should be able to return at least 220 different values for each of the two angles. If your available RNG has a smaller range, you must either first build an RNG with a sufficiently large range on top of the built-in one or you must implement your own suitable RNG. This page may be helpful for that.
The distribution of chords must be indistinguishable from the one produced by "Method 2" in the linked Wikipedia article. If you implement a different algorithm to choose chords, please include a proof of correctness. Whatever algorithm you choose to implement, it must theoretically be able to generate any valid chord in the unit circle (barring limitations of the underlying PRNG or limited-precision data types).
Your implementation should use and return either floating-point numbers (at least 32 bits wide) or fixed-point numbers (at least 24 bits wide) and all arithmetic operations should be accurate within at most 16 ulp.

You may write a full program or a function and take input via STDIN (or closest alternative), command-line argument or function argument and produce output via STDOUT (or closest alternative), function return value or function (out) parameter.
Output may be in any convenient list or string format, as long as the individual numbers are clearly distinguishable and their total number is always even.
This is code golf, so the shortest submission (in bytes) wins. And of course, the shortest submission per user will also enter into the overall leaderboard of the series.
Visualisation
You can use the following snippet to render the generated lines and inspect their distribution. Simply paste a list of pairs of angles into the text area. The snippet should be able to handle almost any list format, as long as the numbers are simple decimal numbers (no scientific notation). I recommend you use at least 1000 lines to get a good idea of the distribution. I've also provided some example data for the different methods presented in the article below.

function draw() {
  document.getElementById("output").innerHTML = svg
}

function drawLines() {
  lines = document.getElementById("lines").value;
  var e = prefix;
  //e += '<circle cx="' + offset + '" + cy="' + offset + '" r="' + radius + '" stroke="black" fill="white"/>';
  lines = lines.match(/-?(?:\d*\.\d+|\d+\.\d*|\d+(?!\.))/g);
  for (i = 0; i < lines.length; i+=2)
  {
    t1 = parseFloat(lines[i]);
    t2 = parseFloat(lines[i+1]);
    x1 = Math.cos(t1);
    y1 = Math.sin(t1);
    x2 = Math.cos(t2);
    y2 = Math.sin(t2);
    e += '<path stroke="black" stroke-opacity="0.2" d="M ' + (x1 * radius + offset) + ' ' + (y1 * radius + offset) + ' L ' + (x2 * radius + offset) + ' ' + (y2 * radius + offset) + '"/>';
  }
  e += suffix;
  svg = e;
  draw();
}
var prefix = '<svg height="450" width="450">',
  suffix = "</svg>",
  scale = 0.95,
  offset = 225,
  radius = scale*offset,
  svg = "";
svg {
  position: absolute;
}
Paste line specifications here

<input id="lines" type="textarea" size="60" oninput='drawLines()' />

Example data generated with method 1.
Example data generated with method 2.
Example data generated with method 3.
Leaderboard
The first post of the series generates a leaderboard.
To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:
# Language Name, N bytes

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

(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)

IA-32 machine code, 54 bytes
Hexdump of the code:
68 00 00 00 4f 0f c7 f0 50 db 04 24 58 d8 34 24
f7 d9 78 f1 d9 c0 dc c8 d9 e8 de e1 d9 fa d9 c9
d9 f3 dc c0 d9 eb de ca d8 c1 dd 1a dd 5a 08 83
c2 10 e2 d1 58 c3

It uses a (slightly modified) algorithm that Wikipedia described. In pseudo-code:
x = rand_uniform(-1, 1)
y = rand_uniform(-1, 1)
output2 = pi * y
output1 = output2 + 2 * acos(x)

I use the range -1...1 because it's easy to make random numbers in this range: the rdrand instruction generates an integer between -2^31 and 2^31-1, which can be easily divided by 2^31.
I should have used the range 0...1 for the other random number (x), which is fed into acos; however, the negative part is symmetric with the positive part - negative numbers produce chords whose span is greater than pi radians, but for the purpose of illustrating the Bertrand paradox, it doesn't matter.
Since the 80386 (or x87) instruction set doesn't have a dedicated acos instruction, I had to express the calculation using only the atan instruction:
acos(x) = atan(sqrt(1-x^2)/x)

Here is the source code that generates the machine code above:
__declspec(naked) void __fastcall doit1(int n, std::pair<double, double>* output)
{
    _asm {
        push 0x4f000000;        // [esp] = float representation of 2^32

    myloop:
        rdrand eax;             // generate a random number, -2^31...2^31-1
        push eax;               // convert it
        fild dword ptr [esp];   // to floating-point
        pop eax;                // restore esp
        fdiv dword ptr [esp];   // convert to range -1...1
        neg ecx;
        js myloop;              // do the above 2 times

        // FPU stack contents:  // x           | y
        fld st(0);              // x           | x   | y
        fmul st(0), st;         // x^2         | x   | y
        fld1;                   // 1           | x^2 | x | y
        fsubrp st(1), st;       // 1-x^2       | x   | y
        fsqrt;                  // sqrt(1-x^2) | x   | y
        fxch;                   // x           | sqrt(1-x^2) | y
        fpatan;                 // acos(x)     | y
        fadd st, st(0);         // 2*acos(x)   | y
        fldpi;                  // pi          | 2*acos(x) | y
        fmulp st(2), st;        // 2*acos(x)   | pi*y
        fadd st, st(1);         // output1     | output2
        fstp qword ptr [edx];   // store the numbers
        fstp qword ptr [edx + 8];

        add edx, 16;            // advance the output pointer
        loop myloop;            // loop

        pop eax;                // restore stack pointer
        ret;                    // return
    }
}

To generate two random numbers, the code uses a nested loop. To organize the loop, the code takes advantage of the ecx register (outer loop counter) being positive. It temporarily negates ecx, and then does it again to restore the original value. The js instruction repeats the loop when ecx is negative (this happens exactly once).

I like this answer for using IA32 assembly! Just to say: this is not strictly 386 machine code as 80386 obviously don't have rdrand instruction nor necessary a FP coprocessor

Yeah, IA32 is a better name. Not specific enough but probably more correct than 80386.

Pyth, 25 23 22 bytes
A port of rcrmn's C++11 answer. This is my first usage of Pyth, and I've had plenty of fun!
VQJ,*y.n0O0.tOZ4,sJ-FJ

23-byte version:
VQJ*y.n0O0K.tOZ4+JK-JKd

Cut a byte by changing the program to use folds+sums and setting J to a tuple, removing K.
Original:
VQJ**2.n0O0K.tO0 4+JK-JKd

Cut off 2 bytes thanks to @orlp.
Explanation:
VQ                         loop as many times as the input number
  J,                       set J to the following tuple expression
    *y.n0O0                2 * .n0 (pi) * O0 (a random number between 0 and 1)
            .tOZ4          .tOZ 4 (acos of OZ (a random number))
                 ,sJ-FJ    print the sum of J and folding J using subtraction in parenthesis, separated by a comma, followed by another newline

Pyth tips: *2_ is the same as y_. Variable Z is initially 0, so you can remove the space in .tO0 4 by writing .tOZ4.

I'm counting 25 bytes...

Also, you can format the output better with ,+JK-JK

@Maltysen Both fixed. Thanks!

@orlp I had no clue about y and forgot about Z. Fixed; thanks!

Julia, 48 bytes
n->(x=2π*rand(n);y=acos(rand(n));hcat(x+y,x-y))

This uses the method 2 algorithm, like most of the answers thus far. It creates a lambda function that takes an integer input and returns an n x 2 array. To call it, give it a name, e.g. f=n->....
Ungolfed + explanation:
function f(n::Int64)
    # The rand() function returns uniform random numbers using
    # the Mersenne-Twister algorithm

    # Get n random chord angles
    x = 2π*rand(n)

    # Get n random rotations
    y = acos(rand(n))

    # Bind into a 2D array
    hcat(x+y, x-y)
end

I really like how the visualizations look, so I'll include one. It's the result of f(1000).

Pyth, 22 bytes
A port of the C++ answer. I had another 23 byte solution (Now 22!), but it was almost a copy of @kirbyfan64sos's pyth answer with optimizations, so I had to think outside the box a little and creatively (ab)use the fold operator.
m,-Fdsdm,y*.nZOZ.tOZ4Q

Note that this doesn't work right now because of a bug in the fold operator after the introduction of reduce2. I'm putting in a pull request.
m             Map
 ,            Tuple of
  -Fd         Fold subtraction on input
  sd          Fold addition on input
 m      Q     Map over range input
  ,           Tuple
   y          Double
    *         Product
     .nZ      Pi
     OZ       [0, 1) RNG
  .t  4       Acos
    OZ        [0, 1) RNG

For refence this was my other solution which works in the same way: VQKy*.nZOZJ.tOZ4,+KJ-KJ

You mispelled my user name... :(

@kirbyfan64sos derp. Sorry ;)

C++11, 214 bytes
#include<random>
#include<iostream>
#include<cmath>
int main(){using namespace std;int n;cin>>n;random_device r;uniform_real_distribution<> d;for(;n;--n){float x=2*M_PI*d(r),y=acos(d(r));cout<<x+y<<' '<<x-y<<';';}}

So this is a straight out implementation of the right algorithm from the wikipedia page. The main problem here in golfing is the oh-so-freaking-long names that the random generator classes have. But, in contrast to good ol' rand, it is at least properly uniform.
Explanation:
#include<random>
#include<iostream>
#include<cmath>
int main()
{
    using namespace std;
    int n;
    cin>>n; // Input number
    random_device r; // Get a random number generator
    uniform_real_distribution<> d;   // Get a uniform distribution of
                                     // floats between 0 and 1
    for(;n;--n)
    {
        float x = 2*M_PI*d(r),       // x: Chosen radius angle
              y = acos(d(r));        // y: Take the distance from the center and
                                     // apply it an inverse cosine, to get the rotation

        cout<<x+y<<' '<<x-y<<';';    // Print the two numbers: they are the rotation
                                     // of the radius +/- the rotation extracted from
                                     // the distance to the center
    }
}

That factor M_PI_2 looks suspicious. I think it should be 1 instead.

Yes, completely right, going to fix it now! Thanks a lot!

IDL, 65 bytes
Obviously this is the same algorithm as @rcrmn, even though I derived it independently before reading their answer.
read,n
print,[2,2]#randomu(x,n)*!pi+[-1,1]#acos(randomu(x,n))
end

IDL's randomu function uses the Mersenne Twister, which has a period of 219937-1.
EDIT: I ran 1000 chords through the visualizer above, here's a screenshot of the result:

APL, 46 bytes
f←{U←⍵ 2⍴∊{(○2×?0)(¯1○?0)}¨⍳⍵⋄⍉2⍵⍴∊(+/U)(-/U)}

My first APL program ever! Surely it can be greatly improved (as my overall understanding of APL is lacking), so any suggestions would be fantastic. This creates a function f which takes an integer as input, computes the pairs of chord points using method 2, and prints each pair separated by a newline.
You can try it online!
Explanation:
f←{ ⍝ Create the function f which takes an argument ⍵

    ⍝ Define U to be an ⍵ x 2 array of pairs, where the first
    ⍝ item is 2 times a random uniform float (?0) times pi (○)
    ⍝ and the second is the arccosine (¯1○) of another random
    ⍝ uniform float.

    U ← ⍵ 2 ⍴ ∊{(○2×?0)(¯1○?0)}¨⍳⍵

    ⍝ Create a 2 x ⍵ array filled with U[;1]+U[;2] (+/U) and
    ⍝ U[;1]-U[;2] (-/U). Transpose it into an ⍵ x 2 array of
    ⍝ chord point pairs and return it.

    ⍉ 2 ⍵ ⍴ ∊(+/U)(-/U)
}

Note: My previous 19-byte solution was invalid since it returned (x, y) rather than (x+y, x-y). Sadness abounds.

Java, 114 bytes
n->{for(;n-->0;){double a=2*Math.PI*Math.random(),b=Math.acos(Math.random());System.out.println(a+b+" "+(a-b));}};

Basic implementation in java. Use as a lambda expression.
Example usage

Can't you reduce the size by storing Math somewhere? Or something? (Im not a Java programmer)

@IsmaelMiguel That would cost an extra 2 characters.

Sorry :/ It's tempting to try to reduce the number of times that Math shows. What does the meta say about using a code to generate another code to solve the issue?

@IsmaelMiguel That's fair game, although I'll be surprised if you're actually better at metagolfing than at golfing.

Ruby, 72 bytes
My first golf here! I used the same code as everyone, I hope that's okay
gets.chomp.to_i.times{puts"#{x=2*Math::PI*rand},#{x+2*Math.acos(rand)}"}

Java, 115 123
This is basically the same as most others, but I need a Java score for this hole, so here it goes:
void i(int n){for(double x;n-->0;System.out.println(x+2*Math.acos(Math.random())+" "+x))x=2*Math.PI*Math.random();}

1000 sample chords can be found at pastebin, here are the first five from one run:
8.147304676211474 3.772704020731153
8.201346559916786 3.4066194978900106
4.655131524088468 2.887965593766409
4.710707820868578 3.8493686706403984
3.3839198612642423 1.1604092552846672

CJam, 24 22 bytes
Similar to other algorithms, here is a version in CJam.
{2P*mr_1dmrmC_++]p}ri*

An input of 1000 produces a distribution like:

How it works
The algorithm is simply x = 2 * Pi * rand(); print [x, x + 2 * acos(rand())]
{                 }ri*        e# Run this loop int(input) times
 2P*mr                        e# x := 2 * Pi * rand()
      _                       e# copy x
       1dmr                   e# y := rand()
           mC                 e# z := acos(y)
             _++              e# o := x + z + z
                ]             e# Wrap x and o in an array
                 p            e# Print the array to STDOUT on a new line

Update: 2 bytes saved thanks to Martin!
Try it here

Python 3, 144 117 bytes
(thanks to Blckknght for the lambda pointer)
Using the same method as others:
import math as m;from random import random as r;f=lambda n:[(x,x+2*m.acos(r()))for x in(2*m.pi*r()for _ in range(n))]

From the Python documentation:

Python uses the Mersenne Twister as the core generator. It produces 53-bit precision floats and has a period of 219937-1.

Output
>>> f(10)
[(4.8142617617843415, 0.3926824824852387), (3.713855302706769, 1.4014527571152318), (3.0705105305032188, 0.7693910749957577), (1.3583477245841715, 0.9120275474824304), (3.8977143863671646, 1.3309852045392736), (0.9047010644291349, 0.6884780437147916), (3.333698164797664, 1.116653229885653), (3.0027328050516493, 0.6695430795843016), (5.258167740541786, 1.1524381034989306), (4.86435124286598, 1.5676690324824722)]

And so on.
Visualization

You can save about 20 bytes if you use a lambda for the function and return a list comprehension (with an inner generator expression): f=lambda n:[(x,x+2*m.acos(r()))for x in(2*m.pi*r()for _ in range(n))]

Ah, I had a lambda originally. I guess I didn't think about doubling up on list comprehensions. Thanks! @Blckknght

Can be shortened to 109 bytes by fiddling with the imports: https://tio.run/#python2

R, 60 56 53 49 bytes
An extra 4 bytes thanks to @JayCe and changing it to a function.
Using the same basic formula as the others.  R uses the Mersenne-Twister method by default, but others can be set.  Outputs a space separated list.
function(n,y=acos(runif(n)))runif(n)*2*pi+c(y,-y)

Try it online!

Hi Micky, you can Save 4 bytes by making it a function and not defining x.

@JayCe that's a lot better thanks

Perl, 60
#!perl -l
use Math::Trig;print$x=2*pi*rand,$",$x+2*acos rand for 1..<>

SmileBASIC, 62 bytes
INPUT N
FOR I=1TO N
X=PI()*2*RNDF()Y=ACOS(RNDF())?X+Y,X-Y
NEXT

source: Stack Exchange

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

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

sort: votes


text:
Real-time string matching
Task
The task is to golf a real-time exact string matching algorithm of your choice.
Input
Two lines of text supplied on standard input, separated by a new line. The first line contains the "pattern" and will simply be an ASCII string drawn from the letters a-z.
The second line contains the longer "text" and will also simply be an ASCII string drawn from the letters a-z.
Output
A list of indices of where the exact matches occur.  You should output the position of the start of each match that occurs.
Specification
Your algorithm can spend linear time preprocessing the pattern. It must then read the text from left to right and take constant time for every single character in the text and output any new match as soon as it occurs.  Matches can of course overlap each other.
Algorithm
There are many real-time exact matching algorithms. One is mentioned on the wiki for KMP for example. You can use any one you like but you must always output the right answer.
I will keep a per language leader table so that those who prefer popular languages can also win in their own way.  Please explain which algorithm you have implemented.
Real-time
It seems there has been a lot of confusion over what real-time means. It doesn't simply mean linear time. So standard KMP is not real-time. The link in the question explicitly points to a part of the wiki page for KMP about a real-time variant of KMP. Neither is Boyer-Moore-Galil real-time.  This cstheory question/answer discusses the issue or one can just google "real-time exact matching" or similar terms.

am I correct in assuming that vectorized answers don't count? i.e., we MUST traverse the text linearly?

So if I had the strings abcd and acbdefg, I would output 1 4, for a and d?

I don't think that's right, both a and d match. There is abcd and acbdefg, and the a and d are at identical positions.

@ASCIIThenANSI You wouldn't output anything. There is no match of abcd in acbdefg .

@ASCIIThenANSI I originally missed that you had swapped b and c around.

So if it was abcd and abcdefg, it would output 4? Or does it output 1?

@ASCIIThenANSI You should output 1 in that case.

And for bcde in abcdefg, I output 2?

@ASCIIThenANSI Yes. "You should output the position of the start of each match that occurs."

OK. If it's EACH match, does this mean bc in abcabc outputs 2 5?

@ASCIIThenANSI YES! :)

OK then. Just trying to make sure I get it right. Thanks! c:

Why are we having 1 based indexes here ? -.-

Python 2, 495 bytes
This one is a real-time KMP, which is a lot shorter and only slightly slower than the BMG algorithm (which is usually sublinear). Call with K(pattern, text); output is identical to the BMG algorithm.
L,R,o=len,range,lambda x:ord(x)-97
def K(P,T):
 M,N=L(P),L(T);Z=[0]*M;Z[0]=M;r=l=0
 for k in R(1,l):
    if k>r:
     n=0
     while n+k<l<P[n]==P[n+k]:n+=1
     Z[k]=n
     if n>0:l,r=k,k+n-1
    else:
     p,_=k-l,r-k+1
     if Z[p]<_:Z[k]=Z[p]
     else:
        i=r+1
        while i<M<P[i]==P[i-k]:i+=1
        Z[k],l,r=i-k,k,i-1
 F=[[0]*26]*M
 for j in R(M-1,0,-1):z=Z[j];i,x=j+z-1,P[z+1];F[i][o(x)]=z
 s=m=0
 while s+m<N:
    c=T[s+m]
    if c==P[m]:
     m+=1
     if m==M:print s,;s+=1;m-=1
    else:
     if m==0:s+=1
     else:f=F[m][o(c)];s+=m-f;m=f

Which reference did you use for real-time KMP out of interest?

The search algorithm was an amalgam of several, but the real-time part came primarily from this with a dash of Wikipedia.

Python 2, 937 bytes
This ain't short, by any means, but it (a) works, (b) satisfies all the requirements, and (c) is golfed as much as I can possibly make it.
L,r,t,o,e,w=len,range,26,lambda x:ord(x)-97,enumerate,max
def m(s,M,i,j,c=0):
 while i<M-c>j<s[i+c]==s[j+c]:c+=1
 return[c,M-i][i==j]
def Z(s):
 M=L(s)
 if M<2:return[[],[1]][M]
 z=[0]*M;z[0:2]=M,m(s,M,0,1)
 for i in r(2,1+z[1]):z[i]=z[1]-i+1
 l=h=0
 for i in r(2+z[1],M):
    if i<=h:k=i-l;b,a=z[k],h-i+1;exec["z[i]=b+m(s,M,a,h+1);l,h=i,i+z[i]-1","z[i]=b","z[i]=min(b,M-i);l,h=i,i+z[i]-1"][cmp(a,b)]
    else:
     z[i]=m(s,M,0,i)
     if z[i]>0:l,h=i,i+z[i]-1
 return z
def S(P,T):
 M,N=L(P),L(T)
 if not 0<M<N:return
 R,a=[[-1]]*t,[-1]*t
 for i,c in e(P):
    a[o(c)]=i
    for j in r(t):R[j]+=a[j],
 if M<=0:R=[[]]*t
 n,F,z,l=Z(P[::-1])[::-1],[0]*M,Z(P),0;G=[[-1,M-n[j]][n[j]>0]for j in r(M-1)]
 for i,v in e(z[::-1]):l=[l,w(v,l)][v==i+1];F[~i]=l
 k,p=M-1,-1
 while k<N:
    i,h=M-1,k
    while 0<=i<[]>h>p<P[i]==T[h]:i-=1;h-=1
    if i<0 or h==p:print-~k-M,;k+=[1,M-F[1]][M>1]
    else:c,q=i-R[o(T[h])][i],i+1;s=w(c,q==M or M-[G,F][G[q]<0][q]);p=[p,k][s>=q];k+=s

This is an implementation of the Boyer-Moore-Galil algorithm. Pretty straightforward - call with S(pattern,text); the other two functions are used in preprocessing. Indeed, everything but the last 5 lines is preprocessing.
An example run, which took about a second:
>>> a = 'a'*1000
>>> b = 'a'*1999 + 'b'
>>> S(a,b)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999

I am not sure this is real-time is it?

Boyer-Moore-Galil runs in a worst case of O(n+m). It's actually faster than KMP.

But real-time is the not the same as linear time.

Under "specifications" it says that the algorithm must run in O(m) preprocessing and O(n) matching [=> O(n+m)], which this does (or better).

Yes but that isn't what real-time means. The whole thing could run in O(n+m) time but take n time for one of the symbols in the text, example.

Well, this algorithm is O(patlen) processing time, followed by O(textlen) matching time, which should be fine.

I am sorry to say that isn't what real-time means.  I have added a link to the question which might help.

BMG uses constant-time lookup tables for each shift. It is more efficient (i.e., fewer comparisons) than KMP. I'm not sure how it doesn't qualify as real-time...

What is the largest number of operations it can take for one single symbol in the text?

It performs at most one comparison per character in the text. The largest number of operations for a given alignment of the pattern is when a substring matches except for the first character and none of the aligned characters have yet been test, which would cause patlen comparisons and then engage the no-match shift. How many operations depends on how you define an operation, but the shift is calculated via constant-time list indexing, independent of textlen.

In the worst case of the same repeated character for both pattern and text, after the initial patlen comparisons with no shift calculation, it's one (constant time) shift calculation per alignment, and each shift is one character with the new character as the only comparison. So it's constant time per text character.

KMP, Python 2(213 bytes)
R=raw_input
E=enumerate
p=R()
t=R()
f=[-1]*((len(p)+1))
j=-1
for i,c in E(p):
 while j+1 and p[j]!=c:j=f[j]
 f[i+1]=j=j+1
j=-1
for i,c in E(t):
 while j+1 and p[j]!=c:j=f[j]
 j+=1
 if j==len(p):print i+1-j;j=f[j]

Ungolfed version. The first loop is to build up the KMP automata. The second loop is walking on the automata. They share nearly the same pattern but abstracting them out will cost more bytes so for a code golf I'd rather duplicate this logic. Similar implementation is actually widely used in programing contests.
pattern = raw_input()
text = raw_input()

fail = [-1] * (len(pattern) + 1)
j = -1
for i, c in enumerate(pattern):
    while j >= 0 and pattern[j] != c:
        j = fail[j]
    j += 1
    fail[i + 1] = j

j = -1
for i, c in enumerate(text):
    while j >= 0 and pattern[j] != c:
        j = fail[j]
    j += 1
    if j == len(pattern):
        print i + 1 - j
        j = fail[j]

This isn't real-time sadly. See the wiki link in the question.

Realtime KMP, Python 2(167 bytes)
R=raw_input
E=enumerate
P=R()
T=R()
F=[{}]
for i,c in E(P):j=F[i].get(c,0);F+=[dict(F[j])];F[i][c]=i+1
j=0
for i,c in E(T):
 j=F[j].get(c,0)
 if j==len(P):print i+1-j

In normal KMP, we simulate the automaton behavior by using a fail function. In this realtime KMP, the full automaton is constructed so that in the matching phrase it can process each character in realtime(constant time).
The preprocessing time and space complexity is O(n m), where m is the alphabet size and n is the length of pattern string. However, in my tests, the actual size of transition table is always less than 2n so maybe we can prove that the time and space complexity is O(n).
Ungolfed version
pattern = raw_input()
text = raw_input()

# transitions[i][c] points to the next state walking from state i by c.
# Transition that point to staet 0 are not stored.
# So use transitions[i].get(c, 0) instead of transitions[i][c]
transitions = [{}]
for i, c in enumerate(pattern):
    j = transitions[i].get(c, 0)
    transitions.append(transitions[j].copy())
    # Before this assignment, transitions[i] served as the fail function
    transitions[i][c] = i + 1

j = 0
for i, c in enumerate(text):
    j = transitions[j].get(c, 0)
    if j == len(pattern):
        print i + 1 - j

Well, sadly, hash table in Python isn't realtime so the implementation here isn't realtime either.

Q, 146 Bytes
W:S:u:"";n:0;p:{$[n<#x;0;x~(#x)#W;#x;0]};f:{{|/p'x}'((1_)\x#W),\:/:u};F:{S::x 1;W::*x;n::#W;u::?W;T:(f'!1+n),\:0;(&n=T\[0;u?S])-n-1}

Test
F"
 ABCDABD
 ABCdABCDABgABCDABCDABDEABCDABzABCDABCDABDE"
generates 15 and 34
Notes
Not restricted to alphabet (support any ascii char, and is case-sensitive).
Not uses any of the specific operations defined by Q over strings -> works on strings as sequences (ops match, length, etc.)
Minimizes transition table joining all characters not in pattern as one unique character-class.
I can squeeze code a little. It's a first attempt to validate solution strategy
Visit any character of text exactly once, and for each input character there is a unique jump. So I assume that search fits as 'real time'
Table construction al state i and char c search for longest substring that ends at i and after appending c is a prefix of S. Construction is not optimized, so i don't know if its valid
Input format doesn't fit well with language. Passing two string arguments will save 16 Bytes
Explanation
global W represents pattern and S corresponds to text to search
x:1_"\n "\:x  weird code to cope with input requirements (Q requires thtat multiline strings has non-first lines indented, so it must discard added space in front of every non-first line)
n::#W calculates W lenght and save as global n
u::?W calculates unique chars in W, and save as global u
u?S  generates the characted-class for each char of S
Construct a transition table T with one row per unique character in W (plus one extra), and a column for each index in W (plus one extra). Extra row correspond to initial state, and extra column collects any char in S but not in W. This strategy minimizes table size
p:{$[n<#x;0;x~(#x)#W;#x;0]} is the function that search longest prefix
f:{{|/p'x}'((1_)\x#W),\:/:u} is the function that calculates a row x of T
T:(f'!1+n),\:0 applies f repeteadly to calculate each row, and adds value 0 to each row

Search text using transition table. T\[0;u?S] iterates over 0 (initial state) and each of the character class of S, using as a new value the value at transitition table T[state][charClass]. Final states has value n, so we look for that value in the sequence of states and returns it adjusted (to indicate initial instead of final position of each match)

Boyer-Moore, Perl (50)
Perl attempts to use Boyer-Moore naturally:
$s=<>;$g=<>;chomp$g;print"$-[0] "while$s=~m/($g)/g

This is not real time sadly.

What do you mean by "real time"?

Constant time for every symbol of the text that is read in. See the wiki link I pasted.


text:
Theseus' New Ship
The Ship of Theseus is an old question that goes something like:

If a ship has had all of its original parts replaced, is it still the same ship?

For this golf, we're going to slowly replace "parts" on a "ship", and see how long it takes to get a whole new ship.
Task
A ship is comprised of at least two parts. The parts are given as an array of positive (non-zero) integers, representing the part's condition.
On each cycle, randomly choose one part from the list in a uniform fashion. That part's condition will be reduced by one. When a part's condition reaches zero, it is replaced by a new part. The new part starts with the same condition value as the original did.
On the first cycle where all parts have been replaced (at least) once, stop and output the number of cycles it took.
For example (assume I'm choosing parts randomly here):
2 2 3  <- starting part conditions (input)
2 1 3  <- second part reduced
2 1 2  ...
2 1 1
2 2 1  <- second part reduced to zero, replaced
1 2 1
1 2 3  <- third part replaced
1 1 3
2 1 3  <- first part replaced

Output for this example would be 8, since it took eight cycles for all parts to be replaced. Exact output should differ for each run.
I/O
The only input is the list/array of integers for part condition. The only output is a number of cycles. You can take/give these values in any of the usual ways: STDIO, function arguments/returns, etc.
Test Cases
Since output is not fixed, you could use whatever you want to test, but here's a couple for standardization purposes:
1 2 3 4

617 734 248 546 780 809 917 168 130 418

19384 74801 37917 81706 67361 50163 22708 78574 39406 4051 78099 7260 2241 45333 92463 45166 68932 54318 17365 36432 71329 4258 22026 23615 44939 74894 19257 49875 39764 62550 23750 4731 54121 8386 45639 54604 77456 58661 34476 49875 35689 5311 19954 80976 9299 59229 95748 42368 13721 49790

Am I missing something, or does it not matter that when a part reaches 0, it is replaced by a new part?

@xnor Well it doesn't matter to get the answer, no (and it seems to be the thing to do to skip it). But thematically, the ship's parts need replacing :P

Pyth, 12 bytes
f!eSXOUQQtZ1

Demonstration.
How it works:
This is based around Pyth's infinite filter, which tests an expression with increasing inputs until it returns something truthy, then returns the input which caused this to happen. However, the expression that will be tested will not use the input value.
Instead, the expression will modify the input list by decrementing a random entry. This is accomplished via the expression XOUQQtZ. This means increase the index OUQ in the list Q by tZ. OUQ is a random index in the length of Q, and tZ is -1. Q is initialized to the input list.
After modifying Q in this fashion, we take its current value, which X returns, take its maximum entry with  eS, and take the logical not of that value with !. This returns a truthy value for the first time when every element of Q has been reduced to 0 or below for the first time.
To ensure that the number returned will be exactly the number of times that Q was modified, we will start the count at 1, indicating the the first time this is called, there has been 1 modification. To see what Q looks like after each iteration of the code, check out the version here.

GolfScript (26 24 bytes) / CJam (20 18 bytes)
GolfScript:
~{$)*}{.,rand{(+}*((+}/,

Online demo
CJam (same idea but slightly different implementation):
q~{_mr((+_$)*}g;],

Online demo
Input is on stdin in the form [2 2 3].
This is one of those rare occasions where GolfScript's unfold operator is useful. It allows us to accumulate the states which the ship passes through, and then count them at the end. Note that the array which is counted includes the initial (input) state but not the final state in which the last element has been reduced to 0.
However, although CJam doesn't have unfold its ability to shuffle an array uniformly for only 2 chars counts for a lot and allows it to come out on top.

Python 3, 91 71 bytes
20(!) bytes saved thanks to @xnor.
from random import*
def f(p):shuffle(p);p[0]-=1;return max(p)<1or-~f(p)

Recursive function calling itself with smaller piece-values until all piece-values are 0 or negative and every function returns the return value of its child + 1 and the lastly called one returns 1.

You can check for the presence of a positive number with max(p)>0.

And negating the condition as max(p)<1or-~f(p) lets you avoid the or 1, since True==1.

You can effectively decrement a random element of p with shuffle(p);p[0]-=1.

@xnor Wow, thanks! These are all great!

Python 3, 175 bytes
import random
p,t=input().split(),0;f,r=[int(i)for i in p],[0]*len(p)
while 0 in r:
 f[random.randint(0,len(f)-1)]-=1;t+=1
 for x in range(len(f)):
  r[x]=int(f[x]<1)
print(t)

Not especially well golfed.
Try it online here

Self destruct comment


text:
Tallest tower from a set of digits

Edit: Bounty puzzle at the end of the question.

Given a set of 1-digit numbers, you should determine how tall a tower they can construct.
The digits live on a horizontal plane with a ground level where they can stand. No digit wants to be confused with a multi-digit number, so they always have an empty space on both of their sides.
4 2  1 9  6  8

A digit can be on top of another one:
2
6

or can be supported by two other diagonally below it:
 9
5 8

The bottom one(s) have to support the weight the upper one supports (if there is any), plus the upper one's weight which is always 1. If there are two supporters, they split the upper one's total weight evenly (50%-50%).
The weight of every digit is 1 independent of it's value.
If one digit supports two others it has to be able to support the sum of their corresponding weight. A digit can support at most its numerical value.
Some valid towers (with heights 4, 3 and 5):
            0
7           1
5    1     1 1         9 supports a total weight of 1.5 = (1+1/2)/2 + (1+1/2)/2
2   5 4    5 5
3  5 9 5  5 6 3        6 supports a total weight of 3 =  1.5 + 1.5 = (2*1+(2*1/2))/2 + (2*1+(2*1/2))/2

Some invalid towers:
1         5           The problems with the towers are (from left to right):
1  12    2 3     8      1 can't support 1+1; no space between 1 and 2;
1  5 6  1 1 1   9       1 can't support 1.5 = (1+1/2)/2 + (1+1/2)/2; 8 isn't properly supported (digits at both bottom diagonals or exactly below the 8)

You should write a program or function which given a list of digits as input outputs or returns the height of the highest tower constructable by using some (maybe all) of those digit.
Input

A list of non-negative single-digit numbers with at least one element.

Output

A single positive integer, the height of the highest constructable tower.
Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).

Examples
Format is Input list => Output number with a possible tower on the next lines which is not part of the output.
[0]  =>  1

0

[0, 1, 1, 1, 1, 1]  =>  3

  0
  1
 1 1

[1, 1, 1, 1, 1, 2, 2]  =>  4

   1
   1
  1 1
 1 2 2

[0, 0, 2, 2, 2, 2, 2, 5, 5, 5, 7, 7, 9]  =>  9

0
2
2
5
5
5
7
7
9

[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5]  =>  9

   1
   2
   2
   3
   4
   5
  3 3
 4 4 4
5 5 5 5

[0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 9]  =>  11

   0
   1
   2
   3
   4
   5
  3 3
  4 5
  5 5
 3 7 3
2 7 9 2

[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]  =>  12

 0
 1
 2
 3
 4
 5
 6
 7
4 5
6 7
8 8
9 9

[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9]  =>  18

      0
      1
      2
      3
      4
      5
      6
      7
      8
      9
     5 5
     6 6
     7 7
    4 8 4
   3 7 7 3
  2 6 8 6 2
 2 5 8 8 5 2
 3 9 9 9 9 3

This is code-golf, so the shortest entry wins.
Bounty
I will award 100 reputation bounty (unrelated to the already awarded one) for solving the extended problem below in polynomial time (in regard to the length of the input list) or proving that it isn't possible (assuming P!=NP). Details of the extended problem:

input numbers can be any non-negative integers not just digits
multi-digit numbers take up take same place as single-digit numbers
multi-digit numbers can support they numerical value e.g. 24 can support 24

The bounty offer has no expiry date. I will add and reward the bounty if a proof appears.

Do you have enough money for a new PC? Then I have a solution :P

Your 3-2-5-7 tower confuses me. You say that "The bottom one(s) have to support the weight the upper one supports (if there is any), plus the upper one's weight which is always 1.", which conflicts with you saying that a digit can support at most 'its numerical value'-- if each digit's weight is one, then what's the point of having different number?

@M.I.Wright the number indicates how much weight you can stack on top of the number. But weight of the number itself is always 1.

@MartinBüttner OH, duh. Thank you.

The title mentions sets of digits, but considering the examples, it looks like you meant lists. Sets can’t have duplicates.

Python 2 - 326
Runs easily under the time limit for all the examples given, though I did sacrifice some efficiency for size, which would probably be noticeable given much larger inputs. Now that I think about it though, since only single digits numbers are allowed the largest possible tower may not be very big, and I wonder what the maximum is.
def S(u,c=0,w=[]):
 for(s,e)in[(len(w),lambda w,i:w[i]),(len(w)+1,lambda w,i:.5*sum(([0]+w+[0])[i:i+2]))]:
    m=u[:];l=[-1]*s
    for n in u:
     for i in range(s):
        if 0>l[i]and n>=e(w,i):m.remove(n);l[i]=n;break
    if([]==l or-1in l)==0:
     for r in S(m,c+1,[1+e(w,i)for i in range(s)]):yield r
 yield c
print max(S(sorted(input())))

Looks like the maximum height is 18.


text:
Death By Shock Probe: That's a lot of dice
In the webcomic Darths & Droids, Pete, who plays R2-D2 in the fictional roleplaying campaign around which the comic is based, once claims (warning: potential spoilers in the linked comic) that, with the Lost Orb of Phanastacoria rigged up to his shock probe, he can now dish out a whopping 1048576d4 of damage. (The GM has neither confirmed nor denied this.) Since it should be reasonably obvious that almost no one will actually have the patience to roll that many dice, write a computer program to do it for him, outputting the total value rolled in some reasonable format. Entries will be ranked by program size (shortest program, by byte count, wins), both overall and per-language, with run time breaking ties. Answer may be either a full program or a function definition.
Scores Per-Language
Pyth
Maltysen - 8 bytes*
Jakube - 10 bytes
APL
Alex A - 10 bytes
CJam
Optimizer - 11 bytes
J
ɐɔıʇǝɥʇuʎs - 12 bytes **
Clip10
Ypnypn - 12 bytes **
K
JohnE - 13 bytes
Ti-84 BASIC
SuperJedi224 - 17 bytes*
R
MickyT - 23 bytes
OCTAVE/MATLAB
Oebele - 24 bytes
PARI/GP
Charles - 25 bytes **
Wolfram/Mathematica
LegionMammal978 - 27 bytes
Perl
Nutki - 29 bytes
AsciiThenAnsii - 34 bytes
Ruby
Haegin - 32 bytes **
ConfusedMr_C - 51 bytes **
Commodore Basic
Mark - 37 bytes **
PHP
Ismael Miguel - 38 bytes
VBA
Sean Cheshire - 40 bytes **
PowerShell
Nacht - 41 bytes **
Javascript
Ralph Marshall - 41 bytes
edc65 - 54 bytes (Requires ES6 functionality not available in all browsers.)
Lua
cryptych - 51 bytes
Java
RobAu - 52 bytes **
Geobits - 65 bytes
C
Functino - 57 bytes
Python
CarpetPython - 58 bytes
Postgre/SQL
Andrew - 59 bytes **
Swift
Skrundz - 69 bytes
GoatInTheMachine - 81 bytes
Haskell
Zeta - 73 bytes **
ActionScript
Brian - 75 bytes **
><>
ConfusedMr_C - 76 bytes
GO
Kristoffer Sall-Storgaard - 78 bytes
C#
Brandon - 91 bytes **
Andrew - 105 bytes
Ewan - 148 bytes
Scratch
SuperJedi224 - 102 bytes
C++
Michelfrancis Bustillos - 154 bytes
Polyglots
Ismael Miguel (Javascript/ActionScript2) - 67 bytes

Top 10 Overall

Maltysen
Alex A
Jakube
Optimizer
ɐɔıʇǝɥʇuʎs/Ypnypn (order uncertain)
JohnE
SuperJedi224
MickyT
Oebele

Warning- entries marked with a * are VERY SLOW.
Programmed marked ** I have not yet been able to properly test

Wait, do I have to give the sum  of the dice roll or just all the rolls in a list?

The sum of the dice roll.

Your question, as it stands, will likely be criticized for being unclear or being overly broad. It would be very helpful if you described in specific, objective terms how programs will be scored and what methods programs should have available to them. Also, the notation of 1048576d4 may be unclear to some users. It would be helpful to provide a description of precisely what should be computed, and any guidelines that must be followed.

This problem can be done too quickly to be a good time trial.

I think you need to update your post: there have been several faster answers than the Perl answer by @AsciiThenAnsii.

I'm working on updating it now.

@isaacg yeah, I think you're right

You could try your hand at making a stack snippet leaderboard to avoid having to manually keep the list of submissions up to date.

I absolutely love this title.

How are you calculating your overall leaderboard ?

It's code size, with run time to break ties. I believe it says that in the current version of the question.

Actually, the polyglot is in ActionScript2. The version is very important, since the var statement is required in version 3, but on version 2 it may be left behind in some situations.

Since this question was asked, the party has lost the Lost Orb. Again.

Pyth - 9 8 bytes
Uses obvious simple method of summation of randint. Took me minute to realize 1048576 was 2^20, now I feel really stupid. Thanks to @Jakube for saving me a byte by pointing out 2^20 = 4^10.
smhO4^4T

The runtime is horrible, it has yet to finish on my computer, so there is no point running it online so here is the 2^10 one: Try it online here.
s        Summation
 m       Map
  h      Incr (accounts for 0-indexed randint)
   O4    Randint 4
  ^4T    Four raised to ten

8 bytes are possible. 2^20 = 4^10

@Jakube thanks for the tip :)

This finishes immediately for me.

@Carcigenicate are you talking about the link I gave? That's the modified one, only sums 1024d4.

@Maltysen Whoops, sorry. Ya, that's it.

Perl - 48 44 37 39 34 bytes
$-+=rand(4)+1for(1..2**20);print$-

Prints the sum without a trailing newline.
Saved 4 bytes by substituting for 2**20 (thanks Maltysen) and removing quotes around print.
Saved another 7 bytes by rearranging the code (thanks Thaylon!)
Lost 2 bytes because my old code generated 0-4 (it should be 1-4).
Once again, saved 5 bytes thanks to Caek and nutki.
Ungolfed, properly written code:
my $s = 0
$s += int( rand(4) + 1 ) for (1 .. 2**20);
print "$s";

It was a little hard to get a timer hooked up, but I eventually got it working.

Since we dont care about warnings ... $s+=int rand(5)for(1..2**20);print$s

int(rand(5)) returns range 0 to 4 while d4 should be 1 to 4.

@nutki OK, thanks. I've edited that in now.

$s+=int rand(4)+1for(1..2**20);print$s Removing the parenthesis for int also works for me, to save a stroke.

$=+=rand(4)+1for(1..2**20);print$= also worked for me to save more strokes. Assigning to the special var $= has the side affect of forcing int.

@Caek $= is initialized to 60 so it would be incorrect. $- has a similar behavior and starts at 0.

@nutki: I forgot it was += and not =.Thanks for that, I'll probably use $- from now on.

try for 1..2**20; instead of for(1..2**20); for another byte?

R, 32 24 23 21 bytes
Edit: Got rid of the as.integer and used integer division %/%.  Speed it up slightly.
Thanks to Alex A for the sample tip ... and Giuseppe for removing the r=
sum(sample(4,2^20,T))

Tested with
i = s = 0
repeat {
i = i + 1
print(sum(sample(4,2^20,r=T)))
s = s + system.time(sum(sample(4,2^20,r=T)))[3]
if (i == 10) break
}
print (s/10)

Outputs
[1] 2621936
[1] 2620047
[1] 2621004
[1] 2621783
[1] 2621149
[1] 2619777
[1] 2620428
[1] 2621840
[1] 2621458
[1] 2620680
elapsed
   0.029

For pure speed the following completes in microseconds.  However I'm not sure I've got my logic correct for it.  The results appear consistent with the random method.  Shame it's a longer length.
sum(rmultinom(1,2^20,rep(1,4))*1:4)

Here's a timing run I did on my machine
system.time(for(i in 1:1000000)sum(rmultinom(1,2^20,rep(1,4))*1:4))
                   user                  system                 elapsed
7.330000000000040927262 0.000000000000000000000 7.370000000000345607987

You can save a couple bytes by using sample() in place of runif(), i.e. sum(sample(4,2^20,r=T)).

Just did some benchmarking on my computer and sample() is actually faster too!

@AlexA.  Thanks will test and change when I get close to a computer

not to necro this or anything but you don't need r=T, just T is fine for replacement.

@Giuseppe, thanks .. this really was an old one

APL, 11 10 bytes
+/?4⍴⍨2*20

This just takes the sum of an array of 220 = 1048576 random integers between 1 and 4.
+/           ⍝ Reduce by summing a
  ?          ⍝ random integer
   4⍴⍨       ⍝ array with values between 1 and 4
      2*20   ⍝ of length 2^20

You can benchmark this on TryAPL by printing the timestamp before and after. It takes about 0.02 seconds.
Saved a byte thanks to marinus and FUZxxl!

One and 5???  A d4 can give 1, 2, 3 or 4.  You can't get 5.

@LorenPechtel: Sorry, my bad. Thanks for pointing that out. It's fixed now. I have tired brain.

Save a byte: +/?4⍴⍨2*20

Small improvement: use +/?4⍴⍨2*20 instead.

@marinus and FUZxxl: Thanks to both of you! Edited to use your suggestion.

Incidtenally, this answer is not golfed in any way: It would be written exactly the same way in production APL code.

Ti-84 Basic, 17 bytes
Total footprint - Size of program header = 17 bytes
Run Time: Unknown, estimated at 5-6 hours based on performance for smaller numbers of rolls (so, basically, not very good)
Σ(randInt(1,4),A,1,2^20

+1 for making it run on a TI-84. I guess time isn't a problem here, those are 30-40 year-old calculators by now.

I presume there's a function for sampling a normal distribution rather than a uniform one?  Should be much quicker.

@BenVoigt: Since this is meant to simulate the rolling of dice, a normal distribution is not appropriate; it would have to be uniform.

If this runs for 5-6 hours straight, I think your calculator battery would die before this finishes.

@AlexA.: Central Limit Theorem provides that the sum of many uniform dice is indistinguishable from a normal distribution.  So it depends on how pedantic we are about "simulating rolling".

@AlexA. the TI-84 series has a USB port for charging.

@M.I.Wright, I thought it was just for communication. At least the one I've got uses AAA batteries.

@ArturoTorresSánchez My apologies, you're actually partially right; it's only the C Silver Edition that uses the port for charging. The monochrome calcs don't really use it for anything.

To save a byte, the close-paren is unnecessary.

JavaScript (ES6), 54 bytes
Average time < 100 msec. Run snippet to test (in Firefox)

// This is the answer
f=t=>(i=>{for(t=i;i--;)t+=Math.random()*4|0})(1<<20)|t

// This is the test
test();

function test(){
  var time = ~new Date;
  var tot = f();
  time -= ~new Date;

  Out.innerHTML = "Tot: " + tot + " in msec: " + time + "\n" + Out.innerHTML;
}
<button onclick="test()">Repeat test</button>

Explanation
With no statistical package built-in, in Javascript the shortest way to obtain the sum of 1 million random number is to call random() for a million times. So simply
f=()=>{
   var t = 0, r, i
   for (i=1<<20; i--; )
   {
      r = Math.random()*4 // random number between 0 and 3.9999999
      r = r + 1 // range 1 ... 4.999999
      r = r | 0 // truncate to int, so range 1 ... 4
      t = t+r
   }
   return t
}

Now, adding 1 for a million times is exactly the same than adding 1 million, or even better, start the sum with 1 million and then add the rest:
f=()=>{
   var t, r, i
   for (t = i = 1<<20; i--; )
   {
      r = Math.random()*4 // random number between 0 and 3.9999999
      r = r | 0 // truncate to int, so range 0 ... 3
      t = t+r
   }
   return t
}

Then golf, drop the temp variable r and drop the declaration of local variables. t is a parameter, as one is needed to shorten the declaration of f. i is global (bad thing)
f=t=>{
   for(t=i=1<<20;i--;)
      t+=Math.random()*4|0
   return t
}

Then find a way to avoid 'return' using a nameless inner function. As a side effect, we gain another parameter so no globals used
f=t=>(
  (i=>{ // start inner function body
     for(t=i;i--;)t=t+Math.random()*4|0 // assign t without returning it
   })(1<<20) // value assigned to parameter i
  | t // the inner function returns 'undefined', binary ored with t gives t again
) // and these open/close bracket can be removed too

Doesn't work in chrome. About to test in FF.

Of course. Chrome is ES5

It has some ES6 support (most of which is only available by enabling experimental javascript from chrome:\flags), but does not yet support arrow functions

Python 2, 58 bytes
We get 1048576 random characters from the operating system, take 2 bits of each, and add them up. Using the os library seems to save a few characters over using the random library.
import os
print sum(1+ord(c)%4 for c in os.urandom(1<<20))

This takes about 0.2 seconds on my PC.

CJam, 12 11 bytes
YK#_{4mr+}*

This is pretty straight foward:
YK                  e# Y is 2, K is 20
  #                 e# 2 to the power 20
   _                e# Copy this 2 to the power 20. The first one acts as a base value
    {    }*         e# Run this code block 2 to the power 20 times
     4mr            e# Get a random int from 0 to 3. 0 to 3 works because we already have
                    e# 2 to the power 20 as base value for summation.
        +           e# Add it to the current sum (initially 2 to the power 20)

But the beauty of this is that its really fast too! On my machine (and using the Java compiler) it takes on an average of 70 milliseconds.
The online version takes around 1.7 seconds on my machine.
Update: 1 byte saved thanks to DocMax

The online version is taking about 6 seconds from the computers here, but that's probably just the network and/or the macbooks the school insists on using. I'll try again when I get home.

@SuperJedi224 The online version is all in JavaScript, does not make any network calls. You can download the Java version and run it using the instructions on the website.

Unless I am missing something (which is sadly too common with CJam and me), instead of seeding with 0 and adding 1 for 2^20 runs, seed with 2^20 to save 1 byte: YK#_{4mr+}*

@DocMax You are right. Thanks!

+1; I was going to post this exact answer (except with 4A# instead of YK#), but you beat me to it. :)

Perl, 29
Generates a table of the required length.
print~~map{0..rand 4}1..2**20

I'm getting a syntax error on this one.

This needs a new enough version of Perl (the smartmatch operator was introduced in 5.10.1, and I think it wasn't made available by default until later).

~~ is not a smartmatch, just a double bit inversion to force scalar context. A one character longer way would be print$x=map.... Maybe on newer versions it warns because of ambiguity with smartmatch, but it does seem to work without warnings on my system and in here: http://ideone.com/LAIWzq

Yep, it works on IDEone. I'll give it to you.

J (12 bytes, about 9.8 milliseconds)
+/>:?4$~2^20

I suspect this is mostly memory bandwith-limited: I can't even get it to max out a single core...
You can test this with the following code:
   timeit =: 13 : '(1000 * >./ ($/x) 6!:2"0 1 y)'
   4 20 timeit '+/>:?4$~2^20'
9.90059

This runs it in 4 groups of 20 trails, and returns the number of milliseconds of the avarage time in the quickest group. An interpreter can be found here.

PHP, 38 37 bytes
This uses a very simple idea: sum them all!
Also, I've noticed that 1048576 is 10000000000000000000 in binary, equivalent to 1<<20.
Here's the code:
while($i++<1<<20)$v+=rand(1,4);echo$v

Test in your browser (with VERY LITTLE changes):
$i=$v=0;while($i++<1<<20)$v+=rand(1,4);printf($v);

//'patch' to make a TRUE polyglot, to work in JS

if('\0'=="\0")//this will be false in PHP, true in JS
{
  //rand function, takes 2 parameters
  function rand($m,$n){
    return ((Math.random()*($n-$m+1))+$m)>>0;

    /*
     *returns an integer number between $m and $n
     *example run, with rand(4,9):
     *(Math.random()*(9-4+1))+4
     *
     *if you run Math.random()*(9-4+1),
     *it will returns numbers between 0 and 5 (9-4+1=6, but Math.random() never returns 1)
     *but the minimum is 4, so, we add it in the end
     *this results in numbers between 0+4 and 4+5
     *
     */

  }

  //for this purpose, this is enough
  function printf($s){
    document.write($s);
  }
}

/*
 *Changes:
 *
 *- instead of echo, use printf
 *    printf outputs a formatted string in php
 *    if I used echo instead, PHP would complain
 *- set an initial value on $i and $v
 *    this avoids errors in Javascript
 *
 */

$i=$v=0;while($i++<1<<20)$v+=rand(1,4);printf($v);

All the changes in the code are explained in comments.

You can remove the ; after echo$v

@Martijn I left it there because most of the time PHP complains about it. But I have removed it now. It works on http://sandbox.onlinephpfunctions.com/ and that's enough.

Haskell, 73 bytes
import System.Random
f=fmap sum.(sequence.replicate(2^20))$randomRIO(1,4)

Usage:
$ ghci sourcefile.hs
ghci> f
2622130

C#: 105 bytes
using System.Linq;class C{int D(){var a=new System.Random();return new int[1<<20].Sum(i=>a.Next(1,5));}}

Nice, I like this even if it's two times wrong. It's 1<<20, not 2<<20. And the second parameter of Random.Next is The *exclusive* upper bound of the range so it should be 5

@edc65 Thanks for catching those errors. I have updated the answer.

You could save 9 chars by eliminating a and moving the new System.Random() inside of the Sum. Sure, it will create a new Random every time, but who cares as long as it gives a result?

@LegionMammal978 if you create a new Random again and again, the result is mostly non-random

@edc65 That is why I didn't go that route. I haven't had a chance to test what happens if I followed the suggestion.

Mathematica, 30 27 bytes
Tr[RandomInteger[3,2^20]+1]

Mathematica has quite long function names...

Pyth, 10 bytes
u+GhO4^4TZ

This has slightly more bytes than @Maltysen's Pyth solution. But it runs in 8.5 seconds on my laptop, while @Maltysen's solution produced no solution in 20 minutes running time.
But still a little bit too slow for the online compiler.
Explanation
u     ^4TZ   start with G = 0, for H in 0, ... 4^10-1:
                G =
 +GhO4              G + (rand_int(4) + 1)
             result is printed implicitly

Will test this this afternoon.

Java, 65
Since we have scores listed by language, why not throw Java into the mix? There's not much to golf here, just a simple loop, but I was able to squeeze a couple out of my initial attempt:
int f(){int i=1<<20,s=i;while(i-->0)s+=Math.random()*4;return s;}

Will test this this afternoon.

No problem. It takes around 80ms on this (slow) PC, but I don't know what you're using to time.

I do not believe your program is a correct model. It can and does in my testing add 0 on some rolls. As I understand it most d4's are 1,2,3,4 (no 0 possible).

@user39526 s (the total sum) starts at 1<<20 (the number of rolls). This is equivalent to adding one to each roll. When the randomizer throws 0, it's rolled a 1, etc.

You should upgrade to Java 8 !http://codegolf.stackexchange.com/a/52919/7021

@RobAu I use it at home, but on the computer I did this on it's taboo. So I end up using 7 sometimes and 8 sometimes. No worse than people using python 2 or 3 :)

Matlab, 24
First submission ever!
sum(randi([1,4],1,2^20))

I had hoped to make use of randi([1,4],1024), which gives a matrix of 1048576 elements, but then I needed a double sum, which takes more characters than this.
Regarding the running speed mentioned in the question, timeit tells me the runtime is about 0.031 seconds. So, pretty much instant.

I'm getting 0.04 to 0.05 seconds via octave online.

Ruby, 32 bytes
(1..2**20).inject{|x|x-~rand(4)}

In a more readable form:
(1..2**20).inject(0) do |x|
  x + rand(4) + 1
end

It creates a range from 1 to 1048576 and then iterates over the block that many times. Each time the block is executed the value from the previous iteration is passed in as x (initially 0, the default for inject). Each iteration it calculates a random number between 0 and 3 (inclusive), adds one so it simulates rolling a d4 and adds that to the total.
On my machine it's pretty fast to run (0.25 real, 0.22 user, 0.02 sys).
If you've got Ruby installed you can run it with ruby -e 'p (1..2**20).inject{|x|x+rand(4)+1}' (the p is necessary to see the output when run in this manner, omit it if you don't care for that or just run it inside IRB where the result is printed to the screen for you). I've tested it on Ruby 2.1.6.
Thanks to histocrat for the bit twiddling hack that replaces x + rand(4) + 1 with x-~rand(4).

Could you explain how it works?

The first online interpreter I could find that actually wants to load claims that the method rand() doesn't exist. I'll try to find another one.

Okay, I found one that works.

Bit twiddling hack: x-~rand(4) is equivalent to x+rand(4)+1.

Also, you can replace 2**20 with 4e10.

C, 57 bytes
main(a,b){for(b=a=1<<20;a--;b+=rand()%4);printf("%d",b);}

This code works... once. If you ever need to roll those dice again, you'll need to put srand(time(0)) in there, adding 14 bytes.

Why would you need to add srand(time(0))? (Sorry, I don't use C.)

@ASCIIThenANSI Many implementations of C's rand seed it to the same value every run. srand seeds the RNG, and time(0) gets the current time in seconds since 1970.

If you initialize a=b=1<<20 then you can skip 1+, this saves 4 bytes.

Also, int before main is not required.

Hint to anybody doing t=0, then t=t (...) +1 for 1048576 times: think again! (see my answer, eventually)

@nutki Thanks for the help!

PARI/GP, 25 bytes
Really, no need for golfing here -- this is the straightforward way of doing the calculation in GP. It runs in 90 milliseconds on my machine. Hoisting the +1 saves about 20 milliseconds.
sum(i=1,2^20,random(4)+1)

Just for fun: if one were optimizing for performance in PARI,
inline long sum32d4(void) {
  long n = rand64();
  // Note: __builtin_popcountll could replace hamming_word if using gcc
  return hamming_word(n) + hamming_word(n & 0xAAAAAAAAAAAAAAAALL);
}

long sum1048576d4(void) {
  long total = 0;
  int i;
  for(i=0; i<32768; i++) total += sum32d4();
  return total;
}

has a very small total operation count -- if xorgens needs ~27 cycles per 64-bit word (can anyone verify this?), then a processor with POPCNT should take only about 0.5 cycle/bit, or a few hundred microseconds for the final number.
This should have close-to-optimal worst-case performance among methods using random numbers of similar or higher quality. It should be possible to greatly increase average speed by combining cases -- maybe a million rolls at a time -- and selecting with (essentially) arithmetic coding.

PostgreSQL, 59 bytes
select sum(ceil(random()*4)) from generate_series(1,1<<20);

I'll admit to the slight problem that random() could, in theory, produce exactly zero, in which case the die roll would be zero.

You don't really need the ; to terminate the query since it is the only one

Javascript, 55 53 50 47 41 bytes
for(a=i=1<<20;i--;)a+=(Math.random()*4)|0

I didn't realize that non-random numbers were a known irritant, so I figure that I ought to post a real solution. Meant no disrespect.
Commentary: as noted by others above you can skip the +1 to each roll by starting off with the number of rolls in your answer, and by not having to write a=0,i=1<<20 you save two bytes, and another 2 because you don't add +1 to each roll. The parseInt function does the same thing as Math.floor but is 2 characters shorter.

Note that this answer is completely different from the one originally commented on by SuperJedi224 and @Andrew

You can remove both brackets and the last semicolon (and only the last one) to cut down a few further characters. Also, the current version is only 50 characters, not 52.

SuperJedi - thanks for the suggestions. I thought I'd tried it without the brackets only to run into problems, but perhaps I had a different problem. In any case, I think this is about as good as it's going to get.

a+=parseInt(Math.random()*4) may be shortened to a+=1+Math.random()*4&7. The 1+ is only if you care if it rolls 0 or not.

You can golf it down to this: for(a=i=1<<20;i--;)a+=(Math.random()*4)|0, that's only 41 bytes

for(a=i=1<<20;i--;)a+=Math.random()*4|0 works as well

VBA, 40 Bytes
for i=1 to 2^20:q=q+int(rnd*4)+1:next:?q

How can I retrieve the output?

@IsmaelMiguel: Paste the line in an immedtiate VBA window. ? is the print statement.

I plan on testing this one as soon as I can get visual studio to finish installing

I should really warn you it's slow... But it's BASIC - what else would you expect?

i reckon solutions that require Visual Studio should include the installation time in the running time! :P

@SuperJedi224 Don't need Visual Studio. It's vbA and it's included in Office Applications. Excel for instance

using excel/word/powerpoint/access, ?timer:for i=1 to 2^20:q=q+int(rnd*4)+1:next:?q:?timer will test it. using a dell latitude E6440, the time was 0.16 secs

you can lose 1 byte by changing this for i=1 to 2... to for i=1To 2

Current versions of excel can use ?[SUM(RANDARRAY(2^20,1,1,4,1))] for 31 bytes, though this code is roughly half the speed of the for loop solution

Commodore Basic, 37 bytes
1F┌I=1TO2↑20:C=C+INT(R/(1)*4+1):N─:?C

PETSCII substitutions: ─ = SHIFT+E, / = SHIFT+N, ┌ = SHIFT+O
Estimated runtime based on runs with lower dice counts: 4.25 hours.
It's tempting to try to golf off two bytes by making C an integer, getting implicit rounding of the random numbers.  However, the range on integers in Commodore Basic is -32678 to 32767 -- not enough, when the median answer is 2621440.

PowerShell, 41 37 bytes
1..1mb|%{(get-random)%4+1}|measure -s

Took my machine 2 minutes 40 seconds

Clip 10, 12 bytes
r+`m[)r4}#WT

         #4T    .- 4^10 = 1048576             -.
   m[   }       .- that many...               -.
     )r4        .-          ...random numbers -.
r+`             .- sum                        -.

It takes approximately 0.6 seconds to run on my machine.

Go, 87 bytes
Naive solution
import"math/rand";func r(){o,n:=0,2<<19;for i:=0;i<n;i++{o+=rand.Intn(4)};println(o+n)}

Run online here: http://play.golang.org/p/gwP5Os7_Sq
Due to the way the Go playground works you have to manually change the seed (time is always the same)

Go, 78 bytes
Golfed
import."math/rand";func r()(o int){for i:=2<<19;i>=0;i--{o+=Intn(4)+1};return}

Still working on it
Run online here http://play.golang.org/p/pCliUpu9Eq

Unfortunately, the golang.org playground doesn't implement the time operations properly and the repl.it one doesn't want to load right now. I'll see what I can do about it this afternoon.

Swift, 64 bytes
Nothing clever, golfing in Swift is hard...
func r()->Int{var x=0;for _ in 0..<(2<<19) {x+=Int(arc4random()%4)+1;};return x;}

Version 2 (too late)
var x=0;for _ in 0..<(2<<19){x+=Int(arc4random()%4)+1;};print(x)

Ruby, 51 47 chars
x=[];(2**20).times{x<<rand(4)+1};p x.inject(:+)

I looked at all of the answers before I did this, and the sum(2**20 times {randInt(4)}) strategy really stuck out, so I used that.
><>, 76 chars
012a*&>2*&1v
|.!33&^?&:-<
3.v < >-:v >
   vxv1v^<;3
  1234    n+
  >>>> >?!^^

I'm not sure if this one works, because my browser crashed when I tried to test it, but here's the online interpreter.

I'll give you a +1 for the ><> answer.

Java (Java 8) - 52
int f(){return new Random().ints(1<<20,1,5).sum();}

C#, 148 (console app)
using R=System.Random;using C=System.Console;class P{static void Main(){int o=0;R r=new R();for(int i=0;i<1048576;i++){o+=r.Next(1,4);}C.Write(o);}}

You can make your code shorter by removing all unnecessary whitespace, for example, int o = 0; to int o=0;.

You can also remove the space after C=, and then you'll have 148 chars (at the moment you have 149, not 150).

It's wrong (just try it: the sum is too low) Should be .Next(1,5), as the second parameter is the exclusive upper bound of the range

Lua 5.1, 51 bytes :)
a=0 for _=1,2^20 do a=a+math.random(4) end print(a)
math.random(n) already returns a number between 1 and n, so I didn't use @edc65's optimization (clever though it is).  Another 26 bytes is required to properly seed the RNG, however....

K, 13 bytes
+/1+(_2^20)?4

Take the sum (+/) of one plus a vector of 2^20 (_2^20) numbers from [0,4) (?4).
The floor _ is necessary because ^ returns a float, which is slightly inconvenient for this problem.
Tested with Kona. On my machine, this runs in roughly 24 milliseconds.
edit:
To test timing, you can prefix the program with \t and get the runtime in milliseconds.
  \t +/1+(_2^20)?4
25

Okay, I'll test this later this afternoon

Microscript, 7 bytes
First, a disclaimer: This is not actually a competing entry for this challenge, as this language is significantly too new.
Now, here's the program:
20ec1r4

Scratch, 102 bytes
The consensus seems to be to convert it to the plaintext form used by the scratchblocks code on the scratch forums, so here we go.
when green flag clicked
set [a v] to [0]
repeat (1048576)
change [a v] by (pick random (1) to (4))
end

Result will be stored in the variable a.

Swift, 69 bytes
var b={return[UInt32](0..<8<<17).reduce(0){$1*0+$0+arc4random()%4+1}}

$1*0 is required for the compiler to infer the type of the closure.

Perl 6, 26 22 bytes
{sum (1..4).pick xx 1+<20}
{sum roll 1..4: 1+<20}

It's not fast...takes about nine seconds on my system.
Try it online!
Six years ago, I apparently didn't know about the roll method.

Thunno 2 S, 6 bytes
T4@ı4ɼ

Try it online!
Explanation
T4@ı4ɼ  # Implicit input
T4@     # Push 4 ** 10
   ı    # Map over the range:
    4ɼ  #  Random number from [1..4]
        # Implicit output of sum

Actionscript 3, 81 77 75 bytes:
function r(){var a=0,i=1<<20;while(i--){a+=int(Math.random()*4+1)}return a}

I don't know Actionscript, but if you can write this as a full program rather than a function it will likely be shorter. And are the trailing semicolons on the final lines prior to the closing braces necessary? Also, you can express 1048576 as 2^20, which is much shorter.

@AlexA. As a full program, you have to write a class declaration in order to have it compile.

1048576 can be replaced with 1<<20. Also, int(Math.random()*4+1) may return 5. Use 1+Math.random()*3>>0 instead. Also, declare it as Actionscript 2 and you have this for you: r=function(){i=a=0;while(i++<1<<20)a+=1+Math.random()*3>>0;return a}. Only 68 bytes!. (or 69, if ; is required after the return)

@IsmaelMiguel Math.random()*4+1 will never return 5.  Math.random() returns 0 <= x < 1.  See the Math asdocs for details.

Hint to anybody doing t=0, then t=t (...) +1 for 1048576 times: think again! (see my answer, eventually)

You are right, it won't return 1. Sorry for that.

Since you haven't accepted my suggestion, I will take it and post it as a polyglot.

@IsmaelMiguel I'd have taken your suggestion if I'd written actionscript 2, but since I wrote actionscript 3, your suggestion would break.

Javascript + ActionScript2, 67 bytes
According to the ActionScript3 documentation, it is only required to use the keyword var when setting a type.
Other than that, it pretty much looks like Javascript.
Since I'm a fan of polyglots, I did this one.
The code:
function r(){i=a=0;while(i++<1<<20)a+=1+Math.random()*4&7;return a}

The &7 has a function to convert the number to an integer value. I could use other methods, but the gain in size would be null.
Test it here:

function r(){i=a=0;while(i++<1<<20)a+=1+Math.random()*4&7;return a}

document.write(r());

This answer is based on Brian's answer in ActionScript3, based in a comment I left with a solution for him.

Er...you do need var in the variable declaration. Depending on settings, it's a compile or runtime error if you omit it.

@Brian According to the documentation, only if I define a datatype (E.g.: var i:Number;) or "type annotation" (as the documentation calls it). And since I'm providing a value to it, according to the documentation, it won't give me any error.

" In ActionScript 3.0, use of the var statement is always required" Are you running as2 or 3? Your answer title says 2, but you cite as 3 documentation. Does your swf run successfully?

@Brian I'm aware of what I'm saying. Quoting: "In ActionScript 2.0, use of the var statement is only required if you use type annotations.". Therefore, the var statement isn't required. I'm reading from ActionScript3 but the code is for ActionScript2. I'm not inventing anything. And I haven't found a way to test it. But I surely will, if I had a way.

Ah.  Might I suggest adding a note to that effect?  Mentioning both as2 and 3 in your answer confuses the issue.

@Brian You are free to edit the question with that footnote, Actually, I would thank if you did so.

C# - 91
I went the function route for this
Func<int,int>G=s=>{int e=s=0;var r=new Random();for(;s<1<<20;s++)e+=r.Next(1,5);return e;};

C++, 154 bytes

Golfed:
#include<iostream>
#include <stdlib.h>
#include <time.h>
int main(){int c=0;srand(time(NULL));for(int x=0;x<=1048576;x++){c=c+(rand()%4+1);}std::cout<<c;}

Ungolfed:
#include<iostream>
#include <stdlib.h>
#include <time.h>

int main(){
    int c = 0;
    srand (time(NULL));
    for(int x = 0; x <= 1048576; x++){
        c = c + (rand() % 4 + 1);
    }

    std::cout<<c;
}

Python 2, 69 67 Bytes
import random
print sum([random.randint(1,4)for _ in range(4**10)])

11 9 bytes more that the existing Python 2 answer :( I'm sure I can find some places to shave off a few bytes though.

I don't think this version gets the distribution right.

@SuperJedi224 you are 100% correct, this is purely uniform where it should be some flavor of normal. I have an idea that involves sum(), I'll see if I can make it work.

You can remove the spaces between 4,) and for, and the space between range and (4**10).

Good eyes, @EasterlyIrk. Thanks!

Vyxal s, 38 bitsv2, 4.75 bytes
k₂ƛ4℅

Try it Online!
Explained
k₂ƛ4℅
k₂ƛ    # For each number in the range [1, 2**20]:
   4℅  #   Choose a random number between 1 and 4
# s flag sums

Created with the help of Luminespire.


text:
Resize rasterized text and make it look non-pixellated
This is a screenshot of some text typed in a text editor:

This is the same text at a larger size.

Notice how visible the aliasing is on letters with prominent diagonal strokes like x and z.  This issue is a major reason why raster fonts have lost popularity to “scalable” formats like TrueType.
But maybe this isn't an inherent problem with raster fonts, just with the way scaling of them is typically implemented.  Here's an alternative rendering using simple bilinear interpolation combined with thresholding.

This is smoother, but not ideal.  Diagonal strokes are still bumpy, and curved letters like c and o are still polygons.  This is especially noticeable at large sizes.
So is there a better way?
The task
Write a program that takes three command-line arguments.
resize INPUT_FILE OUTPUT_FILE SCALE_FACTOR

where

INPUT_FILE is the name of the input file, which is assumed to be an image file containing black text on a white background. You may use any mainstream raster image format (PNG, BMP, etc.) that's convenient.
OUTPUT_FILE is the name of the output file.  It can be either a raster or vector image format.  You may introduce color if you're doing some ClearType-like subpixel rendering.
SCALE_FACTOR is a positive floating-point value that indicates how much the image may be resized.  Given an x × y px input file and scaling factor s, the output will have a size of sx × sy px (rounded to integers).

You may use a third-pary open-source image processing library.
In addition to your code, include sample outputs of your program at scale factors of 1.333, 1.5, 2, 3, and 4 using my first image as input.  You may also try it with other fonts, including proportionally-spaced ones.
Scoring
This is a popularity contest.  The entry with the greatest number of upvotes minus downvotes wins.  In case of an exact tie, the earlier entry wins.
Edit: Deadline extended due to lack of entries.  TBA.
Voters are encouraged to judge based primarily on how good the output images look, and secondarily on the simplicity/elegance of the algorithm.

Is SCALE_FACTOR always > 1?

@kennytm: Yes.  Have edited to explicitly list the scale factors.

Can we assume there is only one line of text in the image?

@GiantTree: Yes.  You can support multi-line text if you want, but this isn't required.

Ruby, with RMagick
The algorithm is very simple—find patterns of pixels that look like this:
    ####
    ####
    ####
    ####
########
########
########
########

and add triangles to make them look like this:
    ####
   #####
  ######
 #######
########
########
########
########

Code:
#!/usr/bin/ruby

require 'rmagick'
require 'rvg/rvg'
include Magick

img = Image.read(ARGV[0] || 'img.png').first
pixels = []
img.each_pixel{|px, x, y|
    if px.red == 0 && px.green == 0 && px.blue == 0
        pixels.push [x, y]
    end
}

scale = ARGV[2].to_f || 5.0
rvg = RVG.new((img.columns * scale).to_i, (img.rows * scale).to_i)
    .viewbox(0, 0, img.columns, img.rows) {|cnv|
    # draw all regular pixels
    pixels.each do |p|
        cnv.rect(1, 1, p[0], p[1])
    end
    # now collect all 2x2 rectangles of pixels
    getpx = ->x, y { !!pixels.find{|p| p[0] == x && p[1] == y } }
    rects = [*0..img.columns].product([*0..img.rows]).map{|x, y|
        [[x, y], [
            [getpx[x, y  ], getpx[x+1, y  ]],
            [getpx[x, y+1], getpx[x+1, y+1]]
        ]]
    }
    # WARNING: ugly code repetition ahead
    # (TODO: ... fix that)
    # find this pattern:
    # ?X
    # XO
    # where X = black pixel, O = white pixel, ? = anything
    rects.select{|r| r[1][0][1] && r[1][1][0] && !r[1][2][1] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+2,y+1, x+1,y+2
        end
    # OX
    # X?
    rects.select{|r| r[1][0][1] && r[1][3][0] && !r[1][0][0] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+0,y+1, x+1,y+0
        end
    # X?
    # OX
    rects.select{|r| r[1][0][0] && r[1][4][1] && !r[1][5][0] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+0,y+1, x+1,y+2
        end
    # XO
    # ?X
    rects.select{|r| r[1][0][0] && r[1][6][1] && !r[1][0][1] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+2,y+1, x+1,y+0
        end
}
rvg.draw.write(ARGV[1] || 'out.png')

Outputs (click any to view image by itself):
1.333

1.5

2

3

4


text:
Last Nonzero Digits of a Factorial in Base
You should write a program or function which given three positive integers n b k as input outputs or returns the last k digits before the trailing zeros in the base b representation of n!.
Example
n=7 b=5 k=4
factorial(n) is 5040
5040 is 130130 in base 5
the last 4 digits of 130130 before the trailing zeros are 3013
the output is 3013

Input

3 positive integers n b k where 2 <= b <= 10.
The order of the input integers can be chosen arbitrarily.

Output

A list of digits returned or outputted as an integer or integer list.
Leading zeros are optional.
Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).

Examples
New tests added to check correctness of submissions. (They are not part of the under 1 minute runtime rule.)
Input => Output (with the choice of omitting leading zeros)
3 10 1  =>  6

7 5 4  =>  3013

3 2 3  =>  11

6 2 10  =>  101101

9 9 6  =>  6127

7 10 4  =>  504

758 9 19  =>  6645002302217537863

158596 8 20  =>  37212476700442254614

359221 2 40  =>  1101111111001100010101100000110001110001

New tests:
----------

9 6 3  =>  144

10 6 3  =>  544

This is code-golf, so the shortest entry wins.

under a minute on my computer is a little difficult to aim for if we don't know any specifics.

Would 7 5 3 output "013" or "13"?

@Claudiu based on the 7 10 4 test case I would say 13

@Claudiu "Leading zeros are optional." so both version is correct.

I'm having a hard time understanding the algorithm necessary. Can someone help explain? I'm looking here, but it's a bit different since there's a change of base: http://mathforum.org/library/drmath/view/71768.html

If we choose integer list for output, does endianness matter?

@Dennis Yes, endianness matters. I used the 1 min rule to clearly separate the simple O(n^2) algorithms from the rest but that might have been a failed attempt.

wont you settle a score-meter for this ?

Is a list of integers as output OK, or is a string required?

@isaacg It is ok. "A list of digits returned or outputted as an integer or integer list."  (just edited the , to or).

Do you have bounds for n?

Must we accept any positive integer for n or k?  Or can we limit them to the range of the language's integer type?

@TobySpeight Your integer type can limit the range where you can solve the problem but the given should cause no problem for your code.

Are you going to change the accepted answer with the renewed interest?

Dyalog APL, 23 bytes
⌽k↑⌽{⍵↓⍨-⊥⍨0=⍵}b⊥⍣¯1⊢!n

This program works as long as the factorial does not exceed internal representation limit. In Dyalog APL, the limit can be raised by ⎕FR←1287.
Assumes the variables n, b, and k have been set (e.g. n b k←7 5 4), but if you rather want prompting for n, b, and k (in that order) then replace the three characters with ⎕.

Every test case I threw at it was computed in about 11 microseconds on my machine (M540).

Python, 198 192 181 chars
def F(n,b,k):
 p=5820556928/8**b%8;z=0;e=f=x=1
 while n/p**e:z+=n/p**e;e+=1
 z/=1791568/4**b%4;B=b**(z+k)
 while x<=n:f=f*x%B;x+=1
 s='';f/=b**z
 while f:s=str(f%b)+s;f/=b
 return s

It's fast enough, ~23 seconds on the biggest example.  And no factorial builtin (I'm looking at you, Mathematica!).

[2,3,2,5,3,7,2,3,5][b-2] could be int('232537235'[b-2]) to save 3 bytes. [1,1,2,1,1,1,3,2,1][b-2] similarly.

For the latter, a lookup table 111973>>2*(b-2)&3 is even shorter. It's the same number of bytes for the former though (90946202>>3*(b-2)&7).

nvm looks like you were right about the higher digits thing

I believe you can save a few bytes by making this a program and not a function.

Mathematica, 57 48 bytes
Saved 9 bytes thanks to @2012rcampion .
IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&

I've never really used mathematica, but couldn't you swap the order of the arguments to make b first to save 2 bytes?

@FryAmTheEggman I'm new to the golfing community, is swapping argument order "kosher"?

You can actually get to 47: IntegerString[#!#2^-#!~IntegerExponent~#2,##2]& (both this and your original are quite fast)

The asker wrote: "The order of the input integers can be chosen arbitrarily." under input, so in this case it's definitely fine

@Fry Wow, looks like I didn't read closely enough.  However, the SlotSequence trick I used in my comment only works with the current order, so you couldn't save any more.

Pyth, 26 35 bytes
M?G%GHg/GHH.N>ju%g*GhHT^T+YslNN1T_Y

This is a function of 3 arguments, number, base, number of digits.
Demonstration.
The slowest test case, the final one, takes 15 seconds on my machine.

@Sp3000 I added a fix which I think should be sufficient.

PARI/GP, 43 bytes
Trading speed for space yields this straightforward algorithm:
(n,b,k)->digits(n!/b^valuation(n!,b)%b^k,b)

Each of the test cases runs in less than a second on my machine.

Haskell, 111 109 bytes
import Data.Digits
f n b k=digits b$foldl(((unDigits b.reverse.take k.snd.span(<1).digitsRev b).).(*))1[1..n]

Usage: f 158596 8 20 -> [3,7,2,1,2,4,7,6,7,0,0,4,4,2,2,5,4,6,1,4]
Takes about 8 seconds for f 359221 2 40 on my 4 year old laptop.
How it works: fold the multiplication (*) into the list [1..n]. Convert every intermediate result to base b as a list of digits (least significant first), strip leading zeros, then take the first k digits and convert to base 10 again. Finally convert to base b again, but with most significant digit first.

you had the idea in my mind , that i was interpreting it using matlab , what a coincidende :D

Python 3, 146 bytes
import math
i,f=input(),int
n=i.split()
e=math.factorial(f(n[0]))
d=''
while e>0:
 d=str((e%f(n[1])))+d;e=e//f(n[1])
print(d.strip('0')[-f(n[2]):])

I'm not sure the test cases will all run fast enough - the larger ones are very slow (as it is looping through the number).
Try it online here (but be careful).

Java, 303 299 296 bytes
import java.math.*;interface R{static void main(String[]a){BigInteger c=new BigInteger(a[1]),b=c.valueOf(1);for(int i=new Integer(a[0]);i>0;i--){b=b.multiply(b.valueOf(i));while(b.mod(c).equals(b.ZERO))b=b.divide(c);b=b.mod(c.pow(new Integer(a[2])));}System.out.print(b.toString(c.intValue()));}}

On my computer, this averages a little under a third of a second on the 359221 2 40 testcase. Takes input via command line arguments.

bc, 75 bytes
define void f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(!x%b)x/=b}
x}

This uses some GNU extensions to reduce code size; a POSIX-conforming equivalent weighs in at 80 bytes:
define f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(x%b==0)x/=b}
return(x)}

To keep run times reasonable, we trim the trailing zeros (while(!x%b)x/=b) and truncate to the final k digits (x%=b^k) as we compute the factorial (for(x=1;n;)x*=n--).
Test program:
f(3, 10, 1)
f(7, 5, 4)
f(3, 2, 3)
f(6, 2, 10)
f(9, 9, 6)
f(7, 10, 4)
f(758, 9, 19)
f(158596, 8, 20)
f(359221, 2, 40)
f(9, 6, 3)
f(10, 6, 3)
quit

Runtime of the full test suite is approx 4¼ seconds on my 2006-vintage workstation.

This is my first ever bc program (golf or not), so any tips are especially welcome...

PHP, 80 bytes
function f($a,$b,$c){echo substr(rtrim(gmp_strval(gmp_fact($a),$b),"0"),-1*$c);}

Used as  f(359221,2,40) for the last test case. Runs pretty smoothly for all test cases.
Try here !