Joints in Space

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), 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].

Great architects like Ecco. They recognize his ability to solve tough structure and placement problems. The feeling is mutual. Ecco doesn't care much for glass towers or phony Victorian, but he holds a deep affection for Italian piazzas, well-designed airports, and clever approaches to traffic flow like the Guggenheim museum in New York or the Senkai complex in Tokyo.

The kinds of problems he's attracted to, though, usually have to do with extreme environments such as Antarctica or underwater cities.

Jordan Tyler brought him such a problem one fine winter day. Tyler's reputation had preceded him. A descendant of a famous railroad designer, he combined mathematics, architecture, and physics in all his creations. It was for that reason that a consortium of space exploration companies led by none other than Mr. Nog Tugget (readers may remember this unsavory descendant of a ruined Alaskan gold rusher) had approached Tyler to design a modular space station.

Tyler's design specified rooms consisting of symmetric cubes 10 meters on a side with a single manhole-sized door in the center of each of the six cube faces.

"We decided there was no reason to prefer one direction to another in space," Tyler explained. "In fact, I'd like to get away from the idea of rooms altogether, but the oldtimers want to be able to quarantine areas in case of leaks or toxicity problems. They've also asked me to help them design the interiors of the 48 cubes, but the first problem is how to arrange them and which company to place in each cube. That's what I'm coming to you for."

"What have they told you about what goes on in the space station?" Ecco asked.

"It is a deep commercial secret, it seems," Tyler answered. "All I know is that 15 companies are involved, each of which occupies one or more cubes that must be connected. I'll indicate this to you with a letter for each corporation, because their names are also secret."

Company Number of rooms

A 10

B 1

C 8

D 2

E 13

F 2

G 2

H 1

I 1

J 1

K 1

L 2

M 2

N 1

O 1

"Also, certain pairs of companies, due to joint ventures, must have neighboring cubes. Here, I represent the necessary adjacency relationships in alphabetical order. For example, the fourth line says that some room of D must be next to some room of A and some (possibly different) room of D must be next to some room of C, and so on for E, F, and G. There is some redundancy in this representation, but I hope it is clear.

"Lack of adjacency imposes no constraint, by the way. The fact that B is not in the adjacency set of D, for example, means that it is not necessary for any room of B to border any room of D, though this is allowed and even desirable. These companies engage in all manner of joint ventures and those joint ventures may require an exchange of materials within the space station."

A -- B C D E F H I J L M

B -- A C

C -- A B D E G M

D -- A C E F G

E -- A C D F G J K L M N O

F -- A D E J N

H -- A I L

I -- A H J L

J -- A E F I

L -- A E H I

M -- A C E

G -- C D E K

K -- E G O

N -- E F

O -- E K

"From your encoding, can we conclude M is a card sharp and K is an empath?" asked Ecco with a smile.

"Random letters produce tantalizing patterns," Tyler answered with a chuckle.

"And when you say the 13 rooms of A must be connected, all you mean is that an astronaut can float from any room in company A's space to any other without passing through any other company's cubes?" asked Liane.

"Correct," Tyler said, nodding to the 10-year old. "As I said, they are all very jealous of their secrets, more secretive in many ways than countries at war."

Reader: Ecco and Liane succeeded in discovering a placement of the cubes in three dimensions and an assignment of the companies to cubes that satisfied these constraints. Can you do it?

After Tyler left, Ecco turned to me.

"My dear professor," he said, "do you think it is possible to do better? I mean, can you find a design that satisfies these constraints but that establishes a proper superset of these adjacency relationships? If so, what is the design and what is the largest number of adjacency relationships you can find?"

Reader: Would you like to give it a try?

Last Month's Solution

When trains can carry only 50 passengers and all stations hold only two trains, this is the best Ecco and Liane could come up with:

Time Trips Started

0 min DBC, EAB, ABF, BFE, FEA

15 min CBD

30 min GBA, BAE, AEF, EFBD, DBC, CBG

45 min CBD

60 min DBC, FBC, EFB, AEF

75 min CBD

90 min Some in transit

105 min Everyone done

When trains can carry 150 passengers and station B can hold four trains, but all other stations hold only two trains, Liane suggested the following: Put the extra 50 person train at station C, so C has two trains to start with. Further, assume the 50 person train that used to start at B now starts at F.

Time Trips Started

0 FBAE (starts with 50 bound to A, picks up 100 passengers at B and proceeds to E after dropping passengers at A), DBC, CBD, AEF, EFBD (150 load at E; train drops off 100 at B and carries 50 to D), CBG (50 person train).

15 GBA (50 person train), FBC (50 person train)

Traffic at Station B:

time 0 -- 0

time 15 -- - one from FA, one from DBC, one from CBD, one from CG

time 30 -- - one from EFBD, one from GC, one from FC.

Reader Solutions to the Fair Swedes Problem

Many readers found correct solutions to the Gutoldenborg map problem (DDJ, January 1999), most by "sitting at the kitchen table and scribbling" as one reader put it. Others used genetic algorithms, gradually refining the solution. Still others used exhaustive search, but more on that later. Finally, Joe Celko managed to find a solution in SQL -- amazing! These readers sent me solutions: Juan Pancorbo, Kerry D. Millen, Pearl Pauling, Ralph Nebiker, Blaine Deal, Scot Billman, Michael S. VanVertloo, Jimmy Hu, Roger Alley, Michael Goldberg, Burghart Hoffrichter, Ernst Munter, Odd Tangen, Mike Robinson, John "Goodboy" Holland, Serguei Patchkovskii, Friedrich von Solms, Franco Venturi, Mark J. Murphy, Jeff Gerald, James Heginbottom, Bill Rooney, Jean-Philippe Langlois, Bryan S. McDaniel, Jacco Kulman, Kakulidis Iulian, Joshua Lynch, Viktor Bresan, Peter Hansen, Mathew R. Davies, and Benjamin C. Chaffin.

As Ralph Nebiker wrote, "This could be a really difficult problem if the boundary conditions and populations weren't quite so well defined. So, I decided to pursue that angle and persuaded some respondents to try to find 14 districts each having approximately 12,000 people and to make it so that the maximum deviation from 12,000 was minimal."

The three best solutions to this second problem came from Roger Alley, Friedrich von Solms, and Serguei Patchkovskii (whose exhaustive search method used 2.5 hours on a cluster of 39 500-MHz 21164 Alphas). The maximum deviation from 12,000 these solutions produced was a surprisingly low 29.

Solution

(11 48 64)

Population: 11992 Diff: 8

(8 15 19 37 66) Population: 11975 Diff: 25

(2 14 36 40 56) Population: 12022 Diff: 22

(10 31 46 62) Population: 11996 Diff: 4

(12 27 43 57) Population: 11996 Diff: 4

(5 25 47 55 58) Population: 12008 Diff: 8

(7 24 32 42 61) Population: 12005 Diff: 5

(1 23 28 45) Population: 12003 Diff: 3

(6 13 30 41 51) Population: 11996 Diff: 4

(3 17 21 33 52) Population: 12005 Diff: 5

(4 9 26 34 49) Population: 11971 Diff: 29

(22 38 50 59 65) Population: 11987 Diff: 13

(16 20 39 53 54 60) Population: 12020 Diff: 20

(18 29 35 44 63) Population: 12000 Diff: 0

DDJ