This kata provides you with a list of parent-child pairs `family_list`, and from this family description you'll need to find the relationship between two members(what is the relation of latter with former) which is given as `target_pair`.

For example, the family list may be given as:

`[('Enid', 'Susan'), ('Susan', 'Deborah'), ('Enid', 'Dianne')]`

This describes the family:

          Enid
            |
       |---------|
     Susan     Dianne
       |
    Deborah

The relationship pair `('Deborah', 'Enid')` should return 'Grandmother' as Enid is Deborah's Grandmother.

This family tree can cover up to 3 generations, with varying numbers of children for each parent. We only focus on the females in the family, and so children will have only one parent.

The possible responses are Mother, Daughter, Grandmother, Granddaughter, Sister, Cousin, Aunt, Niece (each matching their 'real life' equivalents). There will always be a valid answer.

Enjoy, and be nice to your Mother!

Source: codewars | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: def relations(family_list, target_pair):
	

Solutions:
def relations(family_list, target_pair):
	parents = {}
	for (parent, child) in family_list:
		parents[child] = parent
	(a, b) = target_pair
	ap = parents.get(a)
	app = parents.get(ap)
	bp = parents.get(b)
	bpp = parents.get(bp)
	if b == ap:
		return 'Mother'
	if b == app:
		return 'Grandmother'
	if a == bp:
		return 'Daughter'
	if a == bpp:
		return 'Granddaughter'
	if ap == bp:
		return 'Sister'
	if app == bpp:
		return 'Cousin'
	if app == bp:
		return 'Aunt'
	if ap == bpp:
		return 'Niece'


def relations(family, pair):
	if pair in family:
		return 'Daughter'
	if pair[::-1] in family:
		return 'Mother'
	asc = {d: m for (m, d) in family}
	mother = asc.get
	if mother(mother(pair[0])) == pair[1]:
		return 'Grandmother'
	if mother(mother(pair[1])) == pair[0]:
		return 'Granddaughter'
	desc = {}
	for (m, d) in family:
		desc.setdefault(m, []).append(d)
	is_sister = lambda a, b: not all(({a, b} - set(gen) for gen in list(desc.values())))
	if is_sister(*pair):
		return 'Sister'
	if is_sister(mother(pair[0]), pair[1]):
		return 'Aunt'
	if is_sister(mother(pair[1]), pair[0]):
		return 'Niece'
	return 'Cousin'


def relations(f, p):

	def same(a, b):
		return a(p[0], f) == b(p[1], f)
	if same(ID, P):
		return 'Daughter'
	elif same(P, ID):
		return 'Mother'
	elif same(GP, ID):
		return 'Grandmother'
	elif same(ID, GP):
		return 'Granddaughter'
	elif same(P, P):
		return 'Sister'
	elif same(P, GP):
		return 'Niece'
	elif same(GP, P):
		return 'Aunt'
	elif same(GP, GP):
		return 'Cousin'

def ID(child, _):
	return child

def P(child, f):
	return next((p for (p, c) in f if c == child), None)

def GP(child, f):
	return P(P(child, f), f)


def relations(family_list, target_pair):

	def code(family_list, target_pair):
		(source, target) = target_pair
		for rel in family_list:
			for i in (0, 1):
				if rel[i] == source:
					if rel[1 - i] == target:
						return 'cp'[i]
					branch = code(family_list - set([rel]), (rel[1 - i], target))
					if branch:
						return 'cp'[i] + branch
	m = {'p': 'Mother', 'pp': 'Grandmother', 'c': 'Daughter', 'cc': 'Granddaughter', 'pc': 'Sister', 'pcc': 'Niece', 'ppc': 'Aunt', 'ppcc': 'Cousin'}
	return m[code(set(family_list), target_pair)]


def relations(family_list, target_pair):
	people = set()
	gen1 = []
	gen2 = []
	for i in family_list:
		people.add(i[0])
		people.add(i[1])
	for i in people:
		if all((j[1] != i for j in family_list)):
			gen1.append(i)
	for i in family_list:
		if i[0] in gen1:
			gen2.append(i[1])
	gen3 = [[] for i in range(len(gen2))]
	for i in family_list:
		if i[0] in gen2:
			gen3[gen2.index(i[0])].append(i[1])
	g3 = sum(gen3, [])
	(a, b) = target_pair
	if a in gen1 and b in gen2:
		return 'Daughter'
	if a in gen2 and b in gen1:
		return 'Mother'
	if a in gen1 and b in g3:
		return 'Granddaughter'
	if a in g3 and b in gen1:
		return 'Grandmother'
	if a in gen2 and b in gen2:
		return 'Sister'
	for i in gen3:
		if a in i and b in i:
			return 'Sister'
	if a in g3 and b in g3:
		return 'Cousin'
	if a in gen2 and b in gen3[gen2.index(a)]:
		return 'Daughter'
	if b in gen2 and a in gen3[gen2.index(b)]:
		return 'Mother'
	if a in gen2:
		return 'Niece'
	return 'Aunt'


def relations(family_list, target_pair):
	for i in family_list:
		if target_pair[0] == i[1]:
			for j in family_list:
				if target_pair[1] == j[1] and j[0] == i[0]:
					return 'Sister'
		if i == target_pair:
			return 'Daughter'
		elif i[0] == target_pair[1] and i[1] == target_pair[0]:
			return 'Mother'
		elif target_pair[0] == i[1]:
			for j in family_list:
				if i[0] == j[1] and target_pair[1] == j[0]:
					return 'Grandmother'
		elif target_pair[1] == i[1]:
			for j in family_list:
				if i[0] == j[1] and target_pair[0] == j[0]:
					return 'Granddaughter'
		if target_pair[0] == i[1]:
			Gmm = 1
			for j in family_list:
				if i[0] == j[1]:
					Gmm = j[0]
			for k in family_list:
				if target_pair[1] == k[1]:
					for m in family_list:
						if k[0] == m[1] and m[0] == Gmm:
							return 'Cousin'
		if target_pair[0] == i[1]:
			for j in family_list:
				if j[1] == i[0]:
					for k in family_list:
						if k[0] == j[0] and k[1] == target_pair[1] and (k != j):
							return 'Aunt'
		if target_pair[1] == i[1]:
			for j in family_list:
				if j[1] == i[0]:
					for k in family_list:
						if k[0] == j[0] and k[1] == target_pair[0] and (k != j):
							return 'Niece'
print(relations([('Enid', 'Susan'), ('Susan', 'Deborah'), ('Enid', 'Dianne'), ('Dianne', 'Judy'), ('Dianne', 'Fern')], ('Dianne', 'Deborah')))


def relations(family_list, target_pair):
	tree = {}
	for (parent, child) in family_list:
		tree[child] = parent
	a = tree.get(target_pair[0], 0)
	b = tree.get(target_pair[1], 0)
	if a == b:
		return 'Sister'
	elif a == target_pair[1]:
		return 'Mother'
	elif b == target_pair[0]:
		return 'Daughter'
	cnt_a = 0
	while a and a != target_pair[1]:
		cnt_a += 1
		a = tree.get(a, 0)
	cnt_b = 0
	while b and b != target_pair[0]:
		cnt_b += 1
		b = tree.get(b, 0)
	if a and (not b) and (cnt_a == 1):
		return 'Grandmother'
	elif not a and (not b) and (cnt_a == cnt_b):
		return 'Cousin'
	elif not a and (not b) and (cnt_a < cnt_b):
		return 'Niece'
	elif not a and (not b) and (cnt_a > cnt_b):
		return 'Aunt'
	elif not a and cnt_b == 1:
		return 'Granddaughter'
	else:
		return None


def relations(family_list, target_pair):
	daughters = set()
	mothers = {}
	for (mother, daughter) in family_list:
		if mother in daughters:
			daughters.remove(mother)
		daughters.add(daughter)
		mothers[daughter] = mother
	get_ancestors = lambda d: (get_ancestors(mothers[d]) if d in mothers else []) + [d]
	(p1, p2) = target_pair
	rs = {1: 'Mother', -1: 'Daughter', 2: 'Grandmother', -2: 'Granddaughter'}
	for daughter in daughters:
		ancestors = get_ancestors(daughter)
		if p1 in ancestors and p2 in ancestors:
			return rs[ancestors.index(p1) - ancestors.index(p2)]
	mother1 = mothers.get(p1, None)
	mother2 = mothers.get(p2, None)
	if mother1 and mother2 and (mother1 == mother2):
		return 'Sister'
	grandmother1 = mothers.get(mother1, None)
	grandmother2 = mothers.get(mother2, None)
	if grandmother1 == grandmother2:
		return 'Cousin'
	return 'Aunt' if grandmother1 == mother2 else 'Niece'


def relations(family_list, target_pair):
	for i in family_list:
		if target_pair[0] == i[1]:
			for j in family_list:
				if target_pair[1] == j[1] and j[0] == i[0]:
					return 'Sister'
		if i == target_pair:
			return 'Daughter'
		elif i[0] == target_pair[1] and i[1] == target_pair[0]:
			return 'Mother'
		elif target_pair[0] == i[1]:
			for j in family_list:
				if i[0] == j[1] and target_pair[1] == j[0]:
					return 'Grandmother'
		elif target_pair[1] == i[1]:
			for j in family_list:
				if i[0] == j[1] and target_pair[0] == j[0]:
					return 'Granddaughter'
		if target_pair[0] == i[1]:
			gmm = 1
			for j in family_list:
				if i[0] == j[1]:
					gmm = j[0]
			for k in family_list:
				if target_pair[1] == k[1]:
					for m in family_list:
						if k[0] == m[1] and m[0] == gmm:
							return 'Cousin'
		if target_pair[0] == i[1]:
			for j in family_list:
				if j[1] == i[0]:
					for k in family_list:
						if k[0] == j[0] and k != j and (target_pair[1] == k[1]):
							return 'Aunt'
		if target_pair[1] == i[1]:
			for j in family_list:
				if j[1] == i[0]:
					for k in family_list:
						if k[0] == j[0] and k != j and (target_pair[0] == k[1]):
							return 'Niece'


def relations(family, target):
	parents = {}
	for (parent, child) in family:
		parents[child] = parent
	(a, b) = target
	ap = parents.get(a)
	app = parents.get(ap)
	bp = parents.get(b)
	bpp = parents.get(bp)
	if b == ap:
		return 'Mother'
	elif b == app:
		return 'Grandmother'
	elif a == bp:
		return 'Daughter'
	elif a == bpp:
		return 'Granddaughter'
	elif ap == bp:
		return 'Sister'
	elif app == bpp:
		return 'Cousin'
	elif app == bp:
		return 'Aunt'
	elif ap == bpp:
		return 'Niece'