Find a Word Ladder:
PHP Source Code:
<?php
$_starttime = microtime(); // for performance tests
$_builtDictionary = false;
/**
* Use a pre-parsed dictionary if available... dramatically improves speed.
*/
try{
require_once('Cache.class.php');
$cache = new Cache('./cache');
$cache_key = 'dictionary_';
}catch(Exception $e)
{
errorOut($e->getMessage());
}
/**
* Starting word and target word
*/
$start = strtolower($_REQUEST['start']);
$end = strtolower($_REQUEST['end']);
if(strlen($start) < 2 || strlen($end) < 2) errorOut('Words must be at least 2 characters long.');
/**
* Get the dictionary of words that are x length
*/
$length = strlen($start);
$words = $cache->get("$cache_key$length");
if(!$words)
{
$words = array();
$dict = strtolower(file_get_contents('words.dict'));
preg_match_all('/\b\w{'.$length.'}\b/', $dict, $words);
$words = array_flip($words[0]);
set_time_limit(count($words));
$dict = join("\n", array_keys($words));
foreach($words as $k => $w)
{
$subwords = array();
$re_variants = array();
for($j = 0; $j < $length; $j++)
$re_variants[] = '\b' . substr($k, 0, $j) . '[^' . $k{$j} . ']' . substr($k, $j+1) . '\b';
if(preg_match_all('/'.join("|", $re_variants) . '/', $dict, $subwords))
$words[$k] = $subwords[0];
else
$words[$k] = array();
}
$cache->set("$cache_key$length", $words);
$_builtDictionary = true;
}
/**
* Make sure the search is valid (real words, words don't already match, equal lengths, etc.)
*/
if(strlen($start) != strlen($end)) errorOut("Words [$start] and [$end] are not the same length");
if(!in_array($start, array_keys($words))) errorOut("$start is not a real word.");
if(!in_array($end, array_keys($words))) errorOut("$end is not a real word.");
if(!count($words[$start])) errorOut("No paths lead from $start");
if(!count($words[$end])) errorOut("No paths lead to $end");
if($start == $end) errorOut("Words already match.");
/**
* Attempt to build the ladder.
*/
$i = 0;
$found = false;
$search = array(array($start=>null));
$already_used = array();
do
{
foreach($search[$i] as $k=>$v)
{
if(!is_array($search[$i+1])) $search[$i+1] = array();
if(count($words[$k]))
{
if(in_array($end, $words[$k]))
$found = true;
$b = array_flip($words[$k]);
foreach($b as $ck=>$cv)
{
if(!in_array($ck,$already_used))
{
$b[$ck] = $k;
$already_used[] = $ck;
}
else
unset($b[$ck]);
}
$search[$i+1] = array_merge($b,$search[$i+1]);
}
}
}
while(!$found && count($search[$i++ + 1]));
$ladder = array();
if($found)
{
for($i = count($search); $i > -1; $i--)
{
if($end) $ladder[] = $end;
$end = $search[$i-1][$end];
}
$ladder = array_reverse($ladder);
}
if(!$ladder) errorOut('Could not find a path between words');
/**
* Output the result in XML
*/
$xml = new DOMDocument('1.0');
$xmlLadder = $xml->createElement('WordLadder');
$times1 = split(" " , $_starttime);
$times2 = split(" ", microtime());
$_endtime = ($times2[1] - $times1[1]) + ($times2[0] - $times1[0]);
$xmlLadder->setAttribute('execution_time', $_endtime);
$xmlLadder->setAttribute('built_dictionary', $_builtDictionary);
$xmlLadder->setAttribute('start', strtolower($_REQUEST['start']));
$xmlLadder->setAttribute('end', strtolower($_REQUEST['end']));
for($i = 0; $i < count($ladder); $i++)
{
$rung = $xml->createElement('rung');
if($i == 0)
$r = "<strong>$ladder[$i]</strong>";
else
$r = findWordChange($ladder[$i-1],$ladder[$i]);
$rung->appendChild($xml->createCDATASection($r));
$xmlLadder->appendChild($rung);
}
header('Content-Type: text/xml');
echo $xml->saveXML($xmlLadder);
exit;
ladderXML($ladder, $_startTime);
/**
* Creates an XML error message response
* @param string $message
*/
function errorOut($message)
{
$xml = new DOMDocument('1.0');
$error = $xml->createElement('error', $message);
header('Content-Type: text/xml');
echo $xml->saveXML($error);
exit;
}
/**
* Finds the letter changed between words $from and $to
* @param string $from
* @param string $to
* @return string
*/
function findWordChange($from, $to)
{
$out = '';
for($i = 0; $i < strlen($from); $i++)
{
if($from{$i} != $to{$i})
$out .= "<strong><u>" . $to{$i} . "</u></strong>";
else
$out .= $to{$i};
}
return $out;
}
?>
1