Page 1 of 1

Logic Question

Posted: Thu Aug 26, 2004 12:03 pm
by Burrito
I am creating a tournament application for Unreal Tournament 2004 and I am getting stumped on a logic issue.

I have a teams table that consists of the team names and some other info not important for this issue. Right now I'm just working with 8 teams total. I have a select that grabs all of the team names from the table and my issue comes when I'm looping over the names.

I'm trying to create a graphical bracket system that lists out all of the teams and the different rounds (nothing fancy here)...unfortunately I'm already stuck on the first round :(.

I have set up a counter so I can list the game number for each game to be played and I add to it on each iteration of the loop. For eight teams there should be 4 games total...this is where my feeble brain gets lost. Of course with 8 teams in the db, my counter adds up to 8.

what I want is something like this:

Team1
Game 1
Team2

Team3
Game2
Team4

etc.

I'm just doing the graphical brackets using html tables. I've thought about doing some kind of query inside my loop and limiting the results to two for each team, but didn't get very far with that idea. So I started thinking it might be easier to just change the counter somehow (cut it in half), but no idea how to do that.

I hope this is enough information to explain what I"m trying to do, if now let me know and I'll clarify more.

thanks for your time,

Burr

Posted: Thu Aug 26, 2004 12:48 pm
by timvw
start from the beginning

0 teams -> 0 match
1 team -> 0 match
2 teams -> 1 match
4 teams -> 2 * 1 matches
8 teams -> 4 * 2 * 1 matches
16 teams -> 8 * 4 * 2 * 1 matches

Thus, with n teams, you end up with (n/2) * (n/4) * ... * (n/n) matches.
In case n is not a power of 2, you will have to insert some BYE teams.

Now, if you need to display 1 match, you need 3 rows.
Thus, if you have x matches, you need 3 * x rows.

With 0 rounds, you need 1 column
With one round, you need 1+1 column.
With 2 rounds, you need 2+1 columns.
With y rounds, you need y+1 columns.

The easiest way to find y, is to count how many times you cant count the number of teams by 2.

Posted: Thu Aug 26, 2004 1:42 pm
by Burrito
ok, I'm not understanding this at all, I've tried about 20 different formulas with what you posted, and none of them are providing me with what I need. **Note: I must make this more clear, my brain is feeble and I need things hand fed to me...so sorry that I'm not catching on.

here is the last thing I tried which gave me 8 for the game number for everyone....after doing the math myself even I could figure that one out, but I can't seem to get a grasp on how I need to do this. Also I can't figure out how I'm going to get an odd number using the info you provided (ie 3 and 5 and 7).

here is the code:

Code: Select all

<?
	$counter = 4*2*1;
	while($team = mysql_fetch_assoc($gteam))&#123;
	$counter = ($counter / 2) * ($counter / 4) * ($counter / 8);
	?>
		<tr class="name">
		<td align="left" valign="center" width="100%"><?=$team&#1111;"teamname"];?></td>
		<td align="left" valign="center" width="100%">&nbsp;</td>
		</tr>

		 <tr class="blank">
		 <td align="center" valign="center">&nbsp; <b>Game <?=$counter;?></b></td>
		 <td align="left" valign="center" class="name">&nbsp;</td>
		 </tr>
 
		
	
	<? 	&#125; // end while loop for result set ?>
which brings me to my next problem. Assuming I could get that to work correctly, I need an extra table row after the first game, and I don't want the game to be shown for every record in the database. In other words, (if I could get the formula right) it would look like this:

Team1
Game1
Team2
Game1
Team3
Game2
Team4
Game2

etc.

so after I get the formula working right, I need to be able to kill that second mention of each game and also insert another row.

you can check out the actual page I"m working on here:
http://www.burritostand.com/tournament/ ... s.php?id=1

thanks again for your help.

Burr

Posted: Thu Aug 26, 2004 3:34 pm
by McGruff
Let's say the teams collection is an array.

array_shift() a team off the array.

Loop through the array, pairing each array value with the team you shifted off.

Repeat until count($array) == 1.

I'd stick that in a class, with an iterator interface, for example:

Code: Select all

$matches =& new Pairs($teams);
$matches->prepare();

while($matches->isValid())
{
     // do something with $matches->next();
}
Maybe add some checks for the Pairs class array parameter:
(a) count($teams) is a multiple of two
(b) count($teams) is at least two

As it happens I was curious enough to knock something up. It's not the last word (prepare() should maybe be refactored) but it works.

Code: Select all

/*
    CLASS Pairs

    Get unique pairs from a collection of values.
*/
class Pairs 
{
    var $i = 0;
    var $pairs = array();
    var $collection;

    /*
        param (array)
    */
    function Pairs($collection)
    {
        $this->collection = $collection;
    }

    function prepare() 
    {        
        if($this->_checkCollection())
        {
            $this->_setPairs();
            $this->element = each($this->pairs);
        
        } else {
        
            $this->element = false;
        }
        reset($this->pairs);
    }
    
    /*
        return (bool)
    */
    function isValid()
    {
        return ($this->element !== false);
    }

    /*
        return (array)
    */
    function next() 
    {
        $this->element = each($this->pairs);
        return $this->element['value'];
    }
    
    //////////////////////////////////////////
    //              PRIVATE                 //
    //////////////////////////////////////////
    
    /*
        return (bool)
    */
    function _checkCollection() 
    {
        $num_elements = count($this->collection);
        
        if($num_elements > 1 and $num_elements % 2 == 0)
        {
            return true;
        
        } else {
        
            return false;
        }
    }
    
    /*
        build an array of unique $collection pairs
    */
    function _setPairs()
    {
        while($current = array_shift($this->collection))
        {
            foreach($this->collection as $value)
            {
                $this->pairs[$this->i][] = $current;
                $this->pairs[$this->i][] = $value;
                $this->i++;
            }
            if(count($this->collection) == 1)
            {
                break;
            }
        }
    }


}
///////////////
// END CLASS //
///////////////
The unit test (using SimpleTest - see link below). I strongly recommend you look at SimpleTest if you aren't already one of the test-infected.

Code: Select all

require_once('lib/simpletest/unit_tester.php');
require_once('lib/simpletest/reporter.php');

include('lib/iterators/pairs.php');

class TestOfPairs extends UnitTestCase 
{
    function TestOfPairs() 
    {
        $this->UnitTestCase();
    }

    function testValidCollection() 
    {
        $collection = array('a', 'b', 'c', 'd');
        $pairs =& new Pairs($collection);
        $pairs->prepare();
        $this->assertTrue($pairs->isValid());
        $this->assertEqual($pairs->next(), array('a', 'b'));
        $this->assertEqual($pairs->next(), array('a', 'c'));
        $this->assertEqual($pairs->next(), array('a', 'd'));
        $this->assertEqual($pairs->next(), array('b', 'c'));
        $this->assertEqual($pairs->next(), array('b', 'd'));
        $this->assertEqual($pairs->next(), array('c', 'd'));
        $pairs->next();
        $this->assertFalse($pairs->isValid());
    }

    function testInValidCollectionWithCountLessThanTwor() 
    {
        $collection = array('a');
        $pairs =& new Pairs($collection);
        $pairs->prepare();
        $this->assertFalse($pairs->isValid());
    }

    function testInValidCollectionWithOddMemberCount() 
    {
        $collection = array('a', 'b', 'c');
        $pairs =& new Pairs($collection);
        $pairs->prepare();
        $this->assertFalse($pairs->isValid());
    }


}

$test =& new TestOfPairs();
$test->run(new HtmlReporter());

Posted: Thu Aug 26, 2004 3:55 pm
by Burrito
holy smokes! thanks for whipping that up. I tried your link and couldn't find the sample anywhere, can you give me a more precise link so I don't have to search for it?

In the mean time, I just hard coded something in to make it work for now:

It's ugly, but it's getting the job done:

Code: Select all

<?php
if($counter == 1){ $sh="Game 1";
}else if($counter == 2 || $counter == 4 || $counter == 6 || $counter == { $sh = ""; 
}else if($counter == 3){$sh = "Game 2";
}else if($counter == 5){$sh = "Game 3";
}else if($counter == 7){$sh = "Game 4";

}
?>
I'd like to use something more "dynamic" so I don't have to hard code for every different option (different rounds, different number of teams etc) but your code is a little too much for me to digest. I don't mind using it, but I'm gonna need some guidance as to exactly how.

You can see it working the way I've done it here:

http://www.burritostand.com/tournament/ ... s.php?id=1

thx again,

Burr

Posted: Thu Aug 26, 2004 6:32 pm
by McGruff
Creating combinations as iterators is something I've had to use a bit in the past, although not this particular "pairs" method. I was curious to see how it would pan out at the same time as doing a bit of OOP / unit testing cheerleading.

The Pairs class will return unique pairs for all the members of the $collection arg. You don't need to know how the class works to use it - just the interface (see first php block in my last post). Try print_r($matches->next()); in the while loop to see what's going on. If the array arg has less than one element or the number of elements is not divisible by two, nothing happens since isValid() always returns false.

I forgot all about the rounds though...

With all the workings encapsulated behind a class, code becomes more focussed and easier to read - not to mention easier to debug. If you also unit test classes, this drastically reduces the amount of time you spend debugging in any case. It takes a bit of getting used to but trust me: it's much more simple than it looks.

The lastcraft.com link was working when I checked.

Posted: Thu Aug 26, 2004 6:38 pm
by Burrito
Thanks Crimedog...I'll play around with it a bit and see if I can get it going.

Burr