Better, Simpler Programming Contest

[atul]

Originally posted by Saber Cherry:
You have 3 resource types (gold, resources, and holy, abbreviated gcost, rcost, and hcost), and some number (n) of units. We will assume all the units are of value corresponding to their cost.

The goal: Make a production queue that minimizes wasted resources!

This assumes all the different kinds of resources have same value when wasted, and no bonus/penalty is put due different troop composition, just by wasted resources? Sorry, too much school work regarding problems like this, it just bugs to see all the variables having same weight of '1'. That is, if I understood the above correctly.

Haven't followed much these programming contest threads, what are the limits as to programming? Has to be stand-alone application? Specific language? For you know, I think M$ Excel has built-in function to do specifically this kind of optimization (I know, wouldn't apply such to the contest).

Not sure, I have feeling there was some systematic and elegant way of doing this with matrix operations or such of some sort. Should look some old school hand-outs to see for sure.

[Saber Cherry]

And Lastly:

Unless anyone can think of an objection, teams and devs will be allowed (encouraged) to participate. Any team would have to have a captain through whom all communication and file transfers would be handled.

[PhilD]

Originally posted by Saber Cherry:
Note that this problem seems trivial, but is actually NP, meaning it does not have a known good solution.

Let's nitpick a little: just saying the problem is NP does not mean no good solution is known. Every P problem is also NP. What you're thinking of, most likely, is NP-complete.

And yes, I do teach CS, rather on the theoretical side

[Saber Cherry]

Originally posted by atul:
This assumes all the different kinds of resources have same value when wasted, and no bonus/penalty is put due different troop composition, just by wasted resources? Sorry, too much school work regarding problems like this, it just bugs to see all the variables having same weight of '1'. That is, if I understood the above correctly.

Sorry, I was not very clear...

me:
The program will be graded according to how many resources are used (% of total for each type) and how fast it runs.

I meant to say that the ideal would be to minimize the wasted percentage of each resource. So if you had holy=4 and gold=100, wasting 1 point of holy would be a 25% waste, and wasting one gold would only be a 1% waste. It would be possible to specify a problem in which the three resources had arbitrary values... but in the interest of keeping things simple, it seems that giving each resource a value of (100/total) would be OK. What do you think? Would you prefer arbitrary values?

Haven't followed much these programming contest threads, what are the limits as to programming? Has to be stand-alone application? Specific language? For you know, I think M$ Excel has built-in function to do specifically this kind of optimization (I know, wouldn't apply such to the contest).

Not sure, I have feeling there was some systematic and elegant way of doing this with matrix operations or such of some sort. Should look some old school hand-outs to see for sure.

There is no easy way to solve this problem quickly. The limits are this:

1) You can use any language, but you must provide the source code for your solution, without any precompiled black boxes. Thus, a prebuilt Excel function would not work.
2) Scripting Languages and spreadsheets are fine if you put in the algorithms yourself.
3) Library functions are fine for simple things like sorting, storing data, hashing, reading files, comparing strings, and such. All code for solving the actual problem should be your own: in other words, don't cheat by finding some linear-combination optimizer. This is pretty subjective; it's a contest for fun, not for any cash prize=)

[ March 02, 2004, 20:43: Message edited by: Saber Cherry ]

[Norfleet]

Well, ideally, it's to your benefit to prioritize maximization of resources and holy. Unused GOLD is not "wasted", as gold accumulates in your treasury, and has non-troop-building uses.

[Saber Cherry]

Originally posted by Norfleet:
Well, ideally, it's to your benefit to prioritize maximization of resources and holy. Unused GOLD is not "wasted", as gold accumulates in your treasury, and has non-troop-building uses.

I disagree. I try to end my turns having used all my gold. Carrying gold over does not earn interest, and unless you are saving for something, going many turns in a row without spending all your gold will generally put you at a competitive disadvantage. If all units were 0 resources and 0 holy, an ideal solution would spend all the gold, so you could have troops - not save all the gold and build nothing.

[atul]

Originally posted by Saber Cherry:
Sorry, I was not very clear...

quote:

---

me:
The program will be graded according to how many resources are used (% of total for each type) and how fast it runs.

---

Oops, sorry, how stupid of me, missing that part in brackets. Must be the late hour... Anyway, that makes sense.

Just occured to me, wouldn't it be reasonable to be able to assign some arbitrary value to different units, as in 'this is better than that'? For I get the feeling that if all units are equal and only gold/res/holy is taken into account the resulting armies would be very much like the current AI likes (loads of LI) if you give normal dom-values as input (higher gold than resources). Like final goal = Max(units' values - resources lost), your original proposition would be where all units have value of zero. Or maybe that would just be unnecessary complication. Things are good to be kept simple.

Originally posted by Saber Cherry:
in other words, don't cheat by finding some linear-combination optimizer.

Don't worry, didn't cross my mind. Anyway much that you wrote was total greek to me, as I'm not too much into computers. Currently being schooled to be one of those who just use programs like this competition's results without caring how it technically works. Ignorance is a bliss.

Just asking questions out of general interest and occasional boredom.