Code of mr_sketch
<?php
/**********************************************************************
* php-editors.com contest B3 - 20030617
* Author: Jeff Franklin
* Forum name: Mr. Sketch
* E-mail: mr_sketch at xsmail dot com
* Country: USA
**********************************************************************/
// Basic function to tell if a word can be spelt in a given jumble
function get_word($word, $jumble, $maxBlanks)
{
$wordLen = strlen($word);
$text = "";
$preJumble = $jumble;
for($i = 0; $i < $wordLen; $i++)
{
$char = $word[$i];
$pos = strpos($jumble, $char);
if ($pos === false)
{
$charPos = strpos($maxBlanks, $char);
$blankPos = strpos($maxBlanks, ".");
if ($charPos !== false || $blankPos === false)
return array("", "", "");
$maxBlanks[$blankPos] = $char;
$text .= strtoupper($char);
}
else
{
$text .= $char;
$jumble[$pos] = ".";
}
}
return array($text, $jumble, $maxBlanks);
}
// usort function to sort words
function sort_by_length($a, $b)
{
$lena = strlen($a);
$lenb = strlen($b);
if ($lena == $lenb) return 0;
return ($lena > $lenb) ? -1 : 1;
}
// usort function to sort array lengths to trim search
function sort_by_arrlen($a, $b)
{
list($txta, $j, $bla) = $a;
list($txtb, $j, $blb) = $a;
$sa = strlen($txta);
$sb = strlen($txtb);
if ($sa < $sb) return 1;
if ($sa > $sb) return -1;
$ba = substr_count($bla, ".");
$bb = substr_count($blb, ".");
if ($ba > $bb) return -1;
if ($ba < $bb) return 1;
return 0;
}
// print the text out with formatting
function print_text($t)
{
$len = 0;
$p = "";
$tmp = explode(" ", $t);
usort($tmp, "sort_by_length");
$t = join(" ", $tmp);
for ($i = 0; $i < strlen($t); $i++)
{
$l = strtolower($t[$i]);
if ($t[$i] != $l)
$p .= "<font color=\"red\">$l</font>";
else
$p .= $l;
if ($l != " ")
$len++;
}
echo $p . "\n";
return $len;
}
// This os O(N^(k+1)) where k is passed in but it won't always find
// the most optimal solution, however, it should run in a few seconds
// k=2 seems to work well and keeping the top 5 to the next iteration
function suboptimal($arrWords, $jumble, $numBlanks, $k = 2, $maxkeep = 5)
{
$ret = "";
$maxLen = strlen(join("", $arrWords));
$vals = array(array("", $jumble, $numBlanks));
while (true)
{
$startsize = count($vals);
for ($i = 0; $i < $k; $i++)
{
foreach($vals as $val)
{
list($txt, $njum, $nbl) = $val;
foreach($arrWords as $word)
{
if (stristr($txt, $word) !== false) continue;
list($wtxt, $wjum, $wb) = get_word($word, $njum, $nbl);
if ($wtxt == "") continue;
$vals[] = array(ltrim("$txt $wtxt"), $wjum, $wb);
}
}
}
if (count($vals) == $startsize) break;
usort($vals, "sort_by_arrlen");
$vals = array_slice($vals, 0, $maxkeep);
}
list($tst) = $vals[0];
if (strlen($tst) - substr_count($tst, " ") > strlen($ret) - substr_count($ret, " "))
$ret = $tst;
if (strlen($ret) - substr_count($ret, " ") == $maxLen)
return $ret;
return $ret;
}
// preprocess the sentance and words before handing to suboptimal
function find_all($list, $sentance)
{
$arrList = explode(" ", $list);
$jumble = join("", explode(" ", $sentance));
usort($arrList, "sort_by_length");
$numBlanks = ".."; // Two blanks
// Only look at words that can be spelt
$canSpell = array();
foreach($arrList as $word)
{
list($text) = get_word($word, $jumble, $numBlanks);
if ($text != "")
$canSpell[] = $word;
}
$bestText = suboptimal($canSpell, $jumble, $numBlanks);
return print_text($bestText);
}
// *********************** main() ************************
$data = "";
foreach(file("lists.txt") as $line)
{
$data .= trim($line);
}
$data = explode(".", $data);
$totalLen = 0;
$realData = array();
foreach($data as $line)
{
if (strlen($line) == 0)
continue;
$realData[] = $line;
}
foreach($realData as $line)
{
list($list, $sentance) = explode(",", $line);
$totalLen += find_all($list, $sentance);
}
echo "$totalLen\n";
?>
Back to results
|
|
