# Optimally pop all the bubbles

In a given 2d grid of positive integers (representing different types of "bubbles"), there are one of two actions that you can do each "step". You can either:

1. Pop an island (a connected group of bubbles - two bubbles that are diagonally adjacent are not considered connected) of the same type of bubbles, given that the island consists of at least 2 bubbles AND at least one bubble in said island has no bubbles above it.

Or,

1. Drop a single bubble of any type into any column, given that the chosen column is not filled to the top of the grid.

After one of these two steps, all bubbles will fall towards the bottom of the grid, and the next step will start.

The grid can also include 0's, which represent empty space.

Your task is: Given a $$\m\times n\$$ 2d grid of positive integers representing a grid of bubbles and the optional $$\m\$$ and $$\n\$$ and input, determine the fewest amount of moves in which the entire grid can be cleared of bubbles. The input grid is guaranteed to be clearable.

# Worked example

22222
21212
22222
21212
22222


The first step will be to first pop the island of 2's. After all the bubbles have fallen, the grid will then look like this, where the 0's represent empty space:

00000
00000
00000
01010
01010


The second step will be to drop a 1 bubble in the middle column, so that the grid now looks like this:

00000
00000
00000
01010
01110


And the final step is to pop the island of 1's, clearing the entire grid.

# Test Cases

m, n
grid
-> output

5, 5
22222
21212
22222
21212
22222
-> 3

7, 7
1111111
2222222
1111111
2222222
1111111
2222222
1111111
-> 7

7, 6
000000
121212
212121
121212
212121
121212
212121
-> 22

2, 7
0000000
1000001
-> 4

8, 1
0
1
2
2
2
2
2
1
-> 5

8, 2
00
10
20
20
20
20
20
10
-> 4


If any of y'all need it, I also made a (pretty bad) tool that will take in a list of steps (more info in the TIO link) and output the board state after those steps have been taken: Try It Online!

This is , so the shortest solution in bytes for each language wins!

• Does "connected" means 4 edges connected? Or 8 direction connected?
– tsh
Sep 1 at 8:13
• @tsh Looks like 4-connected from the linked code. Sep 1 at 8:28
• The second example can be solved in 4 moves right? Not 7 Sep 1 at 9:24
• @mousetail The way I read it is that "at least one bubble in said island has no bubbles above it." means that you cannot take away a row in the middle and can only work from top to bottom therefore 7 is correct. I may be wrong though. Sep 1 at 10:38
• @mousetail ElPedro is correct, you have to pop all the layers from top to bottom. Sep 1 at 16:59

# Python3, 901 bytes:

E=enumerate
def B(b):
P,R,s=[(x,y)for x,j in E(b)for y,k in E(j)if k],[],[];p=P
while p:
x,y=p[0];q=[(x,y)];s+=p[0],
while(o:=[X for x,y in q for X in[(x+1,y),(x,y+1),(x-1,y),(x,y-1)]if X in P and b[x][y]==b[X[0]][X[1]]and(X in s)^1]):q+=o;s+=o
R+={*q},;p=[i for i in p if(i in s)^1]
return R
F=lambda b:[*map(list,zip(*[[0]*i.count(0)+[j for j in i if j]for i in zip(*b)]))]
def f(b):
q,S=[(b,0)],{}
while q:
b,c=q.pop(0)
if sum(sum(b,[]))<1:return c
I=B(b)
for i in I:
if len(i)>1and sum(all(b[x-t][y]==b[x][y]or 1>b[x-t][y]for t in range(x+1))for x,y in i):
W=eval(str(b))
for x,y in i:W[x][y]=0
if(str(w:=F(W))in S)^1or-~c<S[str(w)]:q+=(w,c+1),;S[str(w)]=c+1
for y,C in E(zip(*b)):
if C[0]<1:
for v in{j for k in b for j in k if j}:
W=eval(str(b));W[0][y]=v
if(len(B(e:=F(W)))<=len(I))&((str(e)in S)^1or-~c<S[str(e)]):q+=(e,c+1),;S[str(e)]=c+1


Try it online!

• 901 bytes Sep 1 at 16:38
• @Steffan Thanks, updated. Sep 1 at 19:57