Big O

Word Rectangle

Write a program to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom). Words should appear in this dictionary: WORD.LST (1.66MB). Heuristic solutions that may not always produce a provably optimal rectangle will be accepted: seek a reasonable tradeoff of efficiency and optimality.

That's a puzzle offered to people who want to work at ITA software, as a test of their nerd-mettle; ITA is a company that has, fame-ishly, used the computer language LISP to plug away at the traveling salesman problem at its most literal, for best I can tell they write software to find the shortest, cheapest, fastest airplane routes.

Not only do I have no desire to work at ITA, but I am in every regard unqualified to do so. There's nothing for me to gain by solving the puzzle. Except. It's like I'm drinking my coffee at breakfast and I want to read the movie reviews in the paper but there's a frog sitting on the Arts section croaking at me instead. I know the frog has something to teach me. What?

I know that you shouldn't just say to the computer, "here's a pile of words in WORDS.LST; go ahead and find me all the ones that line up," because the computer could hurt itself from the strain. Besides, it's a puzzle, not a research project--thus somewhere in there is a crisp little cracker of a solution, fairy functions dancing around the CPU with no global state to weigh them down. And then there are the words "heuristic," "efficiency," and "optimality"--words that mean simple loops won't do (the LISPish bias means the answer is likely small, unexpected, parenthetical). If I was desperate I could make some phone calls to people I know in Organized Math, genuine chipwits. In a half-hour: car pulls up, window rolls down, the puzzle goes into the ground.

But execution doesn't interest me. Admitting that I lack real talent for it, I've turned computer science into a hobby, like weekend landscape watercolorists or dabblers in piano. I mostly like it because I'm cheap. Piano, calligraphy, swinging, macrame--those require trips to special stores, catalog orders, lessons. Computer science is only there inside the machine, waiting for you to sit down with a copy of some heavy book or eager tutorial (the Web has many pushers trying to hook you on a syntax) and start twiddling. It seems that the discipline is entirely about cheapness. The glory goes to parsimony, to the algorithms that invest the fewest CPU cycles for the greatest return.

What scientists saved programmers squander. It must be disappointing to spend your college years cultivating a ponytail and a sense of superiority, discovering the inherent recursive nature of everything, only to wander into a cubicle farm where programmers like myself sit like veal calves, fattened on the candy-colored syntax served up by our platform IDEs, iteratively wasting what you've learned to prize. It must sting to see us burn tons of coal for a single cup of coffee. It stings me in a different way, because I've started to run into programming problems at work that can't be solved just by burning more coal. I've been moving mustard seeds of data with mountain-sized frameworks, and have hit limits personal and processorial. This must be why the puzzle calls to me.