Reducing the time complexity of this algorithm

Question

I'm playing a game that has a weapon-forging component, where you combine two weapons to get a new one. The sheer number of weapon combinations (see "6.1. Blade Combination Tables" at http://www.gamefaqs.com/ps/914326-vagrant-story/faqs/8485) makes it difficult to figure out what you can ultimately create out of your current weapons through repeated forging, so I tried writing a program that would do this for me. I give it a list of weapons that I currently have, such as:

• francisca
• tabarzin
• kris

and it gives me the list of all weapons that I can forge:

• ball mace
• chamkaq
• dirk
• francisca
• large crescent
• throwing knife

The problem is that I'm using a brute-force algorithm that scales extremely poorly; it takes about 15 seconds to calculate all possible weapons for seven starting weapons, and a few minutes to calculate for eight starting weapons. I'd like it to be able to calculate up to 64 weapons (the maximum that you can hold at once), but I don't think I'd live long enough to see the results.

function find_possible_weapons(source_weapons)
{
    for (i in source_weapons)
    {
        for (j in source_weapons)
        {
            if (i != j)
            {
                result_weapon = combine_weapons(source_weapons[i], source_weapons[j]);

                new_weapons = array();
                new_weapons.add(result_weapon);
                for (k in source_weapons)
                {
                    if (k != i && k != j)
                        new_weapons.add(source_weapons[k]);
                }
                find_possible_weapons(new_weapons);
            }
        }
    }
}

In English: I attempt every combination of two weapons from my list of source weapons. For each of those combinations, I create a new list of all weapons that I'd have following that combination (that is, the newly-combined weapon plus all of the source weapons except the two that I combined), and then I repeat these steps for the new list.

Is there a better way to do this?

Note that combining weapons in the reverse order can change the result (Rapier + Firangi = Short Sword, but Firangi + Rapier = Spatha), so I can't skip those reversals in the j loop.

Edit: Here's a breakdown of the test example that I gave above, to show what the algorithm is doing. A line in brackets shows the result of a combination, and the following line is the new list of weapons that's created as a result:

francisca,tabarzin,kris
[francisca + tabarzin = chamkaq]
    chamkaq,kris
    [chamkaq + kris = large crescent]
        large crescent
    [kris + chamkaq = large crescent]
        large crescent
[francisca + kris = dirk]
    dirk,tabarzin
    [dirk + tabarzin = francisca]
        francisca
    [tabarzin + dirk = francisca]
        francisca
[tabarzin + francisca = chamkaq]
    chamkaq,kris
    [chamkaq + kris = large crescent]
        large crescent
    [kris + chamkaq = large crescent]
        large crescent
[tabarzin + kris = throwing knife]
    throwing knife,francisca
    [throwing knife + francisca = ball mace]
        ball mace
    [francisca + throwing knife = ball mace]
        ball mace
[kris + francisca = dirk]
    dirk,tabarzin
    [dirk + tabarzin = francisca]
        francisca
    [tabarzin + dirk = francisca]
        francisca
[kris + tabarzin = throwing knife]
    throwing knife,francisca
    [throwing knife + francisca = ball mace]
        ball mace
    [francisca + throwing knife = ball mace]
        ball mace

Also, note that duplicate items in a list of weapons are significant and can't be removed. For example, if I add a second kris to my list of starting weapons so that I have the following list:

• francisca
• tabarzin
• kris
• kris

then I'm able to forge the following items:

• ball mace
• battle axe
• battle knife
• chamkaq
• dirk
• francisca
• kris
• kudi
• large crescent
• scramasax
• throwing knife

The addition of a duplicate kris allowed me to forge four new items that I couldn't before. It also increased the total number of forge tests to 252 for a four-item list, up from 27 for the three-item list.

Edit: I'm getting the feeling that solving this would require more math and computer science knowledge than I have, so I'm going to give up on it. It seemed like a simple enough problem at first, but then, so does the Travelling Salesman. I'm accepting David Eisenstat's answer since the suggestion of remembering and skipping duplicate item lists made such a huge difference in execution time and seems like it would be applicable to a lot of similar problems.

Answer 1

Start by memoizing the brute force solution, i.e., sort source_weapons, make it hashable (e.g., convert to a string by joining with commas), and look it up in a map of input/output pairs. If it isn't there, do the computation as normal and add the result to the map. This often results in big wins for little effort.

Alternatively, you could do a backward search. Given a multiset of weapons, form predecessors by replacing one of the weapon with two weapons that forge it, in all possible ways. Starting with the singleton list consisting of the singleton multiset consisting of the goal weapon, repeatedly expand the list by predecessors of list elements and then cull multisets that are supersets of others. Stop when you reach a fixed point.

---

If linear programming is an option, then there are systematic ways to prune search trees. In particular, let's make the problem easier by (i) allowing an infinite supply of "catalysts" (maybe not needed here?) (ii) allowing "fractional" forging, e.g., if X + Y => Z, then 0.5 X + 0.5 Y => 0.5 Z. Then there's an LP formulation as follows. For all i + j => k (i and j forge k), the variable x_{ijk} is the number of times this forge is performed.

minimize sum_{i, j => k} x_{ijk} (to prevent wasteful cycles) for all i:   sum_{j, k: j + k => i} x_{jki}            - sum_{j, k: j + i => k} x_{jik}            - sum_{j, k: i + j => k} x_{ijk} >= q_i, for all i + j => k: x_{ijk} >= 0, 

where q_i is 1 if i is the goal item, else minus the number of i initially available. There are efficient solvers for this easy version. Since the reactions are always 2 => 1, you can always recover a feasible forging schedule for an integer solution. Accordingly, I would recommend integer programming for this problem. The paragraph below may still be of interest.

I know shipping an LP solver may be inconvenient, so here's an insight that will let you do without. This LP is feasible if and only if its dual is bounded. Intuitively, the dual problem is to assign a "value" to each item such that, however you forge, the total value of your inventory does not increase. If the goal item is valued at more than the available inventory, then you can't forge it. You can use any method that you can think of to assign these values.

Answer 2

I think you are unlikely to get a good general answer to this question because if there was an efficient algorithm to solve your problem, then it would also be able to solve NP-complete problems.

For example, consider the problem of finding the maximum number of independent rows in a binary matrix.
This is a known NP-complete problem (e.g. by showing equivalence to the maximum independent set problem).

We can reduce this problem to your question in the following manner:

We can start holding one weapon for each column in the binary matrix, and then we imagine each row describes an alternative way of making a new weapon (say a battle axe). We construct the weapon translation table such that to make the battle axe using method i, we need all weapons j such that M[i,j] is equal to 1 (this may involve inventing some additional weapons).

Then we construct a series of super weapons which can be made by combining different numbers of our battle axes.

For example, the mega ultimate battle axe may require 4 battle axes to be combined.

If we are able to work out the best weapon that can be constructed from your starting weapons, then we have solved the problem of finding the maximum number of independent rows in the original binary matrix.

Answer 3

It's not a huge saving, however looking at the source document, there are times when combining weapons produces the same weapon as one that was combined. I assume that you won't want to do this as you'll end up with less weapons.

So if you added a check for if the result_weapon was the same type as one of the inputs, and didn't go ahead and recursively call find_possible_weapons(new_weapons), you'd trim the search down a little.

The other thing I could think of, is you are not keeping a track of work done, so if the return from find_possible_weapons(new_weapons) returns the same weapon that you already have got by combining other weapons, you might well be performing the same search branch multiple times.

e.g. if you have a, b, c, d, e, f, g, and if a + b = x, and c + d = x, then you algorithm will be performing two lots of comparing x against e, f, and g. So if you keep a track of what you've already computed, you'll be onto a winner...

Basically, you have to trim the search tree. There are loads of different techniques to do this: it's called search. If you want more advice, I'd recommend going to the computer science stack exchange.

If you are still struggling, then you could always start weighting items/resulting items, and only focus on doing the calculation on 'high gain' objects...