Pizza Dude Results

[stuart]

At last I finally made time to release the Pizza Dude contest results

Very surprising results - nearly everyone got the same solution. Time ended-up being the decider.

I decided to keep the dest and map pretty short, only slightly larger the the demo one given.

Anyway you all done fantastic - check out the archive page to see how others coded their solution, I intend to dig a bit deaper too (when I get time).

I have not emailed anyone yet regarding prizes. Prizes are all canceled this month.........

Only joking, I will email everyone tomorrow regarding the prizes Watch your mail box dudes, you might get a prizes you didn't expect

Untill next time....

Stuart

[lrutledge]

Congratulations to the winners!

[FryGuy]

Congratulations to everyone that won. I did much better than I thought I would do, so I'm happy

[Transistor]

Hi,
thank you for the congratulations.
Here is my solution including the annotations. ...if somebody is interested

<?php
$time_start = getmicrotime();
$try = 0;
//////////////////////////////////////////////////////
$iResultLength = -1;  	// result length
$arrResultPath = array();  // result path

// load map
$arrNodes = $arrNodeToWay = $arrNodeFromWay = array();
foreach(file("map.txt") as $sLine){
	$arrLine = explode(" ",strtoupper(trim($sLine)));
	if((sizeof($arrLine)==4) && $arrLine[0]!=$arrLine[2]){	// ignore empty/damaged lines and routes that start and end at the same point
 if(!isset($arrNodes[$arrLine[0]][$arrLine[2]]) || $arrNodes[$arrLine[0]][$arrLine[2]]>$arrLine[1]){
 	$arrNodes[$arrLine[0]][$arrLine[2]] = $arrLine[1];
 	if(!isset($arrNodeToWay[$arrLine[2]]) || $arrLine[1]<$arrNodeToWay[$arrLine[2]]){
  $arrNodeToWay[$arrLine[2]] = $arrLine[1];
 	}
 	if(!isset($arrNodeFromWay[$arrLine[0]]) || $arrLine[1]<$arrNodeFromWay[$arrLine[0]]){
  $arrNodeFromWay[$arrLine[0]] = $arrLine[1];
 	}
 }
 if($arrLine[3]==2){    	// bidirectional
 	if(!isset($arrNodes[$arrLine[2]][$arrLine[0]]) || $arrNodes[$arrLine[2]][$arrLine[0]]>$arrLine[1]){
  $arrNodes[$arrLine[2]][$arrLine[0]] = $arrLine[1];
  if(!isset($arrNodeToWay[$arrLine[0]]) || $arrLine[1]<$arrNodeToWay[$arrLine[0]]){
  	$arrNodeToWay[$arrLine[0]] = $arrLine[1];
  }
  if(!isset($arrNodeFromWay[$arrLine[2]]) || $arrLine[1]<$arrNodeFromWay[$arrLine[2]]){
  	$arrNodeFromWay[$arrLine[2]] = $arrLine[1];
  }
 	}
 }
	}
}

// take the shortes way first
reset($arrNodes);
while(list($sKey,) = each($arrNodes)){
	asort($arrNodes[$sKey],SORT_NUMERIC);
}

// load delivery instructions
$arrDelivery = array();
foreach(file("dest.txt") as $sLine){
	if($sLine = trim($sLine)) $arrDelivery = explode(" ",strtoupper($sLine));
}
$sDelivery = implode("",$arrDelivery);
#usort($arrDelivery,"cmpDeliveryNode");
$arrCountDelivery = array_count_values($arrDelivery);

// calculate delivery route
foreach($arrDelivery as $sStartPoint){
	if(isset($GLOBALS["arrNodes"][$sStartPoint])){	// if there is at least one destination node
 processNode(array($sStartPoint),0);
	}
}
echo implode(" ",array_intersect($arrResultPath,$arrDelivery))." ".$iResultLength." ".$try;

function processNode($arrPath,$iLength){

	global $arrNodes,
 	$arrCountDelivery,
 	$arrDelivery,
 	$sDelivery,
 	$arrNodeFromWay,
 	$arrNodeToWay,
 	$iResultLength,
 	$arrResultPath;

++$GLOBALS["try"];

	$sPath = implode("",$arrPath);
	$iStartElement = end($arrPath);
	$iLastElement = prev($arrPath);
	$arrCountPath = array_count_values($arrPath);

	// not yet processed points first
	$arrFirst = $arrSecond = $arrThird = array();
	foreach($arrNodes[$iStartElement] as $sDest=>$iLengthDest){

 if(!isset($arrCountPath[$sDest])){
 	if(isset($arrCountDelivery[$sDest])){
  $arrFirst[$sDest] = $iLengthDest; 	// not visited but on delivery route
 	}
 	else{
  $arrSecond[$sDest] = $iLengthDest; 	// not visited and not on route
 	}
 }
 else{
 	// ignore this when B is not on route for A B (A) or has been visited already
 	if($iLastElement !== $sDest || ($arrCountPath[$iStartElement]<2 && isset($arrCountDelivery[$iStartElement]))){
  $arrThird[$sDest] = $iLengthDest;  // already visited
 	}
 }
	}

	$arrTodo = array_diff($arrDelivery,$arrPath);
	foreach($arrFirst+$arrSecond+$arrThird as $sDest=>$iLengthDest){

 $iEstimatedMinLength = $iTmpLength = $iLength+$iLengthDest;

 $arrPathTmp = $arrPath;
 $arrPathTmp[] = $sDest;
 $arrTodoTmp = $arrTodo;
 if(($iDestKey = array_search($sDest,$arrTodoTmp))!==FALSE){
 	unset($arrTodoTmp[$iDestKey]);
 }
 if($arrTodoTmp && !array_intersect($arrTodoTmp,array_keys($arrNodes[$sDest]))){
 	$iEstimatedMinLength += $arrNodeFromWay[$sDest];
 }
 foreach($arrTodoTmp as $sDeliveryElement){
 	$iEstimatedMinLength += $arrNodeToWay[$sDeliveryElement];
 }
 // path longer than found one 
 if($iResultLength>=0 && $iEstimatedMinLength>=$iResultLength){
 	continue; // maybe another way is shorter -> go on
 }
 // all points processed -> shortest way found
 if(!$arrTodoTmp){
 	$iResultLength = $iTmpLength;
 	$arrResultPath = $arrPathTmp;
# 	echo implode("",$arrPathTmp).": $iTmpLength\n";
 	break; 	// this was the last missing point -> skip the rest
 }

 // don't drive useless circles again and again
 if(($iPos = strrpos($sPath,$sDest))!==FALSE){
 	$sSearch = substr($sPath.$sDest,$iPos+1);
 	$sSearchLength = strlen($sSearch);
 	if((strcspn($sSearch,$sDelivery)===$sSearchLength-1)  	// no destination point in circle
   || substr($sPath,($sSearchLength*-2)+1,$sSearchLength)===$sSearch	// ABCABC
   || strpos($sPath,$sDest.$sSearch)!==FALSE){   // A BCDB EFG BCDB
  continue;	// maybe another way is better -> go on
 	}
 }
 if(isset($arrNodes[$sDest])){	// if there is at least one destination node
 	processNode($arrPathTmp,$iTmpLength);
 }
	}
}

// nodes with less and longer connections first
function cmpDeliveryNode($a,$b){
	global $arrNodes;
	if(isset($arrNodes[$a]) && isset($arrNodes[$b])){
 $aSize = sizeof($arrNodes[$a]);
 $bSize = sizeof($arrNodes[$b]);
 if($aSize==$bSize){
 	if($aSize==1){
  $aLength = end($arrNodes[$a]);
  $bLength = end($arrNodes[$b]);
  if($aLength==$bLength) return 0;
  else return($aLength>$bLength)?-1:1;
 	}
 	else return 0;
 }
 else return($aSize<$bSize)?-1:1;
	}
	else return 0;
}

//////////////////////////////////////////////////////
echo "\n\n".(getmicrotime()-$time_start);

function getmicrotime(){
	list($usec, $sec) = explode(" ",microtime());
	return ((float)$usec + (float)$sec);
}
?>

Transistor

gratz to the winner B)

Torsten Rentsch

what is his nick ?

[Transistor]

Originally posted by Guest_cagrET@Aug 30 2003, 02:58 AM
Torsten Rentsch

what is his nick ?

Transistor == Torsten Rentsch

Transistor

[ciaccia]

Hi,

I hadn't time yet to post my reply, and I'm doing it only now...

My special thanks to stuart and all the php-editors staff, and congratulation to all who entered the contest!

** removed for spammieness **

[gesf]

Congratulations to all of the participants, i believe they all made a great job!