# Rosalind: PCOV — Genome Assembly with Perfect Coverage
# https://rosalind.info/problems/pcov/
#
# Given: A collection of k-mers taken from a circular chromosome with perfect
# coverage — every k-mer appears exactly once.
# Return: A cyclic superstring of minimal length containing them all.

let reads = ["ATTAC", "TTACC", "TACCA", "ACCAT", "CCATC", "CATCA", "ATCAT", "TCATT", "CATTA"]
let k = len(reads[0])

# Perfect coverage means every (k-1)-mer has exactly one k-mer leaving it, so
# the De Bruijn graph is a single cycle and can be walked without any search.
fn suffix_of(read) { substr(read, 1, len(read) - 1) }
fn prefix_of(read) { substr(read, 0, len(read) - 1) }

let order = [reads[0]]
let at = reads[0]
while len(order) < len(reads) {
    let next = (reads |> filter(|r| prefix_of(r) == suffix_of(at)))[0]
    order = push(order, next)
    at = next
}

# Walking the cycle once emits each node's first symbol; the remaining k-1
# symbols are supplied by wrapping around, which is what makes it cyclic.
let cyclic = order |> map(|r| substr(r, 0, 1)) |> join("")

# Every read must appear in the cyclic string, wrapping past the end.
fn appears_cyclically(text, read) {
    let doubled = text ++ text
    doubled |> contains(read)
}

println("Cycle:    " + (order |> join(" -> ")))
println("Result:   " + cyclic + " (length " + str(len(cyclic)) + ")")
println("Expected: a cyclic string of length " + str(len(reads)) + " containing every read")

fn test_pcov_perfect_coverage() {
    # One symbol per read, since each read advances the cycle by exactly one.
    assert len(cyclic) == len(reads), "PCOV: length " + str(len(cyclic))
    let covered = reads |> count_if(|r| appears_cyclically(cyclic, r))
    assert covered == len(reads), "PCOV: only " + str(covered) + " of " + str(len(reads)) + " reads appear"
    # The walk must close: the last read's suffix returns to the first's prefix.
    assert suffix_of(order[len(order) - 1]) == prefix_of(order[0]), "PCOV: the cycle does not close"
}