Recursion to create possible combinations?

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
loungehead
Forum Newbie
Posts: 2
Joined: Mon Aug 03, 2009 3:37 pm

Recursion to create possible combinations?

Post by loungehead »

I haven't been a member of any development community such as this one in the past, so my apologies for offending anyone by joining with the intentions of asking this question.

I've been wracking my brain for weeks over this problem, trying to attack it from different angles, and everything I've done so far hasn't worked. Basically, I've been working on a game very similar to the board game "Ticket to Ride". If you're not familair with it, here's as much information as you'll need to understand my problem.

The playing area is a map of the US and lower Canada. A number of cities are marked on the map, and there are connections between some cities. Each route has a numeric value ranging from 1 to 6; it's generally an indication of the length of the route. Something between Dallas and Houston might only be 1, whereas something between Portland, OR and Salt Lake City might be 6. The game is played by purchasing these routes which in turn fulfill certain demand cards that provide bonus points. For example, if you have a single line of track that connects Montreal with New Orleans, no matter how convoluted the track is, you could qualify for 13 bonus points.

Here's the problem. At the end of the game, there are some points awarded to the owner of the longest track, and I would like to be able to determine this programmatically. My best guess so far is that this can be done recursively by starting with one route, determining the neighboring cities and whether or not the player owns any of those routes and, if so, moving on to them to continue the cycle until they player is out of routes. Unfortunately, I'm very lost in trying to figure this out. Is there anyone out there who might have an idea what to do here? I'm up for pretty much anything, but the end result needs to be able to:

1. Compile a list of possible combinations, and as a result
2. Identify branching tracks and compensate by building possible combinations with them as well

It's really the branching that gets me. What I mean by this is, if I have a track that connects Denver to Kansas City, and Kansas City to St. Louis, that's worth a total of 6 (4 and 2, respectively). If I also have a track that connects Kansas City to Oklahoma City (worth 2) then I've got a problem. All four cities are on the same circuit, but only a single line can qualify for the longest track; I need to be able to have the program figure out that there are essentially 3 possible combinations and list them so that their overall values can be determined.

If you've made it this far, my thanks to you. Any input on how I can go about this is greatly appreciated.
User avatar
jayshields
DevNet Resident
Posts: 1912
Joined: Mon Aug 22, 2005 12:11 pm
Location: Leeds/Manchester, England

Re: Recursion to create possible combinations?

Post by jayshields »

I don't think I comprehend the problem fully (never heard of the board game - I'm English), but I think it probably ties in with the Travelling salesman problem. From that page you can find links to other things which will probably be of interest, such as:
http://en.wikipedia.org/wiki/Hamiltonian_cycle
http://en.wikipedia.org/wiki/Undirected_graph

After thinking about it a bit more you might need to look at Djikstra's algorithm, and maybe the others on this page:
http://en.wikipedia.org/wiki/Graph_traversal
User avatar
m4rw3r
Forum Commoner
Posts: 33
Joined: Mon Aug 03, 2009 4:19 pm
Location: Sweden

Re: Recursion to create possible combinations?

Post by m4rw3r »

He wanted the longest track (or rather, the track with the most points).
I would have calculated all the possible tracks a user can have (it isn't so expensive) and then use array_reduce or something similar to create a score.

Also, keep in mind that PHP has a maximum function/method nesting of about 100 (I think that is configurable).
That means that you cannot recurse as much as you may want to.

Instead try to loop the graph without calling the method/function:

Code: Select all

 
// create a few objects
$a = new StdClass();
$b = new StdClass();
$c = new StdClass();
$d = new StdClass();
$e = new StdClass();
 
// name them, so we can keep track of them
$a->name = 'a';
$b->name = 'b';
$c->name = 'c';
$d->name = 'd';
$e->name = 'e';
 
// link them together
$a->linked = array($b, $c);
$b->linked = array($a); // an end
$c->linked = array($a, $d, $e);
$d->linked = array($c, $e);
$e->linked = array($c, $d, $a);
 
// create a user
$user = new StdClass();
 
// give the user a few segments
$user->segments = array($a, $c, $d, $e);
 
$paths = array();
 
foreach($user->segments as $seg)
{
    $current_paths = array(array($seg));
    
    // set the next segments to check
    $next = array($seg);
    
    while($current_seg = array_shift($next))
    {
        // loop related
        foreach($current_seg->linked as $s)
        {
            // does the user own it?
            if(in_array($s, $user->segments))
            {
                // yes
                // tell if we used the segment
                $used = false;
                
                // loop all the current paths, and see if we can append it
                foreach($current_paths as $k => $p)
                {
                    // is the last segments the current one?
                    // and the next segment musn't be in the existing path
                    if(end($p) == $current_seg && ! in_array($s, $p))
                    {
                        $tmp = $p;
                        $tmp[] = $s;
                        
                        // does the path exists?
                        if( ! in_array($tmp, $current_paths))
                        {
                            // nope, add it
                            $current_paths[] = $tmp;
                            
                            // we've used it, tell it to add it to the iterate queue
                            $used = true;
                        }
                    }
                }
                
                // was it used? and is it "new"?
                if($used && ! in_array($s, $next))
                {
                    $next[] = $s;
                }
            } // end if
        } // end foreach
    } // end while
    
    // merge the paths into the result variable and calculate the results
    foreach($current_paths as $p)
    {
        // just a generic calculation, creates a path by using the nodes' names
        $paths[] = array_reduce($p, function($b, $a) {return $b . $a->name;});
    }
}
 
print_r($paths);
 
I threw together the code above just for a few minutes of fun coding :)
It works (no guarantees ;)), and will probably give you a bit of inspiration, but it is nowhere near perfect and it doesn't differ between abcd and dcba

A short writeout of the parsing of the "a-tree", what happens during execution

add a
a

add c
a
ac

add d
a
ac
acd

add e
a
ac
acde
ace

add d
a
ac
acde
aced
loungehead
Forum Newbie
Posts: 2
Joined: Mon Aug 03, 2009 3:37 pm

Re: Recursion to create possible combinations?

Post by loungehead »

Thank you both for the replies. m4rw3r, it's going to take me a bit to decipher that (even with your comments - I'm just not familiar yet with some of the things you did with arrays) but I look forward to seeing it in action.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: Recursion to create possible combinations?

Post by VladSun »

Maybe if you "inverse" Dijkstra's algorithm for solving shortest path problem, it will work :)

Try it:
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
http://en.giswiki.net/wiki/Dijkstra's_algorithm#PHP
There are 10 types of people in this world, those who understand binary and those who don't
Post Reply