Where will the gem-picking robot end up?

Question

Related puzzle: Pathfinder (available on Puzzle Picnic)

Background

A robot is standing on a cell of a rectangular grid, where each cell has one or more gems except for the one with the robot. The robot can move to a horizontally or vertically adjacent cell in one step, and it picks up one gem from the cell it steps on.

The robot is programmed with which cell to choose for its next step, based on the number of gems each adjacent cell contains. The program is in the form of a > b > c > ... > z, which means that the robot prefers to move into the cell with a gems, followed by one with b gems, and so on. Any such program contains positive integers from 1 to n exactly once, where n is the length of the program. The robot will never move into any cell with no gems.

If there are multiple highest-priority cells around the robot, or all the cells around it are empty, it will get stuck at that point.

For example, if its program is 1 > 3 > 2 (meaning, it prefers the cell with only one gem the most, followed by the one with 3 gems, and then 2 gems) and the current state looks like this (R is the robot, the numbers are gems):

0 3 2
2 R 1
1 2 3

Then it will choose the cell on its right because 1 has the highest priority. Assuming the cell with R is empty, it will continue moving down, left, left, right, right, then get stuck since the cells around it have no gems left.

0 3 2     0 3 2     0 3 2     0 3 2     0 3 2     0 3 2     0 3 2
2 R 1 --> 2 0 R --> 2 0 0 --> 2 0 0 --> 2 0 0 --> 2 0 0 --> 2 0 0
1 2 3     1 2 3     1 2 R     1 R 2     R 1 2     0 R 2     0 0 R
       R         D         L         L         R         R

Using the 1 > 3 > 2 program, it will get stuck at any of the following cases:

0 R 0  # all adjacent cells are empty
2 0 1
1 2 2

3 1 0  # there are two 1s around the robot, so it can't decide where to go
2 R 1
1 0 2

Challenge

Given the initial state of the entire grid and the robot's program, find the position (horizontal and vertical coordinates) in the grid where the robot will eventually get stuck.

The initial state contains the numbers between 1 and 9 inclusive, except for a single 0 which denotes the initial position of the robot. The program is guaranteed to contain all positive numbers that appear in the grid, and the program is always valid (contains each of 1 to the maximum value on the grid exactly once).

You can take the input (grid and program) in any suitable format, and output the coordinates in any sensible way.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

In the example I/O provided, the program has the highest precedence coming first, and the coordinates are 1-based.

Grid:
0 2 1
3 3 2
1 1 3
Program: 3 1 2
Result: 2nd row, 3rd column (Path: DRDRUUD)

Grid: (one row)
0 3 2 3 1 4 4
Program: 4 2 3 1
Result: 1st row, 7th column (Path: RRLRRRRRLRLRLR)

Grid:
0 1 3
3 1 3
2 1 2
Program: 3 1 2
Result: 3rd row, 3rd column (Path: DRRULRDD)

Grid:
2 3 1 2 1
2 0 3 2 2
1 1 3 1 1
Program: 1 3 2
Result: 2nd row, 4th column (Path: DLUUDURRDDRRUULD)

Same grid as above, Program: 3 2 1
Result: 2nd row, 2nd column (Stuck at zero moves)

Answer 1

Python 2, 205 198 bytes

def s(g,w,r):
 p=g.index(0)
 while 1:
    a=[((r+[0]).index(v),n)for n,v in enumerate(g)if(abs(n-p)in[1,w])>(p-n)%w*(p/w!=n/w)];m,n=min(a)
    if~-sum(k[0]==m<len(r)for k in a):return p/w,p%w
    p=n;g[p]-=1

-6 bytes thanks to @ovs

-1 byte thanks to @user202729

Try it online!

Take the input grid as a flattened list with width also passed. Outputs 0-indexed (x,y) coordinates of the final position (I doubt index in the flattened list would be acceptable).

Explanation:

# Function of flattened grid g, width w, pRiorities r
def s(g,w,r):
    # starting position p
    p = g.index(0)
    while 1:
        a = [
            # pair (priority rank of the cell, cell id)
            # priority rank is n for v=0
            ((r+[0]).index(v),n)
            # for each adjacent cell id n with v gems
            for n,v in enumerate(g) if abs(n-p) in [1,w] and (p%w==n%w or p/w==n/w)
        ];
        # min comparison is done by tuple, so it selects one with minimum priority rank
        # m = min priority rank; n = corresponding cell id
        m,n = min(a)
        if sum( # how many adjacent cells
            k[0]==m # have priority rank equal to m
            <len(r) # and the cell value is not 0
            for k in a
        ) ^ 1: # If this count is not 1, then the robot is stuck; return
            return(p/w, p%w)
        # Otherwise, continue with updated position,
        p = n;
        # and take one gem
        g[p] -= 1

Answer 2

Charcoal, 70 bytes

≔⪪Ｓ¹θＷＳ⊞υι≔⪫υ¶ηＰη…η⌕η0≔ＥＫＶ⌕θιυＷ⁼¹№υ⌈υ«Ｍ✳⁻χ⊗⌕υ⌈υＰＩ⊖ＫＫ≔ＥＫＶ⌕θκυ»≔⟦ⅈⅉ⟧υ⎚Ｉυ

Try it online! Link is to verbose version of code. Takes input as the program in ascending order of priority and then the newline-terminated grid and outputs 0-indexed coordinates. Explanation:

≔⪪Ｓ¹θ

Input the program as separate characters.

ＷＳ⊞υι≔⪫υ¶η

Input the grid.

Ｐη…η⌕η0

Print the grid without moving the cursor, then print the part up to the 0 so that the cursor is now at the starting cell.

≔ＥＫＶ⌕θιυ

Get the priorities of the neighbours of the starting cell (or -1 for directions that lie outside the grid).

Ｗ⁼¹№υ⌈υ«

Repeat while there is exactly one neighbouring cell of highest priority.

Ｍ✳⁻χ⊗⌕υ⌈υ

Move to that neighbour.

ＰＩ⊖ＫＫ

Decrement its value.

≔ＥＫＶ⌕θκυ

Get the priorities of the neighbours of the new cell (or -1 for illegal directions).

»≔⟦ⅈⅉ⟧υ

Capture the final position.

⎚Ｉυ

Clear the grid and output the position.

Answer 3

JavaScript (ES7),  142  130 bytes

Expects (program)(matrix), with highest precedence coming first for the program. Returns [column, row], both 0-indexed.

p=>m=>(g=(a,X,Y)=>a.some(k=>m.map((r,y)=>r.map((v,x)=>(X-x)**2+(Y-y)**2-1|v^k||(H=x,V=y,n--)),n=1)|!n)?g(p,H,V,m[V][H]--):[X,Y])``

Try it online!

Commented

p => m => (             // p[] = program, m[] = matrix
g = (                   // g is a recursive function taking:
  a,                    //   a[] = list of possible neighbor values,
                        //         from most to least preferred
  X, Y                  //   (X, Y) = current position
) =>                    //
  a.some(k =>           // for each value k in a[]:
    m.map((r, y) =>     //   for each row r[] at position y in m[]:
      r.map((v, x) =>   //     for each value v in r[]:
        (X - x) ** 2 +  //       compute the squared distance
        (Y - y) ** 2    //       between (X, Y) and (x, y)
        - 1 |           //       abort if it's not equal to 1
        v ^ k ||        //       or v is not equal to k
        (               //       otherwise:
          H = x, V = y, //         save (x, y) in (H, V)
          n--           //         decrement n
        )               //
      ),                //     end of inner map()
      n = 1             //     start with n = 1
    )                   //   end of outer map()
    | !n                //   yield a truthy value if n = 0
  ) ?                   // end of some(); if truthy:
    g(                  //   do a recursive call to g:
      p,                //     using a[] = p[]
      H, V,             //     using (X, Y) = (H, V)
      m[V][H]--         //     decrement the cell at (H, V)
    )                   //   end of recursive call
  :                     // else:
    [ X, Y ]            //   we're stuck: return (X, Y)
)``                     // initial call to g with a[] = ['']

Because g is first called with a = [''] and both X and Y undefined, the test on the squared distance is disabled (because it's always NaN'ish) and v ^ k is equal to 0 only if v == 0. So the first recursive call is triggered on the 0 cell as expected.

Answer 4

J, 109 bytes

Takes in the program on the left, the grid on the right, and returns the 1-based end position.

($-_2&u)@((](r@|.~d{.@/:])`[@.(]2=/@{./:~)[i.(d=:(,-)=i.2){::])^:_)0(]|.~u=:$@]#:(i.~,))_1(r=:-1$!.0~$)@,._,]

Try it online!

How it works

Because I didn't want to handle 3 arguments (program + grid + current position) as this is awkward in tacit J definitions, this approach shifts the grid around with the upper left tile having the robot. A fix point _2 to reconstruct the end position is in the padding.

 _1(r=:…)@,._,]

Pad with _ on the top, and _1 on the left.

 r=:-1$!.0~$

This subtracts one from the top left tile. That makes the _1 to a _2, and as we'll use this later again, assign this function to r.

 0(]|.~u=:$@]#:(i.~,))

This is a bit longer than needed, but in this version we can assign x u y to find the position of x in the grid y. Here we use it to shift the grid so the 0 is at the top left – later we'll use it to search for the _2.

 (…)^:_

Until the output of … does not change, i.e. until the robots moves:

 (d=:(,-)=i.2)

The 4 directions, saved as d.

 (d=:…){::]

Get the numbers at the directions, e.g. 0 0 3 1.

 [i.

Find their position in the program with non-found numbers like 0 _ _1 having program length + 1, e.g. with 1 2 3: 3 3 2 0.

 ](…)`[@.(]2=/@{./:~)

If the first 2 items of the sorted indices 0 2 3 3 -> 0 2 are equal, return the grid (stop moving), otherwise …

 r@|.~d{.@/:]

Sort the directions based on the indices. Take the first one, shift the grid by it and call r to subtract 1 from the top left, i.e. the robots takes a gem.

 ($-_2&u)@

After the robot stopped moving, find the _2 and subtract its position from the grid size to get the final result.

Answer 5

C (gcc), ^{289 \$\cdots\$ 246} 243 bytes

Saved a whopping 37 41 43 46 bytes thanks to ceilingcat!!!

q;c;v;s;d;i;b;u;r;f(g,e,w,p,n)int*g,*p;{r=wcslen(g);for(c=d=0;c-n&&!d;!d&c<n&&--g[r=s])for(c=n,b=4;b--;d=v?q<c?c=q,s=u,0:q>c?d:1:d)for(i=~-(b&2)*(b&1?1:w),v=g[u=r+i]*(u>=0&u<e)*(r%w|~i&&r%w-w+1|i-1),q=0,i=n;i--;)q+=v-p[i]?0:i;*g=r/w;g[1]=r%w;}

Try it online!

Inputs the grid as a flat array, the length of that array, the grid width, the program as an array of integers and the length of the program.
Returns the robot's final position (as zero-based row and column) by storing them in the first two positions of the grid.

Before golfing

new_rank;current_rank;new_value;current_pos;has_doubled;i;news_bits;new_pos;robot_pos;
f(grid,grid_end,grid_width,prog,prog_end)int*grid,*prog;{
    for(robot_pos=0;grid[robot_pos];++robot_pos);
    for(current_rank=has_doubled=0; current_rank!=prog_end && has_doubled == 0;) {
        for(current_rank=prog_end,news_bits=0; news_bits<4; ++news_bits) {
            i = (news_bits&2 - 1)*(news_bits&1?1:grid_width);
            new_pos = robot_pos + i;
            new_value = new_pos >= 0 && new_pos < grid_end?grid[new_pos]:0;
            if((robot_pos%grid_width == 0 && i == -1) ||
               (robot_pos%grid_width == grid_width-1 && i == 1))
                new_value = 0;
            for(i = 0; i < prog_end; ++i)
                if(new_value == prog[i])
                    new_rank = i;
            if(new_value > 0 && new_rank == current_rank) {
                has_doubled = 1;
            }
            if(new_value > 0 && new_rank < current_rank) {
                current_rank = new_rank;
                current_pos = new_pos;
                has_doubled = 0;
            }
        }
        if (has_doubled == 0 && current_rank < prog_end) {
            robot_pos = current_pos;
            --grid[robot_pos];
        }
    }
    grid[0]=robot_pos/grid_width;
    grid[1]=robot_pos%grid_width;
}