Code of baggio
<?php


//-------------------------------------------
//
//  the main body is placed at the end of this file!
//
//-------------------------------------------


/********************************************************
*
*  Compute lenghts
*
*********************************************************/

    
function path_length(&$map$path)
    {
        
// compute the length of a path
        // example: $path = 'ALIGB'
        // return array(
        //   'len' => [the length of the path]
        //   'path_short' => [the path! it self]
        //   'path_full' => [the full path whith every step]
        // )
        
$out_short '';
        
$out_full '';
        
$length 0;
        
$from substr($path01);

        for (
$j 1$j strlen($path); $j++)
        {
            
$to substr($path$j1);
            
$min distance($map$from$to0$from);
            
$length += $min['dist'];
            
$out_full .= substr($min['path'], 0, -1);
            
$out_short .= $from;
            
$from $to;
        }
        
$out_full .= $to;
        
$out_short .= $to;

        return Array(
            
'len' => $length,
            
'path_short' => $out_short,
            
'path_full' => $out_full,
        );
    }

    function 
distance(&$map$from$to$old_length$old_path)
    {
        
// compute the total lenght between two points
        
if (!isset ($map[$from]))
        {
            return 
false;
        }
        foreach (
$map[$from] as $dest => $dist)
        {
            if (
$dest == $to)
            {
                return Array(
                    
'dist' => $old_length $dist,
                    
'path' => $old_path $dest,
                );
            }
            if (
strpos($old_path$dest) !== false)
            {
                continue;
            }
            
$cur distance($map$dest$to$old_length $dist$old_path $dest);
            if (
$cur === false)
            {
                continue;
            }
            if ( (!isset (
$min)) or ($min['dist'] > $cur['dist']) ) {
                
$min $cur;
            }
        }
        if (!isset (
$min)) return false;
        return 
$min;
    }




/********************************************************
*
*  Permutations
*
*********************************************************/
    
function &get_best ($dest, &$map)
    {
        
$result null;
        
$v $dest;
        
$n count($v);
        
permute (1$v$n$result$map);
        return 
$result;
    }

    function 
permute ($i, &$v, &$n, &$result, &$map)
    {
        if (
$i == $n)
        {
            
$path implode (''$v);
            
$cur path_length($map$path);
            
//print $cur['len'] . "\t" . $cur['path_short'] . "\t" . $cur['path_full'] . "\n"; // ******* unComment this line to show all FULL PATH tested
            
if ( (!isset($result)) or ($result['len'] > $cur['len']) )
            {
                
$result $cur;
            }
            return;
        }
        for (
$k $i$k $n$k++)
        {
            
$dummy $v[$k];
            
$v[$k] = $v[$i];
            
$v[$i] = $dummy;
            
permute ($i+1$v$n$result$map);
            
$dummy $v[$k];
            
$v[$k] = $v[$i];
            
$v[$i] = $dummy;
        }
    }



/********************************************************
*
*  ClassPizzaDest
*
*********************************************************/
    
class ClassPizzaDest
    
{
        function 
ClassPizzaDest()
        {
        }

        function &
get($filename)
        {
            
$d =& ClassPizzaDest::load ($filename);
            return 
$d;
        }

        function &
load($filename)
        {
            
$f implode (''file ($filename));
            
$f preg_replace ('#[^A-Z]#s'''$f);
            
$f preg_replace ('#[\n\r]#'''$f);
            
$dest = Array();
            for (
$j 0$j strlen ($f); $j++)
            {
                
$cur substr ($f$j1);
                if (
in_array ($cur$dest))
                {
                    continue;
                }
                
$dest[] = $cur;
            }
            unset (
$f);
            return 
$dest;
        }

        function &
toString(&$dest)
        {
            return 
implode (' '$dest);
        }

    } 
// ClassPizzaMap{}


/********************************************************
*
*  ClassPizzaMap
*
*********************************************************/
    
DEFINE ('PIZZA_MAPkey_DIST'0);
    
DEFINE ('PIZZA_MAPkey_DEST'1);
    
DEFINE ('PIZZA_MAPkey_TYPE'2);

    
DEFINE ('PIZZA_1Way'1);
    
DEFINE ('PIZZA_2Way'2);

    class 
ClassPizzaMap
    
{
        function 
ClassPizzaMap()
        {
        }

        function &
get($filename)
        {
            
// load data and perform optimizations
            
$m ClassPizzaMap::load ($filename);
            
$m ClassPizzaMap::remap2to1 ($m);
            
$m ClassPizzaMap::make ($m);
            return 
$m;
        }

        function &
load($filename)
        {
            
// load row data for paths info
            
$f file ($filename);
            
$f preg_replace ('#[^\w]+#s'''$f);
            
$map = array();
            foreach (
$f as $l)
            {
                if (!
$l)
                {
                    continue;
                }
                
preg_match('#([A-Z])\s*(\d+)\s*([A-Z])\s*(1|2)#s'$l$out);
                
$id $out[1];
                
$map[$id][] = array(
                    
PIZZA_MAPkey_DIST => (int)$out[2],
                    
PIZZA_MAPkey_DEST => $out[3],
                    
PIZZA_MAPkey_TYPE => (int)$out[4],
                );
            }
            return 
$map;
        }

        function &
remap2to1(&$themap)
        {
            
// convert "2 way" to two "1 way"
            
$map $themap;
            
$from array_keys($map);
            foreach (
$from as $f)
            {
                foreach (
$map[$f] as $j => $cur)
                {
                    if (@
$cur[PIZZA_MAPkey_TYPE] === PIZZA_2Way)
                    {
                        
$map$cur[PIZZA_MAPkey_DEST] ][] = array(
                            
PIZZA_MAPkey_DIST => $cur[PIZZA_MAPkey_DIST],
                            
PIZZA_MAPkey_DEST => $f,
                        );
                    }
                    unset (
$map[$f][$j][PIZZA_MAPkey_TYPE]);
                }
            }
            return 
$map;
        }

        function &
make(&$themap)
        {
            
// after "remap2to1" there may be "overload" path between two points
            // choose the shortest arcs between two points discarding the others
            // the output is the "matrix of weights"
            
$nodes array_keys($themap);
            
$map = Array();
            foreach (
$nodes as $node)
            {
                
$cur_from =& $themap[$node];
                
$count_dest  count($cur_from);
                for (
$j 0$j $count_dest $j++)
                {
                    
$cur_dest =& $cur_from[$j][PIZZA_MAPkey_DEST];
                    
$cur_dist =& $cur_from[$j][PIZZA_MAPkey_DIST];
                    
$mapxy =& $map[$node][$cur_dest];
                    if (isset(
$mapxy) and ($mapxy <= $cur_dist)) {
                        continue;
                    }
                    
$mapxy $cur_dist;
                }
            }
            return 
$map;
        }

        
/* // only for debug!
        function &toString(&$map)
        {
            $keys = array_keys($map);
            $out = array();
            foreach ($keys as $k)
            {
                $cur_out =& $out[$k];
                $cur_out = '';
                foreach ($map[$k] as $dest => $dist)
                {
                    $cur_out .= ",$dest$dist";
                }
                $cur_out = substr($cur_out, 1);
            }
            return $out;
        }

        function &out(&$map)
        {
            $out = ClassPizzaMap::toString($map);
            $result = '';
            foreach ($out as $k => $s)
            {
                $result .= "\n$k = $s";
            }
            $result .= "\n";
            return $result;
        }
        */

    
// ClassPizzaMap{}






#********************************************************
#*********                *************************************
#*********   M A I N   *************************************
#*********                *************************************
#*********************************************************

//$time_start = microtime ();
$base dirname (__FILE__) . '/';

// load and prepare data
$map =& ClassPizzaMap::get ($base 'map.txt'); // read the input map file and translate it in a more handy/efficient way
$dest =& ClassPizzaDest::get ($base 'dest.txt'); // read the input dest file
$best =& get_best ($dest$map); // calculate all possible (valid) permutations

// display the best
for ($j 0$j strlen($best['path_short']); $j++)
{
    print 
substr($best['path_short'], $j1) . ' ';
}
print 
$best['len'];

//print "\n  ** " . $time_start . ' --- ' . microtime();

?>


Back to results


© Copyright 2003-2014 www.php-editors.com. The ultimate PHP Editor and PHP IDE site.