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_ROUTEaddmap($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 => $valasort($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


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