Best practice to evaluate permutations

Question

I came across this question, where the OP wanted to improve the following if-block. I open this as a new question because I'm searching a more general solution to this kind of problem.

public int fightMath(int one, int two) {

    if(one == 0 && two == 0) { result = 0; }
    else if(one == 0 && two == 1) { result = 0; }
    else if(one == 0 && two == 2) { result = 1; }
    else if(one == 0 && two == 3) { result = 2; }
    else if(one == 1 && two == 0) { result = 0; }
    else if(one == 1 && two == 1) { result = 0; }
    else if(one == 1 && two == 2) { result = 2; }
    else if(one == 1 && two == 3) { result = 1; }
    else if(one == 2 && two == 0) { result = 2; }
    else if(one == 2 && two == 1) { result = 1; }
    else if(one == 2 && two == 2) { result = 3; }
    else if(one == 2 && two == 3) { result = 3; }
    else if(one == 3 && two == 0) { result = 2; }
    else if(one == 3 && two == 1) { result = 1; }
    else if(one == 3 && two == 2) { result = 3; }
    else if(one == 3 && two == 3) { result = 3; }

    return result;
}

Now there are n^k possibilities to get a result, where n = 2 and k = 4. Some answers are suggesting to use an multi-array as a table to reduce the if-jungle.

But I would like to know how to solve such a problem with big n and k? Because a solution with if, switch and the suggested array approach will not scale well and to type things like that in code should be avoided.

If I think about combinatoric problems, there have to be a way to evaluate them easy.

If there's a simple rule for what `result` should be, implement the rule. If there isn't a simple rule, you may be stuck putting a giant lookup table in a config file or something. — user2357112, Mar 19 '14 at 10:02
how big are n and k? if they are big enough, I would think about database. ;) — Kent, Mar 19 '14 at 10:08
@Kent If there are different problems of this kind, building a database for each with different values is not very effective. — Steve Benett, Mar 19 '14 at 10:33
@SteveBenett I said it depends on the size of your n/k, if they fit in memory, matrix/map/array[][] will work. If they were big enough, like > maxLong, file/database would be the choice. how to design database table structure would be another story. — Kent, Mar 19 '14 at 11:06

score 4 · Answer 1 · answered Mar 19 '14 at 10:02

4

It's just a table of data. The answer to the question is found by multiple keys. It is no different to returning some data held in a database table which could itself be huge and perhaps span multiple tables.

answered Mar 19 '14 at 10:02

jmkgreen

1,633
14
22

score 2 · Answer 2 · answered Mar 19 '14 at 10:09

There are two ways to solve this:

Data-based. For example you could create a HashMap mapping the pair of values to the result.

class Pair {
   int one, two;

   //Generate hashcode and equals
}

Map<Pair, Integer> counts = new HashMap<>();

Pattern-based. Identify a rule/formula that can be used to determine the new value.

This is obviously better but relies on being able to identify a rule that covers all cases.

score 1 · Accepted Answer · edited May 23 '17 at 12:05

I would like to know how to solve such a problem with big n and k.

Since the output is determined arbitrarily (a game designer's whims) instead of mathematically (a formula), there's no guarantee of any pattern. Therefore the only general solution is some kind of lookup table.

Essentially, the question is similar to asking for a program that does f(a,b) -> c mapping, but you don't know any of the data beforehand -- instead it's provided at runtime. That program could process the data and find a pattern/formula (which might not exist) or it could build a lookup table.

Personally, I think it's clearer to change the logic to operate on intent (so reading the code explains how the attack works) instead of the actual outcomes (enumerating the list of inputs and matching outputs). Instead of building an if-jungle or a lookup table, structure your code based on how you want the logic to work. JAB's enum-based solution expresses the fight logic explicitly which makes it easier to see where to add new functionality and easier to see bugs (an off by one error in a lookup table isn't obviously wrong on inspection). A lookup table is a likely optimization, but that's only necessary if a profiler says so.

score 0 · Answer 4 · answered Mar 19 '14 at 10:09

Looking at your question and the original one there appears to be no deducible pattern between the input from the two players and the output (perhaps I'm wrong). Given this the only options are the "if-jungle" you mention or to use a data structure.

To solve such a problem for big n and k values my suggestion would be to create a rule to determine the output (either none, one or both players hit), but ensuring that this rule isn't easily deducible to the players. You could do this by making the rule a function of turn number (e.g. if both players press button 1 on turn #1 the output will be different to if they take the same action on turn #2).

Best practice to evaluate permutations

4 Answers4