[Interview] Roblox

36. Valid Sudoku

Leetcode: https://leetcode.com/problems/valid-sudoku/

def isValidSudoku(self, board: List[List[str]]) -> bool:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    blocks = [[set() for _ in range(3)] for _ in range(3)]
    
    for i in range(9):
        for j in range(9):
            if board[i][j] == ".":
                continue
                
            if board[i][j] in rows[i] or board[i][j] in cols[j] or board[i][j] in blocks[i // 3][j // 3]:
                return False
            rows[i].add(board[i][j])
            cols[j].add(board[i][j])
            blocks[i // 3][j // 3].add(board[i][j])
    
    return True

Valid grid

A nonogram is a logic puzzle, similar to a crossword, in which the player is given a blank grid and has to color it according to some instructions. Specifically, each cell can be either black or white, which we will represent as ‘B’ for black and ‘W’ for white.
+——————+
| W W W W |
| B W W W |
| B W B B |
| W W B W |
| B B W W |
+——————+
For each row and column, the instructions give the lengths of contiguous runs of black (‘B’) cells. For example, the instructions for one row of [ 2, 1 ] indicate that there must be a run of two black cells, followed later by another run of one black cell, and the rest of the row filled with white cells.
These are valid solutions: [ W, B, B, W, B ] and [ B, B, W, W, B ] and also [ B, B, W, B, W ]
This is not valid: [ W, B, W, B, B ] since the runs are not in the correct order.
This is not valid: [ W, B, B, B, W ] since the two runs of Bs are not separated by Ws.
Your job is to write a function to validate a possible solution against a set of instructions. Given a 2D matrix representing a player’s solution; and instructions for each row along with additional instructions for each column; return True or False according to whether both sets of instructions match.
Example instructions #1
matrix1 = [[ W, W, W, W ],
[ B, W, W, W ],
[ B, W, B, B ],
[ W, W, B, W ],
[ B, B, W, W ]]
rows1_1 = [], [1], [1,2], [1], [2]
columns1_1 = [2,1], [1], [2], [1]
validateNonogram(matrix1, rows1_1, columns1_1) => True

def validateNonogram(matrix, rows, cols):
    rowStr = ["" for _ in range(len(matrix))] # ["W4", "B1W3", ...]
    colStr = ["" for _ in range(len(matrix[0]))]
    for i in range(len(matrix)):
        cnt = 0
        curCh = "W"
        for j in range(len(matrix[0])):
            if cnt > 0 and matrix[i][j] != curCh:
                rowStr[i] += curCh + str(cnt)
                curCh = matrix[i][j]
                cnt = 1
            elif matrix[i][j] == curCh:
                cnt += 1
            elif cnt == 0 and matrix[i][j] != curCh:
                curCh = matrix[i][j]
                cnt = 1
        rowStr[i] += curCh + str(cnt)
    for j in range(len(matrix[0])):
        cnt = 0
        curCh = "W"
        for i in range(len(matrix)):
            if cnt > 0 and matrix[i][j] != curCh:
                colStr[j] += curCh + str(cnt)
                curCh = matrix[i][j]
                cnt = 1
            elif matrix[i][j] == curCh:
                cnt += 1
            elif cnt == 0 and matrix[i][j] != curCh:
                curCh = matrix[i][j]
                cnt += 1
        colStr[j] += curCh + str(cnt)

    if not matchStr(colStr, cols) or not matchStr(rowStr, rows):
      return False
    return True

def matchStr(strArr, pattern):
  for i in range(len(strArr)):
    curRule = pattern[i]
    curIndex = 0
    prev = "W"
    for ch in strArr[i]:
      if ch == "B":
        prev = "B"
      elif ch == "W":
        prev = "W"
      else:
        if prev == "B":
          if curIndex >= len(curRule) or int(ch) != curRule[curIndex]:
            return False
          else:
            curIndex += 1
    return True