[Natsu]

An external library? Some sort of linear algebra, I assume? I believe that a very simple algorithm that solves problems like this was featured on HN something like a week ago.

I hope that's not too much of a hint, but anyone who can figure it out from that was probably a good candidate, anyhow.

I should also mention that I did code a solution in Perl, or at least most of one, though I did not submit it. I have a grandmother to care for and that limits me on relocating, even though I would be interested in finding more interesting work.

Assuming I don't eventually go crazy in a futile attempt to explain to corporate that methods which turn a 9/2272 inch rounding error into a piece of glass that's half an inch too big do not qualify as "validation."

[Estragon]

Not linear algebra, although the optimization problem can be expressed in terms of linear programming, I think.

I wish you well in caring for your grandmother. That stuff is way more important than programming techniques.

[Natsu]

It's weird how full-circle I've gone on this. I went from "the naive solution is easy enough to write" to "I bet there's a more efficient way" to "oh crap, my solution doesn't actually work, because the preferences can have ties."

I did have the fun of coding up the algorithm I saw on HN a while back, though, so it was fun.

[Natsu]

Incidentally, I had more time this weekend and found that it gets a lot easier if I use a more suitable algorithm. Considering it as a S-M problem only makes things more complex, because there can be ties (which kills the nice algorithm for solving these) while introducing more complexity than is necessary, given that there's a single cost to be maximized, rather than two distinct preference lists.

Seems like I should have been doing it as an A problem, where you can just use the H algorithm. So I want to say thanks to the guys who posted the challenge: it was a good excuse to teach myself some combinatorial algorithms.

Lest anyone wonder, I'm using those weird abbreviations so as not to spoil the problem. Figuring out which algorithms to use is half the fun and I read about quite a few different types of problems before figuring out which was the most suitable. I'd hate to deny anyone else the same learning experience.