The Dark arts - C&D Master Thread

[kalin]

Below is the code that distributes changes. Changes are assumed to be only increases by 1 (e.g., from 2 to 3). I didn't consider decreases. The code works by taking a population increase and a number of cities as inputs just like before:

python ./diff_change.py <population_in_thousands> <number_of_cities>

The output is one or more sequences of increases in city sizes along with the number of population changed. This is best explained by a few examples:

Code:

python ./diff_change.py 84 2
[('4->5', 42), ('4->5', 42)]

python ./diff_change.py 84 3
[('4->5', 42), ('3->4', 27), ('2->3', 15)]

time python ./diff_change.py 84 4
[('3->4', 27), ('3->4', 27), ('2->3', 15), ('2->3', 15)

For example, to increase by 84k pop over 3 cities, you'd need to grow from 2 to 3, 3 to 4, and 4 to 5. Let me know if you need additional information.

Code:

#!/usr/bin/env python                                                                                                                                                                                              

import sys

MAX_SIZE = 25
dcoins = dict()
for x in range(1,MAX_SIZE):
    y = x + 1
    chg = int(y**2.8) - int(x**2.8)
    dcoins.setdefault( chg, set()).add( "%d->%d" % (x,y) )
coins = [(' '.join(list(y)), x) for (x,y) in sorted(dcoins.items())]

MEMOIZE = True
memo = dict()

def make_change(n, m):

    if MEMOIZE and ((n,m) in memo):
        return(memo[(n,m)])

    if (n == 0):
        res = [ [] ]
        if (MEMOIZE): memo[(n,m)] = res
        return(res)
    elif ( (n < 0) or (m < 0) ):
        return( [] )
    else:
        res1 = [ [coins[m]] + x for x in make_change(n - coins[m][1], m) ]
        res2 = make_change(n, m - 1)
        res = res1 + res2
        if (MEMOIZE): memo[(n,m)] = res
        return(res)

if (__name__ == "__main__"):

    try:
        pop = int(sys.argv[1])
    except:
        pop = 124
    try:
        cities = int(sys.argv[2])
    except:
        cities = 5

    res = make_change( pop, len(coins) - 1 )
    for x in res:
        if (len(x) == cities):
            print x

Kalin

[kjn]

My first run ended in a fiasco, since I missed that the script wanted numbers with the thousands omitted. Ie, I put in 18000 8 instead of 18 8 as parameters.

Anyway, I changed the coins line to:

Code:

coins = [(x,int(x**2.8)-int((x-1)**2.8)) for x in range(1,20)]

and tried it on (10,2) and (109,7) as input, and it worked nicely and in the latter case outputted the two solutions I had found earlier. Now I will have to run it on the earlier turns as well.

[kalin]

@kjn: Using your data from above, here's how you could distribute 109k pop over 7 cities:

Code:

python ./diff_change.py 109 7
[('4->5', 42), ('4->5', 42), ('1->2', 5), ('1->2', 5), ('1->2', 5), ('1->2', 5), ('1->2', 5)]
[('3->4', 27), ('3->4', 27), ('2->3', 15), ('2->3', 15), ('2->3', 15), ('1->2', 5), ('1->2', 5)]

Two options: (a) two 4-to-5 increases, and five 1-to-2 ones or (b) two 3-to-4 increases, three 2-to-3, and two 1-to-2 ones. I haven't followed much, but I am thinking that (b) may be more plausible? Actually, I have no idea...

Makes sense?

Kalin

[kalin]

My first run ended in a fiasco, since I missed that the script wanted numbers with the thousands omitted. Ie, I put in 18000 8 instead of 18 8 as parameters.

Anyway, I changed the coins line to:

Code:

coins = [(x,int(x**2.8)-int((x-1)**2.8)) for x in range(1,20)]

and tried it on (10,2) and (109,7) as input, and it worked nicely and in the latter case outputted the two solutions I had found earlier. Now I will have to run it on the earlier turns as well.

Check the new version And yes, sorry no thousands.

Changing the coin values probably works too.

Kalin

[kjn]

Yes, both versions here work fine, though yours give nicer output.

The idea here is to quickly find all the possible candidate solutions for a turn, so I can concentrate on the other constraints (eg this turn we only had four size 1 cities among the candidates, so the first alternative was out).

Thanks!

[kalin]

Glad to hear it works. I have initially implemented a version that allowed for increases by more than 1, which is why I didn't see that simply changing the coin values to differences would work. Of course, cities cannot increase in size by more than 1

Anyway, thanks for doing all this and let me know if there is anything else I can help with.

Kalin

[Boldly Going Nowhere]

That is all. I just read two pages of what looked like math, tried to understand, and recognize the superiority of my technological overlords. Great work getting a tool that will really help us!

[kalin]

FWIW, my code above was inspired by this:

http://www.algorithmist.com/index.php/Coin_Change

Kalin

[kjn]

Glad to hear it works. I have initially implemented a version that allowed for increases by more than 1, which is why I didn't see that simply changing the coin values to differences would work. Of course, cities cannot increase in size by more than 1

Well, with the Hanging Gardens, they can (I did it in Adventure 54). And I can imagine some whips causing a city to grow twice over as the turn rolls, depending on how the pop growth code is written. But the second is a one-off that can be handled by hand, and the second is probably never seen in practice.

My solution of just switching to differences had a side effect that I get a few bogus answers, since it reports size 1 cities in the possible solution space. I think you remove them earlier on.

[novice]

And I can imagine some whips causing a city to grow twice over as the turn rolls, depending on how the pop growth code is written. But the second is a one-off that can be handled by hand, and the second is probably never seen in practice.

There was an adventure that gave absurd amounts of food, and the cities just accumulated overflow but never grew more than one size per turn.