631. Design Excel Sum Formula - cocoder39/coco39_LC GitHub Wiki
get() is a dfs based approach
class Excel:
def __init__(self, height: int, width: str):
self.height, self.width = height, width
self.cells = collections.defaultdict(int)
self.sums = collections.defaultdict(list) # using list as one cell could appear multiple times in the expression
def set(self, row: int, column: str, val: int) -> None:
if (row, column) in self.sums:
del self.sums[(row, column)]
self.cells[(row, column)] = val
def get(self, row: int, column: str) -> int:
if (row, column) in self.cells:
return self.cells[(row, column)]
val = 0
for r, c in self.sums[(row, column)]:
val += self.get(r, c)
return val
def sum(self, row: int, column: str, numbers: List[str]) -> int:
if (row, column) in self.cells:
del self.cells[(row, column)]
self.sums[(row, column)] = []
val = 0
for number in numbers:
cells = number.split(':')
if len(cells) > 1:
r1, c1 = int(cells[0][1:]), ord(cells[0][0])
r2, c2 = int(cells[1][1:]), ord(cells[1][0])
for r in range(r1, r2+1):
for c in range(c1, c2+1):
ch = chr(c)
val += self.get(r, ch)
self.sums[(row, column)].append((r, ch))
else:
r, c = int(number[1:]), number[0]
val += self.get(r, c)
self.sums[(row, column)].append((r, c))
return val
optimization: add cache challenge when to invalidate cache and which cell to invalidate
class Excel:
def __init__(self, height: int, width: str):
self.height, self.width = height, width
self.constant_values = collections.defaultdict(int)
self.sum_expressions = collections.defaultdict(list) # one cell could appear multiple times in the sum experssion
self.dependents = collections.defaultdict(set) # value of this cell change impact all dependents
self.cache = {} # cache for sum expression
def __invalid_cache(self, row, column):
if (row, column) in self.cache:
del self.cache[(row, column)]
for dependent_row, dependent_column in self.dependents[(row, column)]:
self.__invalid_cache(dependent_row, dependent_column)
def set(self, row: int, column: str, val: int) -> None:
self.__invalid_cache(row, column)
if (row, column) in self.sum_expressions:
del self.sum_expressions[(row, column)]
self.constant_values[(row, column)] = val
def get(self, row: int, column: str) -> int:
if (row, column) in self.constant_values:
return self.constant_values[(row, column)]
if (row, column) in self.cache:
return self.cache[(row, column)]
val = 0
for r, c in self.sum_expressions[(row, column)]:
val += self.get(r, c)
self.cache[(row, column)] = val
return val
def sum(self, row: int, column: str, numbers: List[str]) -> int:
self.__invalid_cache(row, column)
if (row, column) in self.constant_values:
del self.constant_values[(row, column)]
self.sum_expressions[(row, column)] = []
val = 0
for number in numbers:
cells = number.split(':')
if len(cells) > 1:
r1, c1 = int(cells[0][1:]), ord(cells[0][0])
r2, c2 = int(cells[1][1:]), ord(cells[1][0])
for r in range(r1, r2+1):
for c in range(c1, c2+1):
ch = chr(c)
val += self.get(r, ch)
self.sum_expressions[(row, column)].append((r, ch))
self.dependents[(r, ch)].add((row, column))
else:
r, c = int(number[1:]), number[0]
val += self.get(r, c)
self.sum_expressions[(row, column)].append((r, c))
self.dependents[(r, c)].add((row, column))
return val
further optimization: OOD
create cell class to manage cell related operations Excel class manages cross-cell operations: eg cache management
class Cell:
def __init__(self, row: int, col: int):
self.row = row
self.col = col
self.is_constant = True
self.constant_val = 0
self.sum_expression: List[Cell] = []
self.dependents: Set[Cell] = set()
def set_constant_val(self, val: int) -> None:
self.is_constant = True
self.constant_val = val
self.sum_expression = []
def set_sum_expression(self, expression: List['Cell']) -> None:
self.is_constant = False
self.constant_val = None
self.sum_expression = expression
def get(self) -> int:
if self.is_constant:
return self.constant_val
else:
return sum(cell.get() for cell in self.sum_expression)
class Excel:
def __init__(self, height: int, width: str):
self.height, self.width = height, width
self.cells: Dict[Tuple[int, str], Cell] = {}
self.cache: Dict[Tuple[int, str], int] = {}
def __invalidate_cache(self, row, column):
if (row, column) in self.cache:
del self.cache[(row, column)]
if (row, column) in self.cells:
for dependent_cell in self.cells[(row, column)].dependents:
self.__invalidate_cache(dependent_cell.row, dependent_cell.col)
def set(self, row: int, column: str, val: int) -> None:
self.__invalidate_cache(row, column)
if (row, column) not in self.cells:
self.cells[(row, column)] = Cell(row, column)
self.cells[(row, column)].set_constant_val(val)
def get(self, row: int, column: str) -> int:
if (row, column) in self.cache:
return self.cache[(row, column)]
if (row, column) not in self.cells:
self.cells[(row, column)] = Cell(row, column)
val = self.cells[(row, column)].get()
self.cache[(row, column)] = val
return val
def sum(self, row: int, column: str, numbers: List[str]) -> int:
self.__invalidate_cache(row, column)
expression = []
if (row, column) not in self.cells:
self.cells[(row, column)] = Cell(row, column)
for number in numbers:
cells = number.split(':')
if len(cells) > 1:
r1, c1 = int(cells[0][1:]), ord(cells[0][0])
r2, c2 = int(cells[1][1:]), ord(cells[1][0])
for r in range(r1, r2+1):
for c in range(c1, c2+1):
ch = chr(c)
if (r, ch) not in self.cells:
self.cells[(r, ch)] = Cell(r, ch)
expression.append(self.cells[(r, ch)])
self.cells[(r, ch)].dependents.add(self.cells[(row, column)])
else:
r, c = int(number[1:]), number[0]
if (r, c) not in self.cells:
self.cells[(r, c)] = Cell(r, c)
expression.append(self.cells[(r, c)])
self.cells[(r, c)].dependents.add(self.cells[(row, column)])
self.cells[(row, column)].set_sum_expression(expression)
return self.cells[(row, column)].get()
further optimization: 1 method to parse cell 2. observer pattern