| Bytes | Lang | Time | Link |
|---|---|---|---|
| 280 | Python3 | 240809T002313Z | Ajax1234 |
| 068 | Wolfram Language Mathematica | 200825T234538Z | att |
| 211 | Java JDK | 200813T064320Z | mindover |
| 130 | Python 3 | 200817T145906Z | Jitse |
| 3437 | APL Dyalog Unicode | 200816T203518Z | ngn |
| 186 | Javascript | 200814T053722Z | Quelklef |
| 119 | JavaScript ES7 | 200810T083837Z | Arnauld |
| 081 | Charcoal | 200810T102728Z | Neil |
Python3, 280 bytes
E=enumerate
def f(b,n):
d={(x,y):v for x,r in E(b)for y,v in E(r)}
q=[(0,0,[(0,0)],n)]
for x,y,p,c in q:
if(x,y)==(len(b)-1,len(b[0])-1):return 1
for X,Y in[(1,0),(0,1),(-1,0),(0,-1)]:
if(u:=(x+X,y+Y))in d and(d[u]=='.'or c)and u not in p:q+=[(*u,p+[u],c-1*(d[u]=='#'))]
Wolfram Language (Mathematica), 68 bytes
Last@GraphDistance[GridGraph[#2,EdgeWeight->{_b_:>#[[b]]}],1]>#3&
Returns True if there are not enough bombs, and False otherwise. Takes [maze, {w,h}, bombs], where maze is a 1d list of 0s (no wall) and 1s (wall).
Java (JDK), 235 233 227 222 211 bytes
int c(int[][]m,int x,int y,int b){int a=0,v;try{m[x][y]=(b-=v=m[x][y])*v<0?v/0:-1;a+=(x==m.length-1&y==m[0].length-1?1:0)+c(m,x+1,y,b)+c(m,x-1,y,b)+c(m,x,y+1,b)+c(m,x,y-1,b);if(a<1)m[x][y]=v;}finally{return a;}}
Requires an int[][] with 0 as field and 1 as wall.
Returns 0 on failure and 1 on success. I'm unsure if this is a vaild truthy/falsy value for Java though.
A rather simple approach: Walk around and bomb walls until you reach the exit or run out of bombs.
I removed the explaination, it got too messy for me to update because of line length.
EDIT:
-2 thanks to ceilingcat!
-4, again thanks to ceilingcat!
-2 by optimising the goal check
-5, again thanks to ceilingcat! They also fixed the awful formatting in the TIO link.
-11 thanks to Kevin Cruijssen!
Python 3, 130 bytes
def f(g,b,x=0,c=0):w=len(g[0])+1;l=w*len(g);return~x%w*(b>-1<x<l>c)and any(f(g,b-g[x//w][x%w],x+a,c+1)for a in(1,-1,w,-w))or-~x==l
Recursive function to find all paths. Takes a 2D matrix as input, with 0 for empty spaces and 1 for walls. The number of bombs b is reduced by 1 each time it encounters a wall. Recursion stops immediately when the edge of the grid g is detected, more steps c have been taken than the size l of the grid, or the number of bombs remaining falls below zero. Returns True when any of the paths reaches the final space and False otherwise.
Adaptation from my answer to Find the shortest route on an ASCII road.
APL (Dyalog Unicode), 34 or 37 bytes
⎕≥⊃⌽,(0@0@0⊢⌊⎕+(⍉g∘⍉)⌊g←3⌊/,,⊣)⍣≡⍨9e9
this shorter version works in dyalog v18 but not on tio:
⎕≥⊃⌽,(0@0@0⊢⌊⎕+g⍤1⌊g←3⌊⌿⍪⍪⊣)⍣≡⍨9e9
⎕ ⎕ inputs
9e9 a very large number, used as a substitute for infinity
( )⍣≡⍨9e9 apply the function train in parens until convergence, using 9e9 both as a constant always passed on the left, and a starting value initially passed on the right
g←3⌊/,,⊣ helper function to compute the minimum of each cell and its two horizontal neighbours, using 9e9 for the boundary around the matrix
(⍉g∘⍉) same for vertical - this is g under transposition
⎕+..⌊.. min of horizontals and verticals, and add the original matrix (this accounts for the cost of 1 bomb when we encounter a wall)
⊢⌊.. update the matrix of best known path costs
0@0@0 put a 0 in the top left cell
on the first iteration of ( )⍣≡, the scalar 9e9 is extended to a matrix (the matrix of best costs) because of ⎕+, and then it remains a matrix until the end.
⊃⌽, lower right cell
⎕≥ compare with the number of bombs available
Javascript, 186 bytes
Is a function (maze, width, height, bombs) => boolean returning whether or not the maze can be solved with the given number of bombs. The maze should be supplied as a flatten list of booleans, true for walls and false for empty spaces.
(m,w,h,b)=>{s=Array(w*h).fill(1/0);i=d=s[0]=0;l:for(;;){for(i=0;i<w*h;i++)for(d of[-w,-1*!!(i%w),1*!!((i+1)%w),w])if(s[i+d]+m[i]<s[i]){s[i]=s[i+d]+m[i];continue l}return s[w*h-1]<=b;}}
Sadly, I wasn't able to get this below the other JS answer. I tip my hat to @Arnauld and look forward to reading how his works.
Degolfed and annotated:
S = (m, w, h, b) => {
s = Array(w*h).fill(1/0); // initialize the scoreboard to infinity the scoreboard
// .. which holds the running minimum for number of
// .. bombs required to reach a certain grid cell
i = d = s[0] = 0; // declare variables i and d and note on the scoreboard
// .. that we can reach the top-left cell with 0 bombs
l: for(;;) { // repeat infinitely
for (i = 0; i < w*h; i++) // loop over all grid cells
for (d of [-w, // for direction of [up,
-1*!!(i%w), // left, (note: if the cell is at the start of a row
// .. then -1 could wrap; handle this with `*!!(i%w)`)
1*!!((i+1)%w), // right, (likewise here for the end of a row)
w]) // down].
if (s[i+d] + m[i]<s[i]) { // if moving from the given direction onto this cell
// .. would take less bombs than what's currently in
// the scoreboard,
s[i] = s[i + d] + m[i]; // then update the scoreboard
continue l // we've made a change to the scoreboard, so ensure we
// .. don't reach the below `return`
}
return s[w * h - 1] <= b; // return the score value for the bottom-right cell.
// .. due to the above `continue`, this statement will
// .. only be reached once no more changes to the
// .. scoreboard can be made
}
}
JavaScript (ES7), 126 125 119 bytes
Expects (matrix)(bombs), where the matrix is filled with -1 for an empty cell and -2 for a wall.
Returns false if we can exit the maze, or true if we can't.
m=>g=(b,X=0,Y=0)=>m.every((r,y)=>m[Y+1]||r[X+1]?r.every((v,x)=>r[x]*=v>0|(X-x)**2+(Y-y)**2!=1||g(b-~v,x,y,r[x]=1)):b<0)
Commented
m => // m[] = matrix
g = ( // g is a recursive function taking:
b, // b = number of bombs
X = 0, Y = 0 // (X, Y) = current position, starting at (0, 0)
) => //
m.every((r, y) => // for each row r[] at position y in m[]:
m[Y + 1] || // if there's a row below the current cell
r[X + 1] ? // or there's a column on the right:
r.every((v, x) => // for each value v at position x in r[]:
r[x] *= // restore r[x] if any of these tests is true:
v > 0 | // - v is greater than 0 (this cell was visited)
(X - x) ** 2 + // - the squared distance between
(Y - y) ** 2 != 1 // (x, y) and (X, Y) is not equal to 1
|| //
g( // - this recursive call is truthy:
b - ~v, // decrement b if v = -2
x, y, // use the new position (x, y)
r[x] = 1 // mark r[x] as visited by setting it to 1
) // end of recursive call
) // end of inner every()
: // else (bottom-right cell):
b < 0 // return true if we've used too many bombs
) // end of outer every()
Charcoal, 81 bytes
≔⟦⟧θWS⊞θι⊞υ⟦⊕Nω⟧≔⁰ηFυ«⪫θ¶←F§ι¹✳κ+¿∨ⅈⅉFruld«≔⌕….#§ι⁰∨⊟KD²✳κ+ζ¿⊕ζ⊞υEι⁺λ⎇μκ±ζ»≔¹η⎚»η
Try it online! Link is to verbose version of code. Based on my answer to the previous challenge. Works better on grids with lots of walls. Bomb count is separated from the grid by a blank line. Outputs a Charcoal boolean, i.e. - for a path, nothing if not. Explanation:
≔⟦⟧θWS⊞θι
Input the grid.
⊞υ⟦⊕Nω⟧
Start with an initial state of n+1 bombs and no moves. (This is because the algorithm stops when you run out of bombs, rather than when you need a bomb to move.)
≔⁰η
We haven't found a path yet.
Fυ«
Perform a breadth-first search of the states.
⪫θ¶←
Draw the input to the canvas, leaving the cursor at the end point.
F§ι¹✳κ+
Draw the path so far.
¿∨ⅈⅉ
If the start hasn't been reached, then:
Fruld«
Loop over the orthogonal directions.
≔⌕….#§ι⁰∨⊟KD²✳κ+ζ
Look at the next character in that direction to see how many bombs we need (-1 for an illegal move, including running out of bombs).
¿⊕ζ⊞υEι⁺λ⎇μκ±ζ
If the move is legal then create a new state by subtracting the number of bombs and adding the current direction.
»≔¹η
But if the start was reached, then record that we found a path.
⎚»
Clear the canvas ready for the next state (or the final output).
η
Output the flag for whether we found a path.