Code of matteo
<?php

/*********************************************************/ 
/* Pizza Dude (B4) PHP-Editors.com Coding Contest        */ 
/* (C) 2003 Matteo Beccati <matteo@beccati.com>          */ 
/*********************************************************/ 



// Initialize needed vars
$routes = array();
$dest '';
$mappoints = array();
$cache = array();


// Read map routes
$fp = @fopen('map.txt''r');
while (
$buf = @fgets($fp4096))
{
    
preg_match('/^([A-Z]) +([0-9]+) +([A-Z]) +([12])/'strtoupper(trim($buf)), $matches);
    if (
count($matches) == 5)
    {
        
$c $matches[1]; // Source
        
$d $matches[3]; // Destination
        
        // Store existing points 
        
$mappoints[$c] = '';
        
$mappoints[$d] = '';
        
        
// Set cost to -1 if not visited
        
if (!isset($routes[$c][$d])) $routes[$c][$d] = -1;
        
        
// Use this distance if not visited or shorter
        
if ($routes[$c][$d] == -|| $routes[$c][$d] > (int)$matches[2])
            
$routes[$c][$d] = (int)$matches[2];
        
        
// Check for 2-way route
        
if ($matches[4] == 2)
        {
            
// Set cost to -1 if not visited
            
if (!isset($routes[$d][$c])) $routes[$d][$c] = -1;
            
            
// Use this distance if not visited or shorter
            
if ($routes[$d][$c] == -|| $routes[$d][$c] > (int)$matches[2])
                
$routes[$d][$c] = (int)$matches[2];
        }
    }
}
fclose($fp);


// Read destinations
$dest preg_replace('/[^A-Z]/'''strtoupper((join('', @file('dest.txt')))));

// Clean up useless destinations and create shortest path table
$mappoints array_keys($mappoints);
$dest destClean($dest$mappoints);
dijkstra($mappoints);

// Solve the puzzle and print the result
solve();
exit;


function 
destClean($dest$m)
{
    
$d $dest;
    
$m join(''$m);
    
    
$d preg_replace('/[^'.$m.']/'''$d);
    
    if (!
strlen($d)) return $dest;
    
    return 
$d;
}

function 
solve()
{
    global 
$dest;
    
    
// Solve puzzle
    
list ($path$score, ) = start($dest);
    
    
// Strip not destination points and create an array
    
$path preg_split('//'preg_replace('/([^'.$dest.'])/'''$path), -1PREG_SPLIT_NO_EMPTY);
    
    
$path2 = array();
    foreach (
$path as $v)
    {
        if (!
array_key_exists($v$path2))
            
$path2[$v]  = $v;
    }
    
    
// Final output
    
echo join(' '$path2).' '.$score;
}

function 
start($dest$done ''$distance 0$score 0)
{
    global 
$routes$cache;
    
    
$len strlen($dest);
    if (!
$len)
    {
        
// All destinations are reached, finishing
        
        
return array($done$distance$score);
    }
    
    
// Initialize best route vars
    
$d 0;
    
$s 0;
    
$r '';
    
    
// Last visited (current) point
    
$last strlen($done) ? substr($done, -1) : '';
    
    if (
$last && !array_key_exists($last$routes))
    {
        
// Point has no routes
        
return array($done$distance$score);
    }
    
    
    if (
array_key_exists($last.'-'.$dest$cache))
    {
        
// Loading path from cache
        
list($d$r$s) = $cache[$last.'-'.$dest];
    }
    else
    {
        
// Try all the destinations
        
for ($i 0$i $len$i++)
        {
            
$current $dest{$i};
            
            if (!
$last || array_key_exists($current$routes[$last]))
            {
                
// Route found
                
                
if (!$last)
                {
                    
// Starting point, recursion
                    
list ($cr$cd$cs) = start(
                        
str_replace($current''$dest),
                        
$current,
                        
$distance,
                        
$score 1);
                }
                else
                {
                    
// Strip non-destination points
                    
$ndest preg_replace('/['.$routes[$last][$current]['path'].']/'''$dest);
                    
                    
// Recurse
                    
list ($cr$cd$cs) = start(
                        
$ndest,
                        
$done.$routes[$last][$current]['path'],
                        
$distance $routes[$last][$current]['dist'],
                        
$score strlen($dest) - strlen($ndest));
                }
                
                if (!
$d || $cs $s || ($cs == $s && $cd $d))
                {
                    
// Best route found
                    
$d $cd;
                    
$r $cr;
                    
$s $cs;
                    
                    
// Store it in cache
                    
$cache[$last.'-'.$dest] = array($d$r$s);
                }
            }
        }
    }
    
    if (!
$d$d $distance;
    if (!
$r$r $done;
    if (!
$s$s $score;
    
    return array(
$r$d$s);
}

function 
dijkstra($mappoints)
{
    global 
$routes;

    
sort($mappoints);
    
$mappoints join(''$mappoints);
    
$mappointslen strlen($mappoints);
    
    
// Create weighted map
    
for ($x 0$x $mappointslen$x++)
    {
        
$c $mappoints{$x};
        
        for (
$y 0$y $mappointslen$y++)
        {
            
$d $mappoints{$y};
            
            if (
$x == $y)
                
// Set self-path to 0 in the weigthed map
                
$wmap[$c][$d] = 0;
            elseif (isset(
$routes[$c][$d]))
                
// Set direct routes in the weighted map
                
$wmap[$c][$d] = $routes[$c][$d];
            else
                
// Initialize to -1
                
$wmap[$c][$d] = -1;
        }
    }
    
    for (
$x 0$x $mappointslen$x++)
    {
        
$c $mappoints{$x};
        
        for (
$y 0$y $mappointslen$y++)
        {
            
$d $mappoints{$y};
            
            
$spw[$d] = -1;
            
$sp[$d][0] = '';
        }
            
        for (
$y 0$y $mappointslen$y++)
        {
            
$d $mappoints{$y};
            
            if (
$wmap[$c][$d] != -1)
            {
                
$sp[$d][0] = $d;
                
$sp[$d][1] = '';
                
$spw[$d] = $wmap[$c][$d];
            }
        }

        
$changed true;
        
        while (
$changed)
        {
            
$changed false;
            
            for (
$y 0$y $mappointslen$y++)
            {
                
$d $mappoints{$y};
                
                
$i 0;
                while(
$sp[$d][$i] != ''$r $sp[$d][$i++];
            
                if (
$sp[$d][0] != '')
                for (
$z 0$z $mappointslen$z++)
                {
                    
$e $mappoints{$z};
                    
                    if (
$wmap[$d][$e] >= 0)
                        if (
$spw[$d] + $wmap[$d][$e] < $spw[$e] || $spw[$e] == -1)
                        {
                            
$i 0; while($sp[$d][$i] != ''$sp[$e][$i] = $sp[$d][$i++];
                            
$sp[$e][$i++] = $e
                            
$sp[$e][$i] = '';
                            
$spw[$e] = $spw[$d] + $wmap[$d][$e];
                            
$changed true;
                        }
                }
            }
        }
        
        
        
// Rewrite original routes using shortest paths
        
for ($y 0$y $mappointslen$y++)
        {
            
$path '';
            
$d $mappoints{$y};
            
            
$i 0;
            while(
$sp[$d][$i] != '')
                
$path .= $sp[$d][$i++];
            
            if (
$spw[$d] > -1)
                
$routes[$c][$d] = array('path' =>$path'dist' => $spw[$d]);
            else
                
// No route
                
unset($routes[$c][$d]);
        }
    }
}

?>


Back to results


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