The Dark arts - C&D Master Thread

[Cyneheard]

That should be easy. BTW - refresh my memory ... how do we know how many population points?

Combination of a few things:
1) Soldier tracking
2) Score tracking
3) F8

Pop is the only thing that moves soldiers + score simultaneously, so it should be a (mostly) manageable information problem to separate EOT pop increases from other EOT sources of score.

[Ruff_Hi]

wait - I am an idiot - the pop points is what we are trying to work out. I'll be back with a solution.

[antisocialmunky]

Just make a list of everything that contributes to pop points and its easy to make.

[waterbat]

pop points and soldier points only increase in lock step every other growth, correct?

I didnt realize we'd know the number of cities, but i was programming in a range as paramaters (min, max) to cut down on the silly results (i.e. 82 size 1 cities on a pop score of 82,000)

[Ruff_Hi]

pop points and soldier points only increase in lock step every other growth, correct?

I didnt realize we'd know the number of cities, but i was programming in a range as paramaters (min, max) to cut down on the silly results (i.e. 82 size 1 cities on a pop score of 82,000)

If you have started to code this up ... then I won't . However, may as well share how I would have approached it ...

Step 1 - work out the size of the biggest city
We know the following ...

• POP[city] = int( SIZE[city] ^ 2.8 )
  
• POP[civ] = sum( POP[cities] )
  

... thus, the biggest city must be equal to or smaller than ...
ln(SIZE[biggest city]) = ln(POP[civ]) / 2.8

Step 2 - loop over all possible city sizes

Code:

dim Cities(1 to M) as integer
for c = 1 to M
  Cities(c) = 1
next c
do until Cities(1) > BiggestSize
  calc population size
  if population size = magic number then record current Cities array

  Cities(M) = Cities(M) + 1
  for c = M to 2 step -1
    if Cities(M) > BiggestSize then
      Cities(M-1) = Cities(M-1) + 1
      Cities(M) = 1
  next c
loop

Sure - this does way too much but it'll work. The old brute force and stupidity method at work.

[novice]

Total pop points worldwide can be seen from the victory conditions screen. After currency, total pop points for a civ can be deduced from the steal treasury mission if you have visibility on one of the civ's cities.

The brute forcer should take all known city counts plus all known total pop points and the min,max,average,rank population demographics into account. Try all combinations as outlined by Ruff and output those that match the demographics.

[Ruff_Hi]

but wait, there is more ...

The above method will return '5,4,2,1,1' as well as '5,2,1,1,4' . So ...

• Sort each returned group
  
• Sort resulting list of returned groups
  
• Remove duplicates
  

I have some canned excel vba sort routines that we can use.

[waterbat]

(You know how, in some fiction, knowing the True Name of something gives you power over it, like magical or in the occult? Google is like that. )

So.... after putting in a ton of time to understand all kinds of cool solutions to Knapsack problem, it occurred to me that this wasn't a knapsack problem at all! I then thought it was more like a 1-dimensional bin backing problem. So I started looking there and spent a bunch of time implementing those type of algorithms.

Then *finally* I realized - it is a 'Making Change' problem!

If knowing the True Name of something is cult nirvana, mis-knowing it is a hellish rathole you do not want to venture into

As an example of the making change problem: What are all the ways you can make $1.00 out of coins (pennies, nickles, dimes, quarters, fifty-cent pieces) ?
so you are looking for sums of 100 from components of [50,25,10,5,1]
(i think there are 74 ways)

We are asking the same thing! How many ways (and what are the ways) can you make [TOTAL_CIV_POP] out of components of [1000,6000,21000,48000,90000,etc.]


Here's how I solved it:

(populations in thousands for simplicity)
inputs: POP, MAX_CITIES, MIN_CITIES

build table of possible components [ POP - MIN_CITIES ]
for example, if POP score = 93, but MIN_CITIES = 5, 90 isn't a possibility
order the table decending so it looks like this:

example POP = 124 (124000 in-game pop value)
0 90
1 48
2 21
3 6
4 1

find the max number of each of the components:
0 1
1 2
2 5
3 20
4 124

form a table of iterators that essentially counts the number of coins in each group:
0 a
1 b
2 c
3 d
4 e


iterate through the combinations up to the maximum values
(since the number of components itself is dynamic, I used a recursive function. if the number(d) of components was static, I could just write d for..next loops. )

if the sum of the iters > MAX_CITIES, bail (i.e. a+b+c+d+e)

Sum the values of the components, if sum == POP, we have a winner, unless sum of the iters < MIN_CITIES.











Here's a code snippet:

Code:

int main (void) {

        //setup table of POP to SIZE (index + 1)
    vector<int> scoretable = SetupScoreTable( 1, getMaxCitySize() );

    //display table for debug
    DisplayScoreTable(scoretable);
    pause();

    // Call BruteForce recursive routine

    vector < map <int, int> > solmap = BruteForce(CIV_POP, scoretable);

    DisplayVectMap (solmap);

}

vector<map<int, int> > BruteForce(int s, vector<int> scoretab)
{
    vector<map<int, int> > retVect;

    vector<int> maxes;
    vector<int> it;

    maxes.resize(scoretab.size());
    //iterate through scoretab (reverse scoretab for this function to descending) and create maxes based on s (CIV_POP)

    reverse ( scoretab.begin(), scoretab.end() ) ;  
    for ( vector<int>::size_type i=0; i < scoretab.size(); i++) {
        maxes[i] = s/scoretab[i];
    }
    it.resize(scoretab.size() );

    //inner is the recursive function
    inner(scoretab.size(), it,s, scoretab, maxes, retVect);

    return retVect;    
    
}

void inner (int d, vector<int> it, int s, vector<int> scoretab, vector<int> & maxes, vector<map <int, int> > & retvect) {


    if (d>0) {
        for (int i=0;i <= maxes[d-1]; i++) {
            it[d-1]=i;
            if ( SumVi(it) <= MAX_CITIES ) {
                inner(d-1,it,s,scoretab, maxes, retvect);
            } else {  // Log warning, bail!

            }

        }
    } else {

        int val(0);
        for (int i=0; i < it.size(); i++) {
            val += ( it[i] * scoretab[i] );
        }

        if (val == s)
        {        

            if (SumVi(it) < MIN_CITIES) {
                // log warning
            } else {  // found solution!


                map<int, int> temp;
                for (int i=0; i < it.size(); i++) {
                        temp[i] = it[i];
                }
                retvect.push_back(temp);
            }
        }

    }
}

int SumVi (vector<int> v) {
    int s = 0;
    for ( vector<int>::size_type i=0; i < v.size(); ++i) s += v[i];
    return(s);
}

TO DO LIST:

1) when I bail from max, it doesnt appear to bail completely - i.e. a POP of 95 means there is the possibility of 1 size 5 city and 5 size 1 cities. if MAX_CITIES = 3. As soon as I get to 1 5-city and 3 1-cities, i don't recurse. then my program evaluates the next in the loop - 1 - 5-city and 4 1-cities - its also over the max. instead of moving on, i'd like to bail on that whole tree.

2) Sort of related, but has nothing to do with MAX_CITIES: right now, the evaluation to get the maxes is simple int ( POP / value ). so max number of size 5 cities = 1, max number of size 4 cities = 2....etc.... but if pop=124 and i have a 5 size city in my solution, why am i iterating through those 2 loops (and tons of nested loops under them) testing size 4 cities??? fixing this will save a lot of cycles. Right now, If i have a size 5 city in my solution for 124, i iterate 3*6*21*125 times for the rest of the solutions (47250). instead if I fix the max evaluation, I would iterate a max of 1*2*6*35 = 420. WOW! Because the function is recursive, it would even be less than this! ie. if i have a size-5 and a size-3 city, i wouldnt need to iterate 35 times for size 1-cities - only 13 times.

[waterbat]

@Ruff - i think I had some problems with floats and precision to get the ln( ) stuff working right. I also didn't exacly understand it because of the flooring that happens in civ. I think it was throwing me off. I had the same problems in my program with getting the max city size.

i.e. if floor(pow(5, 2.8)) = 90, then when reversing the function, pow(90, 1/2.8) < 5, because we lost the fractional part. So I dont know how to account for that other than going up a size no matter what or just adding in a small fraction (currently 0.05) arbitrarily. I currently am choosing he latter.

[T-hawk]

Then *finally* I realized - it is a 'Making Change' problem!

Yikes. Sorry about the wild goose chase there. But us computer scientists always like reading about an interesting algorithm even if it's the wrong one.

Nice work. I'm not familiar with C++ vectors or how to translate code using them to Javascript for a web page based solution. But I could figure that out, unless you want to implement Javascript yourself too.

i.e. if floor(pow(5, 2.8)) = 90, then when reversing the function, pow(90, 1/2.8) < 5, because we lost the fractional part. So I dont know how to account for that other than going up a size no matter what or just adding in a small fraction (currently 0.05) arbitrarily. I currently am choosing he latter.

Precalculate and store a lookup table. You only need to go up to maybe size 40.
1 1
2 6
3 21
4 48
5 90

And write an accessor function, so that getSize(90) finds and returns 5. This is easy in a language with native hash tables (like C#), and I'm sure you can do it in C++ or Javascript somehow. At worst, binary-search through the array until you find the requested population value.