The Dark arts - C&D Master Thread

[dazedroyalty]

This thread has quickly become "All greek to me!" :P

Good job, though! I'm super impressed.

[SleepingMoogle]

This thread is quickly becoming a smoothy of interesting, awesome and disturbing.

[waterbat]

Precalculate and store a lookup table. You only need to go up to maybe size 40.

This is funny (to me) - initially i was precalculating the whole table up to size 40.
Only after I started using this precalc'd table as part of the solution/algoritm did I go back to trim it to the right size (why i need the reverse function).

So.... i could go back to the large precalc'd table for the reverse function and after that trim it to size for use in the loops. At first I thought 40 would be too small, because I am trying to look up the max number of pop for the whole civilization! But I am guessing in practical terms 40 would be the max of any individual city. In any of these big games has anyone even come close to that? I guess there is some theoretical maximum city with 21 floodplain farms with biology or supermarkets or whatever.

[Cyneheard]

This thread has quickly become "All geek to me!" :P

Good job, though! I'm super impressed.

FTFY

[Cyneheard]

T-Hawk's Sushi game had a capital at size 36. 40 is plenty big.

[waterbat]

wow... trying to bruteforce this problem is insane !

Somehow my todo list item 1 started working as expected - who knows why, but I'll take it but since I have MAX_CITIES, I did adjust all the maxes down with this line:

if (maxes[i] / MAX_CITIES) { maxes[i] = MAX_CITIES; } They aren't dynamic, but they also should not be that large then.



All my tests so far have been on *micro* populations like 124,000:
no max cities logic: 94500 iterations
max cities logic (set to 8): 1173 iterations (609 had to be evaluated, 564 thrown away)
todo dynamic maxes (tbd): tbd

brute force solving for a civ with a *small* population of 1,000,000:

no max cities logic: 2.55 trillion iterations required.
max cities logic (set to 8): 117562 iterations (44617 evaluated)
todo list dynamic maxes (tbd): tbd

So now I can give you the 23 ways that 1000000 can be shared between 4-8 cities:
(city size: city count)

11:0 10:1 9:0 8:0 7:1 6:0 5:1 4:1 3:0 2:0 1:0 city count: 4 pop count: 26
11:0 10:0 9:0 8:0 7:1 6:3 5:3 4:1 3:0 2:0 1:0 city count: 8 pop count: 44
11:0 10:0 9:1 8:0 7:0 6:1 5:4 4:0 3:1 2:0 1:0 city count: 7 pop count: 38
11:0 10:1 9:0 8:0 7:1 6:0 5:0 4:2 3:2 2:0 1:0 city count: 6 pop count: 31
11:0 10:0 9:0 8:1 7:0 6:4 5:0 4:0 3:3 2:0 1:0 city count: 8 pop count: 41
11:1 10:0 9:0 8:0 7:0 6:1 5:0 4:0 3:1 2:1 1:0 city count: 4 pop count: 22
11:0 10:1 9:0 8:0 7:1 6:0 5:1 4:0 3:2 2:1 1:0 city count: 6 pop count: 30
11:0 10:1 9:0 8:0 7:1 6:0 5:0 4:1 3:4 2:1 1:0 city count: 8 pop count: 35
11:0 10:1 9:0 8:1 7:0 6:0 5:0 4:0 3:1 2:2 1:0 city count: 5 pop count: 25
11:0 10:0 9:1 8:0 7:0 6:3 5:0 4:1 3:1 2:2 1:0 city count: 8 pop count: 38
11:1 10:0 9:0 8:0 7:0 6:0 5:0 4:3 3:1 2:2 1:0 city count: 7 pop count: 30
11:1 10:0 9:0 8:0 7:0 6:0 5:1 4:1 3:1 2:3 1:0 city count: 7 pop count: 29
11:0 10:0 9:0 8:1 7:2 6:1 5:0 4:1 3:0 2:0 1:1 city count: 6 pop count: 33
11:0 10:1 9:0 8:0 7:0 6:2 5:0 4:1 3:1 2:0 1:1 city count: 6 pop count: 30
11:0 10:0 9:0 8:1 7:2 6:1 5:0 4:0 3:2 2:1 1:1 city count: 8 pop count: 37
11:0 10:1 9:0 8:0 7:0 6:2 5:0 4:0 3:3 2:1 1:1 city count: 8 pop count: 34
11:0 10:0 9:1 8:0 7:2 6:0 5:0 4:1 3:0 2:3 1:1 city count: 8 pop count: 34
11:0 10:0 9:1 8:1 7:0 6:0 5:0 4:4 3:0 2:0 1:2 city count: 8 pop count: 35
11:0 10:0 9:1 8:1 7:0 6:1 5:0 4:0 3:2 2:0 1:2 city count: 7 pop count: 31
11:0 10:0 9:1 8:1 7:0 6:0 5:1 4:2 3:0 2:1 1:2 city count: 8 pop count: 34
11:0 10:0 9:1 8:1 7:0 6:0 5:2 4:0 3:0 2:2 1:2 city count: 8 pop count: 33
11:0 10:0 9:2 8:0 7:0 6:0 5:0 4:1 3:0 2:2 1:2 city count: 7 pop count: 28
11:0 10:0 9:0 8:2 7:1 6:0 5:1 4:0 3:0 2:0 1:4 city count: 8 pop count: 32

can someone check my math?

[novice]

I think dynamic programming can be applied to this problem to reduce (computational) complexity. Solutions to the big problem are comprised of modified solutions to smaller problems, so the answer can be reached in a bottom-up manner.

Store solutions in a dictionary keyed by total rival population, and expand each solution by adding a city or increasing a city size by 1 (without violating the other solutin constraints) and storing the result under the appropriate key. Populate the dictionary bottom up, and read out your final answers under the target key.

So for example we start with
4k: (4x1)
which is expanded to
5k: (5x1)
9k: (1x2,3x1)
next, 5k is expanded to
6k: (6x1)
10k: (1x2,4x1)
and eventually 9k will contain
(9x1) and (1x2,3x1) and will be expanded to
10k: (1x2, 4x1) (already present), (10x1)
14k: (2x2, 2x1), (1x2, 8x1)
24k: (1x3, 3x1)
and so on.

It may make sense to solve for one list of city sizes for all rivals which satisfies the total city count restraints and average rival pop, and then process this list afterwards for distributions that match min, max, rank and individual rival city count restraints.

[Cyneheard]

can someone check my math?

Math confirmed.

I suspect that Novice has the right idea, but I'm not able to do this level of work.

[SevenSpirits]

When you guys are done with that, I wonder if you could figure out the following for me: Say we know where all of an opponent's cities are, but don't have vision of them yet. Our goal is to uncover all the city tiles so we can track builds, and we only have a single spy unit to make the entire journey. Can you figure out the correct order to send him by all the cities is, to optimize for speed? Thanks in advance!

P.S. Let's only go through each city once OK?

[T-hawk]

Seven, you're hilarious. But the problem requires the cost of each path between nodes; in Civ terms that means knowledge of where the roads are. So it's not solvable at all until after the fact.