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:
- Empty spaces are represented by either
.or a space, your call;
- Rogue's starting position is represented by, of course,
- A gold piece is represented by
- Walls are represented by
- Monsters are represented by characters from the following regexp:
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:
- The rogue can only walk through empty cells or cells containing gold;
- It takes a turn to move to a adjacent or diagonally adjacent cell;
- Picking up the gold is instant;
- The rogue can't stay adjacent or diagonally adjacent to a monster for more than one turn without waking it up, which is forbidden;
- 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.
This is code-golf, the score is the bytes count of your submission with fewer being better.
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
7) @..#.. $.$g.$ ...#.. -> 2
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
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
10) 12345678 a @....g.D b .......$ c .......# d .....h.. -> 1
A path is
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.