wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> HAL 9000 Shutdown
        
(Message started by: william wu on Oct 19^th, 2002, 11:59am)

Title: HAL 9000 Shutdown
Post by william wu on Oct 19^th, 2002, 11:59am

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 :D

Title: Re: HAL 9000 Shutdown
Post by Pietro K.C. on Oct 19^th, 2002, 12:45pm

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! :)

Title: Re: HAL 9000 Shutdown
Post by william wu on Oct 19^th, 2002, 1:04pm

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.

Title: Re: HAL 9000 Shutdown
Post by towr on Oct 20^th, 2002, 12:36pm

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..

Title: Re: HAL 9000 Shutdown
Post by Garzahd on Oct 30^th, 2002, 4:19pm

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?