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.




Ftrain.com is the website of Paul Ford and his pseudonyms. It is showing its age. I'm rewriting the code but it's taking some time.


There is a Facebook group.


You will regret following me on Twitter here.


Enter your email address:

A TinyLetter Email Newsletter

About the author: I've been running this website from 1997. For a living I write stories and essays, program computers, edit things, and help people launch online publications. (LinkedIn). I wrote a novel. I was an editor at Harper's Magazine for five years; then I was a Contributing Editor; now I am a free agent. I was also on NPR's All Things Considered for a while. I still write for The Morning News, and some other places.

If you have any questions for me, I am very accessible by email. You can email me at ford@ftrain.com and ask me things and I will try to answer. Especially if you want to clarify something or write something critical. I am glad to clarify things so that you can disagree more effectively.


Syndicate: RSS1.0, RSS2.0
Links: RSS1.0, RSS2.0


© 1974-2011 Paul Ford


@20, by Paul Ford. Not any kind of eulogy, thanks. And no header image, either. (October 15)

Recent Offsite Work: Code and Prose. As a hobby I write. (January 14)

Rotary Dial. (August 21)

10 Timeframes. (June 20)

Facebook and Instagram: When Your Favorite App Sells Out. (April 10)

Why I Am Leaving the People of the Red Valley. (April 7)

Welcome to the Company. (September 21)

“Facebook and the Epiphanator: An End to Endings?”. Forgot to tell you about this. (July 20)

“The Age of Mechanical Reproduction”. An essay for TheMorningNews.org. (July 11)

Woods+. People call me a lot and say: What is this new thing? You're a nerd. Explain it immediately. (July 10)

Reading Tonight. Reading! (May 25)

Recorded Entertainment #2, by Paul Ford. (May 18)

Recorded Entertainment #1, by Paul Ford. (May 17)

Nanolaw with Daughter. Why privacy mattered. (May 16)

0h30m w/Photoshop, by Paul Ford. It's immediately clear to me now that I'm writing again that I need to come up with some new forms in order to have fun here—so that I can get a rhythm and know what I'm doing. One thing that works for me are time limits; pencils up, pencils down. So: Fridays, write for 30 minutes; edit for 20 minutes max; and go whip up some images if necessary, like the big crappy hand below that's all meaningful and evocative because it's retro and zoomed-in. Post it, and leave it alone. Can I do that every Friday? Yes! Will I? Maybe! But I crave that simple continuity. For today, for absolutely no reason other than that it came unbidden into my brain, the subject will be Photoshop. (Do we have a process? We have a process. It is 11:39 and...) (May 13)

That Shaggy Feeling. Soon, orphans. (May 12)

Antilunchism, by Paul Ford. Snack trams. (May 11)

Tickler File Forever, by Paul Ford. I'll have no one to blame but future me. (May 10)

Time's Inverted Index, by Paul Ford. (1) When robots write history we can get in trouble with our past selves. (2) Search-generated, "false" chrestomathies and the historical fallacy. (May 9)

Bantha Tracks. (May 5)

Tables of Contents