Code of matteo
<?php
/*********************************************************/
/* Jumbled Words for PHP-Editors.com Coding Contest */
/* (C) 2003 Matteo Beccati <matteo@beccati.com> */
/*********************************************************/
$solveTimeLimit = ini_get('max_execution_time');
if (!$solveTimeLimit) $solveTimeLimit = 10000;
$solveMaxTime = time() - 3;
echo "<pre>\n";
parseFile();
$result = 0;
while (list($x, ) = each($entries))
{
$sol[$x] = array();
$result += solveEntry($entries[$x], $sol[$x]);
}
for ($x=0; isset($sol[$x]); $x++)
echo join(' ', $sol[$x])."\n";
echo $result."\n";
echo "</pre>";
/***************************************************/
/* Parse input file */
/***************************************************/
function parseFile()
{
global $entries, $solveTimeLimit, $solveMaxTime, $solveMd5;
$buf = file('lists.txt');
$e = 0;
$c = count($buf);
// Read words
for ($x = 0; $x < $c; $x++)
{
$s = trim($buf[$x]);
$last = substr($s, -1);
if ($last == ',')
{
// List found
$entries[$e][0] = explode(' ', substr($s, 0, strlen($s)-1));
$entries[$e][1] = '';
// Set entry max score as the length of all the words
$entries[$e]['maxscore'] = strlen(join($entries[$e][0]));
}
else
{
// (Part of) Sentence found
if (!isset($entries[$e][1])) $entries[$e][1] = '';
$entries[$e][1] .= str_replace(' ', '', $last == '.' ? substr($s, 0, strlen($s)-1) : $s);
if ($last == '.')
// Last sentence line
$e++;
}
}
$total_score = 0;
for ($x = 0; isset($entries[$x][0]); $x++)
{
$tmp = join('', $entries[$x][0]);
// Calculate md5 of list and sentence to find duplicates (who knows? :)
$entries[$x]['md5'] = md5($tmp.$entries[$x][1]);
// Calculate max theoric score for the pair
if (isset($solveMd5[$entries[$x]['md5']]))
// Pair already present, fake a null max score because only one would be evaluated
$entries[$x]['maxscore'] = 0;
else
{
$solveMd5[$entries[$x]['md5']] = true;
$jlen = strlen($entries[$x][1])+2;
$lasting = strlen(removeLetters(wordSort($entries[$x][1]), wordSort($tmp)));
$lasting = $lasting <= 2 ? 0 : $lasting - 2;
$e2 = $entries[$x]['maxscore'] - $lasting;
$entries[$x]['maxscore'] = min($jlen, $e2);
$total_score += $entries[$x]['maxscore'];
}
}
// Calculate available time for each entry
for ($x = 0; isset($entries[$x][0]); $x++)
{
$entries[$x]['timespan'] = floor($solveTimeLimit * $entries[$x]['maxscore'] / $total_score);
if (!$entries[$x]['timespan'] && $entries[$x]['maxscore'])
{
$entries[$x]['timespan'] = 1;
$solveMaxTime--;
}
}
if (isset($entries[$x])) unset($entries[$x]);
// Sort entries by score, highest first
uasort($entries, "entries_sort_callback");
}
/***************************************************/
/* Sort letters in a word */
/***************************************************/
function wordSort($w)
{
$a = array();
$len = strlen($w);
for ($x=0; $x<$len; $x++)
$a[] = $w{$x};
sort($a);
return join('', $a);
}
/***************************************************/
/* Highlight bonus letters */
/***************************************************/
function highLight($w)
{
for ($i = 0; $i < strlen($w[1]);$i++)
{
$c = $w[1]{$i};
$x = strrpos($w[0], $c);
$w[0] = substr($w[0], 0, $x).'{'.$c.'}'.substr($w[0], $x+1);
}
$w[0] = str_replace('}{', '', $w[0]);
$w[0] = str_replace('{', '<span style="color: red">', $w[0]);
$w[0] = str_replace('}', '</span>', $w[0]);
return $w[0];
}
/***************************************************/
/* Removes needle letters from haystack */
/***************************************************/
function removeLetters($needle, $haystack)
{
while ($haystack !== '' && $needle !== '')
{
if (($x = strpos($haystack, $needle{0})) !== false)
{
$haystack = substr($haystack, 0, $x).substr($haystack, $x+1);
$needle = substr($needle, 1);
}
else
$needle = str_replace($needle{0}, '', $needle);
}
return $haystack;
}
/***************************************************/
/* Solve one entry */
/***************************************************/
function solveEntry($e, &$sol)
{
global $solveEntryBuffer, $solveMaxScore, $solveStop, $solveMaxTime, $solveMd5;
if (is_array($solveMd5[$e['md5']]))
{
$sol = $solveMd5[$e['md5']][0];
return $solveMd5[$e['md5']][1];
}
$solveMaxScore = $e['maxscore'];
foreach ($e[0] as $k => $v)
{
$solveMaxScore += strlen($v);
$e2[0][$k] = wordSort($v);
}
uasort($e2[0], 'strlen_callback');
$e2[1] = wordSort($e[1]);
$solveMaxScore = $e['maxscore'];
$solveStop = false;
$solveMaxTime += $e['timespan'];
$solveEntryBuffer = $e2[0];
$solve = new solver($e2[1]);
$score = $solve->score;
$words = array();
while (isset($solve->best) && isset($solve->children[$solve->best]))
{
$words[] = array($e[0][$solve->best], $solve->children[$solve->best]->blank);
$solve = $solve->children[$solve->best];
}
$blanks = '';
foreach ($words as $k => $v)
{
if (strlen($blanks))
{
$tmp = $blanks;
$blanks = $v[1];
$words[$k][1] = str_replace($tmp, '', $v[1]);
}
elseif (strlen($v[1]))
$blanks = $v[1];
}
usort($words, 'sol_compare_callback');
foreach ($words as $v)
$sol[] = highLight($v);
$solveMd5[$e['md5']] = array($sol, $score);
return $score;
}
/***************************************************/
/* Sort callback functions */
/***************************************************/
function sol_compare_callback(&$a, &$b)
{
$r = strlen($b[0]) - strlen($a[0]);
return $r ? $r : strcmp($a[0], $b[0]);
}
function entries_sort_callback($a, $b)
{
if (!$a['maxscore'])
return 1;
return $a['maxscore'] < $b['maxscore'] ? -1 : 1;
}
/***************************************************/
/* Solver class */
/***************************************************/
class solver
{
var $jumbled;
var $history;
var $score;
var $blank;
var $children;
var $best;
function solver($j, $skip = false)
{
global $solveEntryBuffer, $solveEntryLen;
$this->jumbled = $j;
$this->score = 0;
$this->blank = '';
$this->history = array();
if (!$skip)
{
reset($solveEntryBuffer);
while (list($k, ) = each($solveEntryBuffer))
{
$solveEntryLen[$k] = strlen($solveEntryBuffer[$k]);
$this->unexplored[$k] = $k;
}
$this->start(false);
}
}
function __construct($j, $skip = false)
{
$this->solver($j, $skip);
}
function start($current = false, $blank = '')
{
global $solveEntryBuffer, $solveEntryLen, $solveMaxScore, $solveStop, $solveMaxTime;
$this->children = array();
if ($current !== false)
{
$this->score += strlen($solveEntryBuffer[$current]);
unset ($this->unexplored[$current]);
$this->jumbled = removeLetters($solveEntryBuffer[$current], $this->jumbled);
if ($blank != '')
{
$this->blank .= $blank;
$this->history[] = $current.'-'.$blank;
}
else
$this->history[] = $current;
if (!$solveStop && $this->score >= $solveMaxScore || time() > $solveMaxTime)
$solveStop = true;
}
$jblen = strlen($this->jumbled) + 2 - strlen($this->blank);
for (;!is_null($k = key($this->unexplored));next($this->unexplored))
{
if ($solveStop)
break;
if ($solveEntryLen[$k] > $jblen)
continue;
$s = $solveEntryBuffer[$k];
$st = removeLetters($this->jumbled, $s);
if (!strlen($st))
$this->children[$k] = $this->clone($k);
elseif (strlen($st) == 1 && strlen($this->blank) < 2 && (!strlen($this->blank) || $this->blank{0} != $st))
$this->children[$k] = $this->clone($k, $st);
elseif (strlen($st) == 2 && !strlen($this->blank) && $st{0} != $st{1})
$this->children[$k] = $this->clone($k, $st);
}
$max = 0;
for (reset($this->children);!is_null($c = key($this->children));next($this->children))
{
if ($this->children[$c]->score > $max)
{
$max = $this->children[$c]->score;
$this->best = $c;
}
}
if ($max)
$this->score = $max;
}
function clone($current, $blank = '')
{
$new = new solver($this->jumbled, true);
$new->history = $this->history;
$new->score = $this->score;
$new->blank = $this->blank;
$new->unexplored = $this->unexplored;
$new->start($current, $blank);
return $new;
}
}
?>
Back to results
|
|
