Seamflow: Алгоритмическая секция

Подсказки

• Формула хранит зависимости

  sum(C1, [A1, B1]) означает C1 -> A1 и C1 -> B1.

• Цикл проверяется до записи

  Если зависимость плохая, старое состояние должно остаться прежним.

Идея решения

Эталонный код

class Excel:
    def __init__(self):
        self.values: dict[str, int] = {}
        self.formulas: dict[str, list[str]] = {}

    def set(self, cell: str, value: int) -> None:
        self.values[cell] = value
        self.formulas.pop(cell, None)

    def get(self, cell: str) -> int:
        return self._get(cell, set())

    def _get(self, cell: str, visiting: set[str]) -> int:
        if cell in visiting:
            raise ValueError('cycle')
        if cell not in self.formulas:
            return self.values.get(cell, 0)

        visiting.add(cell)
        value = sum(self._get(ref, visiting) for ref in self.formulas[cell])
        visiting.remove(cell)
        return value

    def _depends_on(self, start: str, target: str, seen: set[str]) -> bool:
        if start == target:
            return True
        if start in seen:
            return False
        seen.add(start)
        return any(self._depends_on(ref, target, seen) for ref in self.formulas.get(start, []))

    def sum(self, cell: str, refs: list[str]) -> int:
        if any(self._depends_on(ref, cell, set()) for ref in refs):
            raise ValueError('cycle')
        self.formulas[cell] = list(refs)
        self.values.pop(cell, None)
        return self.get(cell)


def excel_results(operations: list[list]) -> list:
    excel = Excel()
    output = []

    for op in operations:
        command = op[0]
        if command == 'set':
            excel.set(op[1], op[2])
        elif command == 'get':
            output.append(excel.get(op[1]))
        elif command == 'sum':
            try:
                output.append(excel.sum(op[1], op[2]))
            except ValueError:
                output.append('cycle')

    return output