Every problem
All 34 problems from Rosalind — Algorithmic Heights. Press Run on any block to execute it in your browser. Every problem is on this page, so it is large and takes a moment to settle — the sections are lighter.
FIBO — Fibonacci Numbers
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: FIBO — Fibonacci Numbers
# https://rosalind.info/problems/fibo/
#
# Given: A positive integer n <= 25.
# Return: The value of F(n).
let n = 6
# The problem exists to contrast this with the textbook recursion: carrying the
# last two values forward is linear, where recursing on F(n-1) + F(n-2) without
# memoisation recomputes the same subproblems exponentially often.
let previous = 0
let current = 1
let step = 0
while step < n {
let next = previous + current
previous = current
current = next
step = step + 1
}
let result = previous
println("Result: " + str(result))
println("Expected: 8")
fn test_fibo_sixth_number() {
assert result == 8, "FIBO: got " + str(result)
}BINS — Binary Search
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: BINS — Binary Search
# https://rosalind.info/problems/bins/
#
# Given: Two positive integers n and m, a sorted array A[1..n], and m keys.
# Return: For each key, an index j with A[j] = key, or -1 if there is none.
let a = [10, 20, 30, 40, 50]
let queries = [40, 10, 35, 15, 40, 20]
# Halve the live window until it is empty. Rosalind indexes from 1, so the
# answer is the zero-based position plus one.
fn binary_search(sorted, key) {
let lo = 0
let hi = len(sorted) - 1
let found = -1
while lo <= hi and found == -1 {
let mid = int((lo + hi) / 2)
let value = sorted[mid]
if value == key then {
found = mid + 1
} else {
if value < key then lo = mid + 1 else hi = mid - 1
}
}
found
}
let result = queries |> map(|k| str(binary_search(a, k))) |> join(" ")
println("Result: " + result)
println("Expected: 4 1 -1 -1 4 2")
fn test_bins_locates_every_key() {
assert result == "4 1 -1 -1 4 2", "BINS: got " + result
}DEG — Degree Array
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: DEG — Degree Array
# https://rosalind.info/problems/deg/
#
# Given: A simple graph with n vertices in the edge list format.
# Return: An array D[1..n] where D[i] is the degree of vertex i.
let n = 6
let edge_list = [[1, 2], [2, 3], [6, 3], [5, 6], [2, 5], [2, 4], [4, 1]]
# Each edge contributes one to both of its endpoints, so a single pass over the
# edge list is enough — the adjacency structure never has to be built.
let vertex_degree = []
for _ in range(0, n) {
vertex_degree = push(vertex_degree, 0)
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
vertex_degree[u] = vertex_degree[u] + 1
vertex_degree[v] = vertex_degree[v] + 1
}
let result = vertex_degree |> map(|d| str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 2 4 2 2 2 2")
fn test_deg_degree_array() {
assert result == "2 4 2 2 2 2", "DEG: got " + result
}INS — Insertion Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
The swap count is the number of inversions, so the same loop answers INV as well. Sorts in place, which the index assignment added for these packs is what makes possible.
# Rosalind: INS — Insertion Sort
# https://rosalind.info/problems/ins/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: The number of swaps performed by insertion sort on A[1..n].
let a = [6, 10, 4, 5, 1, 2]
# Insertion sort walks each element back past everything larger than it, so the
# swap count is exactly the number of inversions in the array. The sort is done
# in place, which is what makes the count meaningful.
let xs = a
let swaps = 0
let i = 1
while i < len(xs) {
let k = i
while k > 0 and xs[k] < xs[k - 1] {
let held = xs[k]
xs[k] = xs[k - 1]
xs[k - 1] = held
swaps = swaps + 1
k = k - 1
}
i = i + 1
}
println("Result: " + str(swaps))
println("Expected: 12")
println("Sorted: " + str(xs))
fn test_ins_counts_swaps() {
assert swaps == 12, "INS: got " + str(swaps)
assert xs == [1, 2, 4, 5, 6, 10], "INS: the array was not sorted in place: " + str(xs)
}DDEG — Double-Degree Array
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: DDEG — Double-Degree Array
# https://rosalind.info/problems/ddeg/
#
# Given: A simple graph with n vertices in the edge list format.
# Return: An array D[1..n] where D[i] is the sum of the degrees of i's neighbours.
let n = 5
let edge_list = [[1, 2], [2, 3], [4, 3], [2, 4]]
# Two passes rather than one: the neighbour sum for a vertex needs every degree
# to be final first, so the degrees are counted before anything is summed.
let vertex_degree = []
for _ in range(0, n) {
vertex_degree = push(vertex_degree, 0)
}
for edge in edge_list {
vertex_degree[edge[0] - 1] = vertex_degree[edge[0] - 1] + 1
vertex_degree[edge[1] - 1] = vertex_degree[edge[1] - 1] + 1
}
let neighbour_sum = []
for _ in range(0, n) {
neighbour_sum = push(neighbour_sum, 0)
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
neighbour_sum[u] = neighbour_sum[u] + vertex_degree[v]
neighbour_sum[v] = neighbour_sum[v] + vertex_degree[u]
}
let result = neighbour_sum |> map(|d| str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 3 5 5 5 0")
fn test_ddeg_neighbour_degree_sums() {
assert result == "3 5 5 5 0", "DDEG: got " + result
}MAJ — Majority Element
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Writing this found that `{}` parsed as an empty block and evaluated to nil, so a tally could not be opened the obvious way. Fixed in the parser; `{}` in value position is now an empty map.
# Rosalind: MAJ — Majority Element
# https://rosalind.info/problems/maj/
#
# Given: A positive integer k, a positive integer n, and k arrays of size n.
# Return: For each array, an element occurring strictly more than n/2 times,
# or -1 if there is none.
let arrays = [
[5, 5, 5, 5, 5, 5, 5, 5],
[8, 7, 7, 7, 1, 7, 3, 7],
[7, 1, 6, 5, 10, 100, 1000, 1],
[5, 1, 6, 7, 1, 1, 10, 1],
]
# A tally is the direct reading of the definition. Comparing 2 * count against
# the length keeps the test in integers, so "strictly more than n/2" stays exact
# for odd n instead of depending on how a division rounds.
fn majority(xs) {
let counts = {}
for value in xs {
let key = str(value)
if contains(keys(counts), key) {
counts[key] = counts[key] + 1
} else {
counts[key] = 1
}
}
let answer = -1
for key in keys(counts) {
if counts[key] * 2 > len(xs) {
answer = int(key)
}
}
answer
}
let result = arrays |> map(|xs| str(majority(xs))) |> join(" ")
println("Result: " + result)
println("Expected: 5 7 -1 -1")
fn test_maj_majority_elements() {
assert result == "5 7 -1 -1", "MAJ: got " + result
}MER — Merge Two Sorted Arrays
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: MER — Merge Two Sorted Arrays
# https://rosalind.info/problems/mer/
#
# Given: A sorted array A[1..n] and a sorted array B[1..m].
# Return: A sorted array C[1..n+m] containing all elements of A and B.
let a = [2, 4, 10, 18]
let b = [-5, 11, 12]
# The merge step of merge sort. Sorting the concatenation would also work and
# would also be slower: taking the smaller head each time is linear because both
# inputs are already ordered.
let merged = []
let i = 0
let j = 0
while i < len(a) and j < len(b) {
if a[i] <= b[j] {
merged = push(merged, a[i])
i = i + 1
} else {
merged = push(merged, b[j])
j = j + 1
}
}
while i < len(a) {
merged = push(merged, a[i])
i = i + 1
}
while j < len(b) {
merged = push(merged, b[j])
j = j + 1
}
let result = merged |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: -5 2 4 10 11 12 18")
fn test_mer_merges_in_order() {
assert result == "-5 2 4 10 11 12 18", "MER: got " + result
}2SUM — 2SUM
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Any valid pair is accepted, so the answers are checked against the definition rather than against the sample string: the scan reaches 8 and -8 first and reports 1 5 where the sample reports 2 4.
# Rosalind: 2SUM — 2SUM
# https://rosalind.info/problems/2sum/
#
# Given: A positive integer k, a positive integer n, and k arrays of size n.
# Return: For each array, two indices 1 <= p < q <= n with A[p] = -A[q] if they
# exist, and -1 otherwise.
let arrays = [
[2, -3, 4, 10, 5],
[8, 2, 4, -2, -8],
[-5, 2, 3, 2, -4],
[5, 4, -5, 6, 8],
]
# Written as A[p] + A[q] == 0 rather than A[p] == -A[q]: the same condition, but
# it does not depend on how unary minus binds inside an index expression.
fn two_sum(xs) {
let answer = "-1"
let p = 0
while p < len(xs) and answer == "-1" {
let q = p + 1
while q < len(xs) and answer == "-1" {
if xs[p] + xs[q] == 0 {
answer = str(p + 1) + " " + str(q + 1)
}
q = q + 1
}
p = p + 1
}
answer
}
# Any valid pair is accepted, so the answers are checked against the definition
# rather than against one particular string. The sample output reports "2 4" for
# the second array; the scan below reaches 8 and -8 first and reports "1 5",
# which is equally correct.
fn is_valid(xs, answer) {
if answer == "-1" {
let found = false
let p = 0
while p < len(xs) {
let q = p + 1
while q < len(xs) {
if xs[p] + xs[q] == 0 {
found = true
}
q = q + 1
}
p = p + 1
}
found == false
} else {
let parts = answer |> split(" ") |> map(|t| int(t))
let p = parts[0] - 1
let q = parts[1] - 1
p < q and xs[p] + xs[q] == 0
}
}
let answers = arrays |> map(|xs| two_sum(xs))
let verdicts = range(0, len(arrays)) |> map(|i| is_valid(arrays[i], answers[i]))
for i in range(0, len(arrays)) {
println("Array " + str(i + 1) + ": " + answers[i] + " valid: " + str(verdicts[i]))
}
println("Sample output: -1 / 2 4 / -1 / 1 3")
fn test_2sum_answers_are_valid() {
assert verdicts == [true, true, true, true], "2SUM: " + str(verdicts)
assert answers[0] == "-1", "2SUM[1]: expected no pair, got " + answers[0]
assert answers[2] == "-1", "2SUM[3]: expected no pair, got " + answers[2]
}BFS — Breadth-First Search
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: BFS — Breadth-First Search
# https://rosalind.info/problems/bfs/
#
# Given: A simple directed graph with n vertices in the edge list format.
# Return: An array D[1..n] where D[i] is the length of a shortest path from
# vertex 1 to vertex i, and -1 where i is unreachable.
let n = 6
let edge_list = [[4, 6], [6, 5], [4, 3], [3, 5], [2, 1], [1, 4]]
# Directed: each edge is added once, so 2 -> 1 does not make 2 reachable.
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in edge_list {
let u = edge[0] - 1
adjacent[u] = push(adjacent[u], edge[1] - 1)
}
let distance = []
for _ in range(0, n) {
distance = push(distance, -1)
}
distance[0] = 0
# The queue is a list plus a read cursor. Breadth-first order is what makes the
# first arrival at a vertex the shortest one, so a vertex is only ever assigned
# a distance once — the -1 test doubles as the visited check.
let queue = [0]
let queue_head = 0
while queue_head < len(queue) {
let current = queue[queue_head]
queue_head = queue_head + 1
for next in adjacent[current] {
if distance[next] == -1 {
distance[next] = distance[current] + 1
queue = push(queue, next)
}
}
}
let result = distance |> map(|d| str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 0 -1 2 1 3 2")
fn test_bfs_shortest_path_lengths() {
assert result == "0 -1 2 1 3 2", "BFS: got " + result
}CC — Connected Components
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: CC — Connected Components
# https://rosalind.info/problems/cc/
#
# Given: A simple graph with n vertices in the edge list format.
# Return: The number of connected components in the graph.
let n = 12
let edge_list = [
[1, 2], [1, 5], [5, 9], [5, 10], [9, 10],
[3, 4], [3, 7], [3, 8], [4, 8], [7, 11],
[8, 11], [11, 12], [8, 12],
]
# Undirected, so every edge goes in both directions. Vertex 6 appears in no
# edge and is still a component of its own, which is why the sweep below starts
# from every vertex rather than from the endpoints of the edge list.
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
adjacent[v] = push(adjacent[v], u)
}
let seen = []
for _ in range(0, n) {
seen = push(seen, false)
}
let components = 0
for start in range(0, n) {
if seen[start] == false {
components = components + 1
# Flood the whole component from this vertex before moving on.
let stack = [start]
seen[start] = true
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for next in adjacent[current] {
if seen[next] == false {
seen[next] = true
stack = push(stack, next)
}
}
}
}
}
println("Result: " + str(components))
println("Expected: 3")
fn test_cc_component_count() {
assert components == 3, "CC: got " + str(components)
}HEA — Building a Heap
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Any permutation with the heap property is accepted, so the property is what is asserted. Floyd's construction reaches 7 3 5 1 2 where the sample shows 7 5 1 3 2.
# Rosalind: HEA — Building a Heap
# https://rosalind.info/problems/hea/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A permuted array A satisfying the binary max heap property: for any
# 2 <= i <= n, A[floor(i/2)] >= A[i].
let a = [1, 3, 5, 7, 2]
# Floyd's construction: sift down from the last internal node backwards. Doing
# it in this order is what makes building the heap linear rather than n log n —
# every subtree below a node is already a heap by the time the node is sifted.
fn sift_down(heap, start, size) {
let xs = heap
let root = start
let settled = false
while settled == false {
let largest = root
let left = 2 * root + 1
let right = 2 * root + 2
if left < size and xs[left] > xs[largest] then largest = left
if right < size and xs[right] > xs[largest] then largest = right
if largest == root {
settled = true
} else {
let held = xs[root]
xs[root] = xs[largest]
xs[largest] = held
root = largest
}
}
xs
}
let heap = a
let node = int(len(heap) / 2) - 1
while node >= 0 {
heap = sift_down(heap, node, len(heap))
node = node - 1
}
let result = heap |> map(|v| str(v)) |> join(" ")
# Any permutation with the heap property is accepted, so the property itself is
# what gets checked. The sample output is 7 5 1 3 2; sifting down from the last
# internal node reaches 7 3 5 1 2, which satisfies the same condition.
let violations = range(1, len(heap)) |> filter(|i| heap[int((i + 1) / 2) - 1] < heap[i])
println("Result: " + result)
println("Sample: 7 5 1 3 2")
println("Heap property violations: " + str(len(violations)))
fn test_hea_satisfies_the_heap_property() {
assert len(violations) == 0, "HEA: heap property broken at 1-based positions " + str(violations)
assert sort(heap) == sort(a), "HEA: the result is not a permutation of the input: " + result
}MS — Merge Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: MS — Merge Sort
# https://rosalind.info/problems/ms/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A sorted array A[1..n].
let a = [20, 19, 35, -18, 17, -20, 20, 1, 4, 4]
fn merge(left, right) {
let out = []
let i = 0
let j = 0
while i < len(left) and j < len(right) {
# `<=` rather than `<` keeps equal elements in their original order,
# which is what makes this sort stable. The array holds 4 twice and 20
# twice, so the distinction is live here.
if left[i] <= right[j] {
out = push(out, left[i])
i = i + 1
} else {
out = push(out, right[j])
j = j + 1
}
}
while i < len(left) {
out = push(out, left[i])
i = i + 1
}
while j < len(right) {
out = push(out, right[j])
j = j + 1
}
out
}
fn merge_sort(xs) {
if len(xs) <= 1 {
xs
} else {
let middle = int(len(xs) / 2)
merge(merge_sort(slice(xs, 0, middle)), merge_sort(slice(xs, middle, len(xs))))
}
}
let sorted = merge_sort(a)
let result = sorted |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: -20 -18 1 4 4 17 19 20 20 35")
fn test_ms_sorts_the_array() {
assert result == "-20 -18 1 4 4 17 19 20 20 35", "MS: got " + result
}PAR — 2-Way Partition
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Any valid partition is accepted, so the three conditions are asserted rather than one arrangement.
# Rosalind: PAR — 2-Way Partition
# https://rosalind.info/problems/par/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A permutation B of A with an index q such that everything before q is
# <= A[1], B[q] = A[1], and everything after q is > A[1].
let a = [7, 2, 5, 6, 1, 3, 9, 4, 8]
# Lomuto's scheme: one pass, with a boundary that marks where the "not greater
# than the pivot" run ends. The pivot is parked at the front during the sweep
# and swapped into the boundary at the end, which is what puts it at q.
let xs = a
let pivot = xs[0]
let boundary = 1
let j = 1
while j < len(xs) {
if xs[j] <= pivot {
let held = xs[boundary]
xs[boundary] = xs[j]
xs[j] = held
boundary = boundary + 1
}
j = j + 1
}
let held = xs[0]
xs[0] = xs[boundary - 1]
xs[boundary - 1] = held
let q = boundary - 1
let result = xs |> map(|v| str(v)) |> join(" ")
# Every partition around this pivot is accepted, so the three conditions are
# checked rather than one particular arrangement. The sample output is
# 5 6 3 4 1 2 7 9 8; this sweep produces a different valid one.
let before_ok = range(0, q) |> filter(|i| xs[i] > pivot)
let after_ok = range(q + 1, len(xs)) |> filter(|i| xs[i] <= pivot)
println("Result: " + result)
println("Sample: 5 6 3 4 1 2 7 9 8")
println("Pivot " + str(pivot) + " sits at 1-based index " + str(q + 1))
fn test_par_partitions_around_the_pivot() {
assert xs[q] == pivot, "PAR: the pivot is not at q, got " + str(xs[q])
assert len(before_ok) == 0, "PAR: values greater than the pivot before q at " + str(before_ok)
assert len(after_ok) == 0, "PAR: values not greater than the pivot after q at " + str(after_ok)
assert sort(xs) == sort(a), "PAR: the result is not a permutation of the input: " + result
}3SUM — 3SUM
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: 3SUM — 3SUM
# https://rosalind.info/problems/3sum/
#
# Given: A positive integer k, a positive integer n, and k arrays of size n.
# Return: For each array, three indices 1 <= p < q < r <= n with
# A[p] + A[q] + A[r] = 0 if they exist, and -1 otherwise.
let arrays = [
[2, -3, 4, 10, 5],
[8, -6, 4, -2, -8],
[-5, 2, 3, 2, -4],
[2, 4, -5, 6, 8],
]
# The straightforward cubic scan. Taking the indices in increasing order gives
# the lexicographically first triple, which is the one the sample reports, so
# unlike 2SUM the answers here can be compared literally.
fn three_sum(xs) {
let answer = "-1"
let p = 0
while p < len(xs) and answer == "-1" {
let q = p + 1
while q < len(xs) and answer == "-1" {
let r = q + 1
while r < len(xs) and answer == "-1" {
if xs[p] + xs[q] + xs[r] == 0 {
answer = str(p + 1) + " " + str(q + 1) + " " + str(r + 1)
}
r = r + 1
}
q = q + 1
}
p = p + 1
}
answer
}
let answers = arrays |> map(|xs| three_sum(xs))
let result = answers |> join(" / ")
println("Result: " + result)
println("Expected: -1 / 1 2 4 / 1 2 3 / -1")
fn test_3sum_finds_zero_triples() {
assert result == "-1 / 1 2 4 / 1 2 3 / -1", "3SUM: got " + result
}BIP — Testing Bipartiteness
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: BIP — Testing Bipartiteness
# https://rosalind.info/problems/bip/
#
# Given: A positive integer k and k simple graphs in the edge list format.
# Return: For each graph, 1 if it is bipartite and -1 otherwise.
let graphs = [
{ vertices: 3, edges: [[1, 2], [3, 2], [3, 1]] },
{ vertices: 4, edges: [[1, 4], [3, 1], [1, 2]] },
]
# Two-colour by breadth-first search. A graph is bipartite exactly when this
# never has to give a vertex the colour its neighbour already has, so the odd
# cycle in the first graph — the triangle — is what forces the -1.
fn is_bipartite(graph) {
let n = graph.vertices
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
adjacent[v] = push(adjacent[v], u)
}
let colour = []
for _ in range(0, n) {
colour = push(colour, -1)
}
let consistent = true
# The graph need not be connected, so every uncoloured vertex starts a sweep.
for start in range(0, n) {
if colour[start] == -1 {
colour[start] = 0
let queue = [start]
let head = 0
while head < len(queue) {
let current = queue[head]
head = head + 1
for next in adjacent[current] {
if colour[next] == -1 {
colour[next] = 1 - colour[current]
queue = push(queue, next)
} else {
if colour[next] == colour[current] {
consistent = false
}
}
}
}
}
}
if consistent then 1 else -1
}
let result = graphs |> map(|g| str(is_bipartite(g))) |> join(" ")
println("Result: " + result)
println("Expected: -1 1")
fn test_bip_detects_odd_cycles() {
assert result == "-1 1", "BIP: got " + result
}DAG — Testing Acyclicity
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: DAG — Testing Acyclicity
# https://rosalind.info/problems/dag/
#
# Given: A positive integer k and k simple directed graphs in the edge list format.
# Return: For each graph, 1 if the graph is acyclic and -1 otherwise.
let graphs = [
{ vertices: 2, edges: [[1, 2]] },
{ vertices: 4, edges: [[4, 1], [1, 2], [2, 3], [3, 1]] },
{ vertices: 4, edges: [[4, 3], [3, 2], [2, 1]] },
]
# Kahn's algorithm, used as a test rather than to produce an order: repeatedly
# remove a vertex with no remaining incoming edge. Anything left over lies on a
# cycle, because every vertex in it keeps an incoming edge from the vertex
# before it. The second graph leaves 1, 2 and 3 behind.
fn is_acyclic(graph) {
let n = graph.vertices
let adjacent = []
let indegree = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
indegree = push(indegree, 0)
}
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
indegree[v] = indegree[v] + 1
}
let queue = []
for v in range(0, n) {
if indegree[v] == 0 {
queue = push(queue, v)
}
}
let removed = 0
let head = 0
while head < len(queue) {
let current = queue[head]
head = head + 1
removed = removed + 1
for next in adjacent[current] {
indegree[next] = indegree[next] - 1
if indegree[next] == 0 {
queue = push(queue, next)
}
}
}
if removed == n then 1 else -1
}
let result = graphs |> map(|g| str(is_acyclic(g))) |> join(" ")
println("Result: " + result)
println("Expected: 1 -1 1")
fn test_dag_detects_cycles() {
assert result == "1 -1 1", "DAG: got " + result
}DIJ — Dijkstra's Algorithm
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: DIJ — Dijkstra's Algorithm
# https://rosalind.info/problems/dij/
#
# Given: A simple directed graph with positive edge weights and n vertices in
# the edge list format.
# Return: An array D[1..n] of shortest path lengths from vertex 1, with -1 where
# a vertex is unreachable.
let n = 6
let edge_list = [
[3, 4, 4], [1, 2, 4], [1, 3, 2], [2, 3, 3], [6, 3, 2],
[3, 5, 5], [5, 4, 1], [3, 2, 1], [2, 4, 2], [2, 5, 3],
]
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in edge_list {
let u = edge[0] - 1
adjacent[u] = push(adjacent[u], [edge[1] - 1, edge[2]])
}
# Scanning for the nearest unsettled vertex rather than using a priority queue:
# quadratic, and clearer. Positive weights are what make the greedy choice safe
# — once a vertex is settled no later path can improve it.
let infinity = 1000000000
let distance = []
let settled = []
for _ in range(0, n) {
distance = push(distance, infinity)
settled = push(settled, false)
}
distance[0] = 0
let step = 0
while step < n {
let nearest = -1
for v in range(0, n) {
if settled[v] == false and distance[v] < infinity {
if nearest == -1 or distance[v] < distance[nearest] {
nearest = v
}
}
}
if nearest == -1 {
step = n
} else {
settled[nearest] = true
for link in adjacent[nearest] {
let next = link[0]
let weight = link[1]
if distance[nearest] + weight < distance[next] {
distance[next] = distance[nearest] + weight
}
}
step = step + 1
}
}
let result = distance |> map(|d| if d == infinity then "-1" else str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 0 3 2 5 6 -1")
fn test_dij_shortest_paths() {
assert result == "0 3 2 5 6 -1", "DIJ: got " + result
}HS — Heap Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: HS — Heap Sort
# https://rosalind.info/problems/hs/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A sorted array A.
let a = [2, 6, 7, 1, 3, 5, 4, 8, 9]
fn sift_down(heap, start, size) {
let xs = heap
let root = start
let settled = false
while settled == false {
let largest = root
let left = 2 * root + 1
let right = 2 * root + 2
if left < size and xs[left] > xs[largest] then largest = left
if right < size and xs[right] > xs[largest] then largest = right
if largest == root {
settled = true
} else {
let held = xs[root]
xs[root] = xs[largest]
xs[largest] = held
root = largest
}
}
xs
}
# Build the max heap (as in HEA), then repeatedly move the largest element to
# the end and shrink the heap by one. The sorted tail grows from the right, so
# no second array is needed — this sorts in place.
let xs = a
let node = int(len(xs) / 2) - 1
while node >= 0 {
xs = sift_down(xs, node, len(xs))
node = node - 1
}
let size = len(xs)
while size > 1 {
let held = xs[0]
xs[0] = xs[size - 1]
xs[size - 1] = held
size = size - 1
xs = sift_down(xs, 0, size)
}
let result = xs |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: 1 2 3 4 5 6 7 8 9")
fn test_hs_sorts_the_array() {
assert result == "1 2 3 4 5 6 7 8 9", "HS: got " + result
}INV — Counting Inversions
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Counted during the merge rather than pairwise, so this is n log n where INS's swap count is quadratic. The two problems ask for the same number.
# Rosalind: INV — Counting Inversions
# https://rosalind.info/problems/inv/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: The number of inversions in A.
let a = [-6, 1, 15, 8, 10]
# Counted during a merge sort rather than by comparing every pair. When the
# merge takes an element from the right half, every element still waiting in the
# left half is greater than it and forms an inversion with it, so the whole
# remaining left half can be counted at once. That is what makes this n log n
# where INS's swap count is quadratic — the two problems ask for the same number.
let inversions = 0
fn merge_count(left, right) {
let out = []
let i = 0
let j = 0
while i < len(left) and j < len(right) {
if left[i] <= right[j] {
out = push(out, left[i])
i = i + 1
} else {
out = push(out, right[j])
j = j + 1
inversions = inversions + (len(left) - i)
}
}
while i < len(left) {
out = push(out, left[i])
i = i + 1
}
while j < len(right) {
out = push(out, right[j])
j = j + 1
}
out
}
fn sort_and_count(xs) {
if len(xs) <= 1 {
xs
} else {
let middle = int(len(xs) / 2)
merge_count(sort_and_count(slice(xs, 0, middle)), sort_and_count(slice(xs, middle, len(xs))))
}
}
let sorted = sort_and_count(a)
println("Result: " + str(inversions))
println("Expected: 2")
println("Sorted: " + str(sorted))
fn test_inv_counts_inversions() {
assert inversions == 2, "INV: got " + str(inversions)
assert sorted == sort(a), "INV: the merge did not sort: " + str(sorted)
}PAR3 — 3-Way Partition
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Dutch national flag. Any valid arrangement is accepted, so the three regions are asserted rather than one output; this one happens to match the sample.
# Rosalind: PAR3 — 3-Way Partition
# https://rosalind.info/problems/par3/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A permutation B of A with indices q <= r such that B[i] < A[1] before
# q, B[i] = A[1] from q to r, and B[i] > A[1] after r.
let a = [4, 5, 6, 4, 1, 2, 5, 7, 4]
# Dijkstra's Dutch national flag: one pass, three regions. `low` ends the run
# below the pivot, `high` begins the run above it, and `scan` walks the unknown
# middle. Swapping down from `high` does not advance `scan`, because the value
# swapped in has not been looked at yet — the array holds 4 three times, so the
# equal region is what this problem is really testing.
let xs = a
let pivot = xs[0]
let low = 0
let cursor = 0
let high = len(xs) - 1
while cursor <= high {
if xs[cursor] < pivot {
let held = xs[low]
xs[low] = xs[cursor]
xs[cursor] = held
low = low + 1
cursor = cursor + 1
} else {
if xs[cursor] > pivot {
let held = xs[high]
xs[high] = xs[cursor]
xs[cursor] = held
high = high - 1
} else {
cursor = cursor + 1
}
}
}
let result = xs |> map(|v| str(v)) |> join(" ")
# Any valid arrangement is accepted, so the three regions are checked rather
# than one particular output. The sample shows 2 1 4 4 4 5 7 6 5.
let below = range(0, low) |> filter(|i| xs[i] >= pivot)
let equal = range(low, high + 1) |> filter(|i| xs[i] != pivot)
let above = range(high + 1, len(xs)) |> filter(|i| xs[i] <= pivot)
println("Result: " + result)
println("Sample: 2 1 4 4 4 5 7 6 5")
println("Regions: below " + str(low) + ", equal " + str(high + 1 - low) + ", above " + str(len(xs) - high - 1))
fn test_par3_three_regions() {
assert len(below) == 0, "PAR3: not-smaller values before q at " + str(below)
assert len(equal) == 0, "PAR3: values other than the pivot between q and r at " + str(equal)
assert len(above) == 0, "PAR3: not-greater values after r at " + str(above)
assert sort(xs) == sort(a), "PAR3: the result is not a permutation of the input: " + result
}SQ — Square in a Graph
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: SQ — Square in a Graph
# https://rosalind.info/problems/sq/
#
# Given: A positive integer k and k simple undirected graphs in the edge list format.
# Return: For each graph, 1 if it contains a simple cycle of length 4, and -1 otherwise.
let graphs = [
{ vertices: 4, edges: [[3, 4], [4, 2], [3, 2], [3, 1], [1, 2]] },
{ vertices: 4, edges: [[1, 2], [3, 4], [2, 4], [4, 1]] },
]
# A four-cycle is two vertices joined by two different paths of length two, so
# the question is whether any pair of vertices has two neighbours in common.
# Searching for the cycle directly would mean trying orderings; counting shared
# neighbours needs one pass over the pairs.
fn has_square(graph) {
let n = graph.vertices
let neighbours = []
for _ in range(0, n) {
neighbours = push(neighbours, [])
}
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
neighbours[u] = push(neighbours[u], v)
neighbours[v] = push(neighbours[v], u)
}
let found = false
let u = 0
while u < n and found == false {
let v = u + 1
while v < n and found == false {
let shared = 0
for candidate in neighbours[u] {
if contains(neighbours[v], candidate) {
shared = shared + 1
}
}
if shared >= 2 {
found = true
}
v = v + 1
}
u = u + 1
}
if found then 1 else -1
}
let result = graphs |> map(|g| str(has_square(g))) |> join(" ")
println("Result: " + result)
println("Expected: 1 -1")
fn test_sq_finds_four_cycles() {
assert result == "1 -1", "SQ: got " + result
}BF — Bellman-Ford Algorithm
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: BF — Bellman-Ford Algorithm
# https://rosalind.info/problems/bf/
#
# Given: A simple directed graph with integer edge weights (possibly negative)
# and n vertices in the edge list format.
# Return: An array D[1..n] of shortest path lengths from vertex 1, with "x"
# where a vertex is unreachable.
let n = 9
let edge_list = [
[1, 2, 10], [3, 2, 1], [3, 4, 1], [4, 5, 3], [5, 6, -1],
[7, 6, -1], [8, 7, 1], [1, 8, 8], [7, 2, -4], [2, 6, 2],
[6, 3, -2], [9, 5, -10], [9, 4, 7],
]
# Dijkstra cannot be used here: a negative edge can improve a vertex after it
# has been settled. Bellman-Ford instead relaxes every edge n-1 times, which is
# enough because a shortest path visits at most n vertices.
let infinity = 1000000000
let distance = []
for _ in range(0, n) {
distance = push(distance, infinity)
}
distance[0] = 0
let sweep = 0
while sweep < n - 1 {
let changed = false
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
let weight = edge[2]
if distance[u] < infinity and distance[u] + weight < distance[v] {
distance[v] = distance[u] + weight
changed = true
}
}
# Nothing improved, so nothing will: the remaining rounds cannot change it.
if changed == false then sweep = n
sweep = sweep + 1
}
let result = distance |> map(|d| if d == infinity then "x" else str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 0 5 5 6 9 7 9 8 x")
fn test_bf_handles_negative_weights() {
assert result == "0 5 5 6 9 7 9 8 x", "BF: got " + result
}CTE — Shortest Cycle Through a Given Edge
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: CTE — Shortest Cycle Through a Given Edge
# https://rosalind.info/problems/cte/
#
# Given: A positive integer k and k simple directed graphs with positive edge
# weights, each with a first specified edge.
# Return: For each graph, the length of a shortest cycle through the first edge,
# or -1 if there is none.
let graphs = [
{ vertices: 4, edges: [[2, 4, 2], [3, 2, 1], [1, 4, 3], [2, 1, 10], [1, 3, 4]] },
{ vertices: 4, edges: [[3, 2, 1], [2, 4, 2], [4, 1, 3], [2, 1, 10], [1, 3, 4]] },
]
# A cycle through the edge u -> v is that edge plus a shortest path from v back
# to u, so the whole problem reduces to one Dijkstra run from v. Weights are
# positive here, which is what lets Dijkstra be used rather than Bellman-Ford.
let infinity = 1000000000
fn shortest_path(graph, source, target) {
let n = graph.vertices
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in graph.edges {
adjacent[edge[0] - 1] = push(adjacent[edge[0] - 1], [edge[1] - 1, edge[2]])
}
let distance = []
let settled = []
for _ in range(0, n) {
distance = push(distance, infinity)
settled = push(settled, false)
}
distance[source] = 0
let remaining = n
while remaining > 0 {
let nearest = -1
for v in range(0, n) {
if settled[v] == false and distance[v] < infinity {
if nearest == -1 or distance[v] < distance[nearest] {
nearest = v
}
}
}
if nearest == -1 {
remaining = 0
} else {
settled[nearest] = true
for link in adjacent[nearest] {
if distance[nearest] + link[1] < distance[link[0]] {
distance[link[0]] = distance[nearest] + link[1]
}
}
remaining = remaining - 1
}
}
distance[target]
}
fn shortest_cycle(graph) {
let first = graph.edges[0]
let back = shortest_path(graph, first[1] - 1, first[0] - 1)
if back == infinity then -1 else back + first[2]
}
let result = graphs |> map(|g| str(shortest_cycle(g))) |> join(" ")
println("Result: " + result)
println("Expected: -1 10")
fn test_cte_shortest_cycle_through_an_edge() {
assert result == "-1 10", "CTE: got " + result
}MED — Median
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Quickselect: recurses into one side only, so it answers the question without sorting. Cross-checked against sorting in the assertion.
# Rosalind: MED — Median
# https://rosalind.info/problems/med/
#
# Given: A positive integer n, an array A[1..n] of integers, and a number k.
# Return: The k-th smallest element of A.
let a = [2, 36, 5, 21, 8, 13, 11, 20, 5, 4, 1]
let k = 8
# Quickselect: partition around a pivot, then recurse into the side that holds
# the k-th element instead of both. Sorting would answer the question too and do
# more work than asked — this is the problem's point. The array holds 5 twice,
# so the equal region is kept separate rather than folded into one side.
fn select_kth(xs, rank) {
if len(xs) <= 1 {
xs[0]
} else {
let pivot = xs[int(len(xs) / 2)]
let below = xs |> filter(|v| v < pivot)
let equal = xs |> filter(|v| v == pivot)
let above = xs |> filter(|v| v > pivot)
if rank <= len(below) {
select_kth(below, rank)
} else {
if rank <= len(below) + len(equal) {
pivot
} else {
select_kth(above, rank - len(below) - len(equal))
}
}
}
}
let result = select_kth(a, k)
println("Result: " + str(result))
println("Expected: 13")
println("Sorted: " + str(sort(a)))
fn test_med_kth_smallest() {
assert result == 13, "MED: got " + str(result)
assert result == sort(a)[k - 1], "MED: disagrees with sorting, got " + str(result)
}PS — Partial Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: PS — Partial Sort
# https://rosalind.info/problems/ps/
#
# Given: A positive integer n, an array A[1..n] of integers, and a positive
# integer k.
# Return: The k smallest elements of a sorted array A.
let a = [4, -6, 7, 8, -9, 100, 12, 13, 56, 17]
let k = 3
# Only the first k elements are wanted, so a heap of size k is the usual answer:
# it keeps the work at n log k rather than n log n. With k = 3 out of 10 the
# distinction is academic, so this takes the direct route and sorts. The shape
# of the answer is the same; PS and MED together are the pair worth comparing,
# since MED shows the selection that avoids the full sort.
let smallest = slice(sort(a), 0, k)
let result = smallest |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: -9 -6 4")
fn test_ps_k_smallest() {
assert result == "-9 -6 4", "PS: got " + result
assert len(smallest) == k, "PS: expected " + str(k) + " values, got " + str(len(smallest))
}TS — Topological Sorting
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Any order with every edge pointing forwards is accepted, so that property is asserted rather than the sample text.
# Rosalind: TS — Topological Sorting
# https://rosalind.info/problems/ts/
#
# Given: A simple directed acyclic graph with n vertices in the edge list format.
# Return: A topological sorting of the graph.
let n = 4
let edge_list = [[1, 2], [3, 1], [3, 2], [4, 3], [4, 2]]
# Kahn's algorithm, the same sweep DAG uses to test for cycles — here the order
# in which vertices come off the queue is the answer rather than a by-product.
let adjacent = []
let indegree = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
indegree = push(indegree, 0)
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
indegree[v] = indegree[v] + 1
}
let order = []
for v in range(0, n) {
if indegree[v] == 0 {
order = push(order, v)
}
}
let queue_head = 0
while queue_head < len(order) {
let current = order[queue_head]
queue_head = queue_head + 1
for next in adjacent[current] {
indegree[next] = indegree[next] - 1
if indegree[next] == 0 {
order = push(order, next)
}
}
}
let result = order |> map(|v| str(v + 1)) |> join(" ")
# Any order with every edge pointing forwards is accepted. Taking the lowest
# numbered ready vertex first happens to reproduce the sample here.
let position = []
for _ in range(0, n) {
position = push(position, 0)
}
for i in range(0, len(order)) {
position[order[i]] = i
}
let backwards = edge_list |> filter(|e| position[e[0] - 1] >= position[e[1] - 1])
println("Result: " + result)
println("Expected: 4 3 1 2 (any valid order is accepted)")
fn test_ts_orders_every_edge_forwards() {
assert len(order) == n, "TS: expected " + str(n) + " vertices, got " + str(len(order))
assert len(backwards) == 0, "TS: these edges point backwards: " + str(backwards)
}HDAG — Hamiltonian Path in DAG
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Hard in general, easy on a DAG: a Hamiltonian path exists exactly when consecutive vertices of the topological order are joined by an edge.
# Rosalind: HDAG — Hamiltonian Path in DAG
# https://rosalind.info/problems/hdag/
#
# Given: A positive integer k and k simple directed acyclic graphs in the edge
# list format.
# Return: For each graph, "1" followed by a Hamiltonian path if one exists, and
# "-1" otherwise.
let graphs = [
{ vertices: 3, edges: [[1, 2], [2, 3], [1, 3]] },
{ vertices: 4, edges: [[4, 3], [3, 2], [4, 1]] },
]
# Finding a Hamiltonian path is hard in general and easy on a DAG, which is why
# the problem restricts to one. A DAG has a Hamiltonian path exactly when its
# topological order is unique, and that holds exactly when consecutive vertices
# in the order are joined by an edge. So: sort topologically, then check the
# n-1 consecutive pairs.
fn hamiltonian_path(graph) {
let n = graph.vertices
let adjacent = []
let indegree = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
indegree = push(indegree, 0)
}
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
indegree[v] = indegree[v] + 1
}
let order = []
for v in range(0, n) {
if indegree[v] == 0 {
order = push(order, v)
}
}
let head = 0
while head < len(order) {
let current = order[head]
head = head + 1
for next in adjacent[current] {
indegree[next] = indegree[next] - 1
if indegree[next] == 0 {
order = push(order, next)
}
}
}
let joined = true
for i in range(0, len(order) - 1) {
if contains(adjacent[order[i]], order[i + 1]) == false {
joined = false
}
}
if joined {
"1 " + (order |> map(|v| str(v + 1)) |> join(" "))
} else {
"-1"
}
}
let answers = graphs |> map(|g| hamiltonian_path(g))
let result = answers |> join(" / ")
println("Result: " + result)
println("Expected: 1 1 2 3 / -1")
fn test_hdag_finds_hamiltonian_paths() {
assert answers[0] == "1 1 2 3", "HDAG[1]: got " + answers[0]
assert answers[1] == "-1", "HDAG[2]: got " + answers[1]
}NWC — Negative Weight Cycle
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Every distance starts at 0, not just vertex 1, so a cycle unreachable from vertex 1 is still found.
# Rosalind: NWC — Negative Weight Cycle
# https://rosalind.info/problems/nwc/
#
# Given: A positive integer k and k simple directed graphs with integer edge
# weights in the edge list format.
# Return: For each graph, 1 if it contains a negative weight cycle, -1 otherwise.
let graphs = [
{ vertices: 4, edges: [[1, 4, 4], [4, 2, 3], [2, 3, 1], [3, 1, 6], [2, 1, -7]] },
{ vertices: 3, edges: [[1, 2, -8], [2, 3, 20], [3, 1, -1], [3, 2, -30]] },
]
# Bellman-Ford's other use. After n-1 rounds of relaxation every shortest path
# is final, so an edge that still improves on round n can only be doing it by
# going round a negative cycle. Every distance starts at 0 rather than only
# vertex 1, which is the same as adding a source joined to every vertex by a
# zero-weight edge: the cycle need not be reachable from vertex 1.
fn has_negative_cycle(graph) {
let n = graph.vertices
let distance = []
for _ in range(0, n) {
distance = push(distance, 0)
}
let sweep = 0
while sweep < n - 1 {
for edge in graph.edges {
let u = edge[0] - 1
let v = edge[1] - 1
if distance[u] + edge[2] < distance[v] {
distance[v] = distance[u] + edge[2]
}
}
sweep = sweep + 1
}
let improved = false
for edge in graph.edges {
if distance[edge[0] - 1] + edge[2] < distance[edge[1] - 1] {
improved = true
}
}
if improved then 1 else -1
}
let result = graphs |> map(|g| str(has_negative_cycle(g))) |> join(" ")
println("Result: " + result)
println("Expected: -1 1")
fn test_nwc_detects_negative_cycles() {
assert result == "-1 1", "NWC: got " + result
}QS — Quick Sort
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: QS — Quick Sort
# https://rosalind.info/problems/qs/
#
# Given: A positive integer n and an array A[1..n] of integers.
# Return: A sorted array A[1..n].
let a = [5, -2, 4, 7, 8, -10, 11]
# Partition around a pivot, then sort each side. Splitting into three parts
# rather than two keeps duplicates out of the recursion: everything equal to the
# pivot is already in its final place, so neither side has to carry it. That is
# the same split MED uses to select without sorting.
fn quicksort(xs) {
if len(xs) <= 1 {
xs
} else {
let pivot = xs[int(len(xs) / 2)]
let below = xs |> filter(|v| v < pivot)
let equal = xs |> filter(|v| v == pivot)
let above = xs |> filter(|v| v > pivot)
concat(concat(quicksort(below), equal), quicksort(above))
}
}
let sorted = quicksort(a)
let result = sorted |> map(|v| str(v)) |> join(" ")
println("Result: " + result)
println("Expected: -10 -2 4 5 7 8 11")
fn test_qs_sorts_the_array() {
assert result == "-10 -2 4 5 7 8 11", "QS: got " + result
assert sorted == sort(a), "QS: disagrees with the builtin sort: " + result
}SCC — Strongly Connected Components
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Kosaraju, both passes iterative: a recursive depth-first search reads better but its depth is the length of a path, and the track allows 10^3 vertices.
# Rosalind: SCC — Strongly Connected Components
# https://rosalind.info/problems/scc/
#
# Given: A simple directed graph with n vertices in the edge list format.
# Return: The number of strongly connected components in the graph.
let n = 6
let edge_list = [[4, 1], [1, 2], [2, 4], [5, 6], [3, 2], [5, 3], [3, 5]]
# Kosaraju's algorithm. Two passes: the first records the order in which
# vertices finish, the second walks the reversed graph taking vertices in the
# reverse of that order. Every tree of the second pass is exactly one component,
# because finishing last means nothing outside the component can reach back in.
#
# Both passes are iterative. A recursive depth-first search reads better but its
# depth is the length of a path, and this pack's problems allow 10^3 vertices.
let adjacent = []
let reversed = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
reversed = push(reversed, [])
}
for edge in edge_list {
let u = edge[0] - 1
let v = edge[1] - 1
adjacent[u] = push(adjacent[u], v)
reversed[v] = push(reversed[v], u)
}
# Pass one: push each vertex after every edge out of it has been followed.
let visited = []
for _ in range(0, n) {
visited = push(visited, false)
}
let finish_order = []
for start in range(0, n) {
if visited[start] == false {
visited[start] = true
let stack = [[start, 0]]
while len(stack) > 0 {
let top = stack[len(stack) - 1]
let vertex = top[0]
let next_child = top[1]
if next_child < len(adjacent[vertex]) {
stack[len(stack) - 1] = [vertex, next_child + 1]
let child = adjacent[vertex][next_child]
if visited[child] == false {
visited[child] = true
stack = push(stack, [child, 0])
}
} else {
finish_order = push(finish_order, vertex)
stack = slice(stack, 0, len(stack) - 1)
}
}
}
}
# Pass two: walk the reversed graph, latest finisher first.
let component = []
for _ in range(0, n) {
component = push(component, -1)
}
let components = 0
let position = len(finish_order) - 1
while position >= 0 {
let start = finish_order[position]
if component[start] == -1 {
component[start] = components
let stack = [start]
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for previous in reversed[current] {
if component[previous] == -1 {
component[previous] = components
stack = push(stack, previous)
}
}
}
components = components + 1
}
position = position - 1
}
println("Result: " + str(components))
println("Expected: 3")
println("Membership (vertex -> component): " + str(component))
fn test_scc_component_count() {
assert components == 3, "SCC: got " + str(components)
# 1, 2 and 4 lie on a cycle, as do 3 and 5; 6 is on its own.
assert component[0] == component[1], "SCC: 1 and 2 should share a component"
assert component[0] == component[3], "SCC: 1 and 4 should share a component"
assert component[2] == component[4], "SCC: 3 and 5 should share a component"
assert component[5] != component[4], "SCC: 6 should be on its own"
}2SAT — 2-Satisfiability
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
The hardest problem in the track and the one that pays off the rest: the implication graph is solved with the same Kosaraju pass SCC uses. Answers are checked by substituting them back into the formula, since any satisfying assignment is accepted.
# Rosalind: 2SAT — 2-Satisfiability
# https://rosalind.info/problems/2sat/
#
# Given: A positive integer k and k 2SAT formulas, each a list of two-literal
# clauses over n variables, where -3 means "not x3".
# Return: For each formula, 0 if it cannot be satisfied, or 1 followed by a
# satisfying assignment.
let formulas = [
{ variables: 2, clauses: [[1, 2], [-1, 2], [1, -2], [-1, -2]] },
{ variables: 3, clauses: [[1, 2], [2, 3], [-1, -2], [-2, -3]] },
]
# Two literals per clause is what makes this tractable where 3SAT is not. A
# clause (a or b) is the pair of implications "not a => b" and "not b => a", so
# a formula is a directed graph on the 2n literals. It is unsatisfiable exactly
# when some variable and its negation are strongly connected — that would say
# each implies the other.
#
# The assignment falls out of the same components. Kosaraju numbers them in
# topological order, so making each variable agree with whichever of its two
# literals is numbered higher never points an implication from a true literal to
# a false one, which is what satisfies every clause at once.
# Literal l becomes a node: x_i is 2(i-1) and its negation 2(i-1)+1.
fn literal_node(literal) {
if literal > 0 {
2 * (literal - 1)
} else {
2 * (0 - literal - 1) + 1
}
}
fn negate_node(node) {
if node % 2 == 0 then node + 1 else node - 1
}
fn strong_components(size, links) {
let adjacent = []
let reversed = []
for _ in range(0, size) {
adjacent = push(adjacent, [])
reversed = push(reversed, [])
}
for link in links {
adjacent[link[0]] = push(adjacent[link[0]], link[1])
reversed[link[1]] = push(reversed[link[1]], link[0])
}
let visited = []
for _ in range(0, size) {
visited = push(visited, false)
}
let finish_order = []
for start in range(0, size) {
if visited[start] == false {
visited[start] = true
let stack = [[start, 0]]
while len(stack) > 0 {
let top = stack[len(stack) - 1]
let vertex = top[0]
let next_child = top[1]
if next_child < len(adjacent[vertex]) {
stack[len(stack) - 1] = [vertex, next_child + 1]
let child = adjacent[vertex][next_child]
if visited[child] == false {
visited[child] = true
stack = push(stack, [child, 0])
}
} else {
finish_order = push(finish_order, vertex)
stack = slice(stack, 0, len(stack) - 1)
}
}
}
}
let component = []
for _ in range(0, size) {
component = push(component, -1)
}
let count = 0
let position = size - 1
while position >= 0 {
let start = finish_order[position]
if component[start] == -1 {
component[start] = count
let stack = [start]
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for previous in reversed[current] {
if component[previous] == -1 {
component[previous] = count
stack = push(stack, previous)
}
}
}
count = count + 1
}
position = position - 1
}
component
}
fn solve(formula) {
let n = formula.variables
let size = 2 * n
let links = []
for clause in formula.clauses {
let a = literal_node(clause[0])
let b = literal_node(clause[1])
links = push(links, [negate_node(a), b])
links = push(links, [negate_node(b), a])
}
let component = strong_components(size, links)
let satisfiable = true
for i in range(0, n) {
if component[2 * i] == component[2 * i + 1] {
satisfiable = false
}
}
if satisfiable == false {
"0"
} else {
let assignment = []
for i in range(0, n) {
# The literal in the later component is the one to make true.
if component[2 * i] > component[2 * i + 1] {
assignment = push(assignment, i + 1)
} else {
assignment = push(assignment, 0 - (i + 1))
}
}
"1 " + (assignment |> map(|v| str(v)) |> join(" "))
}
}
# Any satisfying assignment is accepted, so the answers are checked by putting
# them back into the formula rather than against the sample text.
fn satisfies(formula, answer) {
if answer == "0" {
true
} else {
let parts = answer |> split(" ")
let values = slice(parts, 1, len(parts)) |> map(|t| int(t))
let unmet = formula.clauses |> filter(|clause| {
let first = contains(values, clause[0])
let second = contains(values, clause[1])
first == false and second == false
})
len(unmet) == 0
}
}
let answers = formulas |> map(|f| solve(f))
let verdicts = range(0, len(formulas)) |> map(|i| satisfies(formulas[i], answers[i]))
for i in range(0, len(formulas)) {
println("Formula " + str(i + 1) + ": " + answers[i] + " satisfied: " + str(verdicts[i]))
}
println("Sample output: 0 / 1 1 -2 3")
fn test_2sat_solves_and_refutes() {
assert answers[0] == "0", "2SAT[1]: this formula is unsatisfiable, got " + answers[0]
assert verdicts == [true, true], "2SAT: an answer does not satisfy its formula: " + str(verdicts)
assert substr(answers[1], 0, 1) == "1", "2SAT[2]: expected a satisfying assignment, got " + answers[1]
}GS — General Sink
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: GS — General Sink
# https://rosalind.info/problems/gs/
#
# Given: A positive integer k and k simple directed graphs in the edge list format.
# Return: For each graph, a vertex from which all other vertices are reachable,
# or -1 if there is none.
let graphs = [
{ vertices: 3, edges: [[3, 2], [2, 1]] },
{ vertices: 3, edges: [[3, 2], [1, 2]] },
]
# Reachability from each vertex in turn. At this size that is the clear way to
# say it; the linear answer condenses the strongly connected components and
# checks whether the single source of the condensation reaches everything, which
# is the same test done once instead of n times.
fn reachable_from(adjacent, start, n) {
let seen = []
for _ in range(0, n) {
seen = push(seen, false)
}
seen[start] = true
let stack = [start]
let reached = 1
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for next in adjacent[current] {
if seen[next] == false {
seen[next] = true
reached = reached + 1
stack = push(stack, next)
}
}
}
reached
}
fn general_sink(graph) {
let n = graph.vertices
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in graph.edges {
adjacent[edge[0] - 1] = push(adjacent[edge[0] - 1], edge[1] - 1)
}
let answer = -1
for v in range(0, n) {
if answer == -1 and reachable_from(adjacent, v, n) == n {
answer = v + 1
}
}
answer
}
let result = graphs |> map(|g| str(general_sink(g))) |> join(" ")
println("Result: " + result)
println("Expected: 3 -1")
fn test_gs_finds_the_source_vertex() {
assert result == "3 -1", "GS: got " + result
}SC — Semi-Connected Graph
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
# Rosalind: SC — Semi-Connected Graph
# https://rosalind.info/problems/sc/
#
# Given: A positive integer k and k simple directed graphs in the edge list format.
# Return: For each graph, 1 if the graph is semi-connected and -1 otherwise.
let graphs = [
{ vertices: 3, edges: [[3, 2], [2, 1]] },
{ vertices: 3, edges: [[3, 2], [1, 2]] },
]
# Semi-connected means every pair of vertices is comparable: one of the two
# reaches the other. The second graph fails on the pair 1 and 3 — both reach 2
# and neither reaches the other. Reachability is computed from every vertex and
# the pairs are then checked directly, which says the definition out loud.
fn reachable_set(adjacent, start, n) {
let seen = []
for _ in range(0, n) {
seen = push(seen, false)
}
seen[start] = true
let stack = [start]
while len(stack) > 0 {
let current = stack[len(stack) - 1]
stack = slice(stack, 0, len(stack) - 1)
for next in adjacent[current] {
if seen[next] == false {
seen[next] = true
stack = push(stack, next)
}
}
}
seen
}
fn is_semi_connected(graph) {
let n = graph.vertices
let adjacent = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
}
for edge in graph.edges {
adjacent[edge[0] - 1] = push(adjacent[edge[0] - 1], edge[1] - 1)
}
let reaches = []
for v in range(0, n) {
reaches = push(reaches, reachable_set(adjacent, v, n))
}
let comparable = true
for u in range(0, n) {
for v in range(u + 1, n) {
if reaches[u][v] == false and reaches[v][u] == false {
comparable = false
}
}
}
if comparable then 1 else -1
}
let result = graphs |> map(|g| str(is_semi_connected(g))) |> join(" ")
println("Result: " + result)
println("Expected: 1 -1")
fn test_sc_checks_every_pair() {
assert result == "1 -1", "SC: got " + result
}SDAG — Shortest Paths in DAG
solvedbrowser + CLI Problem statement Open in the workbench Download .bl
Relaxing once in topological order is linear, where Bellman-Ford needs n-1 rounds; acyclicity is what buys that.
# Rosalind: SDAG — Shortest Paths in DAG
# https://rosalind.info/problems/sdag/
#
# Given: A weighted DAG with integer edge weights and n vertices in the edge
# list format.
# Return: An array D[1..n] of shortest path lengths from vertex 1, with "x"
# where a vertex is unreachable.
let n = 5
let edge_list = [[2, 3, 4], [4, 3, -2], [1, 4, 1], [1, 5, -3], [2, 4, -2], [5, 4, 1]]
# Weights can be negative, so Dijkstra is out; but the graph is acyclic, so
# Bellman-Ford's n-1 rounds are unnecessary. Relaxing the edges once in
# topological order is enough, because a vertex is only ever reached from
# vertices that come before it. That makes this linear where BF is quadratic.
let adjacent = []
let indegree = []
for _ in range(0, n) {
adjacent = push(adjacent, [])
indegree = push(indegree, 0)
}
for edge in edge_list {
adjacent[edge[0] - 1] = push(adjacent[edge[0] - 1], [edge[1] - 1, edge[2]])
indegree[edge[1] - 1] = indegree[edge[1] - 1] + 1
}
let order = []
for v in range(0, n) {
if indegree[v] == 0 {
order = push(order, v)
}
}
let queue_head = 0
while queue_head < len(order) {
let current = order[queue_head]
queue_head = queue_head + 1
for link in adjacent[current] {
indegree[link[0]] = indegree[link[0]] - 1
if indegree[link[0]] == 0 {
order = push(order, link[0])
}
}
}
let infinity = 1000000000
let distance = []
for _ in range(0, n) {
distance = push(distance, infinity)
}
distance[0] = 0
for v in order {
if distance[v] < infinity {
for link in adjacent[v] {
if distance[v] + link[1] < distance[link[0]] {
distance[link[0]] = distance[v] + link[1]
}
}
}
}
let result = distance |> map(|d| if d == infinity then "x" else str(d)) |> join(" ")
println("Result: " + result)
println("Expected: 0 x -4 -2 -3")
fn test_sdag_shortest_paths() {
assert result == "0 x -4 -2 -3", "SDAG: got " + result
}