Code of bas
<?php
/*
* This code is (C) 2003 by B. Huisman, Appsource
*
* reproduction in any form is prohibited without explicit concent of the author
*
*/
// -----------------------------------------------------------------------------
define('TIMELIMIT',59);
define('FANCY',false);
// map.txt defines
define('MAP_TXT_FILENAME','map.txt');
define('MAP_TXT_FROM',0);
define('MAP_TXT_DISTANCE',1);
define('MAP_TXT_TO',2);
define('MAP_TXT_ROUNTE_TYPE',3);
define('MAP_TXT_TWO_WAY_ROUTE',2);
// -----------------------------------------------------------------------------
// dest.txt defines
define('DEST_TXT_FILENAME','dest.txt');
// -----------------------------------------------------------------------------
function addmap($from,$to,$distance)
{
global $map,$dest,$mapsources,$mapdestinations,$maxdistance;
$from = strtoupper($from);
$to = strtoupper($to);
if (!in_array($from,$mapsources)) $mapsources[] = $from;
if (!in_array($to,$mapdestinations)) $mapdestinations[] = $to;
if (!in_array($from,$dest)) $dest[] = $from;
if (!in_array($to,$dest)) $dest[] = $to;
if ((!isset($map[$from][$to])) || ($distance < $map[$from][$to])) $map[$from][$to] = $distance;
if ($distance > $maxdistance) $maxdistance = $distance;
};
// -----------------------------------------------------------------------------
$dest = Array();
$mapsources = Array();
$mapdestinations = Array();
$maxdistance = 0;
$starttime = time();
//echo 'Reading map ('.MAP_TXT_FILENAME.')...';
$map = Array();
if ($maptxt = @file(MAP_TXT_FILENAME))
{
foreach ($maptxt as $destination)
{
$temp = explode(' ',trim($destination));
addmap($temp[MAP_TXT_FROM],$temp[MAP_TXT_TO],$temp[MAP_TXT_DISTANCE]);
if ($temp[MAP_TXT_ROUNTE_TYPE] == MAP_TXT_TWO_WAY_ROUTE) addmap($temp[MAP_TXT_TO],$temp[MAP_TXT_FROM],$temp[MAP_TXT_DISTANCE]);
};
};
if (!count($map)) die('cannot read '.MAP_TXT_FILENAME.', read 0 map-points'."\n");
ksort($map);
foreach ($map as $key => $val) asort($map[$key]);
//echo 'map read, sources:'.implode($mapsources,',').' dests:'.implode($mapdestinations,',')."\n";
// -----------------------------------------------------------------------------
//echo 'Reading route ('.DEST_TXT_FILENAME.')...';
$dest = Array();
if ($desttxt = @file(DEST_TXT_FILENAME)) $dest = explode(' ',trim(reset($desttxt)));
foreach($dest as $key => $temp) $dest[$key] = strtoupper($temp);
if (!count($dest)) die('cannot read '.DEST_TXT_FILENAME.' read 0 route points'."\n");
//echo 'route read, '.implode($dest,',').' (count='.count($dest).')'."\n";
// -----------------------------------------------------------------------------
/*
echo 'Map:'."\n";
foreach ($map as $from => $destinations)
{
foreach($destinations as $to => $distance)
echo $from.'->'.$to.' d='.$distance."\n";
};
echo 'Route:'."\n";
echo implode($dest,'>')."\n";
*/
// -----------------------------------------------------------------------------
function calcdistance($from,$to)
{
global $map,$mapsources,$mapdestinations;
if ((in_array($from,$mapsources)) && (in_array($to,$mapdestinations)))
{
$closed = Array($from => 0);
$open = $map[$from];
while (count($open) > 0)
{
// echo 'closed:';print_r($closed);
// echo 'open:';print_r($open);
asort($open);
reset($open);
while (!isset($map[key($open)]))
{
if (next($open) === false) die('cannot expand $open, $from='.$from.',$to='.$to."\n");
};
$closed[$new_node = key($open)] = current($open);
if ($new_node == $to) return $closed[$new_node];
unset($open[$new_node]);
// echo 'we now know the distance to node '.$new_node.' d='.$closed[$new_node]."\n";
foreach ($map[$new_node] as $next_node => $next_distance)
{
// if (isset($closed[$next_node])) continue;
if (array_key_exists($next_node,$closed)) continue;
if (array_key_exists($next_node,$open))
{
if ($open[$next_node] > ($closed[$new_node] + $next_distance))
{
$open[$next_node] = $closed[$new_node] + $next_distance;
};
}
else {
$open[$next_node] = $closed[$new_node] + $next_distance;
};
};
};
die('did not find a route to the destination, node '.$to."\n");
}
else die('cannot start from node '.$from.' or route to node '.$to."\n");
};
// -----------------------------------------------------------------------------
$destmap = Array();
foreach ($dest as $d1)
{
$dest2 = $dest;
foreach ($dest2 as $d2)
{
if (($d2 == $d1)|| (!in_array($d1,$mapsources)) || (!in_array($d2,$mapdestinations)))
{
$destmap[$d1.$d2] = $maxdistance * 10;
}
else {
$destmap[$d1.$d2] = calcdistance($d1,$d2);
};
};
};
ksort($destmap);
//foreach ($destmap as $key => $val) asort($destmap[$key]);
//print_r($destmap);
$sol = $dest;
$solsize = count($sol);
$length = calcsollength($sol);
$bestsol = $sol;
$bestlength = $length;
// -----------------------------------------------------------------------------
function calcsollength($sol)
{
global $destmap;
$length = 0;
end($sol);
$lastkey = key($sol);
foreach($sol as $key => $node)
{
if ($key != $lastkey)
{
$nnode = $sol[$key+1];
$length += $destmap[$node.$nnode];
};
};
return $length;
};
function printsol($sol,$length)
{
echo implode($sol,' ').' '.$length;
};
function makeprop()
{
global $sol,$destmap,$solsize,$length;
//while ((($plek1 = rand(0,$solsize-1)) == ($plek2 = rand(0,$solsize-1))) || (abs($plek1 - $plek2) == 1));
while (($plek1 = rand(0,$solsize-1)) == ($plek2 = rand(0,$solsize-1)))
$change = 0;
if (abs($plek1 - $plek2) > 1)
{
if ($plek1 == 0)
{
$change -= $destmap[$sol[$plek1].$sol[$plek1+1]];
$change += $destmap[$sol[$plek2].$sol[$plek1+1]];
}
elseif ($plek1 == ($solsize-1))
{
$change -= $destmap[$sol[$plek1-1].$sol[$plek1]];
$change += $destmap[$sol[$plek1-1].$sol[$plek2]];
}
else {
$change -= $destmap[$sol[$plek1-1].$sol[$plek1]];
$change += $destmap[$sol[$plek1-1].$sol[$plek2]];
$change -= $destmap[$sol[$plek1].$sol[$plek1+1]];
$change += $destmap[$sol[$plek2].$sol[$plek1+1]];
};
if ($plek2 == 0)
{
$change -= $destmap[$sol[$plek2].$sol[$plek2+1]];
$change += $destmap[$sol[$plek1].$sol[$plek2+1]];
}
elseif ($plek2 == ($solsize-1))
{
$change -= $destmap[$sol[$plek2-1].$sol[$plek2]];
$change += $destmap[$sol[$plek2-1].$sol[$plek1]];
}
else {
$change -= $destmap[$sol[$plek2-1].$sol[$plek2]];
$change += $destmap[$sol[$plek2-1].$sol[$plek1]];
$change -= $destmap[$sol[$plek2].$sol[$plek2+1]];
$change += $destmap[$sol[$plek1].$sol[$plek2+1]];
};
}
else {
if ($plek1 > $plek2)
{
$plek1 = $plek2;
$plek2 = $plek1+1;
};
$change -= $destmap[$sol[$plek1].$sol[$plek2]];
$change += $destmap[$sol[$plek2].$sol[$plek1]];
if ($plek1 == 0)
{
$change -= $destmap[$sol[$plek2].$sol[$plek2+1]];
$change += $destmap[$sol[$plek1].$sol[$plek2+1]];
}
elseif ($plek2 == ($solsize-1))
{
$change -= $destmap[$sol[$plek1-1].$sol[$plek1]];
$change += $destmap[$sol[$plek1-1].$sol[$plek2]];
}
else {
$change -= $destmap[$sol[$plek2].$sol[$plek2+1]];
$change += $destmap[$sol[$plek1].$sol[$plek2+1]];
$change -= $destmap[$sol[$plek1-1].$sol[$plek1]];
$change += $destmap[$sol[$plek1-1].$sol[$plek2]];
};
};
return Array($plek1,$plek2,$change);
};
//echo 'destmap:';
//print_r($destmap);
//$length = calcsollength();
$count = 0;
$starttemp = $maxdistance * 1.3;
$temperature = $starttemp;
$proppersec = 0;
while ($temperature >= 0)
{
static $time;
if (!($count % 1000))
{
if (($starttime + TIMELIMIT) <= time()) break;
$temperature = round((float)($starttime + TIMELIMIT - time()) * $starttemp / (float) TIMELIMIT);
static $time2;
if (time() != $time2)
{
$time2 = time();
$proppersec = $count;
$count = 0;
};
if (FANCY) echo 'temp='.$temperature.' length='.$length.' speed='.$proppersec.' bestlength='.$bestlength.' $sol='.implode($sol,' ').' $best='.implode($bestsol,' ')."\r";
};
$count++;
list($plek1,$plek2,$change) = makeprop();
if (($change < $temperature) || (($length+$change) < $bestlength))
{
$temp = $sol[$plek1];
$sol[$plek1] = $sol[$plek2];
$sol[$plek2] = $temp;
$length += $change;
if ($length < $bestlength)
{
$bestsol = $sol;
$bestlength = $length;
};
};
if ($length != calcsollength($sol)) die('FATAL: error in length'."\n");
};
if (FANCY) echo "\n";
if ($bestlength != calcsollength($bestsol)) die('FATAL: final route is invallid');
printsol($bestsol,calcsollength($bestsol));
echo "\n";
php?>
Back to results
|
|
