# Rosalind: BA3H — Reconstruct a String from its k-mer Composition
# https://rosalind.info/problems/ba3h/
#
# Given: An integer k, followed by a list of k-mers Patterns.
# Return: A string Text whose k-mer composition is Patterns.

let k = 4
let patterns = ["CTTA", "ACCA", "TACC", "GGCT", "GCTT", "TTAC"]

# Genome assembly, in miniature. Each k-mer becomes an *edge* from its prefix to
# its suffix — not a node — because then using every read exactly once is
# precisely an Eulerian path, which BA3G already solves in linear time. Making
# reads the nodes instead gives a Hamiltonian path, which is NP-hard: the same
# data, a different graph, and the difference between tractable and not.
let de_bruijn = {}
for pattern in patterns {
    let prefix = substr(pattern, 0, k - 1)
    let suffix = substr(pattern, 1, k - 1)
    if contains(keys(de_bruijn), prefix) {
        de_bruijn[prefix] = push(de_bruijn[prefix], suffix)
    } else {
        de_bruijn[prefix] = [suffix]
    }
}

let path = eulerian_path(de_bruijn)

# Spell the path: the first node in full, then one new character per step.
let text = path[0] + (range(1, len(path))
    |> map(|i| substr(path[i], k - 2, 1))
    |> join(""))

println("Result:   " + text)
println("Expected: GGCTTACCA")

fn test_ba3h_string_reconstruction() {
    assert text == "GGCTTACCA", "BA3H: got " + text
    assert len(text) == len(patterns) + k - 1, "BA3H: n reads of length k spell n + k - 1"
    # The real requirement: the answer's k-mer composition is the input, as a
    # multiset. Sorting both is enough since every read is used once.
    let composition = range(0, len(text) - k + 1) |> map(|i| substr(text, i, k))
    assert sort(composition) == sort(patterns),
        "BA3H: composition " + str(sort(composition)) + " != " + str(sort(patterns))
}