Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992); Database Tuning: A Principled Approach (Prentice Hall, 1992); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer-Verlag, 1998). He can be contacted at [email protected].
Slim and muscular, wearing jeans and a T-shirt, red hair tied back in a pony tail, and a pencil on her ear, she looked the part of a recent design school graduate.
"I am an urban planner, inasmuch as that is possible down there in Texas," our visitor Melissa Whitney said. "The state has no zoning laws, the people love driving, and they demand wide streets. Nature has little chance, at least not in the well-watered areas. A large ranch outside Austin has just been sold to a developer. He has divided it into 144 square parcels, each two acres in size, arranged as a 12 by 12 grid. He's given me five parcels to design as parks. I would like to retard the development of the other 139 parcels as much as possible in the hope that the community will decide to save more of the land. From previous housing development histories, I've observed the following.
"New houses tend to be built near existing ones. So, if there is an empty nonpark parcel next to (vertically, horizontally, or diagonally) at least two developed parcels, then it will be developed in the next year. Parks are considered undeveloped, so they can potentially retard sprawl. My goal is to place the parks in such a way so as to keep at least some nonpark parcels undeveloped for as long as possible.
"Assume the grid is numbered from rows 0 to 11 and columns 0 to 11. The developer has already built the first four houses at locations (3,3), (3,4), (9,9), and (8,9). Without any parks as barriers, the entire ranch will be filled up in 11 years. Let me show you. Each 1 represents a house and each 0 represents undeveloped land."
initial:
000000000000
000000000000
000000000000
000110000000
000000000000
000000000000
000000000000
000000000000
000000000100
000000000100
000000000000
000000000000
000000000000
000000000000
000110000000
000110000000
000110000000
000000000000
000000000000
000000000000
000000001110
000000001110
000000000000
000000000000
000000000000
000110000000
001111000000
001111000000
001111000000
000110000000
000000000000
000000001110
000000011111
000000011111
000000001110
000000000000
000110000000
001111000000
011111100000
011111100000
011111100000
001111000000
000110001110
000000011111
000000111111
000000111111
000000011111
000000001110
001111000000
011111100000
111111110000
111111110000
111111110000
011111111110
001111111111
000111111111
000001111111
000001111111
000000111111
000000011111
011111100000
111111110000
111111111000
111111111000
111111111110
111111111111
011111111111
001111111111
000111111111
000011111111
000001111111
000000111111
...
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
"Let me get this straight: Your goal is to retard development of the nonpark land as many years as possible, right?" asked Liane.
"Why can't you just surround some nonpark land with park land and save it that way? With five park parcels, you could save at least eight nonpark parcels forever.
Reader: Would you like to try to do that before you read on or can you see a way to save more?
"Here is my method. Set up parks at (7,1), (7,2), (8,2), (9,2), and (11,2). You will get the following steady state where P represents a park, 1 represents developed land, and 0 represents undeveloped nonpark land. Not one of the 0s is a neighbor of two or more 1s."
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
1PP111111111
00P111111111
00P111111111
001111111111
00P111111111
"I wish I could do that, honey," she said to 13-year-old Liane, "but the developer might see what I'm up to and fire me on the spot. He also doesn't want me to put parks next to any of the initial houses. Unfortunately, most places that I've thought of to put the parks don't slow things down much, usually by just one year. Can you find a way to save at least some nonpark land for as many years as possible, but not an infinite number of years?"
Reader: Liane came up with a solution in which the last undeveloped nonpark land disappeared after 15 years. Can you do as well or better?
Melissa thanked Liane, though she sighed heavily.
"Four years for all this effort? Am I helping to conserve, or am I merely erecting a small speed bump on the way to natural destruction?" she wondered aloud as she left.
Ecco turned to Liane, who was by then strumming her electric guitar.
"Nice job, at least mathematically speaking," he said. "Suppose we expand the freedom of the players. We have a Sprawler and a Conserver. The Sprawler wants to cover all undeveloped nonpark land in as short a time as possible. The Conserver wants to protect at least some non-park land for as long as possible (even infinitely long for purposes of the game). Clearly, if the Sprawler moves first, the Conserver can surround some nonpark land, thus keeping it forever wild. But if the Conserver moves first, the Sprawler could potentially put his first developments right inside the enclosed area. So, assume the Conserver places the five parks first and then the Sprawler places four initial houses in a way that may depend on the placement of the parks. Can the Sprawler guarantee to cover all undeveloped nonpark land in finite time, no matter how the Conserver first places the parks? If so, in what finite time? If not, what must the Conserver choose as the initial park configuration to guarantee to preserve some nonpark land forever?"
I left before Ecco and Liane were able to solve the problem.
Reader: Would you like to give it a try?
Last Month's Solution
Here was Liane's solution to the first problem. She hit every value and 80 of the 81 cells. This solution missed one of the 42s.
1 2 3 4 5 6 7 8 9 18
27 16 24 14 21 12 18 10 15 8
12 6 9 4 6 2 3 4 5 6
7 8 9 18 27 16 24 14 21 12
18 10 15 8 12 16 25 20 24 28
35 32 36 40 45 48 54 56 63 72
81 64 72 56 63 48 49 42 30 36
30 20 24 28 35 32 36 40 45 54
Reader Notes
In the Perimeters problem (DDJ, August 2001), the goal was to locate guard towers for good visibility of a base in which at least 2900 were visible to one guard or more, at least 775 by three guards or more, and at least 100 by four guards or more. Liane produced a solution, but many clever readers improved on this solution: Dennis Yelle, Andrew Palfreyman, Michael Birken, Jimmy Hu, Jean-François Halleux, Steve Kietzman, Kelley Cook, Jim Rootham, Marc Bellusci, James Waldby, Tim Chase, Rene Tschaggelar, Alexander Fedorov, Rodney Meyer, Scott Williams, Tomas G. Rokicki, Jason Strickland, and Darren Seay.
Some took on the challenge of finding a configuration in which the most possible cells were visible to some guard (of which some could be visible to one guard and some to another — this is a "for all cells, there exists a guard" rather than a "there exists a guard for all cells" kind of statement). Dennis Yelle, Andrew Palfreyman, and Michael Birken were the first to give a solution in which 3119 cells were visible to at least one guard. Birken reports: "I used a series of heuristics to try to speed up the search. For instance, if the total visible area was less than 2900 or was less than the total visible area in the best solution found so far, then the guards tended to repel each other. Depending on other criteria, some tended to attract each other. The movements were governed by probability and the probabilities were updated by the heuristics."
Here is Yelle's solution:
(18,57) (35,25) (36,19) (57,29) (29,22)
in which case,
3119 square meters were visible to 1 guard or more;
1051 to 2 guards or more;
775 to 3 guards or more;
100 to 4 guards or more;
and 0 to 5 guards.
Scott Williams used a slightly different heuristic to come to a similar answer: "...the general placement is for three shacks to be placed fairly close to each other (to generate most of the 3+ meters). Place the fourth shack close enough to generate the 4+ meters (and the last few 3+ meters). Place the last shack completely isolated from the others to get the total meter count up." Tomas Rokicki found a property of his solutions: "All solutions covering 3119 are equivalent through rotation, reflection, and translation of the two independent sections."
DDJ
