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($fp, 4096))
{
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] == -1 || $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] == -1 || $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), -1, PREG_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
|
|
