Blood relations and family trees

// A small family-tree solver for the lesson's five solved examples: it builds the tree from the statements, finds the
// shortest chain of parent, child and spouse links between two people, and names it. When a gender that the
// statements leave open would change the name, it builds one tree for each gender and compares the answers.

/** A family tree: people with a gender ('M', 'F' or unknown), parents, children and a spouse. */
function family() {
  const people = new Map();
  const person = (name, gender) => {
    if (!people.has(name)) people.set(name, { name, gender: null, parents: new Set(), children: new Set(), spouse: null });
    const p = people.get(name);
    if (gender) p.gender = gender;
    return p;
  };
  const link = (child, parent) => {
    person(child).parents.add(parent);
    person(parent).children.add(child);
    // A child's two parents are taken to be a married couple, as test items assume.
    const [a, b] = [...person(child).parents];
    if (b && !person(a).spouse && !person(b).spouse) {
      person(a).spouse = b;
      person(b).spouse = a;
    }
  };
  return {
    person,
    /**
     * `parent` is a parent of `child`; the parent's spouse is the child's other parent. If the child so far had only
     * an unnamed parent shared with a brother or sister, this is that parent, now named.
     */
    parentOf(parent, child, gender) {
      person(parent, gender);
      const unnamed = [...person(child).parents].find((q) => q.startsWith('the parent of '));
      if (unnamed) {
        for (const c of [...people.get(unnamed).children]) {
          person(c).parents.delete(unnamed);
          link(c, parent);
        }
        people.delete(unnamed);
      } else link(child, parent);
      const spouse = person(parent).spouse;
      if (spouse) for (const c of person(parent).children) link(c, spouse);
    },
    /** A married couple shares every child. */
    couple(husband, wife) {
      person(husband, 'M').spouse = wife;
      person(wife, 'F').spouse = husband;
      for (const c of [...person(husband).children, ...person(wife).children]) {
        link(c, husband);
        link(c, wife);
      }
    },
    /** Brothers and sisters share a parent; one is added, unnamed, if neither has a parent yet. */
    siblings(a, b, genderOfA) {
      person(a, genderOfA);
      person(b);
      const shared = [...person(a).parents, ...person(b).parents];
      const parent = shared[0] ?? `the parent of ${a} and ${b}`;
      link(a, parent);
      link(b, parent);
    },
    people,
  };
}

const TERMS = {
  'up': ['father', 'mother', 'parent'],
  'up up': ['grandfather', 'grandmother', 'grandparent'],
  'down': ['son', 'daughter', 'child'],
  'down down': ['grandson', 'granddaughter', 'grandchild'],
  'up down': ['brother', 'sister', 'brother or sister'],
  'up up down': ['uncle', 'aunt', 'uncle or aunt'],
  'up down down': ['nephew', 'niece', 'nephew or niece'],
  'up up down down': ['cousin', 'cousin', 'cousin'],
  'spouse': ['husband', 'wife', 'spouse'],
  'spouse up': ['father-in-law', 'mother-in-law', 'parent-in-law'],
  'down spouse': ['son-in-law', 'daughter-in-law', 'child-in-law'],
  'up down spouse': ['brother-in-law', 'sister-in-law', 'brother-in-law or sister-in-law'],
  'spouse up down': ['brother-in-law', 'sister-in-law', 'brother-in-law or sister-in-law'],
  'up up down spouse': ['uncle', 'aunt', 'uncle or aunt'],
  'spouse up down down': ['nephew', 'niece', 'nephew or niece'],
};

/** "x is y's ___": the shortest chain of links from y to x (breadth-first), named from the table and x's gender. */
function relation(tree, x, y) {
  const seen = new Map([[y, []]]);
  const queue = [y];
  while (queue.length) {
    const at = queue.shift();
    const p = tree.people.get(at);
    const next = [...[...p.parents].map((q) => [q, 'up']), ...[...p.children].map((q) => [q, 'down']), ...(p.spouse ? [[p.spouse, 'spouse']] : [])];
    for (const [q, step] of next) {
      if (seen.has(q)) continue;
      seen.set(q, [...seen.get(at), step]);
      queue.push(q);
    }
  }
  const path = (seen.get(x) ?? []).join(' ');
  const names = TERMS[path];
  if (!names) return `no single term (${path || 'the same person'})`;
  const g = tree.people.get(x).gender;
  return g === 'M' ? names[0] : g === 'F' ? names[1] : names[2];
}

// 1. Pointing to a girl, Varun says: "She is the daughter of my father's only son." Varun is a son of his father,
// and the only one, so "my father's only son" is Varun himself.
const t1 = family();
t1.parentOf("Varun's father", 'Varun', 'M');
t1.person('Varun', 'M');
t1.parentOf('Varun', 'the girl', 'M');
t1.person('the girl', 'F');
console.log(`1. The girl is Varun's ${relation(t1, 'the girl', 'Varun')}`);

// 2. Codes: A @ B means A is B's mother, A # B means A is B's brother. P # Q @ R: P is Q's brother, Q is R's mother.
const t2 = family();
t2.siblings('P', 'Q', 'M');
t2.parentOf('Q', 'R', 'F');
console.log(`2. P # Q @ R: P is R's ${relation(t2, 'P', 'R')}, and R is P's ${relation(t2, 'R', 'P')}`);

// 3. "Neha's mother is the only daughter of Sam's father." Sam's gender is not given, so build both trees.
const answers = [];
for (const g of ['M', 'F']) {
  const t3 = family();
  t3.parentOf("Sam's father", 'Sam', 'M');
  t3.person('Sam', g);
  // If Sam is a woman, she is a daughter of her father, so she is the only daughter; otherwise the daughter is
  // someone else, Sam's sister.
  const daughter = g === 'F' ? 'Sam' : "Sam's sister";
  if (g === 'M') t3.parentOf("Sam's father", daughter, 'M');
  t3.person(daughter, 'F');
  t3.parentOf(daughter, 'Neha', 'F');
  answers.push(`if Sam is ${g === 'M' ? 'a man' : 'a woman'}, Sam is Neha's ${relation(t3, 'Sam', 'Neha')}`);
}
console.log(`3. ${answers.join('; ')}: cannot be determined`);

// 4. Kiran's father is the brother of Meera's mother.
const t4 = family();
t4.parentOf("Kiran's father", 'Kiran', 'M');
t4.parentOf("Meera's mother", 'Meera', 'F');
t4.siblings("Kiran's father", "Meera's mother", 'M');
console.log(`4. Kiran is Meera's ${relation(t4, 'Kiran', 'Meera')}`);

// 5. Rina is the sister of Asha's husband, and Tushar is Rina's son.
const t5 = family();
t5.couple("Asha's husband", 'Asha');
t5.siblings('Rina', "Asha's husband", 'F');
t5.parentOf('Rina', 'Tushar', 'F');
t5.person('Tushar', 'M');
console.log(`5. Tushar is Asha's ${relation(t5, 'Tushar', 'Asha')}, and Asha is Tushar's ${relation(t5, 'Asha', 'Tushar')}`);

1. The girl is Varun's daughter
2. P # Q @ R: P is R's uncle, and R is P's nephew or niece
3. if Sam is a man, Sam is Neha's uncle; if Sam is a woman, Sam is Neha's mother: cannot be determined
4. Kiran is Meera's cousin
5. Tushar is Asha's nephew, and Asha is Tushar's aunt