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.

That doesn't even make sense. What is an arrangement?

>>2
such that no two nonzero elements of the arrays may share the same position.

>>3
What the fuck does that mean?

>>4
such that there exists a proof in which all said positions are possible, hence said positions therefore hence lambda calcyaless.

>>4
... the universe.

Eureka! New discovery: There exists a word "Suppository".

Such that said word may be used such that, "There exists a Science that is suppository". Now, who would like to try out said word?

>>5
Yes but how does ``121012303'' actually relate to the arrays above?

>>8
1010101
 20002
       303
----------
1210121303
I kind of wish I didn't understand what the OP was talking about.

>>9
Ah, that's a different sequence though. Per's missed a 1 out. I thought it might be something like that but pers example didn't make any sense.

But even with the 1 added it isn't optimal because a smaller arrangement exists, unless there is some extra constraint:
1210121303
210121313

What the fuck is going on in this thread. This is the worst /prog/ challenge in years.

such that no two nonzero elements of the arrays may share the same position

Share the same position as what?

Forget it, it's NiggerPenis-complete.

>>13
The same position in the sequence, duh.

Basically you're finding where to put the arrays so that the 0s in them line up with not more than 1 nonzero element in all of the other arrays like >>9 showed.

>>14
I have a feeling it is, but can't think of how to prove it.

>>15
If the number of sequences is constant, but the length of each sequence is variable, then there is a brute force polynomial time algorithm. If there are k different sequences, with a sum length of n, then there are at most n placements for each sequence, giving at most n^k choices to consider. To score a choice, the length of the combined sequence is calculated and collisions are checked between sequences. The length calculation can be fast, O(k), and the collision check can be implemented in O(nk). So this would be an algorithm that runs in O((nk + k)n^k), which is polynomial if k is bounded by a constant, but not so great if k can grow.

This would have applications to scheduling problems. Like if you have a task that will need attention during certain time intervals that are spaced by known delays. Schedule the starting times of the tasks so that they can all be served by a single processor. And make a scheduling that minimizes the total time.

The decision version of this (is it possible to find an arrangement with not more than length n) is NP-complete via reduction from SAT.

This is really interesting. I'd love to see some solutions start pouring in. I'm working on a brute for C solution but there must be some helpful hints because this baby gets out of hand fast.

Problem does not sound too difficult.
1010101 has 3 'free' positions

with the next 20002 you get
2001210101
21012101
1210121
10121012
1010121002
101010120002

with the 303 you basically get
2001213131
210121313 <-- optimal solution
1210121303
10121012303
1313121002 
131310120002
101313120002
101010123032

Actually, this problem seems quite trivial.

>>20

yfw there are cases which will be optimal that are not found by your strategy of only considered strings formed by starting with 1010101 then adding 20002 then 303. The order you begin to consider matching up different strings will determine what options you have at the end.

You need to consider every overlaying of every combination of strings. 1 string with 2 string, 1 string with 3 string, 2 string with 3 string, for an input with 3 strings. And then the higher-order combinations-of-combinations when you have an input with, say, 16 strings.

>>21
This is all academic discussions. OP should supply the dataset so I can disprove all this sissiness.

>>22

Assume the size of the strings and the number of strings is arbitrary, but here, I'll give another dataset.

100010000010001000101001000001010101
200000020000202000222000002000022002
300303030333303030000300003000000000
000040000004040400044400000404000000
500050500055500000505000000505050500
600000000600000000060000000060000006
707077700000700000000000000000070000

now wat.

still doing a brute-force algo, got distracted by making a sandwich

This is still trivial. Start with a dataset where n > 1000000.
then we will talk business.

u wot m8

>>24

finding a non-brute-force algorithm that finds the OPTIMAL packing is very interesting. obviously it's trivial to do a brute-force for the data set provided in >>23. That's not what this is about. How do you propose to find the OPTIMAL packing without just checking every offset with every combination of strings?

>>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.

>>27

These are good ideas. I will take your ideas to heart as I work on my brute-force.

>>28
the key to getting an efficient optimal algorithm will be to consider a number of choices that is polynomially bounded in terms of the lengths of the sequences and the number of sequences, and to do this in the worst case. It can be done if there are exploitable patterns in the sequences. But with no extra knowledge on the sequences, I'm not sure if it can be done. But maybe.

>>18

I don't see it. I see that decision problem exanding into a giant boolean formula, but I can't see how to use a solution to that formula to solve an arbitrary SAT.

It's probably best to get an algorithm for sparse sequences, since if you are merging a large amount of sequences, you are pretty much fucked if every sequences is random and dense.

>>30
You are random and dense.

>>31
uguu~~

>>26
Branch-and-bound.

>>29
Reduction from 3SAT might be more direct, and here's a hint: the position of each array within the solution matrix represents the truth value of a variable in the 3SAT instance.

>>33

thanks, I'll be thinking about it