Puzzles for Programmers and Pros

Dennis E. Shasha

Wiley Publishing, Inc.

Published by

Wiley Publishing, Inc.
10475 Crosspoint Boulevard
Indianapolis, IN 46256
www.wiley.com

© 2007 by Dennis E. Shasha

Published by Wiley Publishing, Inc., Indianapolis, Indiana

Published simultaneously in Canada

ISBN: 9780470121689

Manufactured in the United States of America

10 9 8 7 6 5 4 3 2 1

Library of Congress Cataloging-in-Publication Data

Shasha, Dennis Elliott.
Puzzles for programmers and pros / Dennis E. Shasha.
p. cm.
Includes index.
ISBN 978-0-470-12168-9 (paper/website)
1. Mathematical recreations. 2. Puzzles. I. Title.
QA95.S4699 2007
793.74-dc22
2007002538

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone]. Requests to the Publisher for permission should be addressed to the Legal Department, Wiley Publishing, Inc., 10475 Crosspoint Blvd., Indianapolis, IN 46256, [phone], fax [phone], or online at http://www.wiley.com/go/permissions.

LIMIT OF LIABILITY/DISCLAIMER OF WARRANTY: THE PUBLISHER AND THE AUTHOR MAKE NO REPRESENTATIONS OR WARRANTIES WITH RESPECT TO THE ACCURACY OR COMPLETENESS OF THE CONTENTS OF THIS WORK AND SPECIFICALLY DISCLAIM ALL WARRANTIES, INCLUDING WITHOUT LIMITATION WARRANTIES OF FITNESS FOR A PARTICULAR PURPOSE. NO WARRANTY MAY BE CREATED OR EXTENDED BY SALES OR PROMOTIONAL MATERIALS. THE ADVICE AND STRATEGIES CONTAINED HEREIN MAY NOT BE SUITABLE FOR EVERY SITUATION. THIS WORK IS SOLD WITH THE UNDERSTANDING THAT THE PUBLISHER IS NOT ENGAGED IN RENDERING LEGAL, ACCOUNTING, OR OTHER PROFESSIONAL SERVICES. IF PROFESSIONAL ASSISTANCE IS REQUIRED, THE SERVICES OF A COMPETENT PROFESSIONAL PERSON SHOULD BE SOUGHT. NEITHER THE PUBLISHER NOR THE AUTHOR SHALL BE LIABLE FOR DAMAGES ARISING HERE-FROM. THE FACT THAT AN ORGANIZATION OR WEBSITE IS REFERRED TO IN THIS WORK AS A CITATION AND/OR A POTENTIAL SOURCE OF FURTHER INFORMATION DOES NOT MEAN THAT THE AUTHOR OR THE PUBLISHER ENDORSES THE INFORMATION THE ORGANIZATION OR WEBSITE MAY PROVIDE OR RECOMMENDATIONS IT MAY MAKE. FURTHER, READERS SHOULD BE AWARE THAT INTERNET WEBSITES LISTED IN THIS WORK MAY HAVE CHANGED OR DISAPPEARED BETWEEN WHEN THIS WORK WAS WRITTEN AND WHEN IT IS READ.

For general information on our other products and services please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Trademarks: Wiley, the Wiley logo, Wrox, the Wrox logo, Programmer to Programmer, and related trade dress are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries, and may not be used without written permission. All other trademarks are the property of their respective owners. Wiley Publishing, Inc., is not associated with any product or vendor mentioned in this book.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Dedication

To omniheurists from every corner of the earth

About the Author

Dennis Shasha is a professor of computer science at the Courant Institute of New York University, where he works with biologists on pattern discovery for microarrays, combinatorial design, and network inference; with physicists, musicians, and financial people on algorithms for time series; and on database applications in untrusted environments. Other areas of interest include database tuning as well as tree and graph matching.

Because he likes to type, he has written five books of puzzles before this one, a biography about great computer scientists, and technical books about database tuning, biological pattern recognition, and time series. In addition, he has co-written more than fifty journal papers, sixty conference papers, and seven patents. For fun, he writes the monthly puzzle column for the Scientific American website and sometimes for Dr. Dobb’s Journal.

Acknowledgments

My warmest thanks to the readers of my puzzles. They span every continent except Antarctica and they reveal their intelligence with every communication. Some readers have become good friends, such as that gifted teacher and mathematician Andy Liu and the irrepressibly creative architect Mike Whittaker. When a puzzle that I have invented talks back and twists itself into a version that I can’t answer, I call in my puzzle brain trust. If I were faced with a math/computational problem of great difficulty, I would huddle with these gifted individuals for a week and we’d solve it.

Many of these puzzles have benefited greatly from the editorial suggestions of Scientific American’s John Rennie and Jon Erickson and Deirdre Blake of Dr. Dobb’s. Editors are the first clarity test that an author has of the written version of a puzzle. These editors have surgically exposed any obscurities they have found in my writing. I often pose the oral version of a puzzle to a certain young man named Tyler. Besides solving them (sometimes with the help of a hint or two), he makes it clear when he considers them “lame” (bad) or “ill” (cool). Only the ill ones see print.

Gary Zamchick has graced some of the puzzles with his irreverent cartoons. He has the remarkable ability to capture the essence of a puzzle with just a few pen strokes. This book’s Part III, “Faithful Foes,” requires Dr. Ecco and you to navigate a labyrinth of tunnels and treachery. Karen Shasha has managed, in her photographs, to portray the spirit of that quest exactly as I have envisioned it.

My acquisitions editor, Carol Long; my development editor, Sara Shlaer; the book’s copy editor, Mildred Sanchez; and the book’s designer, LeAndra Hosier, have put up with my demands for ever higher visual appeal and supported the demands of the text. If this book is a winner, they are in large part responsible.

Credits

Executive Editor
Carol Long

Development Editor
Sara Shlaer

Copy Editor
Mildred Sanchez

Editorial Manager
Mary Beth Wakefield

Production Manager
Tim Tate

Vice President and Executive Group Publisher
Richard Swadley

Vice President and Executive Publisher
Joseph B. Wikert

Graphics and Production Specialists
Brooke Graczyk
Denny Hager
Alicia B. South

Quality Control Technician
Brian H. Walls

Project Coordinator
Kristie Rees

Proofreading
Broccoli Information Management

Indexing
Potomac Indexing, LLC

Anniversary Logo Design
Richard Pacifico