## TARGET Solver

What does a geek do during holidays?

Write useless interesting applications of course. Today I was looking at the Target puzzle in the Sydney Morning Herald. The game is as follows. Consider the set of characters shown below:
```E A O I M N T A N```
Find as many words as you can using the above set of characters. The central character (M) must be found in every word. The words must be four characters or longer.

I had no hang-ups about cheating in this and so I wrote a small shell script to compute a solution. I used the collection of words from Corncob .
Here is the powershell script

```	function subset (\$sub, [System.Char[]]\$fullstr)
{
\$val = \$sub.ToCharArray() | sort
\$k= \$fullStr.Length
\$l = \$val.Length
\$found = \$l -le \$k
\$j=0
for(\$i = 0; \$i -lt \$l -and \$found; ++\$i)
{
\$found=\$False
while (-not \$found -and \$j -lt \$k)
{
\$found = \$fullstr[\$j] -eq \$val[\$i]
++\$j
}
}
\$found
}
\$u = "eaoimntan"
\$re = ".*m.*"
\$v = \$u.ToCharArray()| sort
where {\$_.Length -le 9 -and \$_.Length -ge 4 -and \$_ -match \$re} |
where { subset \$_ \$v}
```

In ‘subset’ what we do is compare two words to identify if the first word can be formed from a subset of the letters in the second array of characters which is assumed to be sorted. So now all we have to is for each word in the file corcob_lowercase.txt,  reduce it to its canonical forma and then compare it with the given set of characters (“eaoimntan” in this case) which is also sorted.
The output was:
```amen amine amino anemia animate atom emanation emit inmate item main maine mane mania manna mate mean meant meat mention mien mine mint mite moan moat name naomi nominate omen omit tame team time tome``` 