November 30, 2003

The [then] Current Challenge (given November 30, 2003):

Take the letters of the word TEMPORARY. Arrange them in a 3 by 3 square so that each of the acrosses, downs and the two long diagonals spells a word. Each of the diagonals must read backward as well as forward, making 10 words to be spelled altogether. All the words are common and uncapitalized. What is this special square?

-- WESun Puzzle, 2003-11-30

This example was recorded as a diary while solving the latest puzzle, same day.

1. Brute Force ?

How many possible arrangements? 9!/2 =

>perl -e "print 9*8*7*6*5*4*3"
181440

I don't think we want to generate all combinations and test. How many words?

>perl -nle "$c++ if length == 3; END {print $c}" /usr/dict/words
429

Almost practical to try all combinations of three of those, check with canonicalize if they anagram to TEMPORARY, and then check if columns and diagonals are words too. But that's brute force like we already have done. Let's try computer assisted ..

2. Computer assisted

How many possible Diagonals?

>perl -nle "next unless length == 3; 
	$w{reverse $_}= $_; 
	print $n++,' ',$_,' ',$w{$_} 
		if exists $w{$_};"	 /usr/dict/words
0 bib bib
1 bob bob
2 dad dad
3 did did
4 dub bud
5 eke eke
6 era are
7 ere ere
8 eve eve
9 ewe ewe
10 eye eye
11 gag gag
12 gig gig
13 god dog
...
42 tug gut
43 war raw
44 was saw
45 wed dew
46 won now

How many of those are in TEMPORARY? Note that with only two r's, the palindromes are right out too, so we don't even have to assume "10 words" means "10 different words", it's obvious.

>perl -nle "next unless /^[temporary]{3}$/; 
	$w{reverse $_}= $_; 
	print $n++,' ',$_,' ',$w{$_} 
		if exists $w{$_};" 	/usr/dict/words 
0 era are
1 ere ere
2 eye eye
3 pep pep
4 pop pop
5 ram mar
6 rap par
7 tap pat
8 tar rat
9 top pot


That doesn't limit the ones that repeat non-R's, so we need to limit it some more:

>perl -nle "next unless /^[temporary]{3}$/; 
        next if /(.) (?:\1 . | . \1)/x; 
		$w{reverse $_}= $_; 
		print $n++,' ',$_,' ',$w{$_} if exists $w{$_};"
			 /usr/dict/words 
0 era are
1 ram mar
2 rap par
3 tap pat
4 tar rat
5 top pot

So far, we have computed all the possible words and the possible diagonals. Since both diagonals have to have the same 2nd letter, but can't share any other letter except perhaps an R, we can rule out most of them. We might have expected the center letter to be E, but it's an A. The diagonals must be chosen from 1,2,3,4 above, and can't include both 3 and 4.

The 48 words in my minimal /usr/dict/words that match the above condition without the reversing limit are

>perl -nle "next unless /^[temporary]{3}$/
	 && !/(.) (?:\1 . | . \1)/x; 
	 print"         /usr/dict/words 

amp ape apt are arm art ate aye ear eat era err map mar mat may met mop oar oat opt ore par pat pay pea per pet pot pro pry ram rap rat ray roe rot rye tap tar tea toe too top toy try yea yet

We know the "A" must be in the center of it's words.

>perl -nle "next unless /^[temporary]{3}$/ 
					&& !/(.) (?:\1 . | . \1)/x;
            next if /^a|a$/; 
            print"              /usr/dict/words 

ear eat err map mar mat may met mop oar oat opt ore par pat pay per pet pot pro pry ram rap rat ray roe rot rye tap tar toe too top toy try yet

Note that with only 3.5 vowels, 3 columns, 3 rows, we can't have all the vowels in the center column. We don't have enough options with our Y, our diagonals don't allow for sharing vowels. Each letter must be a beginning, an end, a middle, or, if in a corner, both. Is "rye" a key word? It has the Y in a non-terminal opsition. Probably less important than ear, eat.

Let's try a larger word list, and refine our idea of repetitions.

>perl -nle "next unless /^[temporary]{3}$/ 
				&& !/([^r]) (?:\1 | . \1)/x; 
			next if /^a|a$/; 
			print" /usr/dict/web2 

ear eat err mae mao map mar mat may met mop mor mot moy oam oar oat oer ope opt ore ort ory pam par pat pay per pet poe pom pot poy pro pry pyr ram rap rat ray rep ret roe rot rye tae tam tao tap tar tay toe top tor toy try tye yam yap yar yat yeo yep yer yet yoe yom yor yot

Can you guess which words in this list are sufficiently different to be important in the solution?

And with the cross-reverses, the longer word list finds some dubious reverses, but at least we have some with Ys so we can have PRY or TRY as a vertical:

>perl -nle "next unless /^[temporary]{3}$/; 
	next if /([^r]) (?:\1 | . \1)/x; 
	$w{reverse $_}= $_; 
	push @pr, substr($_,1,1).' '.$_.' '.$w{$_} if exists $w{$_};
	END{print for sort @pr}" /usr/dict/web2

a oam mao
a pam map
a ram mar
a rap par
a tae eat
a tam mat
a tao oat
a tap pat
a tar rat
a yam may
a yap pay
a yar ray
a yat tay
e rea aer
e rep per
o pom mop
o top pot
o tor rot
o yom moy
o yot toy
r era are
r tra art
t eta ate 

The good looking pairs are:

a ram mar
a rap par
a tap pat
a tar rat
a yam may
a yap pay
Either RYE is a collumn, or YAM or PAY needs to be a diagonal. None of the diagonals have E as a terminal, so we'll forget RYE. For instance, the RAM/MAP-PAY/YAP pair has 4 possible configurations (since the other 6 words are standard across/down only), and they don' look possible:

R

 

P

 

A

 

Y

 

M

P

 

R

 

A

 

Y

 

M

Y

 

M

 

A

 

R

 

p

M

 

Y

 

A

 

P

 

R

Focussing on the lack of vowels, what use can we make of the Y?

>perl -nle "next unless /^[temporary]{3}$/ && !/([^r]) (?:\1 | . \1)/x; next if /[aeiou]/; print" /usr/dict/web2
pry
pyr
try

We suspect PRY/TRY to be critical, the words without vowels ... PYR is a Scrabble® word, and only helps one of the end-words. So Y is the lower right corner.

 

 

T

 

A

R

P

R

Y

 

 

P

 

A

R

T

R

Y

This drives one diagonal as PAT/TAP. The letters not already used are few: TEMPORARY, and tell us the other diagnoal must be MAY/YAM.

>perl -nle "next unless /^[temporary]{3}$/ && !/([^r]) (?:\1 | . \1)/x; next unless /[meo]{2}[pt]/; print" /usr/dict/web2
met
mop
mot

The solution is now clear. Note that the diagonal spelling both ways makes the answer unique up to symetry of reflection.

M

E 

T

O 

A

R

P

R

Y

M

O 

P

E 

A

R

T

R

Y

3. Brute Force, but less brute

Let's try to get this solution with brute force, but less brute than "everything" using the tools above and the tools of previous techniques.

>perl Temporary.pl /usr/dict/web2
99 words found
anagram master = aemoprrty
met / oar / pry
mop | ear | try | may | yam | pat | tap
mop / ear / try
met | oar | pry | may | yam | tap | pat
13.028
0.04
0
0

script as text

Now verify that it's not in my /usr/dict/words ... as we thought above ...

>perl Temporary.pl /usr/dict/words
47 words found
anagram master = aemoprrty
1.422
0.02
0
0

That's fast, but useless. Can we go faster? Let's re-write it for filtering the lists in the triple-while, instead of filtering in the inner loop.

>perl Temporary_diff.pl
99 words found
anagram master = aemoprrty
met / oar / pry
mop | ear | try | may | yam | pat | tap
mop / ear / try
met | oar | pry | may | yam | tap | pat
7.991
0.04
0
0

That's faster, 38% faster. Picking your dictionary makes a difference too. The slightly shorter enable1.txt dictionary would run 50% faster.

>perl Temporary_diff.pl /usr/dict/enable1.txt

75 words found
anagram master = aemoprrty
met / oar / pry
mop | ear | try | may | yam | pat | tap
mop / ear / try
met | oar | pry | may | yam | tap | pat
4.005
0.01
0
0


script as text

Verification on NPR.org 12/7:

Challenge given November 30, 2003:

Take the letters of the word TEMPORARY. Arrange them in a 3 by 3 square so that each of the acrosses, downs and the two long diagonals spells a word. Each of the diagonals must read backward as well as forward, making 10 words to be spelled altogether. All the words are common and uncapitalized. What is this special square?

WILL'S ANSWER: MET OAR PRY