preg_grep a word list to show legnth specific results

scrupul0us

I have a rather sizable word list that I am trying to write a de-scrambler for

preg_grep seems like the obvious choice as it will return all matches from the word list array, but, what I'm having issues with is that I don't know how to enforce a minimum length return, that is:

$matches = preg_grep("/(\b\w*[$letters]+\w*\b)/i",$wordList);

basically returns the entire word list where at minimum one of those letters appears...

what i'd like to do is restrict it so 4 -> 10 length matches only

i've been on Google quite a bit and it seems something similar is questioned frequently for scrabble players, but, my attempts to find a regex have come up bone dry...

any help would be greatly appreciated

bradgrafelman

scrupul0us wrote:
what i'd like to do is restrict it so 4 -> 10 length matches only

So instead of using the '+' length modifier, which means "one or more", use '{4,10}', which means "between 4 and 10 (inclusive)."

scrupul0us

that does give me a proper range, but, the issue im still having, not clearly conveyed in my first post regrettably, is that I'm getting word results that have letters not provided by the user

the conditions would be such that:

1) word length 4 -> 10
2) results can only contain letters given to the regex

e.g if I give "cat", "cattle" cannot be returned because it contains letters I haven't provided

is there a way to modify the regex to use both the length restrictions AND just the letters given?

bradgrafelman

In your regexp pattern, why do you have "\w" before the character class containing $letters ? In regexp notation, "\w" translates to "[A-Za-z0-9_]*" (or something close), meaning any letter.

If you only want the results to consist of $letters, then remove that portion of the regexp pattern.

EDIT: See this site for more info on the shorthand notations (e.g. "\w").

scrupul0us

ill have to test further when i get home but essentially your saying:

$matches = preg_grep("/(\b[$letters]{4,10}\b)/i",$wordList);

...should work as I'd only be looking for word boundaries 4 -> 10 characters in length containing $letters?

scrupul0us

actually i was able to test locally... that trims up the invalid results a ton...

the last issue, oh boy, is that i'm getting results that have letters duplicated

for example, an input of "legal" is giving me, amongst others, "gage" as a result

is there a way to remove $letter duplication (unless duplicate letters are provided in the input)?

bradgrafelman

scrupul0us wrote:
is there a way to remove $letter duplication (unless duplicate letters are provided in the input)?

Eh... there's no easy way that I can think of, no. Basically, you're trying to match any permutation of the given set of letters? I'm not sure what the best way to go about doing that would be.

EDIT: Here's one way I can think of that might work... once you get the results using the regexp above, do something like this:

$words = array();
$letter_count = count_chars(strtolower($letters), 1);

foreach($matches as $match) {
    if(count_chars(strtolower($match), 1) == $letter_count)
        $words[] = $match;
}

johanafm

The bracket notation specifies allowed characters (called a character class). So [aba] is the exact same thing as [ab] or [ba].
In your specific case with [legal]{4,10}, which is egal to [aegl]{4,10}, "gage" and "eagel" are ok, while "age" fails due to its length and "bagel" would fail due to the character 'b' which is not present in the character class.

I'm by no means an expert on regexp so it's entirely possible that someone like Nrg Alpha might have a smart solution, but my gut feeling tells me it would be hard to create such a pattern and that it will be less efficient than actually counting the number of occurences of each character and remove the current array element as soon as you hit 2 for any given character.
For example, this pattern (found with google) would only accept a string containing A, B, C and D where there is no sequential repetition, such as AA, BB, CC or DD

$pattern = "(?i:([A-D])(?!\1)([A-D])(?!\1|\2)([A-D])(?!\1|\2|\3)([A-D]))"

And it should be possible to extended this pattern to ascertain that the third character doesn't match the first one either etc, by following the same logic. However, it quickly becomes combersom to deal with increasing string length.

However, if you first check that your character class matches like you did, you could then validate that no character is repeated by looping over the characters in the string once.

# like before
$letters = 'legal';
$pattern = "/(\b[$letters]{4,10}\b)/i";
$wordlist = array(
				'bagel',
				'eagel',
				'age',
				'gale',
				'legal');

echo '<h4>All words</h4>';
echo '<pre>'.print_r($wordlist,1).'</pre>';

$matches = preg_grep($pattern, $wordlist); 
echo '<br/><h4>Acceptable letters</h4>';
echo '<pre>'.print_r($matches,1).'</pre>';

# remove words with repeating characters
foreach ($matches as $k => $m) {
	$count = array();
	$len = strlen($m);
	for ($i = 0; $i < $len; ++$i) {
		if (!isset($count[$m[$i]])) {
			$count[$m[$i]] = 1;
		}
		else {
			++$count[$m[$i]];
		}
		# see comment below php code window
		if ($count[$m[$i]] > 1) {
			unset($matches[$k]);
			break;
		}
	}
}
echo '<br/><h4>No repetition</h4>';
echo '<pre>'.print_r($matches,1).'</pre>';

But perhaps you actually want [legal] to allow for the occurence of two l characters? In that case you could always count the number of occurences of each letter in $letters, then change

if ($count[$m[$i]] > 1) {

to check against maximum number of allowed occurences rather than just "> 1".

scrupul0us

that worked really well thanks

#letter counter
	$letters = str_split($letters);
	foreach ($letters as $letter)
	{
		@$letterCount[strtoupper($letter)]++;
	}

#sanitizer
	foreach ($matches as $k => $m) 
	{
		$count = array();
		$len = strlen($m);
		for ($i = 0; $i < $len; ++$i) 
		{
			if (!isset($count[$m[$i]])) 
			{
				$count[$m[$i]] = 1;
			}
			else 
			{
				++$count[$m[$i]];
			}
			# see comment below php code window
			if ($count[$m[$i]] > $letterCount[$m[$i]]) 
			{
				unset($matches[$k]);
				break;
			}
		}

}