Ethan826/family_bfs.rb

## family_bfs.rb
# frozen_string_literal: true

require "set"
require "minitest/autorun"

# Helper method for `get_levels`. Using a breadth-first search, traverse up the
# parent entries in the adjacency list, setting entries in the `levels` hashmap
# and adding relatives to the `level_known` set. Relies on Ruby's
# pass-by-reference semantics for objects to mutate arguments `levels` and
# `level_known` (which is the point of calling the function).
#
# The traversal works exactly like a normal iterative breadth-first search, see,
# e.g. https://goo.gl/tXAMmS, except that we don't need a `visited` data
# structure because a family without cosanguineous marriage is guaranteed to be
# acyclic.
# rubocop:disable Metrics/MethodLength
def get_levels_bfs(family, current, level, levels, level_known)
  frontier = [current]
  until frontier.empty?
    level += 1
    frontier.each_with_object([]) do |next_node, next_frontier|
      family[next_node].each do |further_node|
        next_frontier << further_node
        level_known << further_node
        levels[further_node] = level
      end
    end
    frontier = next_frontier
  end
end
# rubocop:enable Metrics/MethodLength

# Given an array of paths, traverse up one further level, updating paths. Drop
# paths that cannot go up a level.
#
# @param family [Hash{Symbol => Array<Symbol>}]
def go_up_one_level(family, paths)
  paths.each_with_object([]) do |path, result|
    family[path.last]&.each do |next_node|
      result << (path.clone << next_node)
    end
  end
end

# Reverse a path between relatives. Given a path of the form
# [[:son, :father, :grandfather, :uncle], [:up, :up, :down]],
# return
# [[:uncle, :grandfather, :father, :son], [:up, :down, :down]]
#
# @param path [Array<Array<Symbol>]
# @return [Array<Array<Symbol>>]
def reverse_path(path)
  [
    path.first.reverse,
    path.last.reverse.map do |e|
      unless %i[down up].include?(e)
        raise ArgumentError,
              "Directions must be `:up` or `:down`; #{e} is invalid"
      end
      e == :up ? :down : :up
    end
  ]
end

# Simple path-building bfs. See https://goo.gl/df7G2F
#
# @param family [Hash{Symbol => Set<Symbol>}]
# @param start_node [Symbol]
# @param end_node [Symbol]
# @return [Array<Array<Symbol>>]
def get_up_path(family, start_node, end_node)
  paths = [[start_node]]
  until paths.empty?
    path = paths.pop
    next_node = path[-1]
    return [path, Array.new(path.length.pred, :up)] if next_node == end_node
    family[next_node]&.each do |adjacent|
      paths << (path.clone << adjacent)
    end
  end
  []
end

# Helper method for `get_up_down_paths`. Given a family adjacency list, a
# relative at a lower generation, a relative at a higher generation, and a
# hashset containing the generational levels of all family members, walk up the
# family from both nodes until reaching one generation above the higher node,
# returning the paths from each node to that common generation.
#
# @param family [Hash{Symbol => Set<Symbol>}]
# @param levels [Hash{Symbol => Integer}]
# @param low_node [Symbol]
# @param high_node [Symbol]
# @return [Hash{Symbol => Array<Array<Symbol>>}]
def initialize_high_low_node_paths(family, levels, low_node, high_node)
  low_node_paths = [[low_node]]
  high_node_paths = [[high_node]]

  (levels[high_node] - levels[low_node]).succ.times do
    low_node_paths = go_up_one_level(family, low_node_paths)
  end

  high_node_paths = go_up_one_level(family, high_node_paths)

  { high_node_paths: high_node_paths, low_node_paths: low_node_paths }
end

# Given paths going up the generations from each of two relatives, combine the
# paths to reflect routes going up from the relative in a later generation to
# the common ancestors, then down from the common ancestors to the relative in
# the earlier generation. The result is an array of all the routes, each route
# comprising a two-element array with the first element representing a path of
# length n and the second element an array of n-1 elements, each representing
# the direction to traverse from each relative to the next relative.
#
# @example
#   combine_up_down_paths(
#     [[:proband, :father, :grandmother]], [[:uncle, :grandmother]]
#   ) # => [[[:proband, :father, :grandmother, :uncle], [:up, :up, :down]]]
#
# @param low_node_paths_to_merge [Array<Array<Symbol>>]
# @param high_node_paths_to_merge [Array<Array<Symbol>>]
# @return [Array<Array<Array<Symbol>>>]
def combine_up_down_paths(low_node_paths_to_merge, high_node_paths_to_merge)
  low_node_paths_to_merge.flat_map do |s|
    high_node_paths_to_merge.map do |e|
      [s + e.reverse.drop(1),
       Array.new(s.length.pred, :up) + Array.new(e.length.pred, :down)]
    end
  end
end

# Helper method for `get_up_down_paths`. Given a path through generations,
# combine the paths on all common ancestors if any exist, else nil.
#
# @param low_node_paths [Array<Symbol>]
# @param high_node_paths [Array<Symbol>]
# @return [Array<Array<Array<Symbol>>>, nil]
def combine_paths(low_node_paths, high_node_paths)
  overlap = low_node_paths.map(&:last) & high_node_paths.map(&:last)
  unless overlap.empty? # rubocop:disable Style/GuardClause
    overlap.flat_map do |overlapping_element|
      predicate = ->(path) { path.last == overlapping_element }
      low_node_paths_to_merge = low_node_paths.select(&predicate)
      high_node_paths_to_merge = high_node_paths.select(&predicate)
      combine_up_down_paths(low_node_paths_to_merge, high_node_paths_to_merge)
    end
  end
end

# We go up with a bfs from the lower node to the level of the higher node. Then
# we traverse up one layer from each until we hit a level with common ancestry.
# At that point, we
def get_up_down_paths(family, levels, low_node, high_node)
  high_node_paths, low_node_paths =
    initialize_high_low_node_paths(family, levels, low_node, high_node)
    .values_at(:high_node_paths, :low_node_paths)

  until low_node_paths.empty? || high_node_paths.empty?
    combined_paths = combine_paths(low_node_paths, high_node_paths)

    return combined_paths if combined_paths

    low_node_paths = go_up_one_level(family, low_node_paths)
    high_node_paths = go_up_one_level(family, high_node_paths)
  end
  []
end

# Helper method for `build_paths`. Mutates the `paths` argument. Note that for
# optimization purposes, `up_path` is passed by value.
#
# @param low_node [Symbol]
# @param high_node [Symbol]
# @param up_path [Array<Symbol>]
# @param paths[Hash{Array<Symbol> => Array<Symbol>}]
def handle_direct_lineage(low_node, high_node, up_path, paths)
  paths[[low_node, high_node]] = [up_path]
  paths[[high_node, low_node]] = [reverse_path(up_path)]
end

# Helper method for `build_paths`. Mutates the `paths` argument.
#
# @param low_node [Symbol]
# @param high_node [Symbol]
# @param levels [Hash{Symbol => Integer}]
# @param paths[Hash{Array<Symbol> => Array<Symbol>}]
def handle_no_direct_lineage(low_node, high_node, levels, paths)
  up_down_paths = get_up_down_paths(family, levels, low_node, high_node)

  if !up_down_paths.empty?
    paths[[low_node, high_node]] = up_down_paths
    paths[[high_node, low_node]] =
      up_down_paths.map { |path| reverse_path(path) }
  else
    paths[[low_node, high_node]] = []
    paths[[high_node, low_node]] = []
  end
end

# Given a `family` adjacency list and a `levels` hashmap, construct an hashmap
# with keys as `[start_node, end_node]` and values as
# `[[[:path, :through, :family], [:up, :down]],
#  [[:other, :path, :through], [:up :down]]]`
#
# @param family [Hash{Symbol => Array<Symbol>}]
# @param levels [Hash{Symbol => Integer}]
# @return [Array<Array<Array<Symbol>>>]
def build_paths(family, levels)
  family.keys.combination(2)
        .each_with_object({}) do |(start_node, end_node), paths|
    low_node, high_node = [start_node, end_node].sort_by { |node| levels[node] }
    up_path = get_up_path(family, low_node, high_node)

    if up_path.empty?
      handle_no_direct_lineage(low_node, high_node, levels, paths)
    else
      handle_direct_lineage(low_node, high_node, up_path, paths)
    end
  end
end

# Given a hashmap of type T keys and sets of type T values, each representing
# one family member, compute the "level" of each family member, with internally
# consistent but arbitrary indexing (the indices will include 0, but may contain
# positive or negative numbers).
def get_levels(family) # rubocop:disable Metrics/MethodLength Metrics/AbcSize
  # Table-setting before the first iteration
  level = 0
  levels = family.keys.reduce({}) { |a, k| a.merge(k => nil) }
  current = family.keys.first
  level_known = Set.new

  # We will be done once the `length_known` set has every member of the family.
  # Before each iteration, `current` has been added to the `levels` hashmap.
  until level_known.length == family.keys.length

    # Update data structures to reflect our knowledge of `current`.
    levels[current] = level
    level_known << current

    # Run a depth-first search to update the levels of all family members above
    # `current` in the family.
    get_levels_bfs(family, current, level, levels, level_known)

    # Now we need to find a way to traverse down the family. We'll find a child
    # with a parent in the `levels` hashmap whose level isn't known. That's a
    # person in the `levels` hashmap for whom (1) the value is `nil`, and (2)
    # who has at least one parent in the `levels` hashmap with a non-nil level
    # (we'll need to cross-reference the `family` hashmap to look up parents).
    # Having found that person, we can set the person's level to be one lower
    # than their parent's, set that person to be the new `current`, and loop
    # back through the `get_levels_bfs` function.
    levels.each do |k, v|
      next unless v.nil? # No point working with someone whose level we do know.

      # Take the set intersection of the unknown person's parents with the
      # people whose levels are known. If there is at least one member of the
      # set intersection, we know we have a child of someone with a known level.
      parent = (family[k] & level_known).first
      if parent
        current = k
        level = levels[parent].pred
      end
    end
  end
  levels
end

# :nodoc:
class TestUncleFamily < Minitest::Test
  attr_reader :levels, :family

  def setup # rubocop:disable Metrics/MethodLength
    @levels = { proband: 0,
                mother: 1,
                father: 1,
                grandmother: 2,
                grandfather: 2,
                uncle: 1 }
    @family = { proband: Set.new(%i[mother father]),
                mother: Set.new,
                father: Set.new(%i[grandmother grandfather]),
                grandmother: Set.new,
                grandfather: Set.new,
                uncle: Set.new(%i[grandfather grandmother]) }
  end

  def test_go_up_one_level
    paths = [[:proband]]
    up_one_level = go_up_one_level(family, paths).sort
    assert_equal(up_one_level, [%i[proband mother], %i[proband father]].sort)
    assert_equal(
      go_up_one_level(family, up_one_level),
      [%i[proband father grandmother], %i[proband father grandfather]]
    )
  end

  def test_get_up_down_paths
    assert_equal(
      [[%i[proband father grandmother uncle], %i[up up down]],
       [%i[proband father grandfather uncle], %i[up up down]]],
      get_up_down_paths(family, levels, :proband, :uncle)
    )
  end

  def test_reverse_path
    assert_equal(
      [%i[uncle grandmother father proband], %i[up down down]],
      reverse_path([%i[proband father grandmother uncle], %i[up up down]])
    )
  end

  def test_get_up_path
    assert_equal(
      [%i[proband father grandmother], %i[up up]],
      get_up_path(family, :proband, :grandmother)
    )
  end
end

# :nodoc:
class TestMyFamily < Minitest::Test
  attr_reader :levels, :family

  def setup # rubocop:disable Metrics/MethodLength
    @family = {
      marshall: Set.new,
      belle: Set.new(%i[ethan madigan]),
      betty: Set.new,
      red: Set.new,
      nancy: Set.new,
      clara: Set.new(%i[ethan madigan]),
      ethan: Set.new(%i[steve judy]),
      jonathan: Set.new(%i[betty marshall]),
      judy: Set.new,
      madigan: Set.new(%i[jonathan maggie]),
      maggie: Set.new(%i[red nancy]),
      milo: Set.new(%i[ethan madigan]),
      nick: Set.new(%i[jonathan maggie]),
      steve: Set.new
    }
    @levels = { marshall: 0,
                belle: -3,
                betty: 0,
                red: 0,
                nancy: 0,
                clara: -3,
                ethan: -2,
                jonathan: -1,
                judy: -1,
                madigan: -2,
                maggie: -1,
                milo: -3,
                nick: -2,
                steve: -1 }
  end

  def test_foo
    pp build_paths(family, levels)
  end
end
	# frozen_string_literal: true

	require "set"
	require "minitest/autorun"

	# Helper method for `get_levels`. Using a breadth-first search, traverse up the
	# parent entries in the adjacency list, setting entries in the `levels` hashmap
	# and adding relatives to the `level_known` set. Relies on Ruby's
	# pass-by-reference semantics for objects to mutate arguments `levels` and
	# `level_known` (which is the point of calling the function).
	#
	# The traversal works exactly like a normal iterative breadth-first search, see,
	# e.g. https://goo.gl/tXAMmS, except that we don't need a `visited` data
	# structure because a family without cosanguineous marriage is guaranteed to be
	# acyclic.
	# rubocop:disable Metrics/MethodLength
	def get_levels_bfs(family, current, level, levels, level_known)
	frontier = [current]
	until frontier.empty?
	level += 1
	frontier.each_with_object([]) do \|next_node, next_frontier\|
	family[next_node].each do \|further_node\|
	next_frontier << further_node
	level_known << further_node
	levels[further_node] = level
	end
	end
	frontier = next_frontier
	end
	end
	# rubocop:enable Metrics/MethodLength

	# Given an array of paths, traverse up one further level, updating paths. Drop
	# paths that cannot go up a level.
	#
	# @param family [Hash{Symbol => Array<Symbol>}]
	def go_up_one_level(family, paths)
	paths.each_with_object([]) do \|path, result\|
	family[path.last]&.each do \|next_node\|
	result << (path.clone << next_node)
	end
	end
	end

	# Reverse a path between relatives. Given a path of the form
	# [[:son, :father, :grandfather, :uncle], [:up, :up, :down]],
	# return
	# [[:uncle, :grandfather, :father, :son], [:up, :down, :down]]
	#
	# @param path [Array<Array<Symbol>]
	# @return [Array<Array<Symbol>>]
	def reverse_path(path)
	[
	path.first.reverse,
	path.last.reverse.map do \|e\|
	unless %i[down up].include?(e)
	raise ArgumentError,
	"Directions must be `:up` or `:down`; #{e} is invalid"
	end
	e == :up ? :down : :up
	end
	]
	end

	# Simple path-building bfs. See https://goo.gl/df7G2F
	#
	# @param family [Hash{Symbol => Set<Symbol>}]
	# @param start_node [Symbol]
	# @param end_node [Symbol]
	# @return [Array<Array<Symbol>>]
	def get_up_path(family, start_node, end_node)
	paths = [[start_node]]
	until paths.empty?
	path = paths.pop
	next_node = path[-1]
	return [path, Array.new(path.length.pred, :up)] if next_node == end_node
	family[next_node]&.each do \|adjacent\|
	paths << (path.clone << adjacent)
	end
	end
	[]
	end

	# Helper method for `get_up_down_paths`. Given a family adjacency list, a
	# relative at a lower generation, a relative at a higher generation, and a
	# hashset containing the generational levels of all family members, walk up the
	# family from both nodes until reaching one generation above the higher node,
	# returning the paths from each node to that common generation.
	#
	# @param family [Hash{Symbol => Set<Symbol>}]
	# @param levels [Hash{Symbol => Integer}]
	# @param low_node [Symbol]
	# @param high_node [Symbol]
	# @return [Hash{Symbol => Array<Array<Symbol>>}]
	def initialize_high_low_node_paths(family, levels, low_node, high_node)
	low_node_paths = [[low_node]]
	high_node_paths = [[high_node]]

	(levels[high_node] - levels[low_node]).succ.times do
	low_node_paths = go_up_one_level(family, low_node_paths)
	end

	high_node_paths = go_up_one_level(family, high_node_paths)

	{ high_node_paths: high_node_paths, low_node_paths: low_node_paths }
	end

	# Given paths going up the generations from each of two relatives, combine the
	# paths to reflect routes going up from the relative in a later generation to
	# the common ancestors, then down from the common ancestors to the relative in
	# the earlier generation. The result is an array of all the routes, each route
	# comprising a two-element array with the first element representing a path of
	# length n and the second element an array of n-1 elements, each representing
	# the direction to traverse from each relative to the next relative.
	#
	# @example
	# combine_up_down_paths(
	# [[:proband, :father, :grandmother]], [[:uncle, :grandmother]]
	# ) # => [[[:proband, :father, :grandmother, :uncle], [:up, :up, :down]]]
	#
	# @param low_node_paths_to_merge [Array<Array<Symbol>>]
	# @param high_node_paths_to_merge [Array<Array<Symbol>>]
	# @return [Array<Array<Array<Symbol>>>]
	def combine_up_down_paths(low_node_paths_to_merge, high_node_paths_to_merge)
	low_node_paths_to_merge.flat_map do \|s\|
	high_node_paths_to_merge.map do \|e\|
	[s + e.reverse.drop(1),
	Array.new(s.length.pred, :up) + Array.new(e.length.pred, :down)]
	end
	end
	end

	# Helper method for `get_up_down_paths`. Given a path through generations,
	# combine the paths on all common ancestors if any exist, else nil.
	#
	# @param low_node_paths [Array<Symbol>]
	# @param high_node_paths [Array<Symbol>]
	# @return [Array<Array<Array<Symbol>>>, nil]
	def combine_paths(low_node_paths, high_node_paths)
	overlap = low_node_paths.map(&:last) & high_node_paths.map(&:last)
	unless overlap.empty? # rubocop:disable Style/GuardClause
	overlap.flat_map do \|overlapping_element\|
	predicate = ->(path) { path.last == overlapping_element }
	low_node_paths_to_merge = low_node_paths.select(&predicate)
	high_node_paths_to_merge = high_node_paths.select(&predicate)
	combine_up_down_paths(low_node_paths_to_merge, high_node_paths_to_merge)
	end
	end
	end

	# We go up with a bfs from the lower node to the level of the higher node. Then
	# we traverse up one layer from each until we hit a level with common ancestry.
	# At that point, we
	def get_up_down_paths(family, levels, low_node, high_node)
	high_node_paths, low_node_paths =
	initialize_high_low_node_paths(family, levels, low_node, high_node)
	.values_at(:high_node_paths, :low_node_paths)

	until low_node_paths.empty? \|\| high_node_paths.empty?
	combined_paths = combine_paths(low_node_paths, high_node_paths)

	return combined_paths if combined_paths

	low_node_paths = go_up_one_level(family, low_node_paths)
	high_node_paths = go_up_one_level(family, high_node_paths)
	end
	[]
	end

	# Helper method for `build_paths`. Mutates the `paths` argument. Note that for
	# optimization purposes, `up_path` is passed by value.
	#
	# @param low_node [Symbol]
	# @param high_node [Symbol]
	# @param up_path [Array<Symbol>]
	# @param paths[Hash{Array<Symbol> => Array<Symbol>}]
	def handle_direct_lineage(low_node, high_node, up_path, paths)
	paths[[low_node, high_node]] = [up_path]
	paths[[high_node, low_node]] = [reverse_path(up_path)]
	end

	# Helper method for `build_paths`. Mutates the `paths` argument.
	#
	# @param low_node [Symbol]
	# @param high_node [Symbol]
	# @param levels [Hash{Symbol => Integer}]
	# @param paths[Hash{Array<Symbol> => Array<Symbol>}]
	def handle_no_direct_lineage(low_node, high_node, levels, paths)
	up_down_paths = get_up_down_paths(family, levels, low_node, high_node)

	if !up_down_paths.empty?
	paths[[low_node, high_node]] = up_down_paths
	paths[[high_node, low_node]] =
	up_down_paths.map { \|path\| reverse_path(path) }
	else
	paths[[low_node, high_node]] = []
	paths[[high_node, low_node]] = []
	end
	end

	# Given a `family` adjacency list and a `levels` hashmap, construct an hashmap
	# with keys as `[start_node, end_node]` and values as
	# `[[[:path, :through, :family], [:up, :down]],
	# [[:other, :path, :through], [:up :down]]]`
	#
	# @param family [Hash{Symbol => Array<Symbol>}]
	# @param levels [Hash{Symbol => Integer}]
	# @return [Array<Array<Array<Symbol>>>]
	def build_paths(family, levels)
	family.keys.combination(2)
	.each_with_object({}) do \|(start_node, end_node), paths\|
	low_node, high_node = [start_node, end_node].sort_by { \|node\| levels[node] }
	up_path = get_up_path(family, low_node, high_node)

	if up_path.empty?
	handle_no_direct_lineage(low_node, high_node, levels, paths)
	else
	handle_direct_lineage(low_node, high_node, up_path, paths)
	end
	end
	end

	# Given a hashmap of type T keys and sets of type T values, each representing
	# one family member, compute the "level" of each family member, with internally
	# consistent but arbitrary indexing (the indices will include 0, but may contain
	# positive or negative numbers).
	def get_levels(family) # rubocop:disable Metrics/MethodLength Metrics/AbcSize
	# Table-setting before the first iteration
	level = 0
	levels = family.keys.reduce({}) { \|a, k\| a.merge(k => nil) }
	current = family.keys.first
	level_known = Set.new

	# We will be done once the `length_known` set has every member of the family.
	# Before each iteration, `current` has been added to the `levels` hashmap.
	until level_known.length == family.keys.length

	# Update data structures to reflect our knowledge of `current`.
	levels[current] = level
	level_known << current

	# Run a depth-first search to update the levels of all family members above
	# `current` in the family.
	get_levels_bfs(family, current, level, levels, level_known)

	# Now we need to find a way to traverse down the family. We'll find a child
	# with a parent in the `levels` hashmap whose level isn't known. That's a
	# person in the `levels` hashmap for whom (1) the value is `nil`, and (2)
	# who has at least one parent in the `levels` hashmap with a non-nil level
	# (we'll need to cross-reference the `family` hashmap to look up parents).
	# Having found that person, we can set the person's level to be one lower
	# than their parent's, set that person to be the new `current`, and loop
	# back through the `get_levels_bfs` function.
	levels.each do \|k, v\|
	next unless v.nil? # No point working with someone whose level we do know.

	# Take the set intersection of the unknown person's parents with the
	# people whose levels are known. If there is at least one member of the
	# set intersection, we know we have a child of someone with a known level.
	parent = (family[k] & level_known).first
	if parent
	current = k
	level = levels[parent].pred
	end
	end
	end
	levels
	end

	# :nodoc:
	class TestUncleFamily < Minitest::Test
	attr_reader :levels, :family

	def setup # rubocop:disable Metrics/MethodLength
	@levels = { proband: 0,
	mother: 1,
	father: 1,
	grandmother: 2,
	grandfather: 2,
	uncle: 1 }
	@family = { proband: Set.new(%i[mother father]),
	mother: Set.new,
	father: Set.new(%i[grandmother grandfather]),
	grandmother: Set.new,
	grandfather: Set.new,
	uncle: Set.new(%i[grandfather grandmother]) }
	end

	def test_go_up_one_level
	paths = [[:proband]]
	up_one_level = go_up_one_level(family, paths).sort
	assert_equal(up_one_level, [%i[proband mother], %i[proband father]].sort)
	assert_equal(
	go_up_one_level(family, up_one_level),
	[%i[proband father grandmother], %i[proband father grandfather]]
	)
	end

	def test_get_up_down_paths
	assert_equal(
	[[%i[proband father grandmother uncle], %i[up up down]],
	[%i[proband father grandfather uncle], %i[up up down]]],
	get_up_down_paths(family, levels, :proband, :uncle)
	)
	end

	def test_reverse_path
	assert_equal(
	[%i[uncle grandmother father proband], %i[up down down]],
	reverse_path([%i[proband father grandmother uncle], %i[up up down]])
	)
	end

	def test_get_up_path
	assert_equal(
	[%i[proband father grandmother], %i[up up]],
	get_up_path(family, :proband, :grandmother)
	)
	end
	end

	# :nodoc:
	class TestMyFamily < Minitest::Test
	attr_reader :levels, :family

	def setup # rubocop:disable Metrics/MethodLength
	@family = {
	marshall: Set.new,
	belle: Set.new(%i[ethan madigan]),
	betty: Set.new,
	red: Set.new,
	nancy: Set.new,
	clara: Set.new(%i[ethan madigan]),
	ethan: Set.new(%i[steve judy]),
	jonathan: Set.new(%i[betty marshall]),
	judy: Set.new,
	madigan: Set.new(%i[jonathan maggie]),
	maggie: Set.new(%i[red nancy]),
	milo: Set.new(%i[ethan madigan]),
	nick: Set.new(%i[jonathan maggie]),
	steve: Set.new
	}
	@levels = { marshall: 0,
	belle: -3,
	betty: 0,
	red: 0,
	nancy: 0,
	clara: -3,
	ethan: -2,
	jonathan: -1,
	judy: -1,
	madigan: -2,
	maggie: -1,
	milo: -3,
	nick: -2,
	steve: -1 }
	end

	def test_foo
	pp build_paths(family, levels)
	end
	end