Dynamic programming

4 problems from Rosalind — Bioinformatics Textbook Track. Press Run on any block to execute it in your browser.

# Rosalind: BA5A — Find the Minimum Number of Coins Needed to Make Change
# https://rosalind.info/problems/ba5a/
#
# Given: An integer money and an array Coins.
# Return: The minimum number of coins making that amount.

let money = 40
let coins = [1, 5, 10, 20, 25, 50]

# The greedy answer is wrong here and that is the point of the problem: greedily
# taking 25 leaves 15, needing 25+10+5 = three coins, where 20+20 is two. So
# every amount up to the target is solved from the smaller amounts below it.
let fewest = repeat([0], money + 1)
for amount in range(1, money + 1) {
    let best = money + 1
    for coin in coins {
        if coin <= amount and fewest[amount - coin] + 1 < best {
            best = fewest[amount - coin] + 1
        }
    }
    fewest[amount] = best
}

println("Result:   " + str(fewest[money]))
println("Expected: 2   (20 + 20; greedily taking 25 first would need three)")

fn test_ba5a_minimum_coins() {
    assert fewest[money] == 2, "BA5A: got " + str(fewest[money])
    assert fewest[0] == 0, "BA5A: no coins are needed for nothing"
}

# Rosalind: BA5C — Find a Longest Common Subsequence of Two Strings
# https://rosalind.info/problems/ba5c/
#
# Given: Two strings.
# Return: A longest common subsequence.

let s = "AACCTTGG"
let t = "ACACTGTGA"

# lcs is a builtin. There is generally more than one longest common
# subsequence — the sample shows AACTGG, this returns another of the same
# length — so the assertion checks the length and that it really is a
# subsequence of both, which is what the problem asks for.
let common = lcs(s, t)

println("Result:   " + common + "  (length " + str(len(common)) + ")")
println("Expected: AACTGG, or any other subsequence of length 6")

fn test_ba5c_longest_common_subsequence() {
    assert len(common) == 6, "BA5C: expected length 6, got " + str(len(common))
    assert is_subsequence(common, s), "BA5C: not a subsequence of s"
    assert is_subsequence(common, t), "BA5C: not a subsequence of t"
    assert len(lcs("AACTGG", t)) == 6, "BA5C: the sample answer should also be length 6"
}

# Rosalind: BA5B — Find the Length of a Longest Path in a Manhattan-like Grid
# https://rosalind.info/problems/ba5b/
#
# Given: Integers n and m, an n x (m+1) matrix Down, and an (n+1) x m matrix Right.
# Return: The length of a longest path from (0,0) to (n,m).

let n = 4
let m = 4
let down = [
    [1, 0, 2, 4, 3],
    [4, 6, 5, 2, 1],
    [4, 4, 5, 2, 1],
    [5, 6, 8, 5, 3],
]
let right = [
    [3, 2, 4, 0],
    [3, 2, 4, 2],
    [0, 7, 3, 3],
    [3, 3, 0, 2],
    [1, 3, 2, 2],
]

# The longest path to any corner is the better of arriving from above or from the
# left, and both were already computed — so the whole grid is filled once, in
# order, and never revisited. Searching the paths themselves would mean
# enumerating C(n+m, n) of them; here that is 70, but it grows exponentially.
#
# Longest path is NP-hard in general graphs. It is easy here only because the
# grid is acyclic and already comes in an order that respects its edges.
# The top row has no "above", so it fills from the left alone.
let top = [0]
for j in range(1, m + 1) { top = push(top, top[j - 1] + right[0][j - 1]) }

let best = [top]
for i in range(1, n + 1) {
    # Likewise the left column has only the edge above it.
    let row = [best[i - 1][0] + down[i - 1][0]]
    for j in range(1, m + 1) {
        let from_above = best[i - 1][j] + down[i - 1][j]
        let from_left = row[j - 1] + right[i][j - 1]
        row = push(row, max([from_above, from_left]))
    }
    best = push(best, row)
}

let answer = best[n][m]

println("Result:   " + str(answer))
println("Expected: 34")

fn test_ba5b_manhattan_tourist() {
    assert answer == 34, "BA5B: got " + str(answer)
    # The edges of the grid have only one way in, so those entries are plain
    # running totals — a useful check that the recurrence is indexed correctly.
    assert best[0][m] == sum(right[0]), "BA5B: the top row is the sum of its right edges"
    let left_column = range(0, n) |> map(|i| down[i][0]) |> sum()
    assert best[n][0] == left_column, "BA5B: the left column is the sum of its down edges"
    assert answer >= best[0][m] and answer >= best[n][0],
        "BA5B: the best path is at least as good as going round the edge"
}

# Rosalind: BA5D — Find the Longest Path in a DAG
# https://rosalind.info/problems/ba5d/
#
# Given: A source, a sink, and an edge-weighted directed acyclic graph.
# Return: The length of a longest path from source to sink, and the path.

let source = "0"
let sink = "4"
let arcs = [
    { from_node: "0", to_node: "1", weight: 7 },
    { from_node: "0", to_node: "2", weight: 4 },
    { from_node: "2", to_node: "3", weight: 2 },
    { from_node: "1", to_node: "4", weight: 1 },
    { from_node: "3", to_node: "4", weight: 3 },
]

# Longest path is NP-hard in general — in a graph with a positive cycle there is
# no longest path at all. It is easy here for exactly one reason: the graph is
# acyclic, so its vertices can be put in an order where every edge points forwards,
# and then each node's best score is final by the time it is read.
let incoming = {}
let vertices = sort(unique((arcs |> map(|e| e.from_node)) + (arcs |> map(|e| e.to_node))))
for node in vertices { incoming[node] = [] }
for edge in arcs { incoming[edge.to_node] = push(incoming[edge.to_node], edge) }

# Topological order, as in BA5N.
let pending = {}
for node in vertices { pending[node] = len(incoming[node]) }
let ready = vertices |> filter(|node| pending[node] == 0)
let order = []
while len(ready) > 0 {
    let node = ready[0]
    ready = slice(ready, 1, len(ready))
    order = push(order, node)
    for edge in arcs {
        if edge.from_node == node {
            pending[edge.to_node] = pending[edge.to_node] - 1
            if pending[edge.to_node] == 0 { ready = push(ready, edge.to_node) }
        }
    }
}

# Score every node in that order. Nodes unreachable from the source stay at
# "impossible" rather than 0 — otherwise a detour through one could look better
# than a real path.
let impossible = -1000000
let best = {}
let came_from = {}
for node in vertices { best[node] = impossible }
best[source] = 0

for node in order {
    for edge in incoming[node] {
        let candidate = best[edge.from_node] + edge.weight
        if best[edge.from_node] > impossible and candidate > best[node] {
            best[node] = candidate
            came_from[node] = edge.from_node
        }
    }
}

let path = [sink]
let walk = sink
while walk != source {
    walk = came_from[walk]
    path = push(path, walk)
}
path = reverse(path)

println("Result:   " + str(best[sink]))
println("          " + join(path, "->"))
println("Expected: 9")
println("          0->2->3->4")

fn test_ba5d_longest_path_in_a_dag() {
    assert best[sink] == 9, "BA5D: got " + str(best[sink])
    assert join(path, "->") == "0->2->3->4", "BA5D: got " + join(path, "->")
    # The path must start and end where asked, and its weights must add up to the
    # reported length — a length without a matching path is the usual bug here.
    assert path[0] == source and path[len(path) - 1] == sink, "BA5D: wrong endpoints"
    let walked = range(1, len(path)) |> map(|i| {
        let matching = arcs |> filter(|e| e.from_node == path[i - 1] and e.to_node == path[i])
        assert len(matching) > 0, "BA5D: " + path[i - 1] + "->" + path[i] + " is not an edge"
        matching[0].weight
    })
    assert sum(walked) == best[sink], "BA5D: the path's weights do not sum to its length"
    # The direct route 0->1->4 scores 8, so 9 really is better.
    assert best[sink] > 8, "BA5D: 0->1->4 scores 8 and must be beaten"
}