14
\$\begingroup\$

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)
\$\endgroup\$
  • 4
    \$\begingroup\$ I wonder why you didn't design this as "output the minimum number of bombs needed to solve the maze." \$\endgroup\$ – user253751 Aug 10 at 16:27
  • \$\begingroup\$ @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.) \$\endgroup\$ – Neil Aug 11 at 9:53
  • \$\begingroup\$ @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. \$\endgroup\$ – user253751 Aug 11 at 10:26
  • 1
    \$\begingroup\$ @user253751 Ah, but having a limit means I can use a golfier algorithm. \$\endgroup\$ – Neil Aug 11 at 10:35
  • 1
    \$\begingroup\$ @Quelklef Yes, it's fine (assuming you take at least one of w or h along with the list). \$\endgroup\$ – Bubbler Aug 14 at 4:22
5
\$\begingroup\$

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()
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Really nice. Mind adding a quick explanation? \$\endgroup\$ – Jonah Aug 17 at 0:33
  • 1
    \$\begingroup\$ @Jonah thanks, done \$\endgroup\$ – ngn Aug 17 at 1:13
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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". \$\endgroup\$ – Bubbler Aug 13 at 6:53
  • \$\begingroup\$ Didn't know Java accepts b-=v=m[x][y]! \$\endgroup\$ – mindoverflow Aug 16 at 9:03
  • \$\begingroup\$ -11 bytes by changing catch(Exception e){}return a; to finally{return a;}. \$\endgroup\$ – Kevin Cruijssen Aug 20 at 8:39
  • \$\begingroup\$ Huh. I tried that and it always broke for me, but now it works. Weird. \$\endgroup\$ – mindoverflow Aug 25 at 8:49
1
\$\begingroup\$

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
}

}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Bubbler Aug 14 at 5:45
  • \$\begingroup\$ TIO link added. Thanks for the links! \$\endgroup\$ – Quelklef Aug 14 at 6:27
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.