Code of cagret
<?php
/**
* words.php - php-editors.com [Jumbled Words B3] contest (may/june 2003)
* +-----------------------------------+
* | Author: cagrET (Cezary Tomczak) |
* | Email: cagret@yahoo.com |
* | Homepage: http://cagret.prv.pl |
* | Country: Poland |
* +-----------------------------------+
* All rights reserved, 2003.
*/
set_time_limit(300);
error_reporting(E_ALL);
/**
* ---------------------
* Preparing environment
* ---------------------
*/
define('LETTERS', 'abcdefghijklmnopqrstuvwxyz');
define('WORD_MAX_LENGTH', 20);
define('LINE_MAX_LENGTH', 80);
define('WORD_SEPERATOR', ' ');
define('LIST_SEPERATOR', ',');
define('SENTENCE_SEPERATOR', '.');
define('CRLF_PATTERN', "/(\r\n|\n|\r)/");
define('BLANKS_MAX', 2);
define('BLANK_START', '<span style="color: red;">');
define('BLANK_END', '</span>');
define('BLANK_LINE', "<br />\n");
define('FILE_LISTS', 'lists.txt');
/**
* --------------------
* Initializing objects
* --------------------
*/
/**
* Managing letters
* @package Words
*/
class Letters
{
/**
* Letters pattern
* @var array
* @access private
*/
var $pattern = array(
'a' => 0, 'b' => 0, 'c' => 0, 'd' => 0, 'e' => 0, 'f' => 0,
'g' => 0, 'h' => 0, 'i' => 0, 'j' => 0, 'k' => 0, 'l' => 0,
'm' => 0, 'n' => 0, 'o' => 0, 'p' => 0, 'q' => 0, 'r' => 0,
's' => 0, 't' => 0, 'u' => 0, 'v' => 0, 'w' => 0, 'x' => 0,
'y' => 0, 'z' => 0
);
/**
* Available letters
* @var array
* @access private
*/
var $letters;
/**
* Blanks leters - max 2 can be used
* @var array
* @access private
*/
var $blanks = array();
/**
* Constructor
*/
function Letters()
{
$this->letters = $this->pattern;
}
function __construct()
{
$this->Letters();
}
/**
* Add given letter
*
* @param string $s
* @return void
* @access private
*/
function add($s)
{
if (isset($this->blanks[$s])) {
unset($this->blanks[$s]);
} else {
++$this->letters[$s];
}
}
/**
* Add letters from given word
*
* @param string $word
* @return void
* @access public
*/
function addWord($word)
{
for ($i = 0, $len = strlen($word); $i < $len; ++$i) {
$this->add($word{$i});
}
}
/**
* Remove given letter
*
* @param string $s
* @return void
* @access private
*/
function remove($s)
{
if ($this->letters[$s] > 0) {
--$this->letters[$s];
} else {
$this->blanks[$s] = 1;
}
}
/**
* Remove letters that are in given word
*
* @param string $word
* @return void
* @access public
*/
function removeWord($word)
{
for ($i = 0, $len = strlen($word); $i < $len; ++$i) {
$this->remove($word{$i});
}
}
/**
* Check whether there are available $i given letters
*
* @param string $s letter
* @param int $i how many such letters
* @param int $blanks blank letters already used
* @return bool
* @access private
*/
function exists($s, $i, &$blanks)
{
if ($i == 1) {
if ($this->letters[$s] > ($i - 1)) {
return true;
}
if ((count($blanks) < BLANKS_MAX) && !isset($blanks[$s])) {
array_push($blanks, $s);
return true;
}
} else {
if ($this->letters[$s] > ($i - 1)) {
return true;
}
if ( ($this->letters[$s] > ($i - 2))
&& ((count($blanks) < BLANKS_MAX) && !isset($blanks[$s])) )
{
array_push($blanks, $s);
return true;
}
}
return false;
}
/**
* Check whether there are available letters to create given word
*
* @param string $word
* @return bool
* @access public
*/
function existsWord($word)
{
$blanks = $this->blanks;
$letters = $this->pattern;
for ($i = 0, $len = strlen($word); $i < $len; ++$i) {
++$letters[$word{$i}];
}
foreach ($letters as $letter => $repeat) {
if ($repeat > 0 && !$this->exists($letter, $repeat, $blanks)) {
return false;
}
}
return true;
}
/**
* Get blank letters that were used
*
* @return array with letters as values
* @access public
*/
function getBlanks()
{
return array_keys($this->blanks);
}
/**
* Count characters
*
* @param array $words
* @return int
* @access public
* @static
*/
function count($words)
{
$count = 0;
foreach ($words as $word) {
$count += strlen($word);
}
return $count;
}
}
/**
* Managing lists - searching words
* @package Words
*/
class Words_List
{
/**
* Input words
* @var array
* @access private
*/
var $words;
/**
* Available letters, from sentence
* @var object
* @access private
*/
var $Letters;
/**
* Current words (values as position)
* @var array
* @access private
*/
var $current = array();
/**
* Current position
* @var int
* @access private
*/
var $position = -1;
/**
* Constructor
*
* @param array $words
* @param object $Letters
*/
function Words_List($words, &$Letters)
{
$this->words =& $words;
$this->Letters =& $Letters;
}
function __construct($words, &$Letters)
{
$this->Words_List($words, $Letters);
}
/**
* Walk through combinations of words
*
* @return bool if more combinations exists
* @access public
*/
function next($check = true)
{
if (isset($this->words[$this->position + 1]))
{
$word = $this->words[++$this->position];
if ($this->Letters->existsWord($word)) {
$this->Letters->removeWord($word);
array_push($this->current, $this->position);
return true;
} else {
return $this->next();
}
}
else
{
$count = count($this->current);
if (($count == 0) || ($count == 1 && ($this->current[0] == $this->position) )) {
return false;
}
$this->position = array_pop($this->current);
$this->Letters->addWord($this->words[$this->position]);
return $this->next();
}
}
/**
* Return current list of words
*
* @return array
* @access public
*/
function getCurrent()
{
$ret = array();
foreach ($this->current as $v) {
array_push($ret, $this->words[$v]);
}
return $ret;
}
}
/**
* ---------
* Functions
* ---------
*/
function compare($a, $b)
{
$l1 = strlen($a);
$l2 = strlen($b);
if ($l1 == $l2) {
return 0;
}
return $l1 < $l2 ? +1 : -1;
}
/**
* ----------
* Controller
* ----------
*/
//init vars
$result = array(); //array of array of words
$result_blanks = array(); //array of array of blank letters used to create words
//read data
$fp = @fopen(FILE_LISTS, 'r') or exit('Could not open file: ' . FILE_LISTS);
$content = trim(fread($fp, filesize(FILE_LISTS)));
fclose($fp);
//remove new lines
$content = preg_replace(CRLF_PATTERN, '', $content);
$content = explode(SENTENCE_SEPERATOR, $content);
array_pop($content);
//search
foreach ($content as $v)
{
list($list, $sentence) = explode(LIST_SEPERATOR, $v);
$words = explode(WORD_SEPERATOR, $list);
if ($words[count($words) - 1] == WORD_SEPERATOR) {
array_pop($words);
}
$sentence = str_replace(WORD_SEPERATOR, '', $sentence);
//add letters from sentence
$Letters = new Letters;
$Letters->addWord($sentence);
//remove words that cannot be ever built
$copy = $words;
foreach ($copy as $k => $word) {
if (!$Letters->existsWord($word)) {
unset($copy[$k]);
}
}
$words = array();
foreach ($copy as $word) {
array_push($words, $word);
}
$List = new Words_List($words, $Letters);
$best_list = array();
$best_list_len = 0;
$best_list_blanks = array();
//search all combinations
while ($List->next()) {
$current = $List->getCurrent();
if (($count = Letters::count($current)) > $best_list_len) {
$best_list = $current;
$best_list_len = $count;
$best_list_blanks = $Letters->getBlanks();
}
}
//save best result
$result[] = $best_list;
$result_blanks[] = $best_list_blanks;
}
//output data
$total = 0;
foreach ($result as $k => $words)
{
$total += Letters::count($words);
usort($words, 'compare');
$words = implode(WORD_SEPERATOR, $words);
$words_output = $words;
$blanks = $result_blanks[$k];
//colorize blanks
if ($blanks > 0) {
$words_output = '';
for ($i = 0, $len = strlen($words); $i < $len; ++$i)
{
$letter = $words{$i};
if (in_array($letter, $blanks)) {
foreach ($blanks as $k2 => $blank)
{
if ($letter == $blank) {
$letter = BLANK_START . $letter . BLANK_END;
unset($blanks[$k2]);
}
}
}
$words_output .= $letter;
}
}
print $words_output . BLANK_LINE;
}
print $total;
?>
Back to results
|
|
