Array Packing Challenge

You are given n arrays A₁..A_n of n_k elements each, of which each element in A_n is either 0 or n. Your goal is to find an arrangement of the arrays such that no two nonzero elements of the arrays may share the same position, and the total length of the arrangement is minimised. For example, given the input file containing the lines

1010101
20002
303

One possible optimal arrangement is

121012303

Your program must read an input file of the form specified above from standard input and print out the optimal arrangement to standard output.

You have until 2012-07-01 00:00:00 4chan time.

>>26
First thing that comes to mind:

1) For each array determine the burst length for 0's and non 0's
2) Match the array with the longest 0's burst with the array with the longest non 0's burst
3) Create all combinations where these 2 interleave (the above step will optimize the number of combinations to a minimum)
4) Do this with the remaining arrays in the data set
5) All formed pairs will be the next input dataset for a next iteration
6) Iterate until only 1 array remains. During each iteration the number of datasets will increase, but the number of combinations will decrease (due to decreasing number of holes). Intermediate storage will grow, but will stabilize.

There are numerous forms of optimization possible. Especially with the code that matches the holes in substrings. A lot of full-text searches use similar forms of optimizations.

I am assuming a relative random distribution of 0's and non 0's. So yes, you can conjure a dataset that has a worst-case effect on this approach.