10
\$\begingroup\$

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.

Task

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!

\$\endgroup\$
6
  • \$\begingroup\$ Does "connected" means 4 edges connected? Or 8 direction connected? \$\endgroup\$
    – tsh
    Sep 1 at 8:13
  • \$\begingroup\$ @tsh Looks like 4-connected from the linked code. \$\endgroup\$ Sep 1 at 8:28
  • \$\begingroup\$ The second example can be solved in 4 moves right? Not 7 \$\endgroup\$
    – mousetail
    Sep 1 at 9:24
  • 3
    \$\begingroup\$ @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. \$\endgroup\$
    – ElPedro
    Sep 1 at 10:38
  • \$\begingroup\$ @mousetail ElPedro is correct, you have to pop all the layers from top to bottom. \$\endgroup\$
    – Aiden Chow
    Sep 1 at 16:59

1 Answer 1

5
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ 901 bytes \$\endgroup\$
    – Steffan
    Sep 1 at 16:38
  • \$\begingroup\$ @Steffan Thanks, updated. \$\endgroup\$
    – Ajax1234
    Sep 1 at 19:57

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.