EDIT3: CANCELED due to a degenerate, almost naivly greedy, linear time (O(energy goal + num planets)) algorithm being found. This basically makes this problem no fun at all.
EDIT4: The revised version is NOT coming, due it being shown that the general form of this problem is NP-hard.
Funny, seeing that sicking with the current sets of reactor definitions makes this problem linearly solvable.
Thanks to the recent energy management discussion, I came up with an idea for a programming challenge.
EDIT: Feel free to PM me submissions, but you may want to wait until I get some sample input and output generated first so you can test it.
Also, it will be a while until I can actually test it, as now I need to write the test data and my own "judging" implementation and verifier.
Write an algorithm that given a certain power goal and maximum number of planets to use, will give the best configuration of powered on energy reactors that will minimize per-second resources cost but still at least meets the energy goal. You are free to place as many reactors as you want on as many planets (up to the max) as you want, as long as you minimize per second cost.
Best is defined as the configuration that consumes the lease resources per second. If multiple configurations have the same resources per second cost, then the best is the configuration that costs the least amount to construct all reactors. If multiple configurations are tied in both ways, then the configuration that minimizes number of planets used will be that best. And finally, if all three tie-breakers are tied, then the configuration using the least number of reactors is the best. If all of the above are the same, then the configurations can be considered equal, and if assured to be the best overall, will all be considered "right" optimal answers.
Also, a separate challenge for the above problem but also accepting a list of already constructed energy reactors and working off of those. In this case, you cannot "build" more reactors, you can only return a subset of the reactors given to turn on.
Best is defined the same way, except that instead of measuring cost and number of reactors built, instead it will measure cost and number of reactors turned on in the final configuration.
Just as a note, the naive greedy algorithm (always go for the most efficient reactor first) will not always give the best results (though in most cases, it will give pretty good results). Preferably something less than exponential running time (aka, not take a brute force approach). Keep in mind that LARGE amounts of pruning of the state space can be done due to tell early that some sub-configuration will lead to unoptimal results.
Recognition will go towards those who can give an algorithm with the best worst case asymptotic running time (aka, O(n) time, or in this case O(e, n)). Also, recognition will go to those who have the best average O(n) time given "normal" sets of input that you would expect in a real game. (Some analysis showing why your code runs tends to run better asymptotically in this case would be appreciated)
Special mention will go to those with "clever" or "funny" solutions.
I am avoiding wall-clock time testing due to how difficult it is to compare runtimes fairly across different languages and machines.
Separate recognition for each variation of the challenge. You may submit the same code twice for each challenge, with taking "null" or an empty array or whatever indicating that there is no set of reactors is must work with and thus.
EDIT2: If someone can prove that with the stats used for reactors and the way poor efficiency is handled in the current version of AI war leads to a simple greedy algorithm being optimal, then I will amend the requirements to have the program take an arbitrary set of reactor stat definitions. In fact, I might do that anyways.
This problem is VERY similar to the "change problem". For some sets of denomination/reactor value greedy solutions may work, but in the general case, the greedy solution is not guaranteed to work.
