Paths & Wasting Time

Question

Premise

So recently I was about half an hour early to an appointment, and decided to wait outside. I also determined that it would look strange if I just stood motionlessly in front of the house. Therefore, I decided to go on a quick walk, within a limited area. I also concluded that if I started walking in circles that would make it obvious that I was loitering. So I was inspired to create my first Code Golf challenge.

Specification

You will be given a list, a map of the area, which will contain either " " or "#", which represent free spaces and obstacles of some sort. Free spaces can only be crossed once, and it takes 1 minute to cross it. Your initial position will be signified with a "@" per roguelike tradition, and the target will be represented with a "$" because that's what you're going to lose there. You will also be given an integer which will represent how many minutes you have to waste before not seeming as if you were intruding. When you land on the "$", it will have to have been the exact amount minutes (so if you were counting down, it will have to be 1 on an adjacent tile, and be 0 on the tile). It will always be possible to reach the destination. Your program or function will have to return a list showing the shortest path with <, >, ^, and v to represent the four possible directions.

Examples

Input:

[[" ", " ", " ", " "],
 ["@", " ", " ", "$"],
 [" ", " ", " ", " "],
 [" ", " ", " ", " "]]

and

5

Ouput:

[[">", ">", ">", "v"],
 ["^", " ", " ", "$"],
 [" ", " ", " ", " "],
 [" ", " ", " ", " "]]

Input:

[[" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 ["@", "#", " ", "$", " "],
 [" ", " ", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

and

7

Output:

[[" ", "#", " ", " ", " "],
 [" ", "#", ">", "v", " "],
 ["v", "#", "^", "$", " "],
 [">", ">", "^", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

Input:

[[" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 ["@", "#", " ", "$", " "],
 [" ", " ", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

and

17

Output:

[[" ", "#", " ", "v", "<"],
 [" ", "#", " ", "v", "^"],
 ["v", "#", " ", "$", "^"],
 [">", ">", "v", ">", "^"],
 [" ", "#", "v", "^", "<"],
 [" ", "#", ">", ">", "^"]]

Rules

• Standard loopholes apply
• Each tile must only be moved over once
• The exact amount of time must be spent on the board
• Only one path needs to be displayed in the case of multiple paths
• This is a code golfing question so shortest answer wins
• As per user202729's question in the comments, you may assume valid input.

Add a comment if any further clarification is required

Answer 1

JavaScript (ES6), 171 bytes

Takes input in currying syntax (a)(n). Outputs by modifying the input matrix.

a=>g=(n,y=a[F='findIndex'](r=>~(i=r[F](v=>v>'?'))),x=i,R=a[y])=>!n--|[-1,0,1,2].every(d=>(R[x]='<^>v'[d+1],(c=(a[Y=y+~-d%2]||0)[X=x+d%2])<1?g(n,Y,X):n|c!='$')&&(R[x]=' '))

Try it online!

Commented

a =>                           // a[] = input matrix
g = (                          // g = recursive function taking:
  n,                           //   n = number of remaining moves
                               //   (x, y) = current coordinates, initialized as follows:
  y = a[F = 'findIndex'](r =>  //     y = index of the row containing the starting point,
    ~(i = r[F](v => v > '?'))  //         found by iterating over all rows r until we
  ),                           //         find some i such that r[i] > '?'
  x = i,                       //     x = index of the column of the starting point
  R = a[y]                     //   R[] = current row
) =>                           //
  !n-- |                       // decrement n; force failure if we're out of moves
  [-1, 0, 1, 2].every(d =>     // for each direction d, where -1 = left, 0 = up,
    (                          // 1 = right and 2 = down:
      R[x] = '<^>v'[d + 1], (  //   update the current cell with the direction symbol
        c = (                  //   c = content of the new cell at (X, Y) with:
          a[Y = y + ~-d % 2]   //     Y = y + dy
          || 0                 //     (use a dummy value if this row does not exist)
        )[X = x + d % 2]       //     X = x + dx
      ) < 1 ?                  //   if c is a space:
        g(n, Y, X)             //     we can go on with a recursive call
      :                        //   else:
        n | c != '$'           //     return false if n = 0 and we've reached the target
    ) &&                       //   unless the above result is falsy,
    (R[x] = ' ')               //   restore the current cell to a space
  )                            // end of every()

Answer 2

Python 2, 310 256 bytes

Thanks @cairdcoinheringaahing for except:0 -3 bytes
Thanks @Mnemonic for -8 bytes
Thanks @JonathanAllan for -3 bytes
Thanks @ovs for -5 bytes

G,L=input()
R=[]
def S(x,y,G,c,R):
 try:
	if x>-1<y<G[y][x]in' @':i=0;exec"T=[r[:]for r in G];T[y][x]='<v^>'[i];S(x+~-i/2,y+~-(i^2)/2,T,c-1,R);i+=1;"*4
	R+=[G]*(0==c<'$'==G[y][x])
 except:0
for i,y in enumerate(G):"@"in y>S(y.index("@"),i,G,L,R)
print R[0]

Try it online!

Some explanation:

try-except is used to ensure, that both x and y coordinates are in boundaries. Exception will be raised upon access to G[y][x]. Python is too good and negative indices are acceptable, so check x>-1<y is added.

T=[r[:]for r in G] used to create copy of G by values

~-i/2 and ~-(i^2)/2 are used to generate pairs (-1, 0), (0, 1), (0, -1), (1, 0), that used to move in grid (there still should be shorter way!)

R+=[G]*(0==c<'$'==G[y][x]) check, that '$' is reached in required number of steps. R is used to get this result from recursive function calls.

for i,y in enumerate(G):"@"in y>S(y.index("@"),i,G,L,R) Found x and y of '@' in input and call function S.

print R[0] R might contain more that one solution, so output just first

Answer 3

Python 2, 264 261 251 249 bytes

def f(a,n,r=-1,s=0):
 j=len(a[0]);x=1;z=y=0
 if r<0:s,r=divmod(sum(a,[]).index('@'),j)
 for c in'>v<^':
	u=r+x;v=s+y;x,y=-y,x
	if j>u>-1<v<len(a):b=[e[:]for e in a];b[s][r]=c;w=a[v][u];z=n*(w<'!')and f(b,n-1,u,v)or n==1and w=='$'and b
	if z:return z

Try it online!