Page 1 of 1

Poker, find all straights in an array

Posted: Mon Feb 09, 2004 1:04 am
by penguinboy
Poker.

I'm trying to write a function that will check an unknown ammout of cards
for an unknown ammout of possibilitys of a straight.

Code: Select all

<?php
$hand	 = array(0=>5,1=>7,2=>10,3=>8,4=>6,5=>10,6=>9);
// card_id=>card_value

// all possible straights from a,2,3,4,5 to 10,j,q,k,a

$straights = array(   // card_values
	array(14,2,3,4,5),
	array(2,3,4,5,6),
	array(3,4,5,6,7),
	array(4,5,6,7,8),
	array(5,6,7,8,9),
	array(6,7,8,9,10),
	array(7,8,9,10,11),
	array(8,9,10,11,12),
	array(9,10,11,12,13),
	array(10,11,12,13,14)
);


//  possible straights for this hand
//  return arrays of card_ids

$return = array(
	array(0,4,1,3,6),  // card values 5,6,7,8,9
	array(4,1,3,6,2),  // card values 6,7,8,9,10
	array(4,1,3,6,5)  // card values 6,7,8,9,10
);
?>
I've struggled with this on and off for about a week.
And I just can't seem to figure out how to tackle this problem.
I've tried several different approaches, but all have failed.
I really want to solve this problem on my own,
but I'm just getting too frustrated.

If anyone can just help lead me in the right direction I'd be very happy.

Posted: Mon Feb 09, 2004 9:26 am
by lazy_yogi
First thing to do would be sort the array, so that this array :

$hand = array(5,7,10,8,6,10,9);

becomes

$hand = array(5,6,7,8,9,10,10);

then loop through each item checking if it is one more than the previous one. If so, increment the row_counter, else set row_counter to zero

when you get to a card that is NOT part of the prev set (ie it isnt one more than previous card), check the set is atleast 5 cards
if so, you have n-5 straights (where n is the length of the run of cards)

lesson: sorting makes many problems much much easier.
And in many cases (such as this) reduces the cost of processing enourmously (in this case it's cost is O(nlogn) for sorting, and O(n) for looping through to find number of straights, so total cost is O(nlogn) which is extremely low)

Posted: Mon Feb 09, 2004 10:28 am
by penguinboy
I've attempted several solutions with sorting,
including the one you provided;
but so far, I could only return:

Code: Select all

<?
array( 
   array(0,4,1,3,6),  // card values 5,6,7,8,9 
   array(4,1,3,6,2));  // card values 6,7,8,9,10
?>
But I need it to return every possible set of cards
that can form a straight.

Code: Select all

<?
array( 
   array(0,4,1,3,6),  // card values 5,6,7,8,9 
   array(4,1,3,6,2),  // card values 6,7,8,9,10 
   array(4,1,3,6,5));  // card values 6,7,8,9,10
?>

Posted: Mon Feb 09, 2004 11:48 am
by ilovetoast
Don't wait on me, but I emailed a friend of mine about this question. He plays alot of online poker and so he wrote an application for tracking his play at multiple sites - a combination packet sniffer and analysis engine. I know he has a this type of straight checking code as we talked about it when he wrote it. If I can get him to fork it over I'll post it here.

Posted: Mon Feb 09, 2004 12:01 pm
by penguinboy
Wow thanks a lot!
This has been driving me crazy!

Posted: Tue Feb 10, 2004 12:25 am
by penguinboy
I found a solution.

Code: Select all

<?php
function check_straight($cards)
{
	$temp = array_unique($cards);
	if(count($temp)<5)
		return 0;
		
	sort($temp);
		
	$unique = array();
	foreach($cards as $card_key => $card_value)
		if(!in_array($card_value,$unique))
			$unique[$card_key] = $card_value;
		else
		{
			$key = array_search($card_value,$unique);
			$dupe[$key] = $card_key;
		}

	
	$straights = array(
		array(14,2,3,4,5),
		array(2,3,4,5,6),
		array(3,4,5,6,7),
		array(4,5,6,7,8),
		array(5,6,7,8,9),
		array(6,7,8,9,10),
		array(7,8,9,10,11),
		array(8,9,10,11,12),
		array(9,10,11,12,13),
		array(10,11,12,13,14)
	);
	
	$off_set = count($temp)-4;
	
	for($i=0;$i<$off_set;$i++)
		foreach ($straights as $sa)
			if($sa[0]==$temp[$i]&&$sa[1]==$temp[$i+1]&&$sa[2]==$temp[$i+2]&&$sa[3]==$temp[$i+3]&&$sa[4]==$temp[$i+4])
				$ga[] = $sa;
	
	foreach($unique as $card_key => $card_value)
		foreach($ga as $key => $array)
			foreach($array as $order => $value)
				if($card_value==$value)
					$return[$key][$order] = $card_key;

	foreach($dupe as $original => $duplicate) 
	   foreach($return as $straight_array) 
	      foreach ($straight_array as $key => $card_id) 
	         if($original==$card_id) 
	         { 
	            $temp = $straight_array; 
	            $temp[$key] = $duplicate; 
	            $return[] = $temp; 
	         }
	         
	print '<pre>';
	print_r($return);
}
?>

Posted: Thu May 13, 2004 6:14 am
by dave420
Sort the array, and see if there are no pairs, then tell if the highest card-lowest card = number of cards. If they do, it's a straight.

Posted: Thu May 13, 2004 7:16 am
by lazy_yogi
Nice one. It's the most obvious solution right under your nose that you can easily miss. Well done.

Posted: Thu May 13, 2004 11:11 am
by dave420
I came up with that solution when I was about 12, writing one of my first windows apps, video poker in visual basic.

Why a 12-year-old would want to write a video poker game is beyond me :-P