mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Programming (https://www.mersenneforum.org/forumdisplay.php?f=29)
-   -   sequential number test (https://www.mersenneforum.org/showthread.php?t=16510)

 Bundu 2012-02-08 10:44

sequential number test

Hi folks,

It has been a while since I last posted... a beautiful baby daughter being born kind of sucks up your free time :-)

I have been attempting to build a little fun poker app to help me learn javascript for work and I am currently chugging through the difficult part (hand evaluation!). I am not a math boffin by any means so any help would be appreciated, thanked and if it goes anywhere practical I will come back and make a donation to you (or GIMPS) whichever you prefer.

I have been looking at checking various hands and am currently working on straights. I was wondering if there was any existing formulas that could test a sequence of numbers to determine if they were sequential?
[LIST][*]assuming I have cards from 1 - 14 (ace if 14)[*]A player has 2 cards[*]There are 5 community cards that they pool with[*]of which they can use a maximum of 5 out of the 7 cards[/LIST]
I can create an array of the numerical values of the cards, sort the array so the numbers are listed sequentially and then iterate through the array testing if the next array value is 1 higher than the former and check for 5 or more "true" results.

I was just wondering if there was a simpler more elegant solution than anyone had to hand?

Edit: I realise I would have to test twice with the ace as 14 and as 1!

edit2:

I was thinking that if the numbers were sequential then the total of the numbers would be equal to the first and last number x half the array length but this only works for even length arrays?

[1,2,3,4,5,6] = 21
and (1+6)x3 = 21

[7,8,9,10,11,12] = 57
and 19x3 = 57

but since I am working with 5 and 7 cards this isn't ideal? and thinking about this even more there could be repeated numbers... hmm perhaps iterating through is the most efficient?

 axn 2012-02-08 11:20

Use a bit-based approach.

Let x be an integer variable. For each of the 7 cards, set x = x | (1 << card_value)

Now we need to check if the bit representation of x has 5 consecutive '1' bits.

Check if the expression x & (x << 1) & (x << 2) & (x << 3) & (x << 4) is non-zero. If so, it has 5 consecutive 1's.

 Bundu 2012-02-08 11:29

Ok that is a completely new one on me I will do some research on this area of javascript and get back to you! will a bitwise approach handle potential repeated numbers in the sequence?

for example [2,3,3,3,4,5,6] is a straight but does not have 5 sequential numbers?

 axn 2012-02-08 11:54

[QUOTE=Bundu;288625]Ok that is a completely new one on me I will do some research on this area of javascript and get back to you! will a bitwise approach handle potential repeated numbers in the sequence?

for example [2,3,3,3,4,5,6] is a straight but does not have 5 sequential numbers?[/QUOTE]

It will detect it correctly as a straight. The repeated application of "|" (or) operator on the same bit will not cause any problem.

EDIT:- Sample code
[code]
function is_straight(v)
{
// v is a vector of card values

var x = 0;
var i;
for(i=0; i < 7; i++)
{
x |= (1 << v[i]); // v[i] is assumed to be between 1 and 13, where 1 = 'A' and 13 = 'K'

if (v[i] == 1) // special check for Ace
x |= (1 << 14);

}
x &= (x << 1) & (x << 2) & (x << 3) & (x << 4);

return (x > 0); // return result
}
[/code]

call with "is_straight([1,2,3,4,5,6,7])"

 fivemack 2012-02-08 13:30

Or you could uniqify (put them into a hash table and then pull out the keys), sort, and if a[x+4] == 4+a[x] then there's a straight from a[x] to 4+a[x].

 Bundu 2012-02-08 21:32

axn that function is amazing, thankyou for posting a great off the cuff working example. It is so good it doesn't even need the array to be sorted, is that intentional or a by product of the bitwise operation?

Sorry for the questions but as a complete novice in javascript the bitwise functionality is beyond me at the moment! But I have begun studying it! So far I have only learned to count in binary but it is a start!

This was my approach so far (just so you know I am actually trying to do some work myself and not just sponging!) which feels positively clumsy compared to yours. My thinking was if I was analysing the hand array I would loop through and at the same time perform counts of the numbers which would allow me to decide if I should check for pairs, trips, quads of full boats. I am only at the beginning but further thinking is laid out below.

[CODE]
<!doctype html>

<style>

</style>

<script type="text/javascript">
// --------------------------------------------------------------------- GLOBAL VARIABLES - SET HERE
outputStr = "+++++++++DEBUG OUTPUT+++++++<br />";
playerhandArray = new Array(2);
communityCardarray = new Array(5);
combinedHandArray = new Array(7);
// --------------------------------------------------------------------- GLOBAL VAR END!

playerhandArray = [2,2];
communityCardarray = [3,5,6,13,14];
combinedHandArray = [2,3,3,4,5,5,14];

//reverse sort the array
function decendSort(arrayNM) {
arrayNM.sort(function(a,b){return b - a});
debugOutput(arrayNM);
};

function checkNumSequnce(arrayNM2) {
seqCounter=1;
acePresent=0;
currentStraightHigh=arrayNM2[0];

repeatArray= new Array(13);
repeatArray= [0,0,0,0,0,0,0,0,0,0,0,0,0,0]
if (arrayNM2[0]==14) {
acePresent=1;
}

// Run through the array and get some info number of sequential increments
for (i=0;i<arrayNM2.length-1;i++) {
j=i+1;
if (arrayNM2[i]- arrayNM2[j] == 1) { // check if the two numbers have 1 difference (straight hands)
seqCounter++;

} else if (arrayNM2[i]- arrayNM2[j] != 0) { // if it was equal to zero we have a repeated number and should do nothing

seqCounter=1; // then we break straight sequences by resetting the seqCounter
currentStraightHigh=arrayNM2[j]; // the currentStraightHigh is therefore the next array element

};

repeatArray[(arrayNM2[i]-1)]++ // This counts the number of instances of each value for pair - quad and fb

debugOutput("Seq: " + seqCounter + " Str+: " + currentStraightHigh + " Rpt Array?: " + repeatArray);
}; // end of for loop

repeatArray[(arrayNM2[i]-1)]++ // --------------------------------------> At this point we should analyse the repeat array

debugOutput("<br />Seq: " + seqCounter + " Str+: " + currentStraightHigh + " Rpt Array?: " + repeatArray);

}; // end of function

</script>

<body>

<div id="outerwrap" class="">
<br />
<br />

<div id="debug"></div>
<br />
</div>

</body>
<script type="text/javascript">

function debugOutput(text) {
outputStr = outputStr + text + "<br />";
document.getElementById('debug').innerHTML = outputStr;
};

if (typeof window.onload != 'function') {
} else {
}
func();
}
}
};

debugOutput(playerhandArray);
debugOutput(communityCardarray);
debugOutput(combinedHandArray);
decendSort(combinedHandArray);
});

checkNumSequnce(combinedHandArray);
});

</script>
</html>
[/CODE]

I saw that [URL="http://www.suffecool.net/poker/evaluator.html"]http://www.suffecool.net/poker/evaluator.html[/URL] this chap seemed to have taken the approach that you guys did (working at the bitwise level and hash tables ). Again knowing that this is currently just outside my grasp (and a suspicion that just copying his work with no thought was just plain cheating!) I was thinking that I would try and eliminate possibilities through quick determinations.

As the link specifies if all possible hands are included (5 cards) then there are 2,598,960 hand combinations of which there are 7,462 distinct hands. Becuase he went with an elimination approach I thought I *could* do the same but using simpler calculations. My theory was get some quick hits ( I am trying to replace a pass and play poker app I used to have access to on my iphone but is not on android that a buddy of mine and i played every lunchtime!):

If the players have the same hands(numerical values) you don't have to compute the numeric values of either hand as we have an instant tie and split pot!*(save calcs). [*However If they have the same hand they could avoid a tie with a flush.]
Flush is an *easy* test as there are only 4 suits, flush true breaks tie anything else keeps it the nice thing about this is that although flush mechanics are more complex if the players have the same numerically valued hands the finer flush mechanics can be ignored as they rely on numeric values of cards!

If the players don't have the same hand then we need to do a little more work as we need to evalute both hands so in the code above I thought the "repeatArray" would quickly tell me if quads or full boats were possible (don't bother testing for anything below which elminates flushes and below).
Check each hand for straights and flushes (eliminate below if found)
Then check for trips (elminate below)... and so on

I realise now that my approach involves a lot more logic and will possibly be more computationally intensive which is a bad thing!

So I will persevere for now with what I can and as I learn the bitwise element I should be able to potentially improve my code later!

 Bundu 2012-02-08 21:34

fivemack as per my post above hash tables are a little beyond me at the moment! but again you seem to have intuitively pointed to an optimal solution which sadly is a little outside my skill base at the moment but thank you too!

 Bundu 2012-02-08 21:39

If anyone is interested here was my attempt at flush determination! I thought it was only fair to post my work

[CODE]
<!doctype html>

<style>

<script type="text/javascript">

newline = "<br />"

tc1 = document.getElementById('topC1')
tc2 = document.getElementById('topC2')

tabc1 = document.getElementById('tableC1')
tabc2 = document.getElementById('tableC2')
tabc3 = document.getElementById('tableC3')
tabc4 = document.getElementById('tableC4')
tabc5 = document.getElementById('tableC5')

bc1 = document.getElementById('botC1')
bc1 = document.getElementById('botC2')

//This generates the card array obtained from http://mickweb.com/javascript/arrays/userDefinedSortingArrays4.html
A= new Array();

S = ["h","d","c","s"];
N = [2,3,4,5,6,7,8,9,10,11,12,13,14];

for(var j=0;j<S.length;j++){
for(var i=0;i<N.length;i++){
A[A.length]=S[j]+N[i];
}
}

// Here is a shuffler by/at: + Jonas Raoni Soares Silva + http://jsfromhell.com/array/shuffle [rev. #1]
shuffle = function(v){
for(var j, x, i = v.length; i; j = parseInt(Math.random() * i), x = v[--i], v[i] = v[j], v[j] = x);
return v;
};

function init() {
document.getElementById('startdeck').innerHTML="The Deck is currently stacked like this: " + A;
document.getElementById('shuffleddeck').innerHTML="The Deck has been shuffled to: " + shuffle(A);

player1Hand= A[0] + ", " + A[2];
player2Hand= A[1] + ", " + A[3];
theFlop= A[4] + ", " + A[5] + ", " + A[6];
theTurn= A[7]
theRiver= A[8]

document.getElementById('predeal').innerHTML="SKULL will have: " + player1Hand + "<br />The Flop: " + theFlop + ", " + theTurn + ", " + theRiver + "<br />BUNDU will have: " + player2Hand;

//CREATE ARRAYS FOR HANDS AND FLOPS AND COMBINED STRIPPING OUT NUMERICAL CARD VALUE ONLY
numP1 = [A[0].substring(1),A[2].substring(1)]
suiP1 = [A[0].substring(0,1),A[2].substring(0,1)]
numP1.sort(function(a,b){return a - b});

numP2 = [A[1].substring(1),A[3].substring(1)]
suiP2 = [A[1].substring(0,1),A[3].substring(0,1)]
numP2.sort(function(a,b){return a - b});

numFlop = [A[4].substring(1),A[5].substring(1),A[6].substring(1),A[7].substring(1),A[8].substring(1)];
suiFlop = [A[4].substring(0,1),A[5].substring(0,1),A[6].substring(0,1),A[7].substring(0,1),A[8].substring(0,1)];
numFlop.sort(function(a,b){return a - b});

numLongP1 = [A[0].substring(1),A[2].substring(1),A[4].substring(1),A[5].substring(1),A[6].substring(1),A[7].substring(1),A[8].substring(1)];
suiLongP1 = [A[0].substring(0,1),A[2].substring(0,1),A[4].substring(0,1),A[5].substring(0,1),A[6].substring(0,1),A[7].substring(0,1),A[8].substring(0,1)];
numLongP1.sort(function(a,b){return a - b});

numLongP2 = [A[1].substring(1),A[3].substring(1),A[4].substring(1),A[5].substring(1),A[6].substring(1),A[7].substring(1),A[8].substring(1)];
suiLongP2 = [A[1].substring(0,1),A[3].substring(0,1),A[4].substring(0,1),A[5].substring(0,1),A[6].substring(0,1),A[7].substring(0,1),A[8].substring(0,1)];
numLongP1.sort(function(a,b){return a - b});

suitcounterp1(suiLongP1, 1);
suitcounterp2(suiLongP2, 2);

document.getElementById('debug').innerHTML=numP1 + "<br />" + suiP1 + "<br />" + numFlop + "<br />" + suiFlop + "<br />" + numLongP1 + "<br />" + suiLongP1 + "<br />" + flush1 + "<br />" + flush2;
}

function suitcounterp1(passedArray, player) {
var s1,s2,s3,s4,i;
s1=0;
s2=0;
s3=0;
s4=0;
flush1 = "Player " + player + " has no Flush";
for (i=0; i< passedArray.length; i++) {
switch (passedArray[i]) {
case "h": s1++; break;
case "d": s2++; break;
case "c": s3++; break;
case "s": s4++; break;
default:
}
}

//alert (s1 + "," + s2 + "," + s3 + "," + s4)
if (s1>4 || s2>4 || s3>4 || s4>4) {
flush1 = "Player " + player + " has a Flush!";
}
}

function suitcounterp2(passedArray, player) {
var s1,s2,s3,s4,i;
s1=0;
s2=0;
s3=0;
s4=0;
flush2 = "Player " + player + " has no Flush";
for (i=0; i< passedArray.length; i++) {
switch (passedArray[i]) {
case "h": s1++; break;
case "d": s2++; break;
case "c": s3++; break;
case "s": s4++; break;
default:
}
}

//alert (s1 + "," + s2 + "," + s3 + "," + s4)
if (s1>4 || s2>4 || s3>4 || s4>4) {
flush2 = "Player " + player + " has a Flush!";
}
}

</script>

<body>

<div id="outerwrap" class="">
<br />
<br />
<div id="startdeck"></div>
<div id="shuffleddeck"></div>
<div id="predeal"></div>
<div id="allcards1"></div>
<div id="debug"></div>
<br />

</div>

</body>

</html>
[/CODE]

 Dubslow 2012-02-08 22:39

[QUOTE=Bundu;288662]
Sorry for the questions but as a complete novice in javascript the bitwise functionality is beyond me at the moment! But I have begun studying it! So far I have only learned to count in binary but it is a start![/QUOTE]
Do you mean that you're not familiar with bitwise operations in general, or just how to do them in JavaScript? If it's the former, I recommend [url=http://www.cprogramming.com/tutorial/bitwise_operators.html]this page[/url], which provides an introduction to bitwise operators in C/C++. That's the syntax that axn used in his initial example. It's not JavaScript, but it's a really nice intro to bitwise operations in general. A quick Google shows [url=https://developer.mozilla.org/en/JavaScript/Reference/Operators/Bitwise_Operators]this[/url] for JavaScript, though I'm not sure how good of a tutorial it is, never having used it before. Maybe just read both and see what you learn.

 Bundu 2012-02-08 23:12

[QUOTE=Dubslow;288666]Do you mean that you're not familiar with bitwise operations in general, or just how to do them in JavaScript? [/QUOTE]

It is the former so I will read and inwardly digest the info on links you have provided, thank you.

Yes! :bow:

 Bundu 2012-02-08 23:14