Clay Shentrup

early in 2010, i encountered Aaron Hamlin on a comment thread about alternative voting methods. later that year, we began the 501(c)3 incorporation process for the center for election science.

it wasn’t until 8 1/2 years later that fargo became the first u.s. city to adopt approval voting. electoral reform is glacial, but i believe that approval voting will become an overnight success within a few years.

--

--

problem: given a graph of dependencies, write a function to return an array of ordered dependencies. that is, no dependency comes before one of its dependencies. cycles should be detected and cause failure.

DEPS = {
a: %i[b c],
c: %i[b d],
d: %i[e],
}

def get_deps(deps, ancestors)
deps.flat_map do |child|
raise('cycle') if ancestors.include?(child)
get_deps(DEPS.fetch(child, []), ancestors + [child]) + [child]
end.uniq
end

puts get_deps(DEPS.keys, []).inspect

--

--

Clay Shentrup

Clay Shentrup

advocate of score voting and approval voting. software engineer. father. husband. american.