Wrox Programmer Forums
BOOK: Puzzles for Programmers and Pros BOOK ISBN: 978-0-470-12168-9
This is the forum to discuss the Wrox book Puzzles for Programmers and Pros by Dennis Shasha; ISBN: 9780470121689
Welcome to the p2p.wrox.com Forums.

You are currently viewing the BOOK: Puzzles for Programmers and Pros BOOK ISBN: 978-0-470-12168-9 section of the Wrox Programmer to Programmer discussions. This is a community of software programmers and website developers including Wrox book authors and readers. New member registration was closed in 2019. New posts were shut off and the site was archived into this static format as of October 1, 2020. If you require technical support for a Wrox book please contact http://hub.wiley.com
Old August 31st, 2007, 12:18 PM
Registered User
Join Date: Aug 2007
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Default Dig That!

It seems to me that to solve Part 1, a much more straightforward way is to put probes at the start intersection and the next 5 vertically above it. If the tunnel deviates from the center line, you've got a probe to show where and in which direction. When it returns, it either returns to a probe, in which case you know where it returned or it returns directly at the end intersection in which case you know because no probes triggered after it deviated from the center. Since you know which direction it deviated to, you know how it gets back in this case.

In part 2, I believe that only 4 hours/probes are necessary. The first three go on the center line at rows 2, 4 and 6. The information gathered from these probes tells you where he deviated from the center line (if at all) and where he returned. If he leaves at a probe intersection, it's obvious enough from the info gathered there. If he leaves prior to a probe intersection (rows 1,3, or 5) then all the probes prior to that intersection will show him travelling through and that intersection will be left untriggered. The place where he returns is symmetrically identical. So now you know where he left and returned but not necessarily in which direction. Just place your fourth probe on column 3 on an intersection where you know he's left the center column. If it fires, he deviated left, if not, he deviated right. That's all the info necessary to reconstruct the entire tunnel. Some of this process may be shortcut and require fewer than four probes, but four are the max.

I'm a bit confused as to your answer to number 2. You seem to assume that any single probe solution must match the multiprobe solution in some order. I guess everything you say in the answer is technically correct - you CAN do it in six hours - but it doesn't address the question which is "what is the minimum". Certainly, it's the minimum if you restrict yourself to the sites in the original 6 site solution but there's no argument as to why that should be necessary. Do I misunderstand the problem? Perhaps.

Powered by vBulletin®
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Copyright (c) 2020 John Wiley & Sons, Inc.