Arrays

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
}

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]
}

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
}