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
get-content C:\Users\geek\Downloads\corncob_lowercase\corncob_lowercase.txt |
        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

Advertisements

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Software Puzzle and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s