python-fm-index-backward-search-dna
Done. Here's a summary of the problem, solution, and verified results.
Problem diagnosis — I identified the failure modes typical for this task:
1. BWT built wrong — BWT is the last column of the SA matrix with cyclic wrap: BWT[i] = s[(SA[i]-1) % n] (so SA[i]=0 maps to $). Getting this wrong yields a wrong BWT immediately.
2. Rank off-by-one — rank(c,i) must count BWT[0..i) (half-open); inclusive counting shifts every interval.
3. Sentinel ordering — $ must be the smallest symbol; C-table for the toy must be [$:0, A:1, C:3, G:4, T:5].
4. Rank queries O(n) — a scan per query can't handle 10^5 patterns; I used a two-level prefix-count table (block-start totals + per-block prefixes) giving O(1) rank.
5. SA memory blow-up — Python list of ints or s[i:] sort keys go way over 256 MiB; I used array('I') buffers with prefix-doubling + LSD counting sort.
Implementation — fm_index.py: suffix array (O(n log n), ~4–10 s), BWT, O(1) rank support, backward search returning SA intervals/counts/positions. Pure stdlib.
Verified results:
- Toy GTTCATTA$: SA = [8,7,4,3,0,6,2,5,1], BWT = ATCT$TTAG, search(TA) → (5,6), occ at 6; search(TTA) → (7,8), occ at 5 — exact spec match.
- Random 10^6 (random.Random(42) over ACGT + $, n=1000001): count(CATTAG) = **234** (SA interval [309375, 309609)), cross-checked against str.count and naive scan; build 4.0 s, peak RSS 50.9 MiB (≪ 256 MiB).
- Adversarial all-A 10^6 string: 9.7 s build, counts correct; repetitive-string pattern counts all matched naive scans.
Deliverables written:
- ~/fm_index.py — runnable solution
- ~/solution.md — self-contained report (title, root-cause analysis, full code, verification)
# Evidence - Problem class: python-fm-index-backward-search-dna - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-31T04:24:13.456Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an FM-index over a DNA string s (alphabet {A,C,G,T} plus sentinel $, s ends with $, n up to 10^6) supporting exact-match backward search: build the suffix array, derive the BWT, build rank support (prefix-count table or wavelet tree) within 256 MiB, and answer occurrence counts + SA intervals for up to 10^5 patterns. Validate against the toy string s=GTTCATTA$: BWT=ATCT$TTAG, SA=[8,7,4,3,0,6,2,5,1], backward search of TA must return interval [5,6) (count 1, occurrence at position 6) and TTA must return [7,8). Report the full implementation and the occurrence count of CATTAG in a length-10^6 random DNA string generated with python random.Random(42) over ACGT.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-fm-index-backward-search-dna", "provider": "openrouter", "solved_at": "2026-08-31T04:24:13.456Z", "version": "3.11"}Done. Here's a summary of the problem, solution, and verified results.
Problem diagnosis — I identified the failure modes typical for this task:
1. BWT built wrong — BWT is the last column of the SA matrix with cyclic wrap: BWT[i] = s[(SA[i]-1) % n] (so SA[i]=0 maps to $). Getting this wrong yields a wrong BWT immediately.
2. Rank off-by-one — rank(c,i) must count BWT[0..i) (half-open); inclusive counting shifts every interval.
3. Sentinel ordering — $ must be the smallest symbol; C-table for the toy must be [$:0, A:1, C:3, G:4, T:5].
4. Rank queries O(n) — a scan per query can't handle 10^5 patterns; I used a two-level prefix-count table (block-start totals + per-block prefixes) giving O(1) rank.
5. SA memory blow-up — Python list of ints or s[i:] sort keys go way over 256 MiB; I used array('I') buffers with prefix-doubling + LSD counting sort.
Implementation — fm_index.py: suffix array (O(n log n), ~4–10 s), BWT, O(1) rank support, backward search returning SA intervals/counts/positions. Pure stdlib.
Verified results:
- Toy GTTCATTA$: SA = [8,7,4,3,0,6,2,5,1], BWT = ATCT$TTAG, search(TA) → (5,6), occ at 6; search(TTA) → (7,8), occ at 5 — exact spec match.
- Random 10^6 (random.Random(42) over ACGT + $, n=1000001): count(CATTAG) = **234** (SA interval [309375, 309609)), cross-checked against str.count and naive scan; build 4.0 s, peak RSS 50.9 MiB (≪ 256 MiB).
- Adversarial all-A 10^6 string: 9.7 s build, counts correct; repetitive-string pattern counts all matched naive scans.
Deliverables written:
- ~/fm_index.py — runnable solution
- ~/solution.md — self-contained report (title, root-cause analysis, full code, verification)
# Evidence - Problem class: python-fm-index-backward-search-dna - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-31T04:24:13.456Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an FM-index over a DNA string s (alphabet {A,C,G,T} plus sentinel $, s ends with $, n up to 10^6) supporting exact-match backward search: build the suffix array, derive the BWT, build rank support (prefix-count table or wavelet tree) within 256 MiB, and answer occurrence counts + SA intervals for up to 10^5 patterns. Validate against the toy string s=GTTCATTA$: BWT=ATCT$TTAG, SA=[8,7,4,3,0,6,2,5,1], backward search of TA must return interval [5,6) (count 1, occurrence at position 6) and TTA must return [7,8). Report the full implementation and the occurrence count of CATTAG in a length-10^6 random DNA string generated with python random.Random(42) over ACGT.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-fm-index-backward-search-dna", "provider": "openrouter", "solved_at": "2026-08-31T04:24:13.456Z", "version": "3.11"}