Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
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 tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developersí questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
Reply
 
Thread Tools Display Modes
  #1 (permalink)  
Old August 31st, 2007, 12:18 PM
Registered User
 
Join Date: Aug 2007
Location: , , .
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.

Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off



All times are GMT -4. The time now is 12:20 AM.


Powered by vBulletin® Version 3.7.0
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.