Note: I'm thinking this up as I go along, so take
it with an appropriately sized grain of salt.
Once you've got your data in an appropriate arrangement
(for example, the position Ovid gives us:
1 3 4 5
You can perform at most two operations on each bucket:
- Shift the "bottom" element one stack to the left
- Shift the "top" element one stack to the right
In this case, there are only two legal operations:
- Shift element 2 to the second column
- Shift element 5 to the third column
My first idea was another greedy approach: start with the
data in a valid (though almost certainly not optimal) state,
and perform the operation that gives the most benefit. (In
other words, hill climbing.) Since our score is
the longest column we have so far, we're only going to climb
hills (lower our score, which in this case is good) by
operating on the longest column. Unfortunately, this leads
us to local maxima, not global ones. Note: I haven't
proven this, it's just something that tends to be true of
hill climbing algorithms. I'm a bit hopeful about this
because the domain is finite, and you might get decent
results by picking a few random starting points, hill
climbing on each of them for a small number of iterations,
and picking the best one, but on the other hand....
The hell with paco, vote for Erudil!
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||