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\$
12
  • 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, 2014 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, 2014 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\$ Nov 3, 2014 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, 2016 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, 2019 at 12:46

1 Answer 1

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 and acknowledge you have read our privacy policy.

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