# Rosalind: BA6K — Implement 2-BreakOnGenome
# https://rosalind.info/problems/ba6k/
#
# Given: A genome P and four nodes i, i', j, j'.
# Return: The genome after the 2-break.

let chromosomes = [[1, -2, -4, 3]]
let breakpoint = { i: 1, i_end: 6, j: 3, j_end: 8 }

# The three previous problems assembled. A 2-break is meaningless applied to
# signed integers directly, so the genome is converted to a graph (BA6H), the
# break applied there (BA6J), and the result converted back (BA6I). Here it
# splits one chromosome into two, which is a fission — and the same operation
# with different arguments would fuse, invert or translocate.
fn coloured_edges(g) {
    g |> flat_map(|chromosome| {
        let nodes = chromosome |> flat_map(|block|
            if block > 0 then [2 * block - 1, 2 * block] else [0 - 2 * block, 0 - 2 * block - 1])
        range(1, len(chromosome) + 1) |> map(|j| {
            let to_index = if 2 * j == len(nodes) then 0 else 2 * j
            { a: nodes[2 * j - 1], b: nodes[to_index] }
        })
    })
}

fn same_edge(edge, x, y) {
    (edge.a == x and edge.b == y) or (edge.a == y and edge.b == x)
}

let broken = (coloured_edges(chromosomes) |> filter(|edge|
    same_edge(edge, breakpoint.i, breakpoint.i_end) == false and same_edge(edge, breakpoint.j, breakpoint.j_end) == false))
    + [{ a: breakpoint.i, b: breakpoint.j }, { a: breakpoint.i_end, b: breakpoint.j_end }]

# Back to a genome, exactly as in BA6I.
let links = {}
for edge in broken {
    links[str(edge.a)] = edge.b
    links[str(edge.b)] = edge.a
}

let visited = {}
let rebuilt = []
for edge in broken {
    if contains(keys(visited), str(edge.a)) == false {
        let cycle = []
        let node = edge.a
        let walking = true
        while walking {
            visited[str(node)] = true
            let partner = links[str(node)]
            visited[str(partner)] = true
            cycle = push(cycle, partner)
            let next_node = if partner % 2 == 1 then partner + 1 else partner - 1
            if contains(keys(visited), str(next_node)) { walking = false } else { node = next_node }
        }
        let blocks = cycle |> map(|tail|
            if tail % 2 == 1 then (tail + 1) / 2 else 0 - tail / 2)
        # Circular, so rotate to the lowest-numbered block for a stable listing.
        let lowest = blocks |> map(|b| abs(b)) |> min()
        let at = (range(0, len(blocks)) |> filter(|i| abs(blocks[i]) == lowest))[0]
        rebuilt = push(rebuilt, range(0, len(blocks)) |> map(|i| blocks[(i + at) % len(blocks)]))
    }
}

fn written(items) {
    "(" + (items |> map(|v| if v > 0 then "+" + str(v) else str(v)) |> join(" ")) + ")"
}

let shown = rebuilt |> map(|c| written(c)) |> join(" ")

println("Result:   " + shown)
println("Expected: (+2 -1) (-3 +4)   (up to rotation and which chromosome is listed first)")

fn test_ba6k_two_break_on_genome() {
    # One chromosome became two: this 2-break is a fission.
    assert len(rebuilt) == 2, "BA6K: expected a fission into two chromosomes"
    # Every block survives exactly once, either way up — a 2-break rearranges,
    # it never creates or destroys.
    let magnitudes = sort(rebuilt |> flat_map(|c| c |> map(|b| abs(b))))
    assert magnitudes == [1, 2, 3, 4], "BA6K: every block must survive exactly once"
    # A circular chromosome is the same chromosome under rotation *and* under
    # reading it the other way round, which flips every sign as well as the
    # order. This run produced (+1 -2) where the sample shows (+2 -1) — the same
    # chromosome traversed in the opposite direction. Canonicalising over both
    # symmetries is what makes the comparison meaningful.
    let rotations = |chromosome| range(0, len(chromosome))
        |> map(|shift| join(range(0, len(chromosome))
            |> map(|i| str(chromosome[(i + shift) % len(chromosome)])), " "))
    let flip = |chromosome| reverse(chromosome) |> map(|b| 0 - b)
    let canonical = |chromosome| min(rotations(chromosome) + rotations(flip(chromosome)))

    let mine = sort(rebuilt |> map(|c| canonical(c)))
    let published = sort([canonical([2, -1]), canonical([-3, 4])])
    assert mine == published,
        "BA6K: got " + join(mine, " / ") + " against " + join(published, " / ")
    # And the two really are different listings of the same thing.
    assert canonical([1, -2]) == canonical([2, -1]),
        "BA6K: (+1 -2) and (+2 -1) are one circular chromosome"
}