LC 0723 [M] Candy Crush - ALawliet/algorithms GitHub Wiki
https://www.youtube.com/watch?v=p4jExm5Zf6Q&ab_channel=babybear4812
- check 3 in a row
- keep done/stable state
- tag with - numbers
- crush down is like move zeroes but we move the positive numbers down
class Solution:
def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
if not board:
return board
done = True
#STEP 1: CRUSH ROWS
for r in range(len(board)):
for c in range(len(board[r]) - 2): # stop at 3rd to last
num1 = abs(board[r][c])
num2 = abs(board[r][c+1])
num3 = abs(board[r][c+2])
if num1 == num2 and num2 == num3 and num1 != 0:
board[r][c] = -num1
board[r][c+1] = -num2
board[r][c+2] = -num3
done = False
#STEP 2: CRUSH COLS
for c in range(len(board[0])):
for r in range(len(board) - 2):
num1 = abs(board[r][c])
num2 = abs(board[r+1][c])
num3 = abs(board[r+2][c])
if num1 == num2 and num2 == num3 and num1 != 0:
board[r][c] = -num1
board[r+1][c] = -num2
board[r+2][c] = -num3
done = False
#STEP 3: GRAVITY
if not done:
for c in range(len(board[0])):
# move all positive numbers down
idx = len(board) - 1 # first replacement
for r in range(len(board) - 1, -1, -1): # bottom up
if board[r][c] > 0:
board[idx][c] = board[r][c] # crush down
idx -= 1 # move up (everything below here needs to stay because it's dropped, but we work up)
# put zeroes in for missing prices
for r in range(idx, -1, -1):
board[r][c] = 0
return board if done else self.candyCrush(board)