python-shortest-superstring-helkarp
The solution is complete and verified. Files produced in ~/:
shortest_superstring.py — the working implementationsolution.md — the self-contained diagnosis reportRoot cause: An exact shortest superstring is a shortest Hamiltonian path over the reads, which any greedy approach solves incorrectly and raw permutation search (8! = 40k orderings) needlessly re-walks equal-cost partials. The fix is a Held-Karp subset DP.
Key correctness decisions:
1. Containment pruning — drop reads contained in another; identical duplicates collapse to one copy (an identical read is fully contained in its duplicate and one occurrence satisfies all copies).
2. Strict overlap — overlap is always < min(len(a), len(b)), and since no two surviving reads are comparable, full-containment edges never arise.
3. DP over subsets — dp[mask][last] = (length, lex-smallest string), transitioned in O(2^n·n²).
4. Lexicographic tie-break — carried inside each DP cell (compare on (length, string)), avoiding fragile reconstruction-time tie-breaking.
Verification:
- 6,000 randomized trials (up to 8 reads) match brute-force exhaustive enumeration exactly, with zero missing reads
- All edge cases pass (empty input, single, containment, duplicates, overlap chains, no-overlap tie-break)
- Worst case n=8, len=100 runs in ~3 ms
- Handles both N <reads> and bare <reads> input formats
# Evidence - Problem class: python-shortest-superstring-helkarp - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-21T04:02:42.293Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given up to 8 DNA reads (strings over A/C/G/T, each length up to 100), find the shortest superstring that contains every read as a contiguous substring. First discard any read fully contained in another, then build the directed overlap graph using maximal suffix-prefix overlaps (overlap strictly less than min of the two lengths), and solve the resulting shortest Hamiltonian path exactly with Held-Karp DP over subsets in O(2^n * n^2); when multiple strings tie for minimal length, output the lexicographically smallest one.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-shortest-superstring-helkarp", "provider": "openrouter", "solved_at": "2026-08-21T04:02:42.296Z", "version": "3.11"}The solution is complete and verified. Files produced in ~/:
shortest_superstring.py — the working implementationsolution.md — the self-contained diagnosis reportRoot cause: An exact shortest superstring is a shortest Hamiltonian path over the reads, which any greedy approach solves incorrectly and raw permutation search (8! = 40k orderings) needlessly re-walks equal-cost partials. The fix is a Held-Karp subset DP.
Key correctness decisions:
1. Containment pruning — drop reads contained in another; identical duplicates collapse to one copy (an identical read is fully contained in its duplicate and one occurrence satisfies all copies).
2. Strict overlap — overlap is always < min(len(a), len(b)), and since no two surviving reads are comparable, full-containment edges never arise.
3. DP over subsets — dp[mask][last] = (length, lex-smallest string), transitioned in O(2^n·n²).
4. Lexicographic tie-break — carried inside each DP cell (compare on (length, string)), avoiding fragile reconstruction-time tie-breaking.
Verification:
- 6,000 randomized trials (up to 8 reads) match brute-force exhaustive enumeration exactly, with zero missing reads
- All edge cases pass (empty input, single, containment, duplicates, overlap chains, no-overlap tie-break)
- Worst case n=8, len=100 runs in ~3 ms
- Handles both N <reads> and bare <reads> input formats
# Evidence - Problem class: python-shortest-superstring-helkarp - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-21T04:02:42.293Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given up to 8 DNA reads (strings over A/C/G/T, each length up to 100), find the shortest superstring that contains every read as a contiguous substring. First discard any read fully contained in another, then build the directed overlap graph using maximal suffix-prefix overlaps (overlap strictly less than min of the two lengths), and solve the resulting shortest Hamiltonian path exactly with Held-Karp DP over subsets in O(2^n * n^2); when multiple strings tie for minimal length, output the lexicographically smallest one.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-shortest-superstring-helkarp", "provider": "openrouter", "solved_at": "2026-08-21T04:02:42.296Z", "version": "3.11"}