I’d like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I’ll use an analogue for the rest of the question. For the few who benefit from this information: the game I’m referring to is Magic The Gathering, and the problem is finding whether or not a set of lands can cast a given card.
We can think of the materials as steel and wood. Any resource produces a combination of them. For example:
Requirement: 1 steel + 2 wood Resources: - 1 steel + 1 wood - 1 wood Verdict: POSSIBLE
There may be generic requirements, which can be fulfilled by whatever resource is available.
Requirement: 2 ANY + 1 wood Resources: - 1 steel - 1 wood - 1 wood Verdict: POSSIBLE
Resources may be used to produce different combinations at will, when stated of course.
Requirement: 1 steel + 1 wood Resources: - 1 steel - 1 steel OR 1 wood Verdict: POSSIBLE
Finally, there may be costs associated with certain production. Here marked as
cost -> production.
Requirement: 2 steel Resources: - 1 steel - 1 wood - 1 wood -> 1 steel Verdict: POSSIBLE
Now, given a set of these resources it is relatively easy to figure out if a given requirement can be fulfilled. What I have currently is a naïve exhaustive search with one optimisation (step 1). In pseudo-python it goes as follows:
1. produce with resources that have only one production and no cost to have current "production" 2. can_fulfill(requirement, current production, resource list) def can_fulfill(requirement, production, resources): for i, resource in enumerate(resources): remaining = resources(:i) + resources(i + 1:) for cost, gain in resource: if can_subtract(production, cost): new_production = production - cost + gain if fulfilled(requirement, production): return True recur = can_fulfill(requirement, new_production, remaining) if recur: return True return False
It does work, and for single-production resources it is lightning fast. But in this particular case there can be many resources with multiple production options, which slows the calculation. I think the exhaustive search is my only option, because one can’t know which productions ultimately lead to the fulfillment of a requirement, but could there be more clever optimisations I could implement?