# Rosalind: RSUB — Identifying Reversing Substitutions
# https://rosalind.info/problems/rsub/
#
# Given: A rooted binary tree with every node labelled by a string.
# Return: Every reversing substitution — a change that later changes back, with
# no other change in between.

# (((ostrich,cat)rat,mouse)dog,elephant)robot;
let children = {
    "robot": ["dog", "elephant"],
    "dog": ["rat", "mouse"],
    "rat": ["ostrich", "cat"],
}
let sequences = {
    "robot": "AATTG", "dog": "GGGCA", "mouse": "AAGAC", "rat": "GTTGT",
    "cat": "GAGGC", "ostrich": "GTGTC", "elephant": "AATTC",
}
let root = "robot"

# A site that mutates and later mutates back looks, from the tips alone, as
# though nothing ever happened — the ancestor and the descendant agree. Only the
# internal labels reveal it, which is why this problem hands them over rather
# than asking for them.
#
# It matters because reversing substitutions are exactly what makes distant
# relationships hard to recover: the signal erases itself, and two lineages look
# more similar than their history warrants.
fn kids_of(node) { if has_key(children, node) then children[node] else [] }

# Walk down from a node where a change occurred, following only lineages that
# still carry the new character, and report wherever it changes back.
fn reversions_below(start, position, was, became) {
    let found = []
    let frontier = kids_of(start)
    while len(frontier) > 0 {
        let node = frontier[0]
        frontier = slice(frontier, 1, len(frontier))
        let here = substr(sequences[node], position, 1)
        if here == was {
            # Changed back, with nothing else in between.
            found = push(found, node)
        } else {
            # Still carrying the substitution; keep descending. Any third
            # character ends the lineage's relevance.
            if here == became { frontier = frontier + kids_of(node) }
        }
    }
    found
}

let width = len(sequences[root])
let reported = []
let stack = [root]
while len(stack) > 0 {
    let parent = stack[len(stack) - 1]
    stack = slice(stack, 0, len(stack) - 1)
    for child in kids_of(parent) {
        stack = push(stack, child)
        for i in range(0, width) {
            let was = substr(sequences[parent], i, 1)
            let became = substr(sequences[child], i, 1)
            if was != became {
                for reverted in reversions_below(child, i, was, became) {
                    reported = push(reported, child + " " + reverted + " " + str(i + 1)
                        + " " + was + "->" + became + "->" + was)
                }
            }
        }
    }
}

println("Result:")
for line in sort(reported) { println("  " + line) }
println("Expected (any order): dog mouse 1 A->G->A / dog mouse 2 A->G->A")
println("                      rat ostrich 3 G->T->G / rat cat 3 G->T->G / dog rat 3 T->G->T")

fn test_rsub_reversing_substitutions() {
    let expected = ["dog mouse 1 A->G->A", "dog mouse 2 A->G->A",
                    "rat ostrich 3 G->T->G", "rat cat 3 G->T->G", "dog rat 3 T->G->T"]
    assert sort(reported) == sort(expected), "RSUB: got " + join(sort(reported), " / ")

    # Every report must describe a real reversion: the character genuinely
    # differs from the parent and genuinely returns at the named descendant.
    for line in reported {
        let parts = split(line, " ")
        let changed = parts[0]
        let reverted = parts[1]
        let position = int(parts[2]) - 1
        assert substr(sequences[changed], position, 1) != substr(sequences[reverted], position, 1),
            "RSUB: " + line + " does not actually revert"
    }
    # The tips alone hide this: robot and mouse agree at position 1 despite two
    # substitutions on the path between them.
    assert substr(sequences["robot"], 0, 1) == substr(sequences["mouse"], 0, 1),
        "RSUB: the endpoints agree, which is what makes the change invisible"
    assert substr(sequences["dog"], 0, 1) != substr(sequences["robot"], 0, 1),
        "RSUB: yet the intermediate differs from both"
}