Fel'Unh Ikk
❔ Using crafting simulator to solve recipes
I have crafting simulator class called CraftingEngine. I am given various recipes and I have to solve them using CraftingEngine.
How simulator works:
Recipe is added to simulator as target. Then you add crafting actions, which change certain properties of simulator.
What properties are important to solving:
Progress. Starts at 0. When progress reaches recipe progress target, recipe is considered solved, increased by some actions.
Quality. Starts at 0. More quality means recipe is better, can be increased up to the target quality, also increased by some actions.
Crafting Points. Starts at max. Most actions cost crafting points.
Durability. Starts at max. Most actions reduce durability, but some also restore it, if durability reaches 0 or less with progress not being maxed, recipe fails.
I am also given actions that I can use, around 30 of them, with certain conditions.
My task: Solving recipes with as few actions as possible. In other words, maximizing Progress and Quality, while minimizing action count.
What I tried:
Bruteforcing. Testing every possible combination of actions. However, with 15 minimum actions to solve, 30 raised to 15 is a big number.
Genetic algorithm. It works, but I think it could be solved using something else.
Reducing crafting states count at every step. Generating states from previous iteration and removing all states that have worse properties. Example: you start with one initial state, you generate 30 different states by adding actions, 12 states of those 30 are worse than any other, remove them, generate 30 * 18 states from previous ones, remove all worse states, repeat. With this I can get to about 8 actions deep, before I use up all free memory.
What are your thoughts? How could this be solved?
2 replies
❔ Filtering out worse states from states array
I have a struct, for simplicity, let's call it State. State has many fields not related to each other. It also has a method IsWorse(State), which compares caller State to argument State and returns true if all caller State fields are worse or equal to argument State fields.
I want to quickly filter out states that are worse than any other states in the array, in other words, I want to filter out states that return true for method IsWorse at least once for any state in array.
I can already do this in O(n^2) time. I was thinking maybe there is a faster way.
24 replies