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($path, 0, 1);
for ($j = 1; $j < strlen($path); $j++)
{
$to = substr($path, $j, 1);
$min = distance($map, $from, $to, 0, $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 __construct()
{
$this->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, $j, 1);
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 __construct()
{
$this->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'], $j, 1) . ' ';
}
print $best['len'];
//print "\n ** " . $time_start . ' --- ' . microtime();
?>
Back to results
|
|
