Roguelike pathfinding

Question

Roguelike pathfinding

Your task will be, given a two-dimensional array of the elements described below, which represents a dungeon, to output or return a single number representing the amount of gold pieces the rogue can collect without waking up any monsters.

The elements of the array are as follows:

1. Empty spaces are represented by either . or a space, your call;
2. Rogue's starting position is represented by, of course, @;
3. A gold piece is represented by $;
4. Walls are represented by #;
5. Monsters are represented by characters from the following regexp: [a-zA-Z*&].

The array shall not contain any characters not listed above, so you can assume that anything that is not a wall, an empty space, the rogue or a gold piece is a monster.

The rules for pathfinding are:

1. The rogue can only walk through empty cells or cells containing gold;
2. It takes a turn to move to a adjacent or diagonally adjacent cell;
3. Picking up the gold is instant;
4. The rogue can't stay adjacent or diagonally adjacent to a monster for more than one turn without waking it up, which is forbidden;
5. The rogue can enter the awareness area of a monster any number of times, the monster will only wake up if the rogue spends two consecutive turns near it.

Input and output rules

You can get the input in any reasonable format, including a two-dimensional array, a flat array, a string or whatever else. If it makes your life easier, you may also take the dimensions of the array as well.

It's guaranteed that the rogue will not be near a monster at the beginning.

A full program or a function is fine.

Scoring

This is code-golf, the score is the bytes count of your submission with fewer being better.

Test cases

I use dots for empty spaces here for readability purposes, if you so desire you may use spaces (see above). Also note that this is a pure coincidence that the rogue is always in the upper-left corner, your code should handle any other valid position as well.

1)
@..
.$.
...  -> 1

Just a sanity test.

2)
@....
...g$
.....  -> 0

Again, a sanity test.

3)
@....
...$g
.....  -> 1

The rogue can grab the gold by moving in from the left.

4)
@....g..
.......$
........
.....h..  -> 1

The rogue can zig-zag between the monsters, never staying for more than one turn near each.

5)
@....z..
.......$
.....b..  -> 0

The tactics from the previous test case don't work here - the monster sensitivity areas overlap.

6)
@$#.
###$
....  -> 1

Sanity test.

7)
@..#..
$.$g.$
...#..  -> 2

Ditto.

8)
@#.d#$
$...##
e.....
..$...
##..$b
.#..g$  -> 3

Of all the gold here, only three can be reached safely: the gold near the starting position can be got by moving down one and then back to the starting position. To escape from the top left corner the rogue has to move diagonally down-right twice. The gold in the middle poses no challenge. The outer gold guarded by g and b can be got by moving in diagonally from the place to the right of the middle gold and then back. The rest cannot be got: top-right gold is blocked by walls, and the bottom-right gold requires two turns in monster sensitivity areas.

The following test cases were generously donated by mbomb007.

9)
  12345678
a @....g.D
b .......$
c ......#.
d .....h..  -> 1

This one is tricky. A path is b4-b5-c6-b7-c8-b8(grab).

10)
  12345678
a @....g.D
b .......$
c .......#
d .....h..  -> 1

A path is [bc]4-c5-b6-c7-b8(grab).

11)
  12345678
a @....g.D
b ......#$
c .......#
d .....h..  -> 1

The extra wall doesn't actually change anything, [bc]4-c5-b6-c7-b8(grab) is still a solution.

Answer 1

previous solutions (part of them) can be found in the footer container in the tio link (those are probably more readable)

JavaScript (Node.js),883 436 411 360,345 311 bytes

g=>g.map((r,y)=>[...r].map((c,x)=>A+=c=="$"&&P(g,x,y)),A=0)|A
P=(g,x,y,m={},p={},I=i=9,M={})=>{if(/[.$]/.test(c=(g[y]||0)[x])){for(;i--;)if(/^[^.@$#]$/.test(C=(g[y+~-(i/3)]||0)[x+i%3-1])){if(m[C])return
M[C]=1}for(;I--;)if(!p[(X=x+~-(I/3))+","+(Y=y+I%3-1)]&&P(g,X,Y,M,{...p,[x+","+y]:1}))return 1}return c=="@"}

Try it online!

Explantion -

instead of going from the player to the cash i went from the case to the @. i think i should be faster because i know when to stop looking (reach the @) , and when you look for cash you need to always keep moving until you covered all of the spots (and the ways to get to them). so the algo is pretty simple that way - the main function g.map((r,y)=>[...r].map((c,x)=>A+=c=="$"&&P(g,x,y)),A=0)|A: find cash -> if you found it -> start looking for the player -> if you found him -> increment A now lets got to the path finder aka P if(/[.$]/.test(c=(g[y]||[])[x])) just check if the current cell is "special" -> if so we want to return if its a player. special cases : @#(monster)

for(;i--;) if(/^[a-zA-Z*&]$/.test(C=(g[y+~-(i/3)]||0)[x+i%3-1])) -> if my neighbor is a monster {if(m[C])return false -> and it already was in the previous turn - this path is not value M[C]=1} -> if not just add it to the neighbors monsters for(;I--;) if(!p[(X=x+~-(I / 3))+","+(Y=y+I%3-1)]&&P(g,X,Y,M,{...p,[x+","+y]:1}))return true iterate neighbors again - if i wasn't already there (p is the path taken) continue path (call P)

Answer 2

Python3, 710 bytes

E=enumerate
def F(s,c,C,O,e,M,x,y,U):
 r=[]
 for X,Y in s:e[(x,y)]=e.get((x,y),[])+[((X,Y),c)];r+=[(O+[(x,y)],X,Y,c+C*((X,Y)not in U),M,U+[(X,Y)]*C)]
 return r
def f(b):
 d,D={4:[]},[]
 for x,r in E(b):
  for y,v in E(r):d[K]=d.get(K:=[[[[4,3][v=='$'],2][v=='#'],1][v=='.'],0]['@'==v],[])+[(x,y)];D+=[(x,y)]
 C,e=[],{}
 q=[([],*d[0][0],0,set(),[])]
 while q:
  O,x,y,c,M,U=q.pop(0)
  if c==len(d[3]):return c
  o={a:[(x+X,y+Y)for X,Y in[(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]if(P:=(x+X,y+Y))in b and[]==[1 for(J,K),w in e.get((x,y),[])if(J,K)==P and w>=c]]for a,b in d.items()}
  if not M&{*o[4]}:C+=[c];q=F(o[3],c,1,*(P:=[O,e,{*o[4]},x,y,U]))+q+F(o[1],c,0,*P)+F(o[0],c,0,*P)
 return max(C+[0])

Try it online!