Code of jeff
<?php
/**********************************************************************
* Forumname: Mr. Sketch
* E-Mail: mr_sketch@xsmail.com
* Full Name: Jeffrey Franklin
*
* Algorithms:
* I first generate a complete graph with the shortest distances from
* each destination node to to each other destination node found via
* standard Breath First Search (BFS) shortest path algorithm. From
* that graph I build a quasi-minimum spanning tree from the shortest
* routes in the complete graph until I can get to every node from a
* given start node via Depth First Search (DFS).
*
* While this is sub-optimal, it will find most of the same solutions
* as my brute force search of all possible combinations so I deem it
* worth submitting. I thought about including the brute force and
* do it on smaller nodes (less than 7 nodes in dest.txt), but this
* seems to work just as well on generic input, but I'm sure that it
* would be possible to specially craft input that would make it perform
* poorly.
*
* However, I only do this algorithm if the brute force method takes
* longer than 40 seconds. I also do this method no matter what, since
* sometimes it finds better paths the brute force (go fiture). So
* I just end up comparing the distances with brute force and which
* ever one is shorter wins.
**********************************************************************/
define("INFINITY", 999999999);
$stime = time();
# Finds shortest distance from $a to $b via BFS
function shortest(&$map, $a, $b, &$path)
{
$v = array();
foreach (array_keys($map) as $k)
$v[$k] = 0;
$q = array($a);
$path = '';
while (count($q))
{
$nodearr = array_shift($q);
$node = $nodearr[0];
if ($node == $b)
{
$path = $nodearr;
break;
}
if (!array_key_exists($node, $map))
continue; // can't go anywhere from here
$v[$node] = 1;
$dests = array();
foreach (array_keys($map[$node]) as $n)
{
if (!array_key_exists($n, $v))
$v[$n] = 0;
if ($v[$n] == 0)
$dests[$n] = $map[$node][$n];
}
if (count($dests) == 0)
continue;
asort($dests);
foreach (array_keys($dests) as $n)
array_push($q, "$n$nodearr");
}
$path = strrev($path);
$dist = 0;
for ($i = 0; $i < strlen($path) - 1; $i++)
$dist += $map[$path[$i]][$path[$i+1]];
// No path between $a and $b
if (count($q) == 0 && strlen($path) == 0)
$dist = INFINITY;
return $dist;
}
function add_edges(&$map, $val, &$ret)
{
$m = INFINITY;
foreach ($map as $a)
foreach ($a as $b)
if ($b > $val)
$m = min($m, $b);
foreach ($map as $k1 => $v1)
foreach ($v1 as $k2 => $v2)
if ($v2 == $m)
$ret[$k1][$k2] = $v2;
return $m;
}
# Finds longest path (node count, not dist) from $a to $b via DFS
function longest(&$map, $a, $b, $exclude, &$path)
{
if ($a == $b)
{
if (strlen($path) < strlen($exclude))
$path = $exclude;
return;
}
if (!array_key_exists($a, $map))
return; // can't go anywhere from here
$nodes = array_keys($map[$a]);
foreach ($nodes as $n)
{
if (strpos($exclude, $n) !== false) continue;
longest($map, $n, $b, "$exclude$n", $path);
}
}
function printresults($path, $dist)
{
echo join(' ', preg_split('//', $path, -1, PREG_SPLIT_NO_EMPTY)) . " $dist\n";
exit();
}
function suboptimal($realmindist)
{
global $destmap, $dests;
$newmap = array();
$mlen = 0;
$mindist = INFINITY;
$minpath = '';
$numdests = count($dests);
$path = '';
while(true)
{
$mlen = add_edges($destmap, $mlen, $newmap);
if ($mlen == INFINITY)
break;
foreach ($dests as $d1)
foreach ($dests as $d2)
if ($d1 != $d2)
{
longest($newmap, $d1, $d2, $d1, $path);
if (strlen($path) == $numdests)
{
$dist = 0;
for ($i = 0; $i < strlen($path) - 1; $i++)
$dist += $destmap[$path[$i]][$path[$i+1]];
if ($dist < $mindist)
{
$mindist = $dist;
$minpath = $path;
}
}
}
if ($mindist != INFINITY && $mindist < $realmindist)
printresults($minpath, $mindist);
else if ($mindist != INFINITY)
return;
}
}
$map = array();
$conns = file('map.txt');
foreach ($conns as $c)
{
$carr = explode(' ', strtoupper(trim($c)));
$map[$carr[0]][$carr[2]] = $carr[1];
if ($carr[3] != '1')
$map[$carr[2]][$carr[0]] = $carr[1];
}
$destmap = array();
$dests = explode(' ', strtoupper(trim(join('', file('dest.txt')))));
$path = '';
foreach ($dests as $d1)
foreach ($dests as $d2)
if ($d1 != $d2)
$destmap[$d1][$d2] = shortest($map, $d1, $d2, $path);
# Next do an exhaustive search to find the shortest path
function longest2(&$map, $a, $b, $exclude, &$path)
{
global $stime;
if ($a == $b)
{
if (count($path) < count($exclude))
$path = $exclude;
return;
}
if (!array_key_exists($a, $map))
return; // can't go anywhere from here
$nodes = array_values(array_diff(array_keys($map[$a]), $exclude));
if (count($nodes) == 0)
return;
foreach ($nodes as $n)
{
if (time() - $stime > 40)
suboptimal(INFINITY);
array_push($exclude, $n);
longest2($map, $n, $b, $exclude, $path);
array_pop($exclude);
}
}
function printresults2($path, $dist)
{
echo join(' ', $path) . " $dist\n";
exit();
}
$newmap = array();
$mlen = 0;
$mindist = INFINITY;
$minpath = array();
while(true)
{
$mlen = add_edges($destmap, $mlen, $newmap);
if ($mlen == INFINITY)
break;
foreach ($dests as $d1)
foreach ($dests as $d2)
if ($d1 != $d2)
{
$path = array();
longest2($newmap, $d1, $d2, array($d1), $path);
if (count($path) == count($dests))
{
$dist = 0;
for ($i = 0; $i < count($path) - 1; $i++)
$dist += $destmap[$path[$i]][$path[$i+1]];
if ($dist < $mindist)
{
$mindist = $dist;
$minpath = $path;
}
}
}
if ($mindist != INFINITY)
{
suboptimal($mindist);
printresults2($minpath, $mindist);
}
}
?>
Back to results
|
|
