lessons/scripts/extract_reference_attachments.py

#!/usr/bin/env python3
"""Move standalone C++ solutions out of lessons and insert core pseudocode.

This is an idempotent course-layout migration. It identifies the nearest
preceding VJudge problem link for each fenced block containing main(), writes
the block to 参考实现/<topic>/<OJ-id>.cpp, and replaces it with concise
Python-like pseudocode plus a relative attachment link.
"""

from __future__ import annotations

import re
from pathlib import Path


PSEUDOCODE: dict[str, str] = {
    "POJ-2230": """for each road (u, v):
    add_arc(u, v); add_arc(v, u)
stack = [1]; reversed_route = []
while stack:
    u = stack[-1]
    if u still has an unused outgoing arc: stack.append(take_one_arc(u))
    else: reversed_route.append(stack.pop())
output reverse(reversed_route)""",
    "HDU-1116": """for each word:
    add directed edge first_letter -> last_letter
    update in_degree, out_degree, and undirected DSU
connected = all nonzero-degree letters have one DSU root
degree_ok = all differences are 0, or exactly one +1 and one -1
answer = connected and degree_ok""",
    "CodeForces-508D": """encode every length-2 string as a vertex
for trigram xyz: add edge xy -> yz
check directed Euler degree conditions and select start
path = Hierholzer(start)
if len(path) != edge_count + 1: print NO
else: print first 2-char vertex, then append each later vertex's last char""",
    "CodeForces-723E": """answer = number of even-degree original vertices
add dummy vertex 0 and edge 0-v for every odd-degree vertex v
for every augmented connected component:
    follow an Euler circuit and orient each traversed original edge forward
discard dummy edges and output recorded original orientations""",
    "CodeForces-427C": """components = Tarjan_SCC(graph)
total_cost = 0; ways = 1
for component in components:
    best = minimum(cost[v] for v in component)
    total_cost += best
    ways *= count(v in component where cost[v] == best)  (mod MOD)""",
    "POJ-1236": """component = Tarjan_SCC(graph)
if there is only one component: output 1, 0
build condensation indegree and outdegree
sources = count(indegree == 0)
sinks = count(outdegree == 0)
output sources, max(sources, sinks)""",
    "POJ-2186": """component = Tarjan_SCC(graph)
compute every condensation component's size and outdegree
sink_components = components with outdegree 0
if len(sink_components) != 1: output 0
else: output size of the unique sink component""",
    "CodeForces-1000E": """bridges = find_bridges_with_edge_ids(graph)
component = flood_fill_while_ignoring(bridges)
bridge_tree = contract_components_and_keep_bridges()
a = farthest_vertex(bridge_tree, arbitrary_root)
b, distance = farthest_vertex(bridge_tree, a)
output distance""",
    "POJ-3177": """bridges = find_bridges_with_edge_ids(graph)
component = flood_fill_while_ignoring(bridges)
degree = degrees in the contracted bridge tree
leaves = count(degree == 1)
output ceil(leaves / 2)""",
    "CodeForces-732F": """find bridges and edge-biconnected components
root = component with maximum number of original vertices
inside each component: orient DFS-tree edges down and back edges up
build the bridge tree rooted at root
orient every bridge from child component toward parent component
output size(root) and all orientations in input order""",
    "POJ-1144": """DFS(u, parent_edge):
    dfn[u] = low[u] = next_time()
    for each edge u-v except parent_edge:
        if v unvisited:
            DFS(v); low[u] = min(low[u], low[v])
            if u is non-root and low[v] >= dfn[u]: mark u as cut
        else: low[u] = min(low[u], dfn[v])
    root is cut iff it has at least two DFS children""",
    "CodeForces-962F": """during undirected Tarjan, push tree/back edge IDs on a stack
when low[child] >= dfn[parent]:
    pop through the parent-child edge to obtain one vertex-biconnected block
    vertices = distinct endpoints of popped edges
    if number_of_edges == number_of_vertices:
        add every block edge to answer
sort and output answer edge IDs""",
    "AtCoder-abc258_g": """neighbor[i] = bitset of vertices adjacent to i
sum = 0
for every edge i-j with i < j:
    sum += popcount(neighbor[i] AND neighbor[j])
output sum / 3""",
    "CodeForces-1097F": """state[x][d] = parity of elements in multiset x divisible by d
singleton(v): set exactly the divisor bits of v
union(y, z): state[x] = state[y] XOR state[z]
gcd_product(y, z): state[x] = state[y] AND state[z]
query(v): parity = popcount(state[x] AND squarefree_multiple_mask[v]) mod 2""",
    "CodeForces-914F": """position[c] = bitset of indices currently containing c
update(i, c): clear i in old character set; set i in c
query(l, r, pattern):
    match = all_ones
    for offset, c in enumerate(pattern):
        match &= position[c] >> offset
    discard start positions outside [l, r-len(pattern)+1]
    return popcount(match)""",
    "POJ-3461": """pi = prefix_function(pattern)
matched = answer = 0
for c in text:
    while matched > 0 and c != pattern[matched]: matched = pi[matched-1]
    if c == pattern[matched]: matched += 1
    if matched == len(pattern):
        answer += 1; matched = pi[matched-1]""",
    "POJ-2406": """pi = prefix_function(s)
period = len(s) - pi[-1]
if len(s) is divisible by period: output len(s) / period
else: output 1""",
    "CodeForces-432D": """pi = prefix_function(s)
occ[pi[i]] += 1 for every position i
for length from n down to 1: occ[pi[length-1]] += occ[length]
occ[length] += 1 for each prefix's occurrence at position 0
borders = n, pi[n-1], pi[pi[n-1]-1], ...
output reversed(borders) with occ[length]""",
    "CodeForces-471D": """if target length == 1: output source length
text = adjacent_differences(source_heights)
pattern = adjacent_differences(target_heights)
output KMP_occurrence_count(pattern, text)""",
    "POJ-3974": """d1 = odd_palindrome_radii_by_Manacher(s)
d2 = even_palindrome_radii_by_Manacher(s)
answer = max(max(2*d1[i]-1), max(2*d2[i]))
output answer""",
    "CodeForces-17E": """d1, d2 = Manacher(s)
P = sum(d1) + sum(d2)
for each center and radius:
    range_add all represented start positions
    range_add all represented end positions
start, end = prefix_sums(the two difference arrays)
disjoint = sum(start[i] * number_of_palindromes_ending_before_i)
output choose(P, 2) - disjoint  (mod MOD)""",
    "AtCoder-abc340_d": """for each stage i:
    add edge i -> i+1 with cost A[i]
    add edge i -> X[i] with cost B[i]
dist = Dijkstra(graph, source=1)
output dist[N]""",
    "AtCoder-abc277_e": """state = (vertex, currently_passable_edge_label)
for original edge with label a: connect its endpoints in layer a with cost 1
for each switch vertex: connect its two layers with cost 0
dist = zero_one_BFS(start=(1, label_1))
output min(dist[(N,0)], dist[(N,1)])""",
    "CodeForces-449B": """train[v] = minimum train length to v
run road-only Dijkstra with seeds (capital,0) and every finite train[v]
mark v if some road u-v satisfies dist[u] + w == dist[v]
needed = count(v where train[v] == dist[v] and v has no road predecessor)
output total_trains - needed""",
    "CodeForces-59E": """BFS state is (previous_vertex, current_vertex); start = (0, 1)
for neighbor next of current:
    skip if (previous, current, next) is forbidden
    visit state (current, next) and store parent state
stop at first state whose current vertex is N
follow parent states to restore the vertex path""",
    "CodeForces-229B": """run Dijkstra from planet 1
when finalizing u at time t (unless u is destination):
    binary-search t in u's sorted blocked times
    advance depart across the consecutive blocked run t,t+1,...
    relax every edge using depart + edge_weight
output destination distance or -1""",
    "CodeForces-545E": """run Dijkstra from source
on shorter distance to v: replace distance and parent edge
on equal distance: replace parent edge only if its own weight is smaller
because all weights are positive, chosen parents strictly decrease distance
output sum and IDs of one chosen parent edge for every non-source vertex""",
    "POJ-3255": """first[source] = 0; second[*] = infinity
pop a distance label d at u
for edge u-v:
    candidate = d + weight
    if candidate < first[v]: swap(candidate, first[v]); push first[v]
    if first[v] < candidate < second[v]: set and push second[v]
output second[destination]""",
    "POJ-3169": """convert every constraint to x[v] <= x[u] + weight and add edge u->v
add order edges (i+1)->i with weight 0
if Bellman-Ford from a super-source finds a negative cycle: output -1
dist = Bellman-Ford(source=1)
if N is unreachable: output -2
else: output dist[N], the tightest upper bound on x[N]-x[1]""",
    "AtCoder-arc076_b": """candidates = []
sort towns by x; add every adjacent pair
sort towns by y; add every adjacent pair
give each candidate its true min(|dx|, |dy|) cost
output Kruskal(candidates)""",
    "CodeForces-1245D": """treat building station i as edge super_source-i with cost c[i]
initialize Prim key[i] = c[i], parent[i] = super_source
repeat n times:
    select unused city v with minimum key
    record station if parent is source, otherwise record wire
    update every unused city's key by wire_cost(v, city)
output total and recorded construction""",
    "CodeForces-1095F": """hub = vertex with minimum a[hub]
candidates = all special offers
for every v != hub: add ordinary edge hub-v with cost a[hub]+a[v]
output Kruskal(candidates)""",
    "CodeForces-609E": """T, total = Kruskal_MST(graph)
preprocess binary lifting for maximum edge on every tree path
for edge e=(u,v,w):
    if e belongs to T: answer[e] = total
    else: answer[e] = total + w - maximum_on_tree_path(u,v)""",
    "CodeForces-160D": """sort edges into equal-weight groups; DSU contains only lighter edges
for each group:
    edges already inside one DSU component are 'none'
    contract DSU roots and build a temporary multigraph from remaining edges
    temporary bridges are 'any'; other remaining edges are 'at least one'
    union all group edges in the global DSU""",
    "CodeForces-1706E": """process input edges by index; every successful DSU merge creates a new parent node
new node value = current edge index; its children are the two old component roots
preprocess LCA on the reconstruction tree
need[i] = value(LCA(original_vertex_i, original_vertex_i+1))
answer(l,r) = max(need[l .. r-1]), or 0 when l == r""",
    "CodeForces-888G": """sort and deduplicate values
solve(group, bit):
    split group by current bit
    answer = solve(zero_side, bit-1) + solve(one_side, bit-1)
    if both sides exist:
        build a lower-bit binary trie for the smaller side
        answer += 2^bit + minimum lower-bit XOR across the split
    return answer""",
    "CodeForces-1144F": """two-color the graph
if an edge has equal-colored endpoints: output NO
otherwise orient every edge from color 0 to color 1
translate each orientation back to a 0/1 character in input order""",
    "CodeForces-1354E": """two-color every connected component and store its two sides
group-knapsack: from each component choose one side so total chosen size is n2
recover choices; label chosen side 2
among all remaining vertices label any n1 as 1 and the rest as 3""",
    "CodeForces-741C": """make one vertex for each chair
add an inequality edge for every romantic pair
add inequality edges (1,2), (3,4), ...
two-color every resulting even-cycle component
output the two colors at each romantic pair's chair positions""",
    "POJ-1274": """match_right[stall] = unmatched
for each cow u:
    clear visited stalls
    DFS through acceptable stalls:
        take an empty stall, or recursively move its currently matched cow
    count successful augmentations""",
    "POJ-3041": """rows are left vertices; columns are right vertices
each asteroid adds a row-column edge
maximum_matching = Kuhn(graph)
output maximum_matching  # equals minimum vertex cover by Konig""",
    "CodeForces-1139E": """potential values are left vertices; clubs are right vertices
start with students that never get deleted and maintain a matching
advance mex while the current potential can be augmented
process deletions in reverse:
    record current mex for that day
    add the deleted student's potential-club edge
    continue augmenting from current mex""",
    "HDU-2255": """initialize left label lx[x] = max_y weight[x][y], right label ly = 0
for every left vertex root:
    search an augmenting path using only equality edges lx+ly == weight
    if search fails:
        delta = minimum slack of every unvisited right vertex
        subtract delta from visited lx; add it to visited ly; update slack
    repeat until root is matched
output weight sum of the perfect matching""",
    "CodeForces-498C": """factor all array values and iterate over each distinct prime p
capacity[i] = exponent of p in a[i]
build flow network: source->odd indices, even indices->sink
for every allowed pair add infinite-capacity odd->even edge
answer += maximum_flow(network)
output answer""",
}


BLOCK = re.compile(r"```(?:cpp|c\+\+)\n(.*?)```", flags=re.DOTALL)
VJUDGE = re.compile(r"https://vjudge\.net/problem/([A-Za-z0-9_-]+)")


def main() -> int:
    course = Path("课程")
    attachment_root = Path("参考实现")
    moved = 0
    for document in sorted(course.rglob("*.md")):
        text = document.read_text(encoding="utf-8")
        output: list[str] = []
        cursor = 0
        for match in BLOCK.finditer(text):
            code = match.group(1)
            if not re.search(r"\bint\s+main\s*\(", code):
                continue
            preceding = text[: match.start()]
            queries = VJUDGE.findall(preceding)
            if not queries:
                raise RuntimeError(f"no preceding VJudge ID for {document}")
            query = queries[-1]
            if query not in PSEUDOCODE:
                raise RuntimeError(f"missing pseudocode for {query} in {document}")
            topic = document.parent.name
            attachment = attachment_root / topic / f"{query}.cpp"
            attachment.parent.mkdir(parents=True, exist_ok=True)
            attachment.write_text(code.rstrip() + "\n", encoding="utf-8")
            relative = Path("../..") / attachment
            replacement = (
                "```text\n"
                + PSEUDOCODE[query].rstrip()
                + "\n```\n\n"
                + f"完整 GNU C++17 参考实现见附件：[{query}.cpp]({relative.as_posix()})"
            )
            output.append(text[cursor : match.start()])
            output.append(replacement)
            cursor = match.end()
            moved += 1
        if output:
            output.append(text[cursor:])
            document.write_text("".join(output), encoding="utf-8")
    print(f"moved={moved}")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())