Jungle Book Problem

JungleBook.test.ts

import { JungleBook, Node } from "../src/JungleBook";

describe("Test", function () {
  let jungle: JungleBook;

  beforeEach(() => {
    jungle = new JungleBook();
  });

  it("add an apex predator", function () {
    const node = new Node(0);
    jungle.add(0, -1);
    expect(jungle.root.child[0].data).toEqual(node.data);
  });

  it("an orphan predator is implicitly an apex predator", function () {
    // Arrange
    jungle.add(1, 8);

    // Act
    const predator = jungle.root.child[0];
    const prey = predator.child[0];

    // Assert
    expect(predator.data).toEqual(8);
    expect(predator.parent?.isRoot()).toBe(true);

    expect(prey.data).toEqual(1);
    expect(prey.parent).toEqual(predator);
  });

  it("add an orphan predator then explicitly set it to be an apex predator", function () {
    // Arrange
    jungle.add(1, 8);
    jungle.add(8, -1);

    // Act
    const predator = jungle.root.child[0];
    const prey = predator.child[0];

    // Assert
    expect(predator.data).toEqual(8);
    expect(predator.parent?.isRoot()).toBe(true);

    expect(prey.data).toEqual(1);
    expect(prey.parent).toEqual(predator);
  });

  it("add multiple apex predators", function () {
    // Arrange
    const population = [-1, 8, 6, 0, 7, 3, 8, 9, -1, 6, 1];

    // Act
    jungle.setDebug(false);
    population.forEach((predatorIndex, speciesIndex) => {
      jungle.add(speciesIndex, predatorIndex);
    });

    // Assert
    expect(jungle.root.child.length).toEqual(2);
    expect(jungle.root.child[0].data).toEqual(0);
    expect(jungle.root.child[0].child[0].data).toEqual(3);
    expect(jungle.root.child[0].child[0].child[0].data).toEqual(5);
  });

  it("calculate minimum number of groups forms", function () {
    // Arrange
    const population = [-1, 8, 6, 0, 7, 3, 8, 9, -1, 6, 1];

    // Act
    jungle.setDebug(false);
    population.forEach((predatorIndex, speciesIndex) => {
      jungle.add(speciesIndex, predatorIndex);
    });
    const groups = jungle.groups();
    console.log({groups});

    // Assert
    expect(groups.length).toEqual(5);
  });
});

JungleBook.ts

type Nullable<T> = T | null; 

interface NodeInterface<T> {
  parent: Nullable<NodeInterface<T>>
  child: NodeInterface<T>[];
  data: T;
}

export class Console {
  debug = false;

  setDebug(enabled: boolean) {
    this.debug = enabled;
  }

  getConsole() {
    if (this.debug) {
      return console;
    }

    return {
      log: () => {},
      group: () => {},
      groupEnd: () => {},
    };
  }
}

export class Node<T> extends Console implements NodeInterface<T> {
  public parent: Nullable<Node<T>>;
  public child: Node<T>[] = [];
  public data: T;

  constructor(data: T, parent: Nullable<Node<T>> = null) {
    super();
    this.data = data;
    this.parent = parent;
  }

  add(node: Node<T>) {
    node.parent = this;
    this.child.push(node);
    return this;
  }

  remove(node: Node<T>) {
    node.parent = null;
    const childNodeIndex = this.child.findIndex((childNode) => childNode === node);
    this.child.splice(childNodeIndex, 1);
    return this;
  }

  find(data: T): Node<T> | undefined {
    const group = `Find ${data} in ${this.data}`;
    const context = this;
    this.getConsole().group(group, { context });

    let node: Node<T> | undefined;

    if (this.data === data) {
      node = this;
    } else {
      const candidates = this.child
        .map(node => node.find(data))
        .filter(candidate => candidate != undefined);

      if (candidates.length === 1) {
        node = candidates[0];
      }
    }

    this.getConsole().log(`Find result:`, { node, context });
    this.getConsole().groupEnd();

    return node;
  }

  isRoot() {
    return this.parent === null;
  }
}

export class JungleBook extends Console {
  root = new Node(-1);

  constructor() {
    super();
  }

  add(speciesId: number, predatorId: number) {
    this.root.setDebug(this.debug);

    const group = `Adding species ${speciesId} and its predator ${predatorId}`;
    this.getConsole().group(group);

    let parent = this.root.find(predatorId) || null;
    this.getConsole().log(`Parent ${parent ? 'found' : 'not found'}`, {parent});


    if (parent === null) {
      parent = new Node(predatorId);
      parent.setDebug(this.debug);
      this.root.add(parent);
    }

    let child = this.root.find(speciesId) || null;

    if (child === null) {
      child = new Node(speciesId);
      child.setDebug(this.debug);
      parent.add(child);
    } else if (child.parent && child.parent !== parent) {
      child.parent.remove(child);
      child.parent = null;
      parent.add(child);
    }

    this.getConsole().groupEnd();
    return this;
  }

  groups() {
    const result = [];

    let children = this.root.child;

    while (children.length != 0) {
      result.push(children.map(node => node.data));
      children = children.flatMap(node => node.child);
    }

    return result;
  }
}