Re: Programming Contest
The best path would be the one that wasted fewest gems. There would be 2 ways to determine the best solution.
1) The easy way. Scatter sites around, and determine how many gems were wasted before all provinces were searched. The person whose algorithm finds the most sites the quickest would win, even if it takes him the same amount of time to search all the sites as a worse solution. This would be done for several different site-scatterings, and the sites would be scattered according to terrain probability modifiers. Even if it was done many times, luck would still be a factor.
2) The better way. Sum the wasted probability-time... in other words, if you don't search a Plains province for 5 turns, you get penalized 50%*5. There are no real "sites", per se. For example, if there were 3 provinces, a Swamp (30%), a Forest(80%), and a Mountain(100%), where the numbers indicate their site frequency relative to mountains, and you started in the swamp...
Your output could be (substituting terrains for province numbers)
start swamp
search
move mountain
search
move forest
search
end
...which scores like this:
(30*0)+(100*2)+(80*4)=520
or:
start swamp
move mountain
search
move forest
search
move swamp
search
end
...which scores like this:
(30*5)+(100*1)+(80*3)=490
How does the scoring work? It is (swamp magic site richness)*(turns before searching the swamp)+(mountain magic site richness)*(turns before searching the mountain)+(forest magic site richness)*(turns before searching the forest), with the minimum number best.
In this case, since forests and mountains are richer in terms of magic sites, it is actually BETTER to move instead of searching first! You want to minimize the lost probability-time.
The other factors are search status and already-found sites, which affect probability. For simplicity, we'll assume that there are only level 0-3 sites, equally distributed by level and path, so that there are as many level-3 Unholy sites as level-0 Earth sites. Which is not true, but it makes things a lot easier.
I'll wait on the more complicated probabilities until I get more comments, but generally, if a province has already been searched, or already has some magic sites, the probability of finding new sites is reduced. Obviously, a province that has 4 sites, or that has been searched to level-3 (in Dominions, level-4) in all paths, cannot yield any more sites.
[ March 01, 2004, 07:18: Message edited by: Saber Cherry ]
|