1

I am developing a game that has a winning combination array:

var allwinning = [
['000','010','020'],
['000','100','200'],
['000','001','002'],
['000','101','202'],
['000','011','022'],
['000','110','220']];

The player will need to pick more than 3 numbers randomly. If all numbers are within any of the combinations in allwinning, the player wins.

For example, if the player picks '111','110','000','220', the player will win because allwinning[5] has the combination['000','110','220'].

My question is, what is the best way to do this winning loop? I cannot figure out the optimum way to do this.

Currently, I have a playerpick array to keep what player had picked and possiblewin array:

var playerpick = new Array(['111','110','000','220']);
var playerpicksingle = playerpick[0];
var possiblewin = new Array([]);

Then I go through a loop to capture out the possible win combination first:

for(var i=0 ; i < allwinning.length - 1 ; i++)
    {
        for(var j=0 ; j <3 ; j++)
        {
            if(allwinning[i][j]==playerpicksingle)
            {
            possiblewin.Push(allwinning[i]);
            }
        }
    }

Then I am stuck at this point. I really don't know what else to do.

2
  • 1
    Well, what do you have so far and what makes you think it is not the optimal way? Commented Dec 19, 2013 at 5:36
  • @FelixKling read my edit. Thanks! Commented Dec 19, 2013 at 5:59

1 Answer 1

2

I can think of two ways. One requires you to change your data structure and the other doesn't.

Without changes:

Sort the user input:

pickedNumbers.sort();

and start comparing. By sorting the values beforehand you know when you can back out and continue with the next set of numbers, i.e. you can back out early and don't have to compare all the values (in the average case).

function wins(picked, winning) {
    var winningSet = [];

    for (var i = 0; i < winning.length && winningSet.length < 3; i++) {
        var set = winning[i];
        winningSet = [];
        var j = 0;
        var k = 0;
        while (j < set.length && k < picked.length && winningSet.length < 3) {
            if (picked[k] === set[j]) {
                winningSet.push(set[j]);
                j++; // advance to next element in winning set
            } else if (picked[k] > set[j]) {
                // continue with the next set 
                break;
            }
            // maybe the next element in players picks will match
            k++;
        }
    }
    return winningSet.length === 3 ? winningSet : false;
}

The worst case scenario of this solution is O(n*m*l), but since the input is sorted, the average case will be better.

DEMO

With Array#some and Array#every the code becomes much more concise, though it looses the advantage of using sorted input. If your arrays are small it won't make a difference though:

function wins(picked, winning) {
    return winning.some(function(set) {
        return set.every(function(val) {
            return picked.indexOf(val) !== -1;
        });
    });
}

It also won't give you the actual numbers that matched. The runtime is the same.


The second way would be to build some kind of trie instead of using an array of arrays:

var allwinning = {
    '000': {
        '010': {
            '020': true
        },
        '100': {
            '200': true
        },
        // ...
    }
};

The structure should also be sorted, i.e. the keys of a level are all smaller then the keys of its sublevel etc.

Sort the user input as well and iterate over it. Whenever you found a matching key, you go one level deeper until you have three matches:

function wins(picked, winning) {
    var winningSet = [];
    for (var i = 0; i < picked.length && winningSet.length < 3; i++) {
        if (picked[i] in winning) {
            winningSet.push(picked[i]);
            winning = winning[picked[i]];
        }
    }
    return winningSet.length === 3 ? winningSet : false;
}

This solution has the worst case scenario of O(n), where n is the number of values the user picked (not taking into account the time it takes to test whether an object contains a specific property name. Often this is assumed to constant).

DEMO

Sign up to request clarification or add additional context in comments.

1 Comment

OK after much of analysis I think I got it. I think your first way works for me. Now I just have to sort all my arrays. Thanks!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.