Puzzles for Programmers and Pros

5.1. Dig That!

Imagine a road grid with seven rows as in Figure 1-11.

Figure 5.1. Somewhere between Start and End in this road network is an eight-block tunnel some bad guys have built.

Some bad guys have placed a tunnel from the bottom, beginning at the intersection marked Start in the south, and ending at End in the north. The tunnel follows the path of the roads somehow but may wind around. It is also a simple path (no dead ends and no loops along the way). You want to probe a minimum number of times and yet be able to find the exact route of the tunnel.

A probe device takes an hour to set up. We can set them up at intersections or in the middle of the street. If you establish a probe on a street, you can tell whether the tunnel follows the street. If you set the probe up at an intersection, you can tell whether the tunnel passes through the intersection, and, if so, according to the engineering team, which adjacent streets it goes to.

1. If the tunnel is at most eight blocks long and begins at Start and ends at End, then what is the minimum number of probe devices you would need to guarantee to determine the precise route of the tunnel in one hour?

2. If you had only one probe, what is the minimum time it would take to guarantee to determine the outcome, assuming you could move the ...