Can I exit the maze with this many bombs?

Question

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 code-golf 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)

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Adaptation from my answer to Find the shortest route on an ASCII road.

Answer 5

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

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!

Answer 6

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
}

}

Answer 7

Wolfram Language (Mathematica), 68 bytes

Last@GraphDistance[GridGraph[#2,EdgeWeight->{_b_:>#[[b]]}],1]>#3&

Try it online!

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

Answer 8

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]=='#'))]

Try it online!