I have created a working javascript function to check an array of 5 numbers for a small straight, in a Yahtzee game I'm making. I've tested it to no end and I'm confident it works 100% of the time, but it is also probably the worst algorithm of all time in terms of being efficient. Here is what it looks like:

function calcSmstraight() {
        var sum = 0;
        var r = new Array();
        var r2 = new Array();
        var counter = 0;
        var temp;
        var bool = false;
        var bool2 = false;
        r[0] = document.getElementById('setKeep1').value;
        r[1] = document.getElementById('setKeep2').value;
        r[2] = document.getElementById('setKeep3').value;
        r[3] = document.getElementById('setKeep4').value;
        r[4] = document.getElementById('setKeep5').value;

        // Move non-duplicates to new array
        r2[0] = r[0];
        for(var i=0; i<r.length; i++) {
            for(var j=0; j<r2.length; j++) {
                if(r[i] == r2[j]) {
                    bool2 = true;   // Already in new list
                }
            }
            // Add to new list if not already in it
            if(!bool2) {
                r2.push(r[i]);
            }
            bool2 = false;
        }
        // Make sure list has at least 4 different numbers
        if(r2.length >= 4) {
            // Sort dice from least to greatest
            while(counter < r2.length) {
                if(r2[counter] > r2[counter+1]) {
                    temp = r2[counter];
                    r2[counter] = r2[counter+1];
                    r2[counter+1] = temp;
                    counter = 0;
                } else {
                    counter++;
                }
            }
            // Check if the dice are in order
            if(((r2[0] == (r2[1]-1)) && (r2[1] == (r2[2]-1)) && (r2[2] == (r2[3]-1)))
                || ((r2[1] == (r2[2]-1)) && (r2[2] == (r2[3]-1)) && (r2[3] == (r2[4]-1)))) {
                bool = true;
            }
        }

        if(bool) {
            // If small straight give 30 points
            sum = 30;
        }

        return sum;
}

My strategy is to:

1) Remove duplicates by adding numbers to a new array as they occur

2) Make sure the new array is at least 4 in length (4 different numbers)

3) Sort the array from least to greatest

4) Check if the first 4 OR last 4 (if 5 in length) numbers are in order

My question:

Does anyone know a way that I can improve this method? It seems ridiculously terrible to me but I can't think of a better way to do this and it at least works.

I have created a working javascript function to check an array of 5 numbers for a small straight, in a Yahtzee game I'm making. I've tested it to no end and I'm confident it works 100% of the time, but it is also probably the worst algorithm of all time in terms of being efficient. Here is what it looks like:

function calcSmstraight() {
        var sum = 0;
        var r = new Array();
        var r2 = new Array();
        var counter = 0;
        var temp;
        var bool = false;
        var bool2 = false;
        r[0] = document.getElementById('setKeep1').value;
        r[1] = document.getElementById('setKeep2').value;
        r[2] = document.getElementById('setKeep3').value;
        r[3] = document.getElementById('setKeep4').value;
        r[4] = document.getElementById('setKeep5').value;

        // Move non-duplicates to new array
        r2[0] = r[0];
        for(var i=0; i<r.length; i++) {
            for(var j=0; j<r2.length; j++) {
                if(r[i] == r2[j]) {
                    bool2 = true;   // Already in new list
                }
            }
            // Add to new list if not already in it
            if(!bool2) {
                r2.push(r[i]);
            }
            bool2 = false;
        }
        // Make sure list has at least 4 different numbers
        if(r2.length >= 4) {
            // Sort dice from least to greatest
            while(counter < r2.length) {
                if(r2[counter] > r2[counter+1]) {
                    temp = r2[counter];
                    r2[counter] = r2[counter+1];
                    r2[counter+1] = temp;
                    counter = 0;
                } else {
                    counter++;
                }
            }
            // Check if the dice are in order
            if(((r2[0] == (r2[1]-1)) && (r2[1] == (r2[2]-1)) && (r2[2] == (r2[3]-1)))
                || ((r2[1] == (r2[2]-1)) && (r2[2] == (r2[3]-1)) && (r2[3] == (r2[4]-1)))) {
                bool = true;
            }
        }

        if(bool) {
            // If small straight give 30 points
            sum = 30;
        }

        return sum;
}

My strategy is to:

1) Remove duplicates by adding numbers to a new array as they occur

2) Make sure the new array is at least 4 in length (4 different numbers)

3) Sort the array from least to greatest

4) Check if the first 4 OR last 4 (if 5 in length) numbers are in order

My question:

Does anyone know a way that I can improve this method? It seems ridiculously terrible to me but I can't think of a better way to do this and it at least works.

• javascript
• algorithm

• 2 bool? bool2? Surely you can e up with more meaningful variable names than that. Also, r2.sort(function(a,b){return a-b;}); might help you a bit - no need to implement your own sorting routine when JavaScript already provides one. – nnnnnn Commented Sep 4, 2013 at 13:58
• 1 To start, make your method take parameters instead of grabbing the html elements directly. – Mansfield Commented Sep 4, 2013 at 14:00
• 2 Should be asked on codereview stackexchange – epascarello Commented Sep 4, 2013 at 14:02
• 1 How about using the value of the "card" as the index into an array, and then loop through the array for (i=lowPossibleValue;i<=HiPossibleValue;i++) and see if there are four in a row that exist. – Paul Stearns Commented Sep 4, 2013 at 14:06
• 1 @DaveNewton Please vote to close because the question is off-topic for Stack Overflow, not because it belongs somewhere else. Voting to close because it belongs somewhere else can cause situations where the question is closed on two places. It is okay to redirect people to other sites, but don't vote to close with that reason. – Simon Forsberg Commented Apr 9, 2015 at 19:35

3 Answers 3

Given that you're implementing a Yahtzee game you presumably need to test for other patterns beyond just small straights, so it would be better to create the array of values before calling the function so that you can use them in all tests, rather than getting the values from the DOM elements inside the small straight test.

Anyway, here's the first way that came to my mind to test for a small straight within an array representing the values of five six-sided dice:

    // assume r is an array with the values from the dice
    r.sort();
    if (/1234|2345|3456/.test(r.join("").replace(/(.)\1/,"$1") {
        // is a small straight
    }

Note that you can sort an array of numbers using this code:

r2.sort(function(a,b){return a-b;});

...but in your case the values in the array are strings because they came from the .value attribute of DOM elements, so a default string sort will work with r2.sort(). Either way you don't need your own sort routine, because JavaScript provides one.

EDIT: If you assume that you can just put the five values as a string as above you can implement tests for all possible binations as a big if/else like this:

r.sort();
r = r.join("");
if (/(.)\1{4}/.test(r)) {
    alert("Five of a Kind");
} else if (/(.)\1{3}/.test(r)) {
    alert("Four of a Kind");
} else if (/(.)\1{2}(.)\2|(.)\3(.)\4{2}/.test(r)) {
    alert("Full House");
} else if (/(.)\1{2}/.test(r)) {
    alert("Three of a Kind");
} else if (/1234|2345|3456/.test( r.replace(/(.)\1/,"$1") ) {
    alert("Small Straight");
} // etc.

Demo: http://jsfiddle/4Qzfw/

Why don't you just have a six-element array of booleans indicating whether a number is present, then check 1-4, 2-5, and 3-6 for being all true? In pseudocode:

numFlags = array(6);
foreach(dice)
    numFlags[die.value-1] = true;
if(numFlags[0] && numFlags[1] && numFlags[2] && numFlags[3]) return true
//Repeat for 1-4 and 2-5
return false

This wouldn't be a useful algorithm if you were using million-sided dice, but for six-siders there are only three possible small straights to check for, so it's simple and straightforward.

I do not play Yahtzee, but I do play cards, and it would appear the algorithm might be similar. This routine, written in ActionScript (my JavaScript is a bit rusty) has been piled but not tested. It should accept 5 cards for input, and return a message for either straights greater than 3 cards or pairs or higher.

private function checkCards(card1:int,card2:int,card3:int,card4:int,card5:int):String
{
    // Assumes that the 5 cards have a value between 0-12 (Ace-King)
    //The key to the routine is using the card values as pointers into an array of possible card values.
    var aryCardValues:Array = new Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
    aryCardValues[card1] += 1;
    aryCardValues[card1] += 1;
    aryCardValues[card1] += 1;
    aryCardValues[card1] += 1;
    aryCardValues[card1] += 1;
    var aryCardNames:Array = new Array("Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King");
    var strOutMessage:String;
    var intCardCount:int = 0;
    var strSeperator:String;
    var strHighCard:String;
    for (var i:int = 0;i < aryCardValues.length;i++)
    {
        //Check for runs of three of a kind or greater.
        if (aryCardValues[i] >= 2) 
        {
            strOutMessage = strOutMessage + strSeperator + i + "-" + aryCardNames[i] + "s";
            strSeperator = " & ";
        }
        //Check for values in a straight.
        if (aryCardValues[i] > 0)
        {
            intCardCount++;
            if (intCardCount > 3)strHighCard = aryCardNames[i];
        }
        else
        {
            if (intCardCount < 3)intCardCount = 0;
        }
    }
    if (intCardCount > 3) strOutMessage = intCardCount + " run " + strHighCard + " High."
    return strOutMessage;
}

It may not be as concise as the regular expressions used above, but it might be more readable and easily modified. One change that could be made is to pass in an array of cards rather than discrete variables for each card.