Poker, find all straights in an array

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

Post Reply
penguinboy
Forum Contributor
Posts: 171
Joined: Thu Nov 07, 2002 11:25 am

Poker, find all straights in an array

Post 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.
User avatar
lazy_yogi
Forum Contributor
Posts: 243
Joined: Fri Jan 24, 2003 3:27 am

Post 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)
penguinboy
Forum Contributor
Posts: 171
Joined: Thu Nov 07, 2002 11:25 am

Post 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
?>
ilovetoast
Forum Contributor
Posts: 142
Joined: Thu Jan 15, 2004 7:34 pm

Post 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.
penguinboy
Forum Contributor
Posts: 171
Joined: Thu Nov 07, 2002 11:25 am

Post by penguinboy »

Wow thanks a lot!
This has been driving me crazy!
penguinboy
Forum Contributor
Posts: 171
Joined: Thu Nov 07, 2002 11:25 am

Post 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);
}
?>
dave420
Forum Contributor
Posts: 106
Joined: Tue Feb 17, 2004 8:03 am

Post 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.
User avatar
lazy_yogi
Forum Contributor
Posts: 243
Joined: Fri Jan 24, 2003 3:27 am

Post by lazy_yogi »

Nice one. It's the most obvious solution right under your nose that you can easily miss. Well done.
dave420
Forum Contributor
Posts: 106
Joined: Tue Feb 17, 2004 8:03 am

Post 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
Post Reply