Respuesta A: OpenAI GPT-6 Sol
"""Un motor de hojas de cálculo pequeño e incremental. Las fórmulas se analizan y se convierten en árboles de expresión. Las referencias y los rangos rectangulares expandidos forman un grafo de dependencias, con aristas inversas que se usan para invalidar solo los dependientes transitivos de una celda modificada. Los valores se almacenan en caché y se recalculan bajo demanda. El recálculo primero encuentra las celdas alcanzables que no están en caché y, después, usa pasadas iterativas de Kosaraju para identificar todas las celdas que forman parte de un ciclo. Las celdas de ciclo se guardan en caché como #CYCLE;...
Mostrar respuesta completa ▼
"""Un motor de hojas de cálculo pequeño e incremental.
Las fórmulas se analizan y se convierten en árboles de expresión. Las referencias y los rangos rectangulares expandidos forman un grafo de dependencias, con aristas inversas que se usan para invalidar solo los dependientes transitivos de una celda modificada. Los valores se almacenan en caché y se recalculan bajo demanda. El recálculo primero encuentra las celdas alcanzables que no están en caché y, después, usa pasadas iterativas de Kosaraju para identificar todas las celdas que forman parte de un ciclo. Las celdas de ciclo se guardan en caché como #CYCLE; las celdas restantes se evalúan en orden de dependencia iterativo. Los árboles de expresión también se evalúan de forma iterativa, de modo que las cadenas largas de dependencias no consumen la pila de llamadas de Python. Al borrar o cambiar una celda, primero se eliminan sus aristas antiguas antes de la invalidación, lo que permite que los ciclos detectados anteriormente desaparezcan.
"""
import re
_CELL = re.compile(r"[A-Z][1-9][0-9]{0,2}\Z")
_NUMBER = re.compile(r"-?[0-9]+(?:\.[0-9]+)?\Z")
_TOKEN = re.compile(r"[A-Za-z_][A-Za-z_0-9]*|[0-9]+(?:\.[0-9]+)?|[()+\-*/,:]")
_ERRORS = {"#PARSE", "#DIV/0", "#CYCLE"}
def _cell_id(name):
if not isinstance(name, str) or _CELL.fullmatch(name) is None:
raise ValueError("invalid cell name")
return (int(name[1:]) - 1) * 26 + ord(name[0]) - ord("A")
def _number(text):
return float(text) if "." in text else int(text)
class _Parser:
def __init__(self, source):
self.tokens = []
self.deps = set()
pos = 0
while pos < len(source):
if source[pos].isspace():
pos += 1
continue
match = _TOKEN.match(source, pos)
if match is None:
raise ValueError("invalid token")
text = match.group()
kind = ("number" if text[0].isdigit() else
"word" if text[0].isalpha() or text[0] == "_" else text)
self.tokens.append((kind, text))
pos = match.end()
self.tokens.append(("end", ""))
self.pos = 0
def kind(self):
return self.tokens[self.pos][0]
def take(self, kind):
if self.kind() != kind:
raise ValueError("unexpected token")
text = self.tokens[self.pos][1]
self.pos += 1
return text
def reference(self):
name = self.take("word")
ref = _cell_id(name)
self.deps.add(ref)
return ref
def argument(self):
# Un rango solo es válido si constituye un argumento completo de función.
if (self.kind() == "word" and
self.tokens[self.pos + 1][0] == ":"):
first = self.reference()
self.take(":")
last = self.reference()
r1, c1 = divmod(first, 26)
r2, c2 = divmod(last, 26)
refs = tuple(r * 26 + c
for r in range(min(r1, r2), max(r1, r2) + 1)
for c in range(min(c1, c2), max(c1, c2) + 1))
self.deps.update(refs)
return ("range", refs)
return self.expression(0)
def expression(self, minimum):
kind = self.kind()
if kind == "-":
self.take("-")
left = ("unary", self.expression(3))
elif kind == "number":
left = ("number", _number(self.take("number")))
elif kind == "word":
if self.tokens[self.pos + 1][0] == "(":
name = self.take("word")
if name not in ("SUM", "MIN", "MAX"):
raise ValueError("unknown function")
self.take("(")
args = [self.argument()]
while self.kind() == ",":
self.take(",")
args.append(self.argument())
self.take(")")
left = ("function", name, tuple(args))
else:
left = ("reference", self.reference())
elif kind == "(":
self.take("(")
left = self.expression(0)
self.take(")")
else:
raise ValueError("expected expression")
while self.kind() in ("+", "-", "*", "/"):
op = self.kind()
precedence = 1 if op in ("+", "-") else 2
if precedence < minimum:
break
self.take(op)
right = self.expression(precedence + 1)
left = ("binary", op, left, right)
return left
def parse(self):
tree = self.expression(0)
self.take("end")
return tree, self.deps
class Sheet:
def __init__(self):
self._cells = {} # id -> (tipo, literal o árbol de expresión)
self._deps = {} # id -> ids referenciados
self._reverse = {} # id referenciado -> ids dependientes
self._cache = {} # id -> valor evaluado
def set(self, cell: str, raw: str) -> None:
key = _cell_id(cell)
if raw == "":
entry, new_deps = None, set()
elif raw.startswith("="):
try:
tree, new_deps = _Parser(raw[1:]).parse()
entry = ("formula", tree)
except ValueError:
entry, new_deps = ("bad", None), set()
elif _NUMBER.fullmatch(raw):
entry, new_deps = ("literal", _number(raw)), set()
else:
entry, new_deps = ("bad", None), set()
for dep in self._deps.pop(key, ()):
users = self._reverse[dep]
users.remove(key)
if not users:
del self._reverse[dep]
if entry is None:
self._cells.pop(key, None)
else:
self._cells[key] = entry
if new_deps:
self._deps[key] = new_deps
for dep in new_deps:
self._reverse.setdefault(dep, set()).add(key)
# El nuevo grafo determina qué valores previamente almacenados en caché están obsoletos.
pending = [key]
seen = {key}
for current in pending:
self._cache.pop(current, None)
for user in self._reverse.get(current, ()):
if user not in seen:
seen.add(user)
pending.append(user)
def get(self, cell: str) -> int | float | str:
key = _cell_id(cell)
if key not in self._cells:
return 0
if key not in self._cache:
self._recalculate(key)
return self._cache[key]
def _recalculate(self, root):
# Recolecta solo las celdas alcanzables no almacenadas en caché y sus aristas inversas internas.
pending = [root]
nodes = {root}
backwards = {}
for current in pending:
for dep in self._deps.get(current, ()):
if dep not in self._cells or dep in self._cache:
continue
backwards.setdefault(dep, []).append(current)
if dep not in nodes:
nodes.add(dep)
pending.append(dep)
# Kosaraju iterativo: orden de finalización y, después, componentes en el grafo inverso.
visited = set()
finishing = []
for start in pending:
if start in visited:
continue
visited.add(start)
stack = [(start, iter(self._deps.get(start, ())))]
while stack:
current, edges = stack[-1]
dep = next(edges, None)
if dep is None:
finishing.append(current)
stack.pop()
elif dep in nodes and dep not in visited:
visited.add(dep)
stack.append((dep, iter(self._deps.get(dep, ()))))
assigned = set()
for start in reversed(finishing):
if start in assigned:
continue
component = []
stack = [start]
assigned.add(start)
while stack:
current = stack.pop()
component.append(current)
for parent in backwards.get(current, ()):
if parent not in assigned:
assigned.add(parent)
stack.append(parent)
if len(component) > 1 or start in self._deps.get(start, ()):
for current in component:
self._cache[current] = "#CYCLE"
# Con las celdas cíclicas en caché, las dependencias restantes forman un DAG.
# La evaluación en postorden es iterativa y evalúa cada celda una sola vez.
visited = set()
stack = [(root, False)]
while stack:
current, ready = stack.pop()
if current in self._cache:
continue
if ready:
kind, contents = self._cells[current]
if kind == "bad":
value = "#PARSE"
elif kind == "literal":
value = contents
else:
value = self._evaluate(contents)
self._cache[current] = value
elif current not in visited:
visited.add(current)
stack.append((current, True))
for dep in self._deps.get(current, ()):
if dep in nodes and dep not in self._cache:
stack.append((dep, False))
def _evaluate(self, tree):
values = []
stack = [(tree, False)]
while stack:
node, ready = stack.pop()
kind = node[0]
if not ready:
if kind == "number":
values.append(node[1])
elif kind == "reference":
ref = node[1]
values.append(self._cache[ref] if ref in self._cells else 0)
elif kind == "range":
values.append([(self._cache[ref] if ref in self._cells else 0,
ref in self._cells) for ref in node[1]])
else:
stack.append((node, True))
if kind == "unary":
stack.append((node[1], False))
elif kind == "binary":
stack.append((node[3], False))
stack.append((node[2], False))
else:
for arg in reversed(node[2]):
stack.append((arg, False))
continue
if kind == "unary":
operand = values.pop()
values.append(operand if isinstance(operand, str) else -operand)
elif kind == "binary":
right = values.pop()
left = values.pop()
if isinstance(left, str):
result = left
elif isinstance(right, str):
result = right
elif node[1] == "+":
result = left + right
elif node[1] == "-":
result = left - right
elif node[1] == "*":
result = left * right
else:
result = "#DIV/0" if right == 0 else left / right
values.append(result)
else: # función
count = len(node[2])
args = values[-count:]
del values[-count:]
selected = []
error = None
for arg in args:
items = arg if isinstance(arg, list) else [(arg, True)]
for value, nonempty in items:
if isinstance(value, str):
if error is None:
error = value
elif node[1] == "SUM" or nonempty:
selected.append(value)
if error is not None:
result = error
elif node[1] == "SUM":
result = sum(selected)
elif node[1] == "MIN":
result = min(selected) if selected else 0
else:
result = max(selected) if selected else 0
values.append(result)
return values[0]
def _tests():
s = Sheet()
s.set("A1", "=-2+3*4")
assert s.get("A1") == 10
s.set("A1", "=-(2+3)*4")
assert s.get("A1") == -20
s.set("A2", "=8/2/2")
assert s.get("A2") == 2.0 and isinstance(s.get("A2"), float)
s.set("A1", "5")
s.set("B1", "7")
s.set("C1", "=SUM(B2:A1)")
assert s.get("C1") == 12
s.set("C2", "=MIN(A2:B2)")
s.set("D2", "=MAX(A2:B2)")
assert s.get("C2") == 2.0 and s.get("D2") == 2.0
s.set("A2", "")
assert s.get("C2") == 0 and s.get("D2") == 0
s.set("E1", "=1/0")
s.set("F1", "not a number")
s.set("G1", "=E1+F1")
s.set("H1", "=F1+E1")
assert s.get("G1") == "#DIV/0" and s.get("H1") == "#PARSE"
s.set("I1", "=I1+1")
assert s.get("I1") == "#CYCLE"
s.set("J1", "=K1")
s.set("K1", "=SUM(J1:J2)")
s.set("L1", "=J1+2")
assert s.get("J1") == s.get("K1") == s.get("L1") == "#CYCLE"
s.set("K1", "3")
assert s.get("J1") == 3 and s.get("L1") == 5
s.set("K1", "")
assert s.get("K1") == 0 and s.get("L1") == 2
for bad in ("=A0", "=AA1", "=A1000", "=A01", "=SUM(A1:A0)",
"=A1:B2", "=UNKNOWN(A1)"):
s.set("M1", bad)
assert s.get("M1") == "#PARSE"
for bad in ("a1", "A0", "AA1", "A01", "Z1000"):
for operation in (lambda: s.get(bad), lambda: s.set(bad, "1")):
try:
operation()
assert False, bad
except ValueError:
pass
chain = Sheet()
def name(index):
return chr(ord("A") + index % 26) + str(index // 26 + 1)
length = 20_000
chain.set(name(length - 1), "1")
for index in range(length - 2, -1, -1):
chain.set(name(index), "=" + name(index + 1) + "+1")
assert chain.get(name(0)) == length
chain.set(name(length - 1), "2")
assert chain.get(name(0)) == length + 1
if __name__ == "__main__":
_tests()Resultado
Votos ganadores
3 / 3
Puntuación media
Puntuación total
Comentario general
Comentario general:
La Respuesta A es una implementación completa y ejecutable. Tiene un analizador sintáctico real de ascenso de precedencia, y el menos unario se enlaza más fuerte que * y /, como se requiere. Los rangos se expanden en dependencias y funcionan con esquinas invertidas. Las aristas inversas permiten invalidar solo las celdas que dependen de un cambio. Los ciclos se detectan mediante una pasada iterativa de Kosaraju, incluidos los bucles propios y los ciclos que atraviesan rangos, y tanto la evaluación de celdas como la de expresiones son no recursivas. Maneja correctamente las reglas de error: los errores provienen del primer operando de izquierda a derecha, y el error de análisis propio de una celda tiene prioridad. Las celdas vacías cuentan como 0 en SUM pero se ignoran en MIN y MAX, y los ciclos se limpian correctamente cuando una celda se edita o se borra. Las pruebas cubren todos los escenarios requeridos, incluida la cadena de 20.000 celdas. Debilidades menores: el analizador sigue recursionando en paréntesis profundamente anidados, el docstring es algo denso y las pruebas están en una sola función en lugar de en casos separados.
Ver detalle de evaluación ▼
Corrección
Peso 35%La precedencia, el menos unario, los resultados int frente a float, los rangos invertidos, MIN/MAX frente a SUM en celdas vacías, el orden de los errores, la prioridad de errores de análisis, la detección de ciclos a través de rangos, la propagación a celdas dependientes y la resolución de ciclos tras las ediciones parecen correctos. Los nombres inválidos generan ValueError.
Integridad
Peso 20%Entrega los tres entregables: el módulo, una explicación del diseño y pruebas que cubren todos los escenarios listados, incluida la cadena de 20.000 celdas.
Calidad del código
Peso 20%El analizador está bien estructurado, los algoritmos iterativos están bien organizados y el código no usa eval. El código es denso en algunos puntos, y las pruebas están agrupadas en una sola función.
Valor práctico
Peso 15%Utilizable tal cual. Escala a cadenas largas y recalcula solo las celdas afectadas.
Seguimiento de instrucciones
Peso 10%Sigue la API, usa solo la biblioteca estándar y cumple los requisitos de no recursión e incrementalidad. La explicación es concisa y coincide con el código.
Puntuación total
Comentario general
La Respuesta A ofrece un motor de hojas de cálculo completo, robusto y totalmente implementado que cumple con todos los requisitos del enunciado. Incluye un analizador sintáctico real de descenso recursivo, grafos de dependencias explícitos con mapeo directo e inverso, un algoritmo iterativo de detección de ciclos basado en Kosaraju, evaluación iterativa de expresiones y casos de prueba exhaustivos. Maneja correctamente los casos límite e implementa una invalidación incremental en lugar de vaciar toda la caché.
Ver detalle de evaluación ▼
Corrección
Peso 35%Implementa una semántica exacta para el análisis sintáctico, los operadores, los rangos, la propagación de errores, la detección de ciclos y las actualizaciones de múltiples celdas, superando todos los casos de prueba exhaustivos.
Integridad
Peso 20%Proporciona el código completo del módulo, una explicación del diseño y pruebas exhaustivas que cubren todos los casos límite requeridos y las cadenas de estrés.
Calidad del código
Peso 20%Código Python limpio, bien estructurado y modular, con algoritmos robustos para el análisis sintáctico, el seguimiento de dependencias y la evaluación iterativa.
Valor práctico
Peso 15%Totalmente listo para producción según la especificación, admite cadenas de 20.000 celdas de forma iterativa sin límites de recursión y mantiene actualizaciones incrementales de la caché.
Seguimiento de instrucciones
Peso 10%Sigue estrictamente todas las definiciones de API, el formato, la generación de errores, los requisitos no funcionales y las directrices de entrega.
Puntuación total
Comentario general
Answer A ofrece un motor completo y ejecutable, con un analizador real, seguimiento explícito de dependencias, invalidación de caché dirigida, detección iterativa de ciclos y evaluación de dependencias no recursiva. Sus pruebas cubren los escenarios solicitados, incluida una cadena de 20.000 celdas y actualizaciones a través de ella. La principal limitación de robustez es el análisis recursivo de expresiones muy anidadas; además, el objetivo de rendimiento para operaciones mixtas no está demostrado.
Ver detalle de evaluación ▼
Corrección
Peso 35%La implementación maneja correctamente la precedencia, los tipos numéricos del resultado, los rangos invertidos, el tratamiento de celdas vacías, la propagación ordenada de errores y la pertenencia a ciclos mediante componentes fuertemente conexas. Eliminar las dependencias de las celdas con errores de sintaxis preserva su prioridad propia de error de sintaxis. El análisis recursivo aún puede provocar RecursionError en fórmulas válidas suficientemente anidadas.
Integridad
Peso 20%Incluye el módulo completo, una explicación breve del diseño y aserciones ejecutables que cubren todas las categorías de prueba solicitadas. Añadir pruebas adicionales para la prioridad de errores de sintaxis en la propia fórmula y para errores en competencia que involucran ciclos fortalecería el conjunto de pruebas.
Calidad del código
Peso 20%El análisis, el mantenimiento del grafo, el recálculo y la evaluación de expresiones están claramente separados. Las pilas de recorrido explícitas y las fases del grafo documentadas hacen que la implementación sea mantenible a pesar de su complejidad. Los nodos sintácticos basados en tuplas y la constante de error no utilizada son problemas menores de acabado.
Valor práctico
Peso 15%Las dependencias inversas limitan la invalidación a las celdas afectadas, las lecturas en caché son baratas y el recorrido del grafo es lineal en el subgrafo relevante. La prueba de cadena larga ejercita tanto la evaluación inicial como una actualización aguas arriba sin recursión de dependencias. No hay una prueba de tiempo con operaciones mixtas que establezca el objetivo de rendimiento declarado.
Seguimiento de instrucciones
Peso 10%Usa solo la biblioteca estándar, expone la API anotada solicitada, ofrece una explicación breve y precisa e incluye el caso de estrés requerido. La implementación sigue el enfoque incremental y de procesamiento no recursivo de dependencias que se pidió.