Skip to content

Relative Distance

Find the degree of separation between two people in a family tree, where a step joins a parent and a child or two siblings.

Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.

// FILE: relative_distance.nomi
//# The degree of separation between two people in a family tree.

/// The fewest steps from `from` to `to` in `family`, which maps each
/// parent to their children. A step joins a parent and a child, or two
/// children of one parent. `None` when no steps join them.
pub fn degree_of_separation(
    family: Map<String, List<String>>,
    from:   String,
    to:     String,
) -> Maybe<Int>
    search([from], [from], 0, relatives(family), to)
end

/// A breadth-first search: `frontier` is every person `distance` steps
/// reach that no fewer steps do, and `seen` every person reached so far.
fn search(
    frontier:  Set<String>,
    seen:      Set<String>,
    distance:  Int,
    relatives: Map<String, Set<String>>,
    to:        String,
) -> Maybe<Int>
    if to in frontier then return Some(distance)

    next =
        frontier
        |> Iter.flat_map(&(Map.get(relatives, &1) |> Maybe.with_default([])))
        |> Iter.reject(&(&1 in seen))
        |> Iter.to_set()

    if Iter.is_empty(next) then
        None
    else
        search(next, Set.union(seen, next), distance + 1, relatives, to)
    end
end

/// Each person's relatives one step away: their parents, their children
/// and their siblings.
fn relatives(family: Map<String, List<String>>) -> Map<String, Set<String>>
    family
    |> Iter.flat_map(fn (parent, children) ->
        Iter.flat_map(children, fn child ->
            siblings = children |> Iter.filter(&(&1 != child)) |> Iter.map(&(child, &1))
            [(parent, child), (child, parent), ..siblings]
        end)
    end)
    |> Iter.group_by(.first)
    |> Map.map_values(fn links -> links |> Iter.map(.second) |> Iter.to_set())
end

// FILE: relative_distance_test.nomi
import relative_distance

/// The family the canonical data's first two complex cases share.
once family = {
    "Aiko"    => ["Bao", "Carlos"],
    "Bao"     => ["Dalia", "Elias"],
    "Carlos"  => ["Fatima", "Gustavo"],
    "Dalia"   => ["Hassan", "Isla"],
    "Elias"   => ["Javier"],
    "Fatima"  => ["Khadija", "Liam"],
    "Gustavo" => ["Mina"],
    "Hassan"  => ["Noah", "Olga"],
    "Isla"    => ["Pedro"],
    "Javier"  => ["Quynh", "Ravi"],
    "Khadija" => ["Sofia"],
    "Liam"    => ["Tariq", "Uma"],
    "Mina"    => ["Viktor", "Wang"],
    "Noah"    => ["Xiomara"],
    "Olga"    => ["Yuki"],
    "Pedro"   => ["Zane", "Aditi"],
    "Quynh"   => ["Boris"],
    "Ravi"    => ["Celine"],
    "Sofia"   => ["Diego", "Elif"],
    "Tariq"   => ["Farah"],
    "Uma"     => ["Giorgio"],
    "Viktor"  => ["Hana", "Ian"],
    "Wang"    => ["Jing"],
    "Xiomara" => ["Kaito"],
    "Yuki"    => ["Leila"],
    "Zane"    => ["Mateo"],
    "Aditi"   => ["Nia"],
    "Boris"   => ["Oscar"],
    "Celine"  => ["Priya"],
    "Diego"   => ["Qi"],
    "Elif"    => ["Rami"],
    "Farah"   => ["Sven"],
    "Giorgio" => ["Tomoko"],
    "Hana"    => ["Umar"],
    "Ian"     => ["Vera"],
    "Jing"    => ["Wyatt"],
    "Kaito"   => ["Xia"],
    "Leila"   => ["Yassin"],
    "Mateo"   => ["Zara"],
    "Nia"     => ["Antonio"],
    "Oscar"   => ["Bianca"],
    "Priya"   => ["Cai"],
    "Qi"      => ["Dimitri"],
    "Rami"    => ["Ewa"],
    "Sven"    => ["Fabio"],
    "Tomoko"  => ["Gabriela"],
    "Umar"    => ["Helena"],
    "Vera"    => ["Igor"],
    "Wyatt"   => ["Jun"],
    "Xia"     => ["Kim"],
    "Yassin"  => ["Lucia"],
    "Zara"    => ["Mohammed"],
}

/// The family of the last complex case: `family` with Elias left out, so
/// Javier's line is a tree of its own.
once split_family = {
    "Aiko"    => ["Bao", "Carlos"],
    "Bao"     => ["Dalia"],
    "Carlos"  => ["Fatima", "Gustavo"],
    "Dalia"   => ["Hassan", "Isla"],
    "Fatima"  => ["Khadija", "Liam"],
    "Gustavo" => ["Mina"],
    "Hassan"  => ["Noah", "Olga"],
    "Isla"    => ["Pedro"],
    "Javier"  => ["Quynh", "Ravi"],
    "Khadija" => ["Sofia"],
    "Liam"    => ["Tariq", "Uma"],
    "Mina"    => ["Viktor", "Wang"],
    "Noah"    => ["Xiomara"],
    "Olga"    => ["Yuki"],
    "Pedro"   => ["Zane", "Aditi"],
    "Quynh"   => ["Boris"],
    "Ravi"    => ["Celine"],
    "Sofia"   => ["Diego", "Elif"],
    "Tariq"   => ["Farah"],
    "Uma"     => ["Giorgio"],
    "Viktor"  => ["Hana", "Ian"],
    "Wang"    => ["Jing"],
    "Xiomara" => ["Kaito"],
    "Yuki"    => ["Leila"],
    "Zane"    => ["Mateo"],
    "Aditi"   => ["Nia"],
    "Boris"   => ["Oscar"],
    "Celine"  => ["Priya"],
    "Diego"   => ["Qi"],
    "Elif"    => ["Rami"],
    "Farah"   => ["Sven"],
    "Giorgio" => ["Tomoko"],
    "Hana"    => ["Umar"],
    "Ian"     => ["Vera"],
    "Jing"    => ["Wyatt"],
    "Kaito"   => ["Xia"],
    "Leila"   => ["Yassin"],
    "Mateo"   => ["Zara"],
    "Nia"     => ["Antonio"],
    "Oscar"   => ["Bianca"],
    "Priya"   => ["Cai"],
    "Qi"      => ["Dimitri"],
    "Rami"    => ["Ewa"],
    "Sven"    => ["Fabio"],
    "Tomoko"  => ["Gabriela"],
    "Umar"    => ["Helena"],
    "Vera"    => ["Igor"],
    "Wyatt"   => ["Jun"],
    "Xia"     => ["Kim"],
    "Yassin"  => ["Lucia"],
    "Zara"    => ["Mohammed"],
}

test "degree of separation"
    [
        (
            "Direct parent-child relation",
            {"Vera" => ["Tomoko"], "Tomoko" => ["Aditi"]},
            "Vera",
            "Tomoko",
            Some(1),
        ),
        ("Sibling relationship", {"Dalia" => ["Olga", "Yassin"]}, "Olga", "Yassin", Some(1)),
        (
            "Two degrees of separation, grandchild",
            {"Khadija" => ["Mateo"], "Mateo" => ["Rami"]},
            "Khadija",
            "Rami",
            Some(2),
        ),
        (
            "Unrelated individuals",
            {"Priya" => ["Rami"], "Kaito" => ["Elif"]},
            "Priya",
            "Kaito",
            None,
        ),
        ("Complex graph, cousins",                         family, "Dimitri", "Fabio", Some(9)),
        ("Complex graph, no shortcut, far removed nephew", family, "Lucia",   "Jun",   Some(14)),
        (
            "Complex graph, some shortcuts, cross-down and cross-up, cousins several times removed, with unrelated family tree",
            split_family,
            "Wyatt",
            "Xia",
            Some(12),
        ),
    ]
    |> subtests (description, tree, from, to, expected), description
        assert relative_distance.degree_of_separation(tree, from, to) == expected
    end
end
  • The family tree is the canonical data’s shape, a Map<String, List<String>> from each parent to their children, and the answer is Maybe<Int>, with None for two people no steps join (the canonical null).
  • relatives turns the tree into each person’s set of people one step away: every parent and child both ways, and every pair of children of one parent. Each link is a (person, relative) pair; Iter.group_by on the person and Map.map_values to a set of relatives finish it. Siblings are linked directly, as the instructions ask, so a sibling is one step, not two through the parent.
  • The search is breadth first, a tail-recursive function over the frontier, the set of people seen and the distance, as in two-bucket. The first frontier holding the target is reached in the fewest steps, and a frontier that adds nobody new means no steps join them.
  • The seven canonical cases are one subtests table. The three complex cases use two large trees, written once each as a once above the test: the first two cases share one tree, and the last uses a variant of it with one branch cut off.