Dig That

Dennis Shasha

Omniheurist Course

Computer Science



There is a grid . 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.

Suppose a probe can tell whether a tunnel ran under an intersection or not and which of the four possible entering streets the tunnel runs under. We call these directional probes.

If the tunnel is at most k blocks long and begins at Start and ends at End, then what is the minimum number of directional probe devices you would need to place to guarantee to determine the precise route of the tunnel in two hours? That is, you'll place some number of probes in the first hour and you can move those probes in the second hour based on the responses from the first. Your score is the maximum number of probes you use in either hour.

Your Task

You will take the role of a Detector and a Badguy. An outside challenger will specify a number k such that the Badguy is allowed a length k for the tunnel. The Detector will compute and then claim that it can detect a tunnel using p probes (which is the maximum of the number of probes needed in the two hours). The Detector will tell the architect where they should go. The Badguy will not be informed of their placement, but will place a tunnel of length k blocks or fewer. The architect will tell the Detector which probes noticed a tunnel and the directions of the streets in which the tunnel is also present The Detector will then propose a route. If Detector's route and Badguy's route are the same, then Detector gets the score p. Otherwise, the Detector gets the score infinity. The winner is the Detector who gets the lowest score.

Architecture Team

Your job is to draw the grid, then place the probes, then show the BadGuy route, then report which probes detect the tunnel, then show the Detector's predicted route in a different color and evaluate success. Keep track of the time of each player.