text:
Complexity-free Kolmogorov(-Smirnov)
In statistics, sometimes it's useful to know whether two data samples come from the same underlying distribution. One way to do this is to use the two-sample Kolmogorov-Smirnov test.
Your task will be to write a program that reads in two unsorted nonnegative integer arrays and calculates the main statistic used in the test.

Given an array A and a real number x, define the distribution function F by
F(A,x) = (#number of elements in A less than or equal to x)/(#number of elements in A)

Given two arrays A1 and A2, define
D(x) = |F(A1, x) - F(A2, x)|

The two-sample Kolmogorov-Smirnov statistic is the maximum value of D over all real x.
Example
A1 = [1, 2, 1, 4, 3, 6]
A2 = [3, 4, 5, 4]

Then:
D(1) = |2/6 - 0| = 1/3
D(2) = |3/6 - 0| = 1/2
D(3) = |4/6 - 1/4| = 5/12
D(4) = |5/6 - 3/4| = 1/12
D(5) = |5/6 - 4/4| = 1/6
D(6) = |6/6 - 4/4| = 0

The KS-statistic for the two arrays is 1/2, the maximum value of D.
Test cases
[0] [0] -> 0.0
[0] [1] -> 1.0
[1, 2, 3, 4, 5] [2, 3, 4, 5, 6] -> 0.2
[3, 3, 3, 3, 3] [5, 4, 3, 2, 1] -> 0.4
[1, 2, 1, 4, 3, 6] [3, 4, 5, 4] -> 0.5
[8, 9, 9, 5, 5, 0, 3] [4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9] -> 0.175824
[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7] [7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8] -> 0.363636

Rules

You may write a function or a full program. Input may be via STDIN or function argument, and output may be via STDOUT or return value.
You may assume any unambiguous list or string format for the input, as long as it is consistent for both arrays
On the off-chance that your language has a builtin for this, you may not use it.
Answers need to be correct to at least 3 significant figures
This is code-golf, so the program in the fewest bytes wins

Are all inputs going to be integer arrays, or can they contain floating points?

@KennyTM Just nonnegative integers. I thought I'd keep things simple.

Is there a maximum value we can assume for arrays? (E.g. all entries of A are below length(A)?)

@flawr No you can't assume a maximum value

I like the title. I'm stile targeting the kolmogorov complexity bagde, but not this time.

APL (29 24)
(Thanks to Zgarb for the extra inspiration.)
{⌈/|-⌿⍺⍵∘.(+/≤÷(⍴⊣))∊⍺⍵}

This is a function that takes the arrays as its left and right arguments.
      8 9 9 5 5 0 3 {⌈/|-⌿⍺⍵∘.(+/≤÷(⍴⊣))∊⍺⍵} 4 9 0 5 5 0 4 6 9 10 4 0 9
0.1758241758

Explanation:
{⌈/                                maximum of
   |                               the absolute value of
    -⌿                             the difference between
      ⍺⍵∘.(         )∊⍺⍵          for both arrays, and each element in both arrays
            +/≤                    the amount of items in that array ≤ the element
               ÷                   divided by
                (⍴⊣)              the length of that array
                          }

I didn't know you could do ⍺⍵! That's handy.

Also, I think ⍳⌈/ is unnecessary, since the maximum is obtained exactly at one of the array values.

@Zgarb: you're right of course, I just have to test for each possible array value. That means I can get rid of the 0, too, as it'll test for that if the array contains it. Thanks! (And that'll teach me, as usually if you have to add in a special case, that means the algorithm isn't simple enough.)

This is true sorcery, right here.

@Sp3000: did you write the one-element arrays correctly? You can't just write 1, as that would be a scalar. You should write (,1) instead. If you do that, it works.

So it does - thanks for clarifying :)

J - 39
I'm sure can be shorten much more
f=:+/@|:@(>:/)%(]#)
>./@:|@((,f])-(,f[))

Usage
2 10 10 10 1 6 7 2 10 4 7 >./@:|@((,f])-(,f[)) 7 7 9 9 6 6 5 2 7 2 8
0.363636

Does this create a function or use stdin/stdout? What does the second part exactly do? (Looks a bit long for a function call?)

@flawr A function, similar to APL

I think you could avoid explicitly defining f if you use something like >./@:|@({.-{:)f"1@, but I'm not quite sure.

JavaScript (ES6) 99 119 128
More or less straightforward JavaScript implementation, probably more golfable.
In the F function I use > instead of <=, as abs(F(a)-F(b)) === abs((1-F(a))-(1-F(b)))
No more function definition as default parameer in this last edit.
As I said, it's straightforward. The F function is the F function, the D function is the unnamed function used in line 2. It's evaluated using .map for each value present in the two arrays, as the max value for all reals must be one of these. At last, the spread operator (...) is used to pass the D values array as a parameter list to the max function.
K=(a,b)=>Math.max(...a.concat(b).map(x=>
  Math.abs((F=a=>a.filter(v=>v>x).length/a.length)(a)-F(b))
))

Test In FireFox/FireBug console
;[[[0],[0]], [[0],[1]],
[[1, 2, 3, 4, 5],[2, 3, 4, 5, 6]],
[[3, 3, 3, 3, 3],[5, 4, 3, 2, 1]],
[[1, 2, 1, 4, 3, 6],[3, 4, 5, 4]],
[[8, 9, 9, 5, 5, 0, 3],[4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9]],
[[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7],[7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8]]]
.forEach(x=>console.log(x[0],x[1],K(x[0],x[1]).toFixed(6)))

Output
[0] [0] 0.000000
[0] [1] 1.000000
[1, 2, 3, 4, 5] [2, 3, 4, 5, 6] 0.200000
[3, 3, 3, 3, 3] [5, 4, 3, 2, 1] 0.400000
[1, 2, 1, 4, 3, 6] [3, 4, 5, 4] 0.500000
[8, 9, 9, 5, 5, 0, 3] [4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9] 0.175824
[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7] [7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8] 0.363636

I am curous about your function K: Is it correct that you define other functions F,D in the argument list? Does this behave like some optional arguments or so?

@flawr yes, they are optional arguments with a default value. So avoiding the pollution of global variable space (that's not a problem in code golf, but anyway...)

Plus, since the function already required 2 variables (thus the brackets), it would be 2 extra bytes to move those variables out of the option var list to inside of the function body.

Python 3, 132 108 95 88
f=lambda a,x:sum(n>x for n in a)/len(a)
g=lambda a,b:max(abs(f(a,x)-f(b,x))for x in a+b)

The input are 2 lists to the function g
Thanks to: Sp3000, xnor, undergroundmonorail
Line 2, first call to f reads like "fax". I found that mildly amusing

To count the number of elements of a list that satisfy a property, it's shorter to do sum(n>x for n in a). Also, it looks like you're not using s=filter. And for max, you don't actually need the list brackets; Python lets the function parens double as comprehension parens.

Thanks! I used filter in a previous version, forgot to remove it. Sadly I can't remove the first pair of square brackets since then it will be a generator, which has no len.

you don't need len, read the comment again :P

CJam, 33 31 bytes
q~_:+f{\f{f<_:+\,d/}}z{~-z}%$W=

Input is a CJam styles array of the two arrays.
Example:
[[8 9 9 5 5 0 3] [4 9 0 5 5 0 4 6 9 10 4 0 9]]

Output:
0.17582417582417587

Try it online here

Matlab (121)(119)
This is a program that takes two lists throu stdin and prints the result to stdout. It is a strightfwd approcht and I tried to golf it as much as possible. K(a) returns a function that calculates x -> F(a,x). Then the anonymous function @(x)abs(g(x)-h(x)) which corresponds to the function D is applied to every possible integer of 0:max([a,b]) and the maximum of the results is displayed. (arrayfun does the same as map in other languages: it applies a function to every element of a array)
a=input('');b=input('');
K=@(a)@(x)sum(a<=x)/numel(a);
g=K(a);h=K(b);
disp(max(arrayfun(@(x)abs(g(x)-h(x)),0:max([a,b]))))

Erlang, 96 Bytes
edc65's JavaScript solution ported to Erlang.
f(A,B)->F=fun(A,X)->length([V||V<-A,V>X])/length(A)end,lists:max([abs(F(A,X)-F(B,X))||X<-A++B]).

Test:
lists:foreach(fun ([H,T] = L) -> io:format("~p ~p~n", [L, w:f(H, T)]) end, [[[0],[0]], [[0],[1]],
        [[1, 2, 3, 4, 5],[2, 3, 4, 5, 6]],
        [[3, 3, 3, 3, 3],[5, 4, 3, 2, 1]],
        [[1, 2, 1, 4, 3, 6],[3, 4, 5, 4]],
        [[8, 9, 9, 5, 5, 0, 3],[4, 9, 0, 5, 5, 0, 4, 6, 9, 10, 4, 0, 9]],
        [[2, 10, 10, 10, 1, 6, 7, 2, 10, 4, 7],[7, 7, 9, 9, 6, 6, 5, 2, 7, 2, 8]]]).

Output:
[[0],[0]] 0.0
[[0],[1]] 1.0
[[1,2,3,4,5],[2,3,4,5,6]] 0.20000000000000007
[[3,3,3,3,3],[5,4,3,2,1]] 0.4
[[1,2,1,4,3,6],[3,4,5,4]] 0.5
[[8,9,9,5,5,0,3],[4,9,0,5,5,0,4,6,9,10,4,0,9]] 0.17582417582417587
[[2,10,10,10,1,6,7,2,10,4,7],[7,7,9,9,6,6,5,2,7,2,8]] 0.36363636363636365

STATA 215
This is 90% getting the input into a format that can be used because STATA already has a ksmirnov command.
di _r(a)
di _r(b)
file open q using "b.c",w
forv x=1/wordcount($a){
file w q "1,"(word($a,`x'))_n
}
forv x=1/wordcount($b){
file w q "2,"(word($b,`x'))_n
}
file close q
insheet using "b.c"
ksmirnov v2,by(v1)
di r(D)

Oh wow, I didn't think that languages would have a builtin for this...  I just did some research and I decided it would be best to disallow builtins from now on, but you can keep this because it was posted before the rule change :)

R, 65 bytes
f=function(a,b){d=c(a,b);e=ecdf(a);g=ecdf(b);max(abs(e(d)-g(d)))}

This function takes two vectors as arguments and returns the maximum difference of their empirical cumulative distribution functions.
If built-ins were allowed, it would reduce to mere 12 bytes:
ks.test(a,b)

Mathematica, 76 73 63
Mathematica has the built-in function KolmogorovSmirnovTest, but I won't use it here.
k=N@MaxValue[Abs[#-#2]&@@(Tr@UnitStep[x-#]/Length@#&/@{##}),x]&

Usage:
k[{1, 2, 1, 4, 3, 6}, {3, 4, 5, 4}]

0.5

Quick implementation in Python 3.4.2 (79 bytes):
F=lambda A,x:len([n for n in A if n<=x])/len(A)
D=lambda x:abs(F(A1,x)-F(A2,x))

Example:
>>> A1 = [-5, 10, 8, -2, 9, 2, -3, -4, -4, 9]
>>> A2 = [-5, -3, -10, 8, -4, 1, -7, 6, 9, 5, -7]
>>> D(0)
0.045454545454545414

The requirement is to find the maximum value of D(x) for all integers values of x. Please comply to the problem spec.

Welcome! As Optimizer says, the task is to find the maximum value of D, not to just implement D as a function. Also, I'm sorry if I wasn't clear, but you can't assume that A1 and A2 are already defined variables (you can put them in the lambda though, e.g. lambda x,A1,A2: - that's okay)

Also I've added some syntax highlighting - I think it makes it look prettier :)

Sorry about that, I'm new here.

No problems :) If anything's unclear, you can ask in the comments. But once again, welcome!

Java - 633 622 Bytes
Ok,first up, trying to get better at java so thats why i tried it in java, I know i'll never do well, but eh, its fun.
second, I honestly thought i could do this in way less, then i got to the stage where there were doubles everywhere, and the method declarations meant using methods only saved 4-5 chars in total.
in short, i'm a bad golfer.
edit: usage format> java K "2,10,10,10,1,6,7,2,10,4,7" "7,7,9,9,6,6,5,2,7,2,8"
import java.lang.*;
class K{public static void main(String[]a){double[]s1=m(a[0]);double[]s2=m(a[1]);
int h=0;if(H(s1)<H(s2))h=(int)H(s2);else h=(int)H(s1);double[]D=new double[h];
for(int i=0;i<h;i++){D[i]=Math.abs(F(s1,i)-F(s2,i));}System.out.println(H(D));}
static double[]m(String S){String[]b=S.split(",");double[]i=new double[b.length];
for(int j=0;j<b.length;j++){i[j]=new Integer(b[j]);}return i;}
static double H(double[]i){double t=0;for(int j=0;j<i.length;j++)
{if(i[j]>t)t=i[j];}return t;}
static double F(double[]A,int x){double t=0;double l=A.length;
for(int i=0;i<l;i++){if(A[i]<=x)t++;}return t/l;}}

you were right. updating.

Haskell 96 83
l=fromIntegral.length
a%x=l(filter(<=x)a)/l a
a!b=maximum$map(\x->abs$a%x-b%x)$a++b

(!) is the kolmogorov-smirnov function which takes two lists

some quick golfs: use map rather than fmap; use maximum rather than foldr1 max; define l=fromIntegral.length and you can get rid of i, and then you can shorten % to l(filter(<=x)a)/l a. Gets it down to 84!

R, 107 bytes
Different Approach
f=function(a,b){e=0
d=sort(unique(c(a,b)))
for(i in d-min(diff(d))*0.8)e=max(abs(mean(a<i)-mean(b<i)),e)
e}

Ungolfed
f=function(a,b){
    e=0
    d=sort(unique(c(a,b)))
    d=d-min(diff(d))*0.8
    for(i in d) {
        f=mean(a<i)-mean(b<i)
        e=max(e,abs(f))
    }
    e
}


text:
Counting k-mers
The task is to count the number of distinct substrings of length k, for k = 1,2,3,4,.....
Output
You should output one line per k you manage to complete with one number per output line. Your output should be in order of increasing k until you run out of time.
Score
Your score is the highest k you can get to on my computer in under 1 minute.
You should use http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/chr2.fa.gz as your input and ignore newlines.  Your code should, however, be case sensitive.
You can decompress the input before starting the timing.
The following (inefficient) code counts the number of distinct 4-mers.
awk -v substr_length=4 '(len=length($0))>=substr_length{for (i=1; (i-substr_length)<len; i++) substrs[substr($0,i,substr_length)]++}; END{for (i in substrs) print substrs[i], i}' file.txt|wc

Memory limits
To make your code behave nicely on my computer and to make the task more challenging, I will limit the RAM you can use to 2GB by using
ulimit -v 2000000
before running your code.  I am aware this is not a rock solid way of limiting RAM usage so please don't use imaginative ways to get round this limit by, for example, spawning new processes.  Of course you can write multi-threaded code but if someone does, I will have to learn how to limit the total RAM used for that.
Tie Breaker
In the case of a tie for some maximum k I will time how long it takes to give the outputs up to k+1 and the quickest one wins. In the case that they run in the same time to within a second up to k+1, the first submission wins.
Languages and libraries
You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also freely available for Linux.
My machine
The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor on an Asus M5A78L-M/USB3 Motherboard (Socket AM3+, 8GB DDR3). This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.

Test output
FUZxxl's code outputs the following (but not all within 1 minute) which I believe is correct.
14
92
520
2923
15714
71330
265861
890895
2482912
5509765
12324706
29759234

League table

k >= 4000 FUZxxl (C)
k = 16 by Keith Randall (C++)
k = 10 by FUZxxl (C)

How much can you specialize your code to the input?

Clearly it would ruin the competition if you just precomputed the answers and had your code output them.  Don't do that.
Ideally, anything your code needs to learn about the data that it will use to run more quickly it can learn at run-time.
You can however assume the input will look like the data in the *.fa files at http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .

In J, a naïve solution would simply be [:~.]\ but guess that won't cut it.

@FUZxxl Well... how large a k does it give you in one minute and much RAM does it use?

Well, for 2 it returns in about 5 seconds, for 3 it take 3.2 GB of RAM and takes about a minute. I didn't try what it would do for four. Let me try...

@FUZxxl Well... please feel free to submit it as an answer :)  Remember I cut it off at 2GB of RAM.

Is a solution required to abort itself after one minute or are you going to do this?

Is there any restriction on how input has to be provided? Can we assume input comes from stdin and is attached to a file?

Does the order matter in which we output the entries in one line? With what character are they separated?

Are we allowed to put trailing spaces into the output?

@FUZxxl You can assume a file called chr2.fa as input. If you want it on stdin you will need to pipe it.  The order of the output matters. It should be for k  = 1,2,3,4,5,6,7,... in that order.  The output is one number per line.

Can we use the special properties of the given file to improve the effectiveness of our program on the test? (While producing correct output for any input.)

I get 110 for k==2.  Could you double-check the correct result?

@KeithRandall The first few solutions I get are 15, 93, 521, 2924, 15715, 71331, 265862, 890896, and 2482913. I'm not sure if they are correct, but OP thinks so.

@FUZxxl: ah, I need to remove \n first.  You have a bug also though, the +1 after ftello() allows one zero byte to sneak in at the end.

Huch? Are you sure? Let me remove that…

When you say "You can decompress the input before starting the timing.": a) Does that include a licence to read the input from a ready-decompressed file? b) Does it include a licence to strip the newlines from that prepared file?

@KeithRandall You are right it is all out by one currently.

@PeterTaylor Yes to reading from a ready-decompressed file. No to stripping the newlines beforehand. Handling newlines should be part of the code that is timed.

@randomra I updated the question. Please let me know if it helps.

I found a wonderful method to compute the indices for all k in very brief time, but the preprocessing takes so long -.-

@FUZxxl What is it? I am very interested.

@Lembik I won't tell you. I'm currently in the process of altering the solution so it gives output earlies (but is slower overall). It take 9 minutes to preprocess the data on my machine.

@Lembik I won't tell you because I'm afraid someone implements the approach and beats me. I can tell you later, when it's done.

@Lembik I improved my solution. It's not the new strategy I am thinking about though.

@Lembik Would you mind rating my solution?

C (≥ 4000)
This code neither uses less than 2 GB of RAM (it uses slightly more) nor produces any output in the first minute. But if you wait for about six minutes, it prints out all the k-mer counts at once.
An option is included to limit the highest k for which we count the k-mers. When k is limited to a reasonable range, the code terminates in less than one minute and uses less than 2 GiB of RAM. OP has rated this solution and it terminates in less than one minute for a limit not significantly higher than 4000.
How does it work?
The algorithm has four steps.

Read the input file into a buffer and strip newlines.
Suffix-sort an array of indices into the input buffer. For instance, the suffixes of the string mississippi are:
mississippi
ississippi
ssissippi
sissippi
issippi
ssippi
sippi
ippi
ppi
pi
i

These strings sorted in lexicographic order are:
i
ippi
issippi
ississippi
mississippi
pi
ppi
sippi
sissippi
ssippi
ssissippi

It is easy to see that all equal substrings of length k for all k are found in adjacent entries of the suffix-sorted array.
An integer array is populated in which we store at each index k the number of distinct k-mers. This is done in a slightly convoluted fashion to speed up the process. Consider two adjacent entries the suffix sorted array.
   p     l
   v     v
issippi
ississippi

p denotes the length of longest common prefix of the two entries, l denotes the length of the second entry. For such a pair, we find a new distinct substring of length k for p < k ≤ l. Since p ≪ l often holds, it is impractical to increment a large number of array entries for each pair. Instead we store the array as a difference array, where each entry k denotes the difference to the number of k-mers to the number of (k - 1)-mers. This turns an update of the form
0  0  0  0 +1 +1 +1 +1 +1 +1  0  0  0

into a much faster update of the form
0  0  0  0 +1  0  0  0  0  0 -1  0  0

By carefully observing that l is always different and in fact every 0 < l < n will appear exactly once, we can omit the subtractions and instead subtract 1 from each difference when converting from differences into amounts.
Differences are converted into amounts and printed out.

The source code
This source uses the libdivsufsort for sorting suffix arrays. The code generates output according to the specification when compiled with this invocation.
cc -O -o dsskmer dsskmer.c -ldivsufsort

alternatively the code can generate binary output when compiled with the following invocation.
cc -O -o dsskmer -DBINOUTPUT dsskmer.c -ldivsufsort

To limit the highest k for which k-mers are to be counted, supply -DICAP=k where k is the limit:
cc -O -o dsskmer -DICAP=64 dsskmer.c -ldivsufsort

Compile with -O3 if your compiler supplies this option.
#include <stdlib.h>
#include <stdio.h>

#include <divsufsort.h>

#ifndef BINOUTPUT
static char stdoutbuf[1024*1024];
#endif

/*
 * load input from stdin and remove newlines. Save length in flen.
 */
static unsigned char*
input(flen)
    int *flen;
{
    size_t n, len, pos, i, j;
    off_t slen;
    unsigned char *buf, *sbuf;

    if (fseek(stdin, 0L, SEEK_END) != 0) {
        perror("Cannot seek stdin");
        abort();
    }

    slen = ftello(stdin);
    if (slen == -1) {
        perror("Cannot tell stdin");
        abort();
    }

    len = (size_t)slen;

    rewind(stdin);

    /* Prepare for one extra trailing \0 byte */
    buf = malloc(len + 1);
    if (buf == NULL) {
        perror("Cannot malloc");
        abort();
    }

    pos = 0;

    while ((n = fread(buf + pos, 1, len - pos, stdin)) != 0)
        pos += n;

    if (ferror(stdin)) {
        perror("Cannot read from stdin");
        abort();
    }

    /* remove newlines */
    for (i = j = 0; i < len; i++)
        if (buf[i] != '\n')
            buf[j++] = buf[i];

    /* try to reclaim some memory */
    sbuf = realloc(buf, j);
    if (sbuf == NULL)
        sbuf = buf;

    *flen = (int)j;
    return sbuf;
}

/*
 * Compute for all k the number of k-mers. kmers will contain at index i the
 * number of (i + 1) mers. The count is computed as an array of differences,
 * where kmers[i] == kmersum[i] - kmersum[i-1] + 1 and then summed up by the
 * caller. This algorithm is a little bit unclear, but when you write subsequent
 * suffixes of an array on a piece of paper, it's easy to see how and why it
 * works.
 */
static void
count(buf, sa, kmers, n)
    const unsigned char *buf;
    const int *sa;
    int *kmers;
{
    int i, cl, cp;

    /* the first item needs special treatment */
    kmers[0]++;

    for (i = 1; i < n; i++) {
        /* The longest common prefix of the two suffixes */
        cl = n - (sa[i-1] > sa[i] ? sa[i-1] : sa[i]);
#ifdef ICAP
        cl = (cl > ICAP ? ICAP : cl);
#endif
        for (cp = 0; cp < cl; cp++)
            if (buf[sa[i-1] + cp] != buf[sa[i] + cp])
                break;

        /* add new prefixes to the table */
        kmers[cp]++;
    }
}

extern int
main()
{
    unsigned char *buf;
    int blen, ilen, *sa, *kmers, i;

    buf = input(&blen);

    sa = malloc(blen * sizeof *sa);

    if (divsufsort(buf, sa, blen) != 0) {
        puts("Cannot divsufsort");
        abort();
    }

#ifdef ICAP
    ilen = ICAP;
    kmers = calloc(ilen + 1, sizeof *kmers);
#else
    ilen = blen;
    kmers = calloc(ilen, sizeof *kmers);
#endif

    if (kmers == NULL) {
        perror("Cannot malloc");
        abort();
    }

    count(buf, sa, kmers, blen);

#ifndef BINOUTPUT
    /* sum up kmers differences */
    for (i = 1; i < ilen; i++)
        kmers[i] += kmers[i-1] - 1;

    /* enlarge buffer of stdout for better IO performance */
    setvbuf(stdout, stdoutbuf, _IOFBF, sizeof stdoutbuf);

    /* human output */
    for (i = 0; i < ilen; i++)
        printf("%d\n", kmers[i]);
#else
    /* binary output in host endianess */
    fprintf(stderr, "writing out result...\n");
    fwrite(kmers, sizeof *kmers, ilen, stdout);
#endif

    return 0;
}

The binary file format can be converted into the human-readable output format with the following program:
#include <stdlib.h>
#include <stdio.h>

static int inbuf[BUFSIZ];
static char outbuf[BUFSIZ];

extern int main()
{
    int i, n, sum = 1;

    setbuf(stdout, outbuf);

    while ((n = fread(inbuf, sizeof *inbuf, BUFSIZ, stdin)) > 0)
        for (i = 0; i < n; i++)
            printf("%d\n", sum += inbuf[i] - 1);

    if (ferror(stdin)) {
        perror("Error reading input");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

sample output
Sample output in the binary format for the file chr22.fa can be found here. Please decompress with bzip2 -d first. Output is provided in binary format only because it compresses much better (3.5 kB vs. 260 MB) than output in human-readable format. Beware though that the reference output has a size of 924 MB when uncompressed. You might want to use a pipe like this:
bzip2 -dc chr2.kmerdiffdat.bz2 | ./unbin | less

This is very interesting. Can you break down the time taken by each part? It seems constructing the suffix array is less than 10% of the time.

step one takes about three seconds, step two takes about 20 seconds, step three takes the entire rest. The time taken by step four is negligible.

If you like, you can place strategic fprintf(stderr, "doing step n\n"); statements to figure out how long the steps take.

@FUZxxl did you plot the distribution of the maximum p-values to see how much you can speed up step 3 by cutting of if p>k (counting only to k-mers)? although if step 2 takes 20 secs there might not be much room there. great explanation btw

@randomra It should indeed be possible to cap the highest k we observe and I was able to cut the runtime to under one minute with such an approach. Let me check.

Yeah, it works. I didn't bother checking before. Wait a minute as I update the post.

I always get gcc  -Wall -O3 -o dsskmer -DICAP=64 dsskmer.c
/tmp/ccsuEc2x.o: In function main': dsskmer.c:(.text.startup+0xf9): undefined reference to divsufsort' . How exactly are you compiling it?  I just followed the instructions in the file INSTALL to install libdivsufsort.

Ah sorry, you have to compile with -ldivsufsort. I forgot to say that.

and that has to be the last argument.

OK.. I had to do sudo ldconfig as well.Now I get   cat ~/Downloads/chr2.fa |./dsskmer
Cannot seek stdin: Illegal seek

@Lembik Do not use cat. Use shell redirection like in ./dsskmer <~/Downloads/chr2.fs. The code needs to know how long the input file is and that's not possible with a pipe.

Well.. it's very impressive! I get to 4000 at least. Also I notice that the number of kmers goes up very slowly at this point. I wonder if there is some way of taking advantage of this. For example, the last 4 values up to k = 4000 are 240581805
240581816
240581827
240581838

@Lembik that's because the file only has about that many entries (go figure). It's the reason why the compressed representation is so small; the difference is all zeros at the end. (they actually all decrement by one, but that one is not part of the difference representation).

@Lembik Well, I guess that bounty is mine then :-). Let's see if someone finds a better solution. How did you actually get the idea for this challenge?

It's something that people really want to do in bioinformatics. But they are always complaining it is too slow and uses too much memory :) I will leave the bounty awarding until the end of the period if that is OK.

@Lembik Doesn't seem too slow for me. Maybe they're just bad programmers.

C++, k=16, 37 seconds
Computes all of the 16-mers in the input.  Each 16-mer is packed 4 bits to a symbol into a 64-bit word (with one bit pattern reserved for EOF).  The 64-bit words are then sorted.  The answer for each k can be read off by looking at how often the 4*k top bits of the sorted words change.
For the test input I use about 1.8GB, just under the wire.
I'm sure the reading speed could be improved.
Output:
14
92
520
2923
15714
71330
265861
890895
2482912
5509765
12324706
29759234
69001539
123930801
166196504
188354964

Program:
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

int main(int argc, char *argv[]) {
    // read file
    printf("reading\n");
    FILE *f = fopen(argv[1], "rb");
    fseek(f, 0, SEEK_END);
    int32_t size = ftell(f);
    printf("size: %d\n", size);
    fseek(f, 0, SEEK_SET);

    // table to convert 8-bit input into 4-bit tokens.  Reserve 15 for EOF.
    int ntokens = 0;
    int8_t squash[256];
    for(int i = 0; i < 256; i++) squash[i] = -1;

    uint64_t *buf = (uint64_t*)malloc(8*size);

    int32_t n = 0;
    uint64_t z = 0;
    for(int32_t i = 0; i < size; i++) {
        char c = fgetc(f);
        if(c == '\n') continue;
        int8_t s = squash[c];
        if(s == -1) {
            if(ntokens == 15) {
                printf("too many tokens\n");
                exit(1);
            }
            squash[c] = s = ntokens++;
        }
        z <<= 4;
        z += s;
        n++;

        if(n >= 16) buf[n-16] = z;
    }
    for(int32_t i = 1; i < 16; i++) {
        z <<= 4;
        z += 15;
        buf[n-16+i] = z;
    }
    printf("   n: %d\n", n);

    // sort these uint64_t's
    printf("sorting\n");
    std::sort(buf, buf+n);

    for(int32_t k = 1; k <= 16; k++) {
        // count unique entries
        int32_t shift = 64-4*k;
        int32_t cnt = 1;
        int64_t e = buf[0] >> shift;
        for(int32_t i = 1; i < n; i++) {
            int64_t v = buf[i] >> shift;
            if((v & 15) == 15) continue; // ignore EOF entries
            if(v != e) {
                cnt++;
                e = v;
            }
        }

        printf("%d\n", cnt);
    }
}

Compile with g++ -O3 kmer.cc -o kmer and run with ./kmer chr2.fa.

Please obey the output format; do not k.

This is a cool solution otherwise.

@FUZxxl: fixed.

How long do you think it takes to find the longest length of any repeated substring? I was thinking you automatically know all the answers for any k longer than that.

@Lembik: Longest repeated substring can be done in linear time.  But I don't think it is very helpful - there are really long repeated substrings in the sample input, thousands of symbols at least.

@Lembik My “improved” approach was to sort an array of suffixes of the input file lexicographically. Then for all k the equal k-mers are adjacent. The problem is that sorting like that takes quite a while, around 8 minutes on my machine. I was too lazy to devise a better sorting scheme. The advantage is, that after you have created that sorted array, you can generate the answer for each k rather quickly. If you want, you can even generate the answer for all k at once.

@FUZxxl You can compute the suffix array in linear time so this could be promising. Whether you can actually get it under 1 minute is an interesting question. Some papers online seem to say you can usefully use multi cores to speed up suffix array construction too.

@Lembik Indeed. It's just takes me a while to implement. Let me try…

@Lembik The algorithm I tried (SA-IS, dubbed the fastest one for this purpose) still takes about two minutes to suffix-sort the entire array. I don't think it can be parallelized.

@FUZxxl That's interesting. I found http://algo2.iti.kit.edu/sanders/papers/KulSan06a.pdf and also https://code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks .

@Lembik That's weird. Maybe I made a mistake copying the code?

@FUZxxl Which of the existing suffix array implementations have you managed to try? I couldn't get some of them to run at all.

@Lembik I actually only tried SA-IS and it took over two minutes, which is so much more than one minute that it didn't seem worth trying the others.

Let us continue this discussion in chat.

After discussing it with FUZxxl, it seems you can make the suffix array of chr2.fa in under 30 seconds using only 1.1GB of RAM.

C++ - an improvement over FUZxxl solution
I deserve absolutely no credit for the computation method itself, and if no better approach shows up in the mean time, the bounty should go to FUZxxl by right.
#define _CRT_SECURE_NO_WARNINGS // a Microsoft thing about strcpy security issues
#include <vector>

#include <string>
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;

#include "divsufsort.h"

// graceful exit of sorts
void panic(const char * msg)
{
    cerr << msg;
    exit(0);
}

// approximative timing of various steps
struct tTimer {
    time_t begin;
    tTimer() { begin = time(NULL); }
    void print(const char * msg)
    {
        time_t now = time(NULL);
        cerr << msg << " in " << now - begin << "s\n";
        begin = now;
    }
};

// load input pattern
unsigned char * read_sequence (const char * filename, int& len)
{
    ifstream file(filename);
    if (!file) panic("could not open file");

    string str;
    std::string line;
    while (getline(file, line)) str += line;
    unsigned char * res = new unsigned char[str.length() + 1];
    len = str.length()+1;
    strcpy((char *)res, str.c_str());
    return res;
}

#ifdef FUZXXL_METHOD
/*
* Compute for all k the number of k-mers. kmers will contain at index i the
* number of (i + 1) mers. The count is computed as an array of differences,
* where kmers[i] == kmersum[i] - kmersum[i-1] + 1 and then summed up by the
* caller. This algorithm is a little bit unclear, but when you write subsequent
* suffixes of an array on a piece of paper, it's easy to see how and why it
* works.
*/
static void count(const unsigned char *buf, const int *sa, int *kmers, int n)
{
    int i, cl, cp;

    /* the first item needs special treatment */
    /*
        kuroi neko: since SA now includes the null string, kmers[0] is indeed 0 instead of 1
    */
//  kmers[0]++;

    for (i = 1; i < n; i++) {
        /* The longest common prefix of the two suffixes */
        cl = n - (sa[i - 1] > sa[i] ? sa[i - 1] : sa[i]);
#ifdef ICAP
        cl = (cl > ICAP ? ICAP : cl);
#endif
        for (cp = 0; cp < cl; cp++)
        if (buf[sa[i - 1] + cp] != buf[sa[i] + cp])
            break;

        /* add new prefixes to the table */
        kmers[cp]++;
    }
}

#else // Kasai et al. method

// compute kmer cumulative count using Kasai et al. LCP construction algorithm
void compute_kmer_cumulative_sums(const unsigned char * t, const int * sa, int * kmer, int len)
{
    // build inverse suffix array
    int * isa = new int[len];
    for (int i = 0; i != len; i++) isa[sa[i]] = i;

    // enumerate common prefix lengths
    memset(kmer, 0, len*sizeof(*kmer));
    int lcp = 0;
    int limit = len - 1;
    for (int i = 0; i != limit; i++)
    {
        int k = isa[i];
        int j = sa[k - 1];
        while (t[i + lcp] == t[j + lcp]) lcp++;

        // lcp now holds the kth longest commpn prefix length, which is just what we need to compute our kmer counts
        kmer[lcp]++;
        if (lcp > 0) lcp--;
    }
    delete[] isa;
}

#endif // FUZXXL_METHOD

int main (int argc, char * argv[])
{
    if (argc != 2) panic ("missing data file name");

    tTimer timer;
    int blen;
    unsigned char * sequence;
    sequence = read_sequence(argv[1], blen);
    timer.print("input read");

    vector<int>sa;
    sa.assign(blen, 0);
    if (divsufsort(sequence, &sa[0], blen) != 0) panic("divsufsort failed");
    timer.print("suffix table constructed");

    vector<int>kmers;
    kmers.assign(blen,0);

#ifdef FUZXXL_METHOD
    count(sequence, &sa[0], &kmers[0], blen);
    timer.print("FUZxxl count done");
#else
    compute_kmer_cumulative_sums(sequence, &sa[0], &kmers[0], blen);
    timer.print("Kasai  count done");
#endif

    /* sum up kmers differences */
    for (int i = 1; i < blen; i++) kmers[i] += kmers[i - 1] - 1;
    timer.print("sum done");

    /* human output */

    if (blen>10) blen = 10; // output limited to the first few values to avoid cluttering display or saturating disks

    for (int i = 0; i != blen; i++) printf("%d ", kmers[i]);
    return 0;
}

I simply used Kasai et al. algorithm to compute LCPs in O(n).
The rest is a mere adaptation of FUZxxl code, using more concise C++ features here and there.
I left original computation code to allow comparisons.
Since the slowest processes are SA construction and LCP count, I removed most of the other optimizations to avoid cluttering the code for neglectible gain.
I extended SA table to include the zero-length prefix. That makes LCP computation easier.
I did not provide a length limitation option, the slowest process being now SA computation that cannot be downsized (or at least I don't see how it could be).
I also removed binary output option and limited display to the first 10 values.
I assume this code is just a proof of concept, so no need to clutter displays or saturate disks.
Building the executable
I had to compile the whole project (including the lite version of divsufsort) for x64 to overcome Win32 2Gb allocation limit.
divsufsort code throws a bunch of warnings due to heavy use of ints instead of size_ts, but that will not be an issue for inputs under 2Gb (which would require 26Gb of RAM anyway :D).
Linux build
compile main.cpp and divsufsort.c using the commands:
g++ -c -O3 -fomit-frame-pointer divsufsort.c
g++ -O3 main.cpp -o kmers divsufsort.o

I assume the regular divsufsort library should work fine on native Linux, as long as you can allocate a bit more than 3Gb.
Performances
The Kasai algorithm requires the inverse SA table, which eats up 4 more bytes per character for a total of 13 (instead of 9 with FUZxxl method).
Memory consumption for reference input is thus above 3Gb.
On the other hand, computation time is dramatically improved, and the whole algorithm is now in O(n):
input read in 5s
suffix table constructed in 37s
FUZxxl count done in 389s
Kasai  count done in 27s
14 92 520 2923 15714 71330 265861 890895 2482912 5509765 (etc.)

Further improvements
SA construction is now the slowest process.
Some bits of the divsufsort algorithm are meant to be parallelized with whatever builtin feature of a compiler unknown to me, but if necessary the code should be easy to adapt to more classic multithreading (à la C++11, for instance).
The lib has also a truckload of parameters, including various bucket sizes and the number of distinct symbols in the input string. I only had a cursory look at them, but I suspect compressing the alphabet might be worth a try if your strings are endless ACTG permutations (and you're desperate for performances).
There exist some parallelizable methods for computing LCP from SA too, but since the code should run under one minute on a processor slightly more powerful than my puny i3-2100@3.1GHz and the whole algorithm is in O(n), I doubt this would be worth the effort.

+1 for giving credit where credit is due ;) (and nice speed-up!)

This is neat. Nice improvement.

I didn't even know about LCP arrays. The Kasai et al. algorithm is really neat, too. It's a bit said that it takes so much memory.

@FUZxxl ah well, it's always the same old speed/memory tradeoff, but I think a 45% mem. cost increase is an acceptable price for reaching an O(n) complexity.

@kuroineko True. Notice that my O(n²) approach can save even more memory: It's possible to write out the index array into a temporary file and then read it in chunks as you don't need random access, cutting down the memory usage.

@FUZxxl Indeed. Using disk as a buffer would make it rather slow, but I wonder if the O(n) algorithm would still win with disk swap on random memory blocks. Anyway, people in genetics labs are surely rich enough to afford SSDs :). Seriously, I know there is another algorithm that produces LCP in a different order, but since order does not matter in our case it might be worth a try.

Would it work to compute BWT instead of the suffix array and then the LCP array instead? The BWT uses less space than the suffix array.

Indeed. Now we only need to find a fast BWT algorithm and implement the BWT->LCP transform :)

I may be compiling it wrong but I get https://bpaste.net/show/77b03516372a in linux.

What is your exact command line when you compiled with  g++4.7 ? (I am not a C++ person so I may also be missing options that are obvious to an expert.) My g++ is version 4.8.2 .

Doesn't libdivsufsort also compute the BWT? http://encode.ru/threads/1879-SACA-K-vs-divsufsort-for-computing-BWT also seems relevant (seems to be called divbwt there).

OK, Linux build fixed. About BWT, we can indeed use libsufsort to compute it, but I could not find a comprehensive enough description of an algorithm to build LCP from BWT, and frankly I don't feel like ploughing through raw research papers to try and implement one.

@kuroineko I have an idea how to construct the data we need in linear time without using an LCP array. Let me check…

C (can solve for up to 10 in a minute on my machine)
This is a very simple solution. It constructs a tree of the k-mers found and counts them. To conserve memory, characters are first converted into integers from 0 to n - 1 where n is the number of different characters in the input, so we don't need to provide space for characters that never appear. Additionally, less memory is allocated for the leaves than for other nodes as to conserve further memory. This solution uses about 200 MiB of RAM during its runtime on my machine. I'm still improving it, so perhaps in the iteration it might be even faster!
To compile, save the code below in a file named kmers.c and then execute on a POSIX-like operating system:
cc -O -o kmers kmers.c

You might want to substitute -O3 for -O if your compiler supports that. To run, first unpack chr2.fa.gz into chr2.fa and then run:
./kmers <chr2.fa

This produces the output step by step. You might want to limit both time and space. Use something like
( ulimit -t 60 -v 2000000 ; ./kmers <chrs.fa )

to reduce resources as needed.
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
 * A tree for the k-mers. It contains k layers where each layer is an
 * array of struct tr. The last layer contains a 1 for every kmer found,
 * the others pointers to the next layer or NULL.
 */
struct tr {
    struct tr *n;
};

/* a struct tr to point to */
static struct tr token;

static void     *mem(size_t s);
static int       add(struct tr*, unsigned char*, int, size_t);
static unsigned char    *input(size_t*);
extern int       main(void);

/*
 * Allocate memory, fail if we can't.
 */
static void*
mem(s)
    size_t s;
{
    void *p;

    p = calloc(s, 1);
    if (p != NULL)
        return p;

    perror("Cannot malloc");
    abort();
}

/*
 * add s to b, return 1 if added, 0 if present before. Assume that n - 1 layers
 * of struct tr already exist and only add an n-th layer if needed. In the n-th
 * layer, a NULL pointer denotes non-existance, while a pointer to token denotes
 * existance.
 */
static int
add(b, s, n, is)
    struct tr *b;
    unsigned char *s;
    size_t is;
{
    struct tr **nb;
    int added;
    int i;

    for (i = 0; i < n - 2; i++) {
        b = b[s[i]].n;
    }

    nb = &b[s[n - 2]].n;

    if (*nb == NULL || *nb == &token)
        *nb = mem(is * sizeof *b);

    added = (*nb)[s[n - 1]].n == NULL;
    (*nb)[s[n - 1]].n = &token;

    return (added);
}

/*
 * load input from stdin and remove newlines. Save length in flen.
 */
static unsigned char*
input(flen)
    size_t *flen;
{
    size_t n, len, pos, i, j;
    unsigned char *buf;

    if (fseek(stdin, 0L, SEEK_END) != 0) {
        perror("Cannot seek stdin");
        abort();
    }

    len = ftello(stdin);
    if (len == -1) {
        perror("Cannot tell stdin");
        abort();
    }

    rewind(stdin);

    /* no need to zero out, so no mem() */
    buf = malloc(len);
    if (buf == NULL) {
        perror("Cannot malloc");
        abort();
    }

    pos = 0;

    while ((n = fread(buf + pos, 1, len - pos, stdin)) != 0)
        pos += n;

    if (ferror(stdin)) {
        perror("Cannot read from stdin");
        abort();
    }

    /* remove newlines */
    for (i = j = 0; i < len; i++)
        if (buf[i] != '\n')
            buf[j++] = buf[i];

    *flen = j;
    return buf;
}

extern int
main()
{
    struct tr *b;
    size_t flen, c, i, k, is;
    unsigned char *buf, itab[1 << CHAR_BIT];

    buf = input(&flen);

    memset(itab, 0, sizeof itab);

    /* process 1-mers */
    for (i = 0; i < flen; i++)
        itab[buf[i]] = 1;

    is = 0;
    for (i = 0; i < sizeof itab / sizeof *itab; i++)
        if (itab[i] != 0)
            itab[i] = is++;

    printf("%zd\n", is);

    /* translate characters into indices */
    for (i = 0; i < flen; i++)
        buf[i] = itab[buf[i]];

    b = mem(is * sizeof *b);

    /* process remaining k-mers */
    for (k = 2; k < flen; k++) {
        c = 0;

        for (i = 0; i < flen - k + 1; i++)
            c += add(b, buf + i, k, is);

        printf("%zd\n", c);
    }

    return 0;
}

Improvements

8 → 9: Read the entire file in the beginning, pre-process it once and keep it in-core. This greatly improves throughput.
Use less memory, write correct output.
Fix output format again.
Fix off-by-one.
9 → 10: Don't throw away what you already did.

The output should really be one number per line. It seems currently to output strings from the input file.

@Lembik Ah, I see! It seems like I misunderstood the output format. Give me a minute to fix it.

@Lembik Output format fixed again. If you like, I can add code that kills the program after one minute.

Thanks. You are currently the winner :) timeout 60s works OK for me so no need to build in a way to kill the code after 1 minute.

You could also use ulimit -t 60.

source: Stack Exchange

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

sort: votes


text:
Fill In the Blanks
Input
A nonnegative integer n, and a nonempty string s containing only alphanumeric characters and underscores _.
The first character of s is not _.
The underscores of s are interpreted as blank spaces that can be filled with other characters.
We define an infinite sequence of "infinite strings" as follows.
The string s1 = s s s... is just s repeated infinitely many times.
For all k > 1, the string sk+1 is obtained from sk by filling its blank spaces with the characters of s1, so that the first _ of sk is replaced with s1[0], the second with s1[1], and so on.
Since the first letter of s is not _, every blank space gets filled eventually, and we denote by s∞ the infinite string where every _ has been replaced by its eventual value.
Output
The first n characters of s∞ as a string.
Example
Consider the inputs n = 30 and s = ab_c_.
We have
s1 = ab_c_ab_c_ab_c_ab_c_ab_c_ab_c_ab_c_...
Substituting s1 to the blanks of s1, we have
s2 = abacbab_ccab_caabbc_abcc_abacbab_cc...
We again substitute s1 to the blanks, which results in
s3 = abacbabaccabbcaabbc_abcccabacbab_cc...
One more substitution:
s4 = abacbabaccabbcaabbcaabcccabacbabbcc...
From this we can already deduce the first 30 characters of s∞, which are
abacbabaccabbcaabbcaabcccabacb

This is the correct output.
Rules
You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Crashing on incorrect input is acceptable.
Test Cases
0  "ab__"    -> ""
1  "ab__"    -> "a"
3  "ab__"    -> "aba"
20 "ab"      -> "abababababababababab"
20 "ab__"    -> "abababababababababab"
20 "ab_"     -> "abaabbabaabaabbabbab"
30 "ab_c_"   -> "abacbabaccabbcaabbcaabcccabacb"
50 "ab_a_cc" -> "abaabccabaaaccabbacccabcaaccabbaaccabaaaccabcaccca"
50 "abc____" -> "abcabcaabcbcaaabcbcbcabcaaababccbcbabccabcabcaaaba"

Can we take input in the opposite order (in languages where the order matters)?

@MartinBüttner Sure, I'll allow that.

Pyth, 17
<ussC,cG\_GUQ*zQQ

Input should be given with the string on the first line, and the length on the second, on STDIN. For example:
abc____
50

Try it here.
Explanation:
                             Implicit:
                             z = input()              z is the string.
                             Q = eval(input())        Q is the length.

<               Q            First Q characters of
 u         UQ*zQ             Reduce, with an initial value of z repeated Q times,
                             on the list range(len(Q)).
                             Since the reduce function doesn't use the sequence variable H
                             this function amounts to applying the inner code Q times to
                             the initial value, where the working variable is G.
  ss                         Sum from list of tuples of strings, to tuple of strings,
                             to string.
    C,                       Zip together
      cG\_                   G split on underscores
          G                  with G.
                             This inserts a character of G between every underscore
                             separated group of G, which amounts to replacing the
                             underscores with characters of G, after summation.

CJam, 26 24 20 bytes
4 bytes saved thanks to Peter.
l~:I*{_'_/[\]zsI<}I*

Test it here. Takes the string first and n second on STDIN.
You can run all test cases by pasting them into the input as they are (include the -> output if you want), and using the following test harness (which reverses the order for the code):
qN/{"->"/0=S/W%S*

~:I*{_'_/[\]zsI<}I*

]oNo}/

Explanation
l~:I*{_'_/[\]zsI<}I*
l~                       "Read the input and evaluate.";
  :I                     "Store n in I for future use.";
    *                    "Repeat s n times to ensure it's long enough for the output.";
     {           }I*     "Repeat this block n times. This will always be enough passes.";
      _                  "Duplicate the string.";
       '_/               "Split the string on underscores.";
          [\]            "Swap with the other copy, putting both in an array.";
             z           "Zip the two arrays together, interleaving substrings from the split
                          copy with characters from the unsplit copy. Extraneous
                          characters from the unsplit copy just go at the end and
                          can be ignored.";
              s          "Convert the result into a string, flattening the array in the
                          process. This basically joins the two interleaved strings together.";
               I<        "Truncate to n characters.";

The result is printed automatically at the end of the program.
A note on [\]: In principle, [ remembers the current size of the stack and ] collects everything down to the last remembered size in an array. However, if the array size falls below the remembered size in between, then the start of the array gets adjusted accordingly. Now you might think that swapping the top two array elements doesn't affect the array size at all, but \ actually pops two value and then pushes them in reverse order. This is what pushes the start of the array down by two. Therefore, [\] is the shortest way to wrap the top two stack elements in an array. Sometimes, the side effect of collecting them in reverse order is quite annoying, but in this case, it's exactly what I need.

I think you could replace _'_#) g with I*. Works for me in GolfScript.

@PeterTaylor oh, very good idea, thanks!

APL 29 28
{a⊣(b/a)←a↑⍨+/b←'_'=a←⍺⍴⍵}⍣≡

it's used like this:
fun←{a⊣(b/a)←a↑⍨+/b←'_'=a←⍺⍴⍵}⍣≡
20 fun 'ab_c_'
abacbabaccabbcaabbca

Explanation:
a←⍺⍴⍵           makes vector long as left argument using repeated chars in right argument
a↑⍨+/b←'_'=a   takes a string from the beginning of string a (a↑⍨), long as the number of _'s in a (+/b←'_'=a)
(b/a)←          puts those chars in place of the _'s in the original vector
a⊣             and returns a
{}⍣≡            repeats function ( {} ) until results doesn't change anymore

Tryapl.org

⍣≡ is a nifty idea. Maybe I should try to port this to J...

Python 3, 110 bytes
n=int(input())
*b,=input()*n
a=b[:n]
while"_"in a:b,a=b[:],[x*(x!="_")or b.pop(0)for x in a]
print("".join(a))

Needs a fair bit more golfing, but here is some sheer insanity. Reads in n then s from STDIN.
The fun part is, in the loop's assignment we copy b, then start popping from b during a list comprehension. If the assignment was the other way around, it wouldn't work!

k, 30
{{@[x;i;:;(#i:&"_"=x)#x]}/x#y}

Java - 162 174
It's not every day I get to use a do/while loop when golfing in Java :D
This just iterates and fills in blanks as they come. It just keeps going until there are no more _ in the result.
char[]a(int n,char[]s){char[]o=new char[n];if(n>0)do for(int i=0,j=0;i<n;i++)if(o[i]==95|o[i]<1)o[i]=s[j++%s.length];while(new String(o).contains("_"));return o;}

With line breaks:
char[]a(int n,char[]s){
    char[]o=new char[n];
    if(n>0)
        do
            for(int i=0,j=0;i<n;i++)
                if(o[i]==95|o[i]<1)
                    o[i]=s[j++%s.length];
        while(new String(o).contains("_"));
    return o;
}

I wasn't going to answer this, but the other Java answer was too long to let stand ;)

Java 8, 238
(n,s)->{int i=0,j=0;for(s=String.join("",java.util.Collections.nCopies(n,new String(s))).toCharArray();j<1;){for(i=0;i<n;i++){for(;s[++j]!=95&j<n;);if(j<n)s[j]=s[i];}for(j=1,i=0;i<n;)j=s[++i]==95?0:1;}return java.util.Arrays.copyOf(s,n);}

Less golfed:
(Integer n, char[] s) -> {
    int i = 0, j = 0;
    for (s = String.join("", java.util.Collections.nCopies(n, new String(s))).toCharArray(); j < 1;) {
        for (i = 0; i < n; i++) {
            for (; s[j] != 95 & j < n; j++);
            if (j < n) {
                s[j] = s[i];
            }
        }
        for (j = 1, i = 0; i < n;) {
            j = s[++i] == 95 ? 0 : 1;
        }
    }
    return java.util.Arrays.copyOf(s, n);
}

Haskell (93) 67
I haven't written any Haskell in a while, so this can probably be shortened by a lot. but it was so good, we had to shorten it and make it better!
('_':b)&(d:e)=d:b&e;(a:b)&c=a:b&c
f n s=take n$q where q=cycle s&q

Usage:
*Main> f 50 "ab_a_cc"
"abaabccabaaaccabbacccabcaaccabbaaccabaaaccabcaccca"

Ruby, 60
->n,s{eval"r=%1$p.chars;s.gsub!(?_){r.next};"*n%s*=n;s[0,n]}

Concatenates s to itself n times, then generates n copies of code that replaces underscores with s, evaluates those copies, and returns the first n characters of the result. Since at least one underscore is removed in each loop, this is guaranteed to give us n underscore-free characters.

What is the right syntax to run this? When I call it f and run puts f[10,"ab_"], I get the following error: in 'eval': undefined method 'next' for #<Array:.... It does seem to work when there are no underscores in the string, though.

Oh, interesting, it looks like the behavior of String#chars changed between Ruby 1.9.3 and Ruby 2.0; in Ruby 1 it returns an enumerator when there's no block, in Ruby 2 an array. It can be made version-insensitive by changing chars to each_char, at the cost of 4 more net bytes of code.

Python 2, 75
n,s=input()
S='';c=0
for x in s*n:b=x=='_';S+=S[c:c+b]or x;c+=b
print S[:n]

This expects input like (30,"ab_c_").
In Python, strings don't allow assignment. So, replacing the blanks with the desired character is hard. One can get around this by converting to a list and back, but I found it shorter to just generate the output string from scratch, adding on the desired characters one at a time.
The output being constructed is S, which starts empty. We loop through the characters of the input s copied many times to simulate a circle. We check if it's a blank via the Boolean b. We check equality x=='_' rather than comparison because the underscore lies between capital and lowercase letters.
If the character is not a blank, we just add it onto S. If it is blank, we add the next unused letter of the output-so-far S. We track used letters by an index pointer c that starts at 0 and is incremented each time we encounter a blank.
At the end, we print the first n characters of the resulting string S.
We have to use S[c:c+b] in place of the shorter b*S[c] because the latter gives an out-of-bounds error when S starts empty and c is 0. It never matters because we're guaranteed the first character of s is non-blank, so this S[c] is never needed, but the code doesn't know it. Flipping the or to short-circuit could also solve this, but costs more characters.

Python 2, 83
A Pyth-to-Python port of isaacg's solution, which uses split and zip to perform the replacement:
n,s=input()
s*=n
exec"s=''.join(a+b for a,b in zip(s.split('_'),s));"*n
print s[:n]

It turned out longer because, suprise, named methods are long in python. But it can perhaps be improved by riffling s and s.split('_') together in a shorter way.

Nice! Didn't expect reconstructing the string to be so much shorter!

Batch - 425
Do I lose?
@echo off&setLocal enableDelayedExpansion&set s=%2
if "%3"=="" (for /l %%a in (1,1,%1)do set o=!o!%s%)else set o=%3
set o=!o:~0,%1!&set l=0
:c
if defined s set/al+=1&set "s=%s:~1%"&goto c
set s=%2&set/ap=%1-1
set y=&set c=0&for /l %%a in (0,1,%p%)do set x=!o:~%%a,1!&if !x!==_ (for %%b in (!c!)do set y=!y!!s:~%%b,1!&set/ac+=1)else (set y=!y!!x!)&if !c!==%l% set c=0
if "!y:_=!"=="!y!" echo !y!&goto :EOF
%0 %1 %2 !y!

Batch has limitations - I accept this. For example; I had to use a for loop to get a single variable in a usable format due to limitations of variable parsing syntax. for %%b in (!c!)do...  just exists so I can use %%b instead of !c! so I can actually do the string manipulation !s:~%%b,1! and have the variables expand at the correct time.
There are a couple of pretty basic things I could do to golf this further, but probably not below 400 bytes. I'll have another crack soon.

Unless someone else posts a better Batch answer, I wouldn't call this losing :)

@Sp3000 If only someone would.

ECMAScript 6, 78
f=(s,n,i=0)=>[...s.repeat(n)].reduce((s,x)=>s+(x=='_'?s[i++]:x),'').slice(0,n)

Starts off with an empty string and for every occurrence of underscore, replaces it with the character at the next index of the current string.

Python 2 - 99 97 bytes

Because 4 python-based submissions aren't enough...
n,s=input();S=s=s*n
while"_"in S:x=iter(s);S="".join(j>"_"and j or next(x)for j in S)
print S[:n]

Example:
$ python2 t.py
(50, "ab_a_cc")
abaabccabaaaccabbacccabcaaccabbaaccabaaaccabcaccca

ECMAScript 6, 93 91
(n,s)=>{for(x="_".repeat(n);n=0,/_/.test(x);)x=x.replace(/_/g,a=>s[n++%s.length]);return x}

Shaved off 2 characters from the first version.
(n,s)=>{x="_".repeat(n);while(/_/.test(x)){n=0,x=x.replace(/_/g,a=>s[n++%s.length])}return x}

C# - 162
I stole Geobits solution and changed it to C#
char[]p(int n,string s){var r=new char[n];if(n>0)do for(int i=0,j=0;i<n;i++)if(r[i]=='_'||r[i]<1)r[i]=s[j++%s.Length];while(r.ToList().IndexOf('_')>=0);return r;}

1 char better, so you can improve Geobits ;)

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


text:
Implement Enigma Cipher
Your task is to implement an Enigma encryption machine. Your program will accept the machine initialization information followed by a string of text to be encrypted.
Initialization vector will be

Rotors used (Left to right). Will be three characters. Rotors 1-5 are valid.
Initial rotor settings (A-Z) Left to right.
Ring Setting, Left to Right.
Number of plugs (0-13)
N pairs for the plugboard.

After the initialization vector, encrypt all text until a newline (0xA) character is encountered. Any text not in the A-Z range (including lower case for simplicity) should be output as is.
You can compare output against
this simulator. The initialization vecotr for the default state is 123MCKAAA0
If you click 'set from passkey' and enter 'codegolf', your equivalent initialization vector is 245FZPPAM10FTJQAOHGMYCKWRIXVPES With this setting, baaaaaaaaaaa... should translate to
OXVXI NSRPS RGUXY XZVGB QUNJH TWTVD JNPSI TBWKJ XCVNR IUUVK LJWXV OMCGL VQOKD TVJVW HCFZF DBDQS FYECN SDTPC GESYN OWGNZ WWSYQ WJJBT GVMQM GUUVC XZNCV EPGLM MCNHY KLRJC LISZZ PTYIZ GIEUP OPZUI DPZZZ ULXFZ ONGRI WETGU CICMT KKQBW ZJMNL BZSLJ TLMGR RMZDZ BCNGM RYRGJ MKXRF JKQGG PYZFD UUZRE EIKPD OFUPE XODND DFXKY OHXHX ODWDC SXFPV. This should fully test a double stepping scenario.
You may assume the Initialization vector will be valid. Rotors will be in required range, no letter will be used in multiple plugs, etc. Only Reflector B will be used.
All needed info (rotor wirings etc...) must be included in your program, not fetched from an outside source. Most details you need are on wikipedia.
Shortest code wins.

This question is missing a specification of the procedure for encrypting the text.

The encryption details are specified in the Wikipedia links specified, as well as elsewhere on the web. What details would you like put here?

@CMP All details necessary to compete in the challenge. Challenge should be self-contained.

@MartinBüttner, that doesn't always seem practical. should http://codegolf.stackexchange.com/questions/4732/emulate-an-intel-8086-cpu have included the entire 8086 spec?

@MartinBüttner Normally, you'd be correct, but in this case, it would be impractical.

@CMP If it's too much spec to include in the challenge, then you should consider if it's too much to be implemented for an interesting code golf challenge.

(To be clear, I don't think Enigma encryption is too much for an interesting code golf, but I also think the relevant information can be condensed sufficiently to fit nicely into the challenge spec, and you'd still have a much shorter specification than some other challenges. Just saying, if it doesn't fit in the challenge body, it's probably too elaborate to begin with.)

x87 spec > enigma spec.  Also at a quick glance, the x86 specs are much more technically concise than the enigma wikipedia page, so should require less interpretation.  Also the x86 challenge is [tag:code-challenge] which tends to have less strict requirements than [tag:code-golf]. Having said that, I don't think these are necessarily hard-and-fast rules; generally community consensus is the best guide to what is required in the face of ambiguity.

I will work on adding some details.

oops - s/x87 spec/x86 spec/

More than an exact spec, I'd like to see a well-written reference implementation.

Alright, I'll come back with a better writeup.