11
\$\begingroup\$

Challenge

Walking around Marks and Spencers, I noticed that they had air conditioning units placed randomly around the shop. Wanting to keep cool, I wondered what was the easiest way to move around the whole shop without being away from an air conditioning unit for too long.

Given a map, you must find a way to travel around the whole map keeping the distance from an air conditioning unit as short as possible (even if the AC unit is on the other side of a wall).

Map

The map may be supplied in any way you like and uses the following symbols:

+ is a corner of a wall
| is a east/west facing wall
- is a north/south facing wall
X is an air conditioning unit
S is the start and end point

An example map would be:

+------S---+
|   X      |
| ---+-+ X |
|    |X|   |
| ---+ +---+
|   X      |
+----------+

or

+---+--+
| X |  |
|   |  +-----+------+
|   | X      | X    |
|     ---+       |  S
|   |    |  X    |  |
|   |  +-+-------+--+
| X    |
+------+

Travelling around the whole map means passing through every empty space and air conditioner. You cannot travel through a wall and may only travel orthogonally. A map may not always be rectangular.

Keeping the distance as short as possible from an AC unit is the sum over all time steps.

Passing through means entering and leaving.

You may output the path in any way you like. Examples include:

  • Outputting the map with the path included
  • Outputting the path as a succession of compass points (e.g. NNSESW)
\$\endgroup\$
  • 2
    \$\begingroup\$ @BetaDecay And how is that calculated? The maximum distance at any point in time? The sum/average of the distance over all time steps? \$\endgroup\$ – Ingo Bürk Nov 2 '14 at 13:17
  • 5
    \$\begingroup\$ It's impossible to understand what the goal of this problem is. If you must visit every square, the maximum distance is a constant. \$\endgroup\$ – feersum Nov 2 '14 at 23:37
  • 1
    \$\begingroup\$ @feersum Why is that? Couldn't the map layout make it necessary to revisit certain squares and thus giving multiple possibilites for the pathing? \$\endgroup\$ – InvisiblePanda Nov 3 '14 at 9:09
  • 6
    \$\begingroup\$ Is this an optimization problem? If not, there should be some test cases with correct outputs. \$\endgroup\$ – mbomb007 Dec 23 '16 at 17:25
  • 2
    \$\begingroup\$ Could u give us the distance for the only two possible traveling way for the first example? \$\endgroup\$ – mdahmoune Feb 6 at 12:46
1
\$\begingroup\$

PowerShell for Windows, 376 367 bytes

Like a lazy man, I don't go to every shelf, I move from air conditioner to air conditioner in a store. I believe I traveled all over the store visiting every air conditioner in it.

$f={param($m,$d,$o=@{})$w=(($l=$m-split"
")|% le*|sort)[-1]
$m=($l|% *ht $w)-join"
"
if(!$o.$m-or$o.$m-ge$d-and$m-match'(?s)X.*S|S.*X'){$o.$m=$d++
$n=-split")X(S )X(.{$w}S S)X( S.{$w})X("|%{sls "(?s)^(.*$_.*)$" -inp $m -a|% m*|%{($_.Groups-replace'S',' ')[1,2]-join'S'}}
$d=(($n+,($m-replace"(?s)(?<=S(.{$w})?) | (?=(.{$w})?S)",'S')*!$n)|%{&$f $_ $d $o}|sort)[0]}+$d}

Try it online!

Unrolled:

$f={
    param($map,$distance,$o=@{})
    $lines = $map-split"`n"
    $width = ($lines|% length|sort)[-1]
    $map = ($lines|% padRight $width)-join"`n"                              # to rectangle

    if(!$o.$map -or $o.$map-ge$distance -and $map-match'(?s)X.*S|S.*X'){
        $o.$map = $distance++                                               # store a map to avoid recalculations
        $n = -split")X(S )X(.{$width}S S)X( S.{$width})X("|%{               # search a nearest X in 4 directions
            select-string "(?s)^(.*$_.*)$" -InputObject $map -AllMatches|% Matches|%{
                ($_.Groups-replace'S',' ')[1,2]-join'S'                     # start a new segment (reset all S and replace the nearest X by S)
            }
        }
        $stepMore = $map-replace"(?s)(?<=S(.{$w})?) | (?=(.{$w})?S)",'S'
        $n += ,$stepMore*!$n                                                # add a step if X was not found
        $distance=($n|%{&$f $_ $distance $o}|sort)[0]                       # recursive repeat
    }

    +$distance
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.