Yesterday I solved an interesting question that went as follows: given two players with a list of integers evaluate whether or not a player has won based on 3 rules. Note that the question was not EXACTLY worded like this but this is the gist of it.

The first rule is if player 1 has a fibonacci sequence player 1 wins, otherwise player 2 wins and if there’s a tie we evalute the second rule. If need be, we evaluate the third rule if the second rule results in a tie also.

The second rule is the player with the highest # wins.

And the third rule is the player with a higher count of prime numbers wins.

The solution

Initially my solution was to simply write a function that evaluated each of the 3 rules one by one, resolving ties if needed. This solution basically breaks down into a tree and a sort of messy if/else branch. We can think of evaluating a rule as returning 3 values PLAYER1_WON, PLAYER2_WON, or TIE. We can use separate functions like count_primes(list), isFibonacci(list) and max_card(list) to avoid redundant code and simplify everything. I coded it and then my interviewer asked me to do better for arbitrary N rules.

As I was coding the worse solution that worked, I realized we could just simplify each rule into a list of them and evaluate them one by one top down much like you would in a directed-acylic graph of dependencies or a decision tree. This approach is nice because in essence we only have to write code for each rule, then evaluate them sequentially instead of writing very branchy/bug-prone and difficult to read code. With this approach we think of our rules as a pipeline and just evaluate the next rule if the current rule evaluates to a tie.

class Rule {
    virtual RULE_RESULT evaluate(vector<int>& list1, vector<int>& list2);
}

and then have each rule override accordingly using virtual inheritance

class FibonacciRule : public Rule {
    virtual RULE_RESULT evaluate(vector<int>& list1, vector<int>& list2) {
        // implement logic for determining who won the fib sequence rule
    }
}

class MaxHandrule : public Rule {
    virtual RULE_RESULT evaluate(vector<int>& list1, vector<int>& list2) {
        // implement this
    }
}

class PrimeRule : public Rule {
    virtual RULE_RESULT evaluate(vector<int>& list1, vector<int>& list2) {
        // implement this
    }
}

When we want to evaluate any number of N rules we can just pass in a list of rules and go through to evaluate a hand like so, continuing if any ties occur

RULE_RESULT evaluateLists(vector<int>& list1, vector<int>& list2, vector<Rule>& rules) {
    for (Rule& rule: rules) {
        RULE_RESULT result = rule.evaluate(list1, list2);
        if (result != TIE)
            return result;
    }
    // All the rules were ties
    return TIE;
}

So we simplified the problem, reduced the amount of work to do and improved the maintainability of our code by taking this approach to solve this problem.