Skip to content

Instantly share code, notes, and snippets.

@disouzam

disouzam/topo_lex.py

Forked from bbelderbos/topo_lex.py
Created October 17, 2025 18:14
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save disouzam/0a574fd4dd74de6d28458a5bb12bd9c0 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save disouzam/0a574fd4dd74de6d28458a5bb12bd9c0 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
topo_lex.py
from collections import defaultdict
from graphlib import TopologicalSorter
from heapq import heappush, heappop, heapify
def topo_lex(pairs):
deps = defaultdict(set) # node -> set(dependencies)
for a, b in pairs:
deps.setdefault(a, set())
deps[b].add(a)
ts = TopologicalSorter(deps)
ts.prepare()
pq = list(ts.get_ready())
heapify(pq)
out = []
while pq:
n = heappop(pq) # smallest ready node
out.append(n)
ts.done(n)
for r in ts.get_ready():
heappush(pq, r)
if len(out) != len(deps):
raise ValueError("cycle")
return "".join(out)
pairs = [
("C", "A"),
("C", "F"),
("A", "B"),
("A", "D"),
("B", "E"),
("D", "E"),
("F", "E"),
]
assert topo_lex(pairs) == "CABDFE"
@disouzam
Copy link
Author

disouzam commented Oct 17, 2025

Useful references:

  1. Original post by @bbelderbos in LinkedIn that sparked my interest: https://www.linkedin.com/posts/bbelderbos_was-fun-to-see-howdags-directed-acyclic-activity-7384936288921059328-uIzF?utm_source=share&utm_medium=member_desktop&rcm=ACoAAAY52UwBb01pVF3N-E_Bb-Ye09GZMUdyOXM
  2. Original Gist by @bdelderbors: https://gist.github.com/bbelderbos/f577bf2c35ffd575696df089842c4731
  3. Post by @abhamra: https://abhamra.com/blog/aoc24day5/
  4. 2024 Advent of Code's Day 5 challenge: https://adventofcode.com/2024/day/5

@disouzam
Copy link
Author

disouzam commented Oct 22, 2025

As pointed out by @bbelderbos in the original gist, the correct challenge in which this algorithm was used is 2018 Advent of Code's Day 7 challenge: https://adventofcode.com/2018/day/7

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment