Author |
Topic: HAL 9000 Shutdown (Read 2540 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
HAL 9000 Shutdown
« on: Oct 19th, 2002, 11:59am » |
 Quote  Modify
|
HAL 9000 SHUTDOWN
Aboard the spaceship Discovery, the HAL 9000 has gone rogue and needs to be shut down as quickly as possible! The computer has M microprocessors working in parallel, each of which is located in a different area of the ship. If any N of these processors is destroyed, the HAL 9000 will become inoperational. Using your trusty hammer, you plan to do exactly that. You have a map of the spaceship, which looks like a K by K maze grid with walls here and there. Coordinates (1,1) correspond to the corner square on the bottom-left of the map. The map shows the locations of all M processors; each processor consumes one grid square. You are currently standing at coordinates (X,Y).
Having taken CS courses at the Space Academy, you realize that a computer program could help you out here. Although the on-board computers can't be trusted, you have an uncorrupted PDA that could do the job. Write an algorithm for finding the shortest route from where you are standing right now that allow you to bash N processors along the way. Assume that you can only move up, down, left, and right.
Note 1: All aforementioned variables are positive integers. M >= N. K >= X. K >= Y.
Note 2: Problem adapted from topcoder.com. Storyline by me 
|
| « Last Edit: Oct 19th, 2002, 3:24pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: HAL 9000 Shutdown
« Reply #1 on: Oct 19th, 2002, 12:45pm » |
Quote Modify
|
Does the map say WHERE the M processors are, or do you otherwise know this information (i.e. can you make it an input parameter)?
Note: Cool puzzle! It's interesting how much a storyline can increase my interest! 
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: HAL 9000 Shutdown
« Reply #2 on: Oct 19th, 2002, 1:04pm » |
Quote Modify
|
Hehe oops. Man I never seem to get anything right the first time. Yes the map tells you where the processors are, I've fixed it now
Yup, storylines are really important for generating interest.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
Guest
|
This seems to be some variant of the travelling sales-man problem..
The easy solution would be making a table of all distances from every processor to every processor (use a maze-solver for this), then take all combination leading past all processors (or at least N different ones) and take the one that brings you past N the fastest..
But you'd be dead before your PDA's done.. (unless N is trivially small). Even optimal algorithms would still be NP-complete I think (unless I've missed something vital), so lots of waiting for large N..
Now it really get's fun when HAL throws up obstacles you don't know about, blocking some corridors. Now find an optimal path with redundancy for, let's say, 2 obstacles..
|
|
IP Logged |
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: HAL 9000 Shutdown
« Reply #4 on: Oct 30th, 2002, 4:19pm » |
Quote Modify
|
Fortunately, when this problem was posted on topcoder, N was limited to a maximum of 6 doorknobs (er.. processors), so I used towr's solution when I actually solved this one; I tested all N! different paths.
wwu, I didn't know you did TC... what name do you use?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove