Can I exit the maze with this many bombs?

Inspired by this Puzzling challenge, and easier version of my previous challenge.

Challenge

A 2D rectangular grid is given, where each cell is either an empty space or a wall. You start at the top left cell, and you need to exit through the bottom right cell. You can move to one of four adjacent cells in one step.

You have some bombs, so that using one bomb will let you break exactly one cell-sized wall and go through it. Can you exit the maze using just what you have?

Input and output

The input is the maze and the initial number of bombs. The maze can be taken as a matrix (or any equivalent) containing two distinct values to represent empty spaces and walls. The top left and bottom right cells are guaranteed to be empty. The number of bombs n is always a non-negative integer.

The output should be truthy if you can exit the maze using n or fewer bombs, falsy otherwise. You can output truthy/falsy using your language's convention (swapping is allowed), or use two distinct values to represent true or false respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

Uses .# for spaces and walls.

Input maze
..#..#..
Output: false (for 0 or 1 bomb), true (≥2 bombs)

Input maze
.....
####.
.....
.####
.....
Output: true (for any bombs)

Input maze
.
Output: true (for any bombs)

Input maze
.#.#.
##.##
.###.
Output: false (for ≤2 bombs), true (≥3 bombs)

Input maze
.####
#####
##.##
#####
####.
Output: false (for ≤5 bombs), true (≥6 bombs)

• I wonder why you didn't design this as "output the minimum number of bombs needed to solve the maze." Aug 10, 2020 at 16:27
• @user253751 It seems to be that would be too similar to the previous challenge. (My algorithm to the previous answer only needs two trivial changes, one to avoid tracking the number of non-bomb steps and one to print out the minimum number of bombs.)
– Neil
Aug 11, 2020 at 9:53
• @Neil And now it needs three trivial changes: those two, plus: input another number and see if the result of the algorithm is less than or equal to that. Aug 11, 2020 at 10:26
• @user253751 Ah, but having a limit means I can use a golfier algorithm.
– Neil
Aug 11, 2020 at 10:35
• @Quelklef Yes, it's fine (assuming you take at least one of w or h along with the list). Aug 14, 2020 at 4:22

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)


Try it online!

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

≔⟦⟧θＷＳ⊞θι⊞υ⟦⊕Ｎω⟧≔⁰ηＦυ«⪫θ¶←Ｆ§ι¹✳κ+¿∨ⅈⅉＦruld«≔⌕….#§ι⁰∨⊟ＫＤ²✳κ+ζ¿⊕ζ⊞υＥι⁺λ⎇μκ±ζ»≔¹η⎚»η


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:

≔⟦⟧θＷＳ⊞θι


Input the grid.

⊞υ⟦⊕Ｎω⟧


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.

Ｆυ«


Perform a breadth-first search of the states.

⪫θ¶←


Draw the input to the canvas, leaving the cursor at the end point.

Ｆ§ι¹✳κ+


Draw the path so far.

¿∨ⅈⅉ


If the start hasn't been reached, then:

Ｆruld«


Loop over the orthogonal directions.

≔⌕….#§ι⁰∨⊟ＫＤ²✳κ+ζ


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).

¿⊕ζ⊞υＥι⁺λ⎇μκ±ζ


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.

APL (Dyalog Unicode), 34 or 37 bytes

⎕≥⊃⌽,(0@0@0⊢⌊⎕+(⍉g∘⍉)⌊g←3⌊/,,⊣)⍣≡⍨9e9


Try it online!

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

• Really nice. Mind adding a quick explanation? Aug 17, 2020 at 0:33
• @Jonah thanks, done
– ngn
Aug 17, 2020 at 1:13

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


Try it online!

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.

Java (JDK), 235233227222 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;}}


Try it online!

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!

• Using 0 and 1 is a valid output format regardless of truthiness in Java, as it meets the second method of output: "use two distinct values to represent true or false respectively". Aug 13, 2020 at 6:53
• Didn't know Java accepts b-=v=m[x][y]! Aug 16, 2020 at 9:03
• -11 bytes by changing catch(Exception e){}return a; to finally{return a;}. Aug 20, 2020 at 8:39
• Huh. I tried that and it always broke for me, but now it works. Weird. Aug 25, 2020 at 8:49

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;}}


Try it online!

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
}

}

• It is recommended to use Try it online! to demonstrate the solution so that others can easily validate the results. (It calculates the byte count for you, and it comes with Code Golf post generator too.) Also, check out JS golfing tips and ES6+ golfing tips. Aug 14, 2020 at 5:45
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).