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) == && 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, -1PREG_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


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