example monte carlo solver for elemental chemistry

montecarlo.py

import numpy as np
import random

earth = np.array([40.,0.,0.,0.])
air = np.array([0.,40.,0.,0.])
fire = np.array([0.,0.,40.,0.])
water = np.array([0.,0.,0.,40.])

mud = ( earth*3 + water ) / 4
muck = ( earth + water*3 ) / 4

steam =  ( water + fire*3 ) / 4
brick = mud + fire - steam

fog = ( air*7 + water ) / 8
wind =  ( air*2 + fire + water ) / 4

living_wood = ( earth*3 + air + fire + water*3 ) / 8
dry_wood = ( living_wood*8 - water + air ) / 8
ash = dry_wood + fire - steam

chaos = np.array([10.,10.,10.,10.])

materials = { 'earth':earth, 'air':air, 'fire':fire, 
    'water':water, 'mud':mud, 'muck':muck, 
    'brick':brick, 'steam':steam,
    'fog':fog, 'wind':wind,
    'living_wood':living_wood , 'dry_wood':dry_wood,
    'ash':ash, 'chaos':chaos
     }


def purity(a):
    return ((a/a.sum())**2).sum()

def hashed_purity(hashed_element_count):
    total = 0
    for element_name in hashed_element_count:
        total += purity(materials[element_name]) * hashed_element_count[element_name]
    return total

def hashed_to_value(hashed_element_count):
    results = [ materials[name] * hashed_element_count[name] for name in hashed_element_count.keys() ]
    result = results[0]
    for index in range(1,len(results)):
        result += results[index]
    return result


def list_to_hash(items):
    result = {}
    for item in items:
        if item not in result:
            result[item] = 0
        result[item] += 1
    return result

def hash_to_list(hashed_element_count):
    result = []
    for name in hashed_element_count:
        for _ in range(hashed_element_count[name]):
            result.append(name)
    return result

def lists_to_hash(items) :
    return [ list_to_hash(item) for item in items ]



def uniq(lst):
    last = object()
    for item in lst:
        if item == last:
            continue
        yield item
        last = item


def solve(input,budget=None) :
    epsilon = 0.1
    if type(input) == dict :
        result = [sorted(hash_to_list(input))]
        input = hashed_to_value(input)
    else :
        result = []
    budget = budget or [10000]
    budget = budget if type(budget) == list else [budget]
    names = materials.keys()
    random.shuffle(names)
    for name in names:
        remainder = input - materials[name]
        if remainder.sum() <= epsilon and remainder.sum() >= -epsilon and remainder.min() >= -epsilon :
            result.append([name])
        if remainder.min() >= -epsilon :
            solutions = solve(input - materials[name],budget)
            solutions = [sorted(solution + [name]) for solution in solutions]
            result.extend( solutions )
        budget[0] -= 1
        if budget[0] <= 0 :
            return [item for item in uniq(sorted(result))]
    return [item for item in uniq(sorted(result))]



print """
--- Solving combinations of materials ---
"""

print "solve( earth*5 + water*2 )"
print lists_to_hash(solve(earth*5+water*2))

print

print "solve( mud + fire )"
print lists_to_hash(solve(mud+fire))

print 

print "solve( mud*4 )"
print lists_to_hash(solve(mud*4))

print

def purity_report( weights , budget=None ) :
    results = lists_to_hash( solve( weights , budget ) )
    for result in results :
        print result , hashed_purity( result )

print "purity_report( earth*200 + water*200 )"
purity_report( earth*200 + water*200 )

print 

print "purity_report( {'earth':200, 'water':200} )"
purity_report( {'earth':200, 'water':200} )

print 

print "purity_report( {'earth':5, 'water':5} )"
purity_report( {'earth':5, 'water':5} )

print 

print "purity_report( {'muck':5, 'mud':5} )"
purity_report( {'muck':5, 'mud':5} )

print

print "purity_report( steam*4 + air )"
purity_report( steam*4 + air )

print

print "purity_report( mud + fire )"
purity_report( mud + fire )

print """
--- Done ---
"""


purity_report( { 'earth':100, 'air':100, 'fire':100, 'water':100, 'mud':100, 'muck':100, 'brick':100, 'steam':100 })

Example output

 time python montecarlo.py

--- Solving combinations of elements ---

solve( earth*5 + water*2 )
[{'water': 2, 'earth': 5}, {'muck': 1, 'earth': 4, 'water': 1, 'mud': 1}, {'muck': 2, 'earth': 3, 'mud': 2}, {'water': 1, 'earth': 2, 'mud': 4}, {'muck': 1, 'earth': 1, 'mud': 5}]

solve( mud + fire )
[{'brick': 1, 'steam': 1}, {'fire': 1, 'mud': 1}]

solve( mud*4 )
[{'water': 1, 'earth': 3}, {'muck': 1, 'earth': 2, 'mud': 1}, {'mud': 4}]

--- Done ---


real	0m0.224s
user	0m0.174s
sys	0m0.043s