8
\$\begingroup\$

This challenge is inspired by a board game I played some time ago.
The story of this challenge doesn't necessarily have to be read, the goal of the challenge-section should explain everything necessary.

The Story

People are locked inside a large room with a human-devouring monster. The walls of the room are enchanted, teleporting objects across the room when touched. Said monster marches across the room, hunting for flesh. The first human in its sight will be consumed by its sharp teeth.

The Goal of the Challenge

You are given the map of the room, including the people's and the monster's location.

%%%KLMNOPQRSTA%
%%J           B
%I       %    C
H             D
G   %%        E
F             F
E      %      G
D             H
C   %        I%
B           J%%
%ATSRQPONMLK%%%

Let's break down the components of the map.

  • Letters from A to T: If the monster steps onto one of these, it will be teleported to this letter's second appearance and not change its direction. There will only ever be zero or two of any letter on the board.
  • %: Wall tiles. Just for formatting & nice looks.
  • #: The monster's starting location.
  • *: The people's locations.
  •  : Empty tiles, the monster can move freely on them.

Some additional things to note about the map:

  • The map dimensions and object location will not be constant, so your code will have to dynamically adapt to that.

The monster will always go in the direction that it currently facing (facing west at the start) unless it spots a human, in which case it will turn towards the closest human.
The monster spots a human if there are no wall or teleporter tiles in a straight horizontal or vertical line between it and the human.

Another thing to note is that if the monster is in front of a solid wall (%) or has to decide between two humans, it will always prioritize right over left.

If the monster is not able to turn right and make a step forwards for some reason, it will turn left instead.

So, in the end, the order that the monster prioritizes directions would we forward, right, left, backwards.

Input

  • The map, including the monster's starting location and the people's positions as their respective characters. There should not be any other input than the map string, or the array of strings, or characters.

The input may be received in any reasonable format; a single string or an array of strings for the map.

Output

The coordinate of the person that first gets eaten by the monster.

The coordinates start from the top-left corner and are 0-indexed, so the first tile will have the coordinates (0|0). If you are using 1-indexing, please specify it in your answer.

Rules

  • This is , the shortest code in bytes in any language wins.
  • Standard loopholes are forbidden.
  • You may assume that the monster will always be able to reach a human.

Test Cases

Input:

%%%KLMNOPQRSTA%
%%J           B
%I       %*   C
H   *         D
G   %%        E
F       #     F
E      %      G
D      *      H
C   %        I%
B           J%%
%ATSRQPONMLK%%%

Output: (10,2), since the monster cannot see the two other people when it runs past them, it gets teleported to the other F wall, where it will then see the last person.

Input:

%%%KLMNOPQRSTA%
%%J           B
%I      *     C
H     %%%   * D
G      #%     E
F     %%%   % F
E             G
D       %     H
C       *    I%
B       *   J%%
%ATSRQPONMLK%%%

Output: (12,3)

Input:

%%%KLMNOPQRSTA%
%%J           B
%I     %%%    C
H     *%#%    D
G             E
F             F
E       %     G
D             H
C            I%
B           J%%
%ATSRQPONMLK%%%

Output: (6, 3)

Input:

%%%%%%%%%%%%%%%
%#%       %%% %
%A%ABCD   %*% %
%*F     G %%% %
% %BC% FD     %
% %   %    %%%%
% %  %       %%
%   % %%   G  %
%             %
%*%    %    % %
%%%%%%%%%%%%%%%

Output: (1,9)


Good luck!

\$\endgroup\$
1
  • \$\begingroup\$ You should state, explicitly and early in the description, that the humans don't move. I didn't realize at first that they are stationary. If I were a human in that situation, I'd certainly be moving! \$\endgroup\$
    – DLosc
    Sep 28, 2017 at 16:48

3 Answers 3

7
\$\begingroup\$

Python 2, 565 .. 422 4451 .. 444 4632 .. 468 467 463 bytes

u,U='*%'
G=lambda s:u==s.strip('# ')[0]and len(N)-s.find(u)
b=input()
D=3;j=''.join;N,w,P,t,B=j(b),len(b[0]),[0,1,0,-1],{},map(j,zip(*b))
for c in N:
 l,r=N.find(c),N.rfind(c)
 if u<c:t[l]=r;t[r]=l
 if'#'==c:x,y=l%w,l/w
while u!=b[y][x]:
 O=[B[x][y-1::-1],b[y][x+1:],B[x][y+1:],b[y][x-1::-1]];L,R=O[D-1],O[~D]
 if u<b[y][x]:X=t[x+w*y];x,y=X%w,X/w
 elif(G(O[D])<1)*(G(R)+G(L)+(U==O[D][0])):D-=0<G(L)>G(R)or(U==R[0])*-~(U==L[0])or-1;D%=4
 x+=P[D];y+=P[~D]
print x,y

Try it online!

Saved a lot of bytes thanks to Halvard, Ian and Jonathan

1: Got longer, in order to fix the case of turning twice, and to find the location of the monster.
2: Got even longer.. Monster shouldn't change direction on when teleporting.

\$\endgroup\$
12
  • \$\begingroup\$ Somewhat golfed to 482 bytes. Shortened link due to TIO being to long \$\endgroup\$ Sep 27, 2017 at 16:44
  • \$\begingroup\$ @Halvard A small golf, just 1 byte: 481 \$\endgroup\$
    – user74686
    Sep 27, 2017 at 17:00
  • 1
    \$\begingroup\$ l.replace('#',' ') -> l.replace(*"# "). \$\endgroup\$ Sep 27, 2017 at 17:47
  • \$\begingroup\$ Fixed, but now it's the same length as yours, 434 bytes \$\endgroup\$
    – user74686
    Sep 27, 2017 at 19:44
  • 2
    \$\begingroup\$ @KevinCruijssen I know Ian said my answer counts as valid, but I'll change it anyway. \$\endgroup\$
    – TFeld
    Sep 28, 2017 at 7:55
6
\$\begingroup\$

Perl 6, 343 334 333 328 322 308 bytes

{my \m=%((^@^a X ^@a[0]).map:{.[0]i+.[1]=>@a[.[0]][.[1]]});my \a=m<>:k.classify
({m{$_}});my$m=a<#>[0];my$d=-1;{$d=($d,i*$d,-i*$d,-$d).min({$^q;first ?*,map
{(((my \u=m{$m+$_*$q})~~"%")*(1+!($_-1))+(u~~"A".."Z"))*m+(u~~"*")*$_},^m});
$m+=$d;$m=$d+(a{m{$m}}∖~$m).pick while m{$m}~~"A".."Z"}...{m{$m}~~"*"};$m}

Try it online!

(There are no newlines in the actual code. I inserted them just to wrap the lines for easier reading.)

This is unable to deal with maps where it is possible to see outside of the map bounds. (I. e. maps with empty spaces at the border.) If this matters, +5 bytes. But, since the teleporters block LoS now, it shouldn't.

Explanation: It's a function which takes the map as a list of lists of characters. Let's break it down into statements:

my \m=%((^@^a X ^@a[0]).map:{.[0]i+.[1]=>@a[.[0]][.[1]]});: Let's make a hash ("dictionary" for Pythonists) called m (it's a sigilless variable, so we need to be explicit about assigning a hash into it with %(...)) which associates complex keys of form x+iy with characters which are in the yth rown and xth column of the map.

my \a=m<>:k.classify({m{$_}});: This makes an "inverse dictionary" of m, called a: there is one key corresponding to each value in m, and the value is a list of complex coordinates (keys in m) that contain that character. So, for instance a{"#"} will give a list of all coordinates where there is a # on the map. (This is also a sigilless variable, but we're in luck since classify returns a hash.)

my$m=a<#>[0];my$d=-1: Set the initial monster position. We look up the # in the inverse hash a. We must use [0] since a<#> is still a list, even when it contains only 1 element. The $d contains the direction of monster; we set it to the West. (The direction is a complex number as well, so -1 is west.)

OK, the next statement is quite nasty. First, let's have a look at this: {$^q;first ?*,map {(((my$u=m{my$t=$m+$_*$q})~~"%")*(1+!($_-1))+($u~~"A".."Z"))*m+($u~~"*")*abs($t-$m)},^m} This is a routine that evaluates LoS in the given direction. If there is a human in this direction, it returns the distance to the human. If there is a wall or a teleport in this direction, it returns the total number of squares of the map. (The point is to give such a high number that it is greater than any legitimate distance to a human.) Finally, if the wall is in this direction and in distance 1, we return 2 × total number of squares of the map. (We want never ever be running through walls, so these need even a bigger score. We will be choosing the minimum shortly.)

We use this in the construct $d=($d,i*$d,-i*$d,-$d).min( LoS deciding block );. Since we use complex numbers for everything, we can easily get directions which are relative forward, right, left and backwards from the original direction just by multiplying it by 1, i, -i (remember that the y axis goes the other way that you may be used to from math) and -1, respectively. So we form the list of directions in this order, and find the direction which has the minimal "distance to a human" (according to the block above), which makes sure that any human beats any wall and anything beats a wall which is right under the monster's nose. We use the fact that the min function gives the first minimal value. If there is a tie in distance between several directions, the monster will prefer forward to right to left to backwards, which is exactly what we want. So we get a new direction which is then assigned to $d.

$m+=$d; just makes the monster step in the new direction.

$m=$d+(a{m{$m}}∖~$m).pick while m{$m}~~"A".."Z" takes care of the teleports. Let's say the monster is at a teleport A. First we search for A in the inverse hash %a and that turns up the two positions of the teleport A, then we discard the current position using the set difference operator (which looks like a backslash). Since there are exactly 2 occurences of each teleport on the map and the monster is surely standing on one, the difference will be a set with 1 element. We then use .pick to pick a random element (believe or not, but this is the shortest way to get the element of 1-element set :—)). This kind of thing happens until the monster ends up somewhere not in a portal.

Everything in the last 4 paragraphs describes one massive construction of form {change direction; step; handle teleports}...{m{$m}~~"*"}. This is a sequence that calls the block on the left of ... until the condition on the right of the ... is true. And that one is true when the monster is on a square with a human. The list itself contains return values of the huge block on the left, which is garbage (most likely (Any)) because it returns the value of the while loop at the end. Essentially, we use it as a cheaper while loop. The value of the list is discarded (and the compiler moans about a "useless use of ... in a sink contest", but who cares). When this all is done, we return $m — the monster's position after it found a human, still as a complex number (so, for the first test, we give 10+2i and so on).

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice explanation! :) \$\endgroup\$
    – Ian H.
    Sep 27, 2017 at 20:32
  • \$\begingroup\$ This is priceless. Absolutely Brilliant and pure elegant explanation! \$\endgroup\$ Mar 18, 2021 at 11:07
3
\$\begingroup\$

JavaScript (ES6), 258 245

g=>eval("m=g[I='indexOf']`#`,D=[w=g[I]`\n`+1,-1,-w,k=t=1],g=[...g];for(n=1/0;n;(o=g[m+=d=D[k]])>'@'?g[g[u=m]=t=1,m=g[I](o),u]=o:o<'%'?t=1:o<'*'&&(m-=d,k=k+t++&3))D.map((d,j)=>{for(q=0,u=m;g[u+=d]<'%';++q);g[u]=='*'&n>q&&(n=q,k=j)});[m%w,m/w|0]")

Less golfed

g=>{
    var u, // temp current position 
        q, // distance so far scanning for a human
        o, // value of grid at current position
        d, // offset to move given current direction
        n = 1/0 // current distance from human
        m = g.indexOf(`#`), // monster position
        w = g.indexOf(`\n`)+1, // grid width + 1 (offset to next row)
        D = [w,-1,-w,1], // offset for moves, clockwise
        k = 1, // current direction, start going west
        t = 1; // displacement for turn
    g=[...g]; // string to array
    while (n) // repeat while not found (distance > 0)
    {
      // look around to find humans
      D.forEach( (d,j) => { // for each direction
        // scan grid to find a human
        for(q=0, u=m; g[u+=d]<'$'; ++q); // loop while blank space
        if ( g[u] == '*' // human found at position u
             & n>q ) // and at a shorter distance than current
        {
           n = q; // remember min distance
           k = j; // set current direction
        }
      })
      // if human found, the current direction is changed accordingly
      d = D[k] // get delta
      m += d // move
      o = g[m] // current cell in o
      if (o > '@') // check if letter (teleporter)
      {
        t = 1 // keep current direction, next turn will be right
        u = m // save current position in u
        g[u] = 1 // clear current cell, so I can find only the other teleporter
        m = g.indexOf(o) // set current position to other teleporter
        g[u] = o // reset previous cell content
      }
      else if (o > '%') // check if '*'
      {
        // set result, so we can exit the loop
        r = [ m%w, m/w|0 ] // x and y position 
      }
      else if (o == '%') // check if wall
      {
        // turn
        m -= d // current position invalid, go back
        k = (k+t) % 4 // turn right 90° * t
        t = t+1 // next turn will be wider
      }
      else
      {
        t = 1 // keep current direction, next turn will be right
      }
    }
    return r
}

Test

var F=
g=>eval("m=g[I='indexOf']`#`,D=[w=g[I]`\n`+1,-1,-w,k=t=1],g=[...g];for(n=1/0;n;(o=g[m+=d=D[k]])>'@'?g[g[u=m]=t=1,m=g[I](o),u]=o:o<'%'?t=1:o<'*'&&(m-=d,k=k+t++&3))D.map((d,j)=>{for(q=0,u=m;g[u+=d]<'%';++q);g[u]=='*'&n>q&&(n=q,k=j)});[m%w,m/w|0]")

var grid=[`%%%KLMNOPQRSTA%\n%%J           B\n%I       %*   C\nH   *         D\nG   %%        E\nF       #     F\nE      %      G\nD      *      H\nC   %        I%\nB           J%%\n%ATSRQPONMLK%%%`
,'%%%KLMNOPQRSTA%\n%%J           B\n%I      *     C\nH     %%%   * D\nG      #%     E\nF     %%%   % F\nE             G\nD       %     H\nC       *    I%\nB       *   J%%\n%ATSRQPONMLK%%%'
,'%%%KLMNOPQRSTA%\n%%J           B\n%I     %%%    C\nH     *%#%    D\nG             E\nF             F\nE       %     G\nD             H\nC            I%\nB           J%%\n%ATSRQPONMLK%%%'
,'%%%%%%%%%%%%%%%\n%#%       %%% %\n%A%ABCD   %*% %\n%*F     G %%% %\n% %BC% FD     %\n% %   %    %%%%\n% %  %       %%\n%   % %%   G  %\n%             %\n%*%    %    % %\n%%%%%%%%%%%%%%%'
]
$(function(){
  var $tr = $('tr')
  grid.forEach(x=>{
    $tr.eq(0).append("<td>"+x+"</td>")
    $tr.eq(1).append("<td>"+F(x)+"</td>")
  })
})
td {padding: 4px; border: 1px solid #000; white-space:pre; font-family:monospace }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table ><tr/><tr/></table>

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