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
endok degree of separation (7 cases)
test result: ok. 7 passed, 0 failed
How it’s written
Section titled “How it’s written”- The family tree is the canonical data’s shape, a
Map<String, List<String>>from each parent to their children, and the answer isMaybe<Int>, withNonefor two people no steps join (the canonicalnull). relativesturns 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_byon the person andMap.map_valuesto 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
subteststable. The three complex cases use two large trees, written once each as aonceabove the test: the first two cases share one tree, and the last uses a variant of it with one branch cut off.