python-egraph-saturation-congruence-rebuild-cost-extraction
Done. Everything compiles and all 8 verification cases pass with FAILURES: 0.
I built and verified a complete pure-Python equality-saturation engine. The write-up is in ~/SOLUTION.md, with runnable code in ~/egraph.py and ~/verify.py.
(f a) and (f b) never merge after a=b.rebuild() loops, restarting the scan after each merge, and installs a fresh canonical hash-cons table on a clean sweep (returns merge count).saturate() has explicit max_iters/max_nodes budgets and reports whether the rule fixpoint was reached.cost = 1 + Σ children), then reconstructs in increasing-cost order; because a parent is always strictly costlier than its children, reconstruction can't loop. Ties break on the serialized term, not ids.rehash() rebuilds an isomorphic graph with randomized ids for the invariance test.Each term is checked for: fix (a fresh rebuild does 0 merges), opt (size equals an independent brute-force BFS minimum), member (extracted term is reachable by rewriting), and inv (identical after 5 randomized re-hashes). All pass, including budget-stopped mixed-operator terms.
# Evidence - Problem class: python-egraph-saturation-congruence-rebuild-cost-extraction - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-23T22:43:51.716Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an equality-saturation engine in pure Python: an e-graph with hash-consed nodes, union-find with congruence closure, and a rebuild pass, driven by a ruleset of deliberately non-terminating rewrites (associativity, commutativity, distributivity, x*1->x, x+0->x) under explicit iteration and e-node budgets. Saturation must reach a real fixpoint, so a second full pass over the canonicalized graph performs zero merges, and extraction must return a minimum-cost term for each root e-class from a cyclic e-class graph instead of recursing into cycles. Verify against brute-force optimal rewriting over a bounded depth for small ground terms, and assert that the extracted term is invariant to e-node id order after a randomized graph re-hash.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-egraph-saturation-congruence-rebuild-cost-extraction", "provider": "openrouter", "solved_at": "2026-09-23T22:43:51.717Z", "version": "3.11"}Done. Everything compiles and all 8 verification cases pass with FAILURES: 0.
I built and verified a complete pure-Python equality-saturation engine. The write-up is in ~/SOLUTION.md, with runnable code in ~/egraph.py and ~/verify.py.
(f a) and (f b) never merge after a=b.rebuild() loops, restarting the scan after each merge, and installs a fresh canonical hash-cons table on a clean sweep (returns merge count).saturate() has explicit max_iters/max_nodes budgets and reports whether the rule fixpoint was reached.cost = 1 + Σ children), then reconstructs in increasing-cost order; because a parent is always strictly costlier than its children, reconstruction can't loop. Ties break on the serialized term, not ids.rehash() rebuilds an isomorphic graph with randomized ids for the invariance test.Each term is checked for: fix (a fresh rebuild does 0 merges), opt (size equals an independent brute-force BFS minimum), member (extracted term is reachable by rewriting), and inv (identical after 5 randomized re-hashes). All pass, including budget-stopped mixed-operator terms.
# Evidence - Problem class: python-egraph-saturation-congruence-rebuild-cost-extraction - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-23T22:43:51.716Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an equality-saturation engine in pure Python: an e-graph with hash-consed nodes, union-find with congruence closure, and a rebuild pass, driven by a ruleset of deliberately non-terminating rewrites (associativity, commutativity, distributivity, x*1->x, x+0->x) under explicit iteration and e-node budgets. Saturation must reach a real fixpoint, so a second full pass over the canonicalized graph performs zero merges, and extraction must return a minimum-cost term for each root e-class from a cyclic e-class graph instead of recursing into cycles. Verify against brute-force optimal rewriting over a bounded depth for small ground terms, and assert that the extracted term is invariant to e-node id order after a randomized graph re-hash.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-egraph-saturation-congruence-rebuild-cost-extraction", "provider": "openrouter", "solved_at": "2026-09-23T22:43:51.717Z", "version": "3.11"}