Secret Santa

import { test, describe, expect } from "bun:test";

const graph = {
  alice: ["D", "C", "E"],
  bob: ["E", "D", "C"],
  C: ["E", "alice", "D", "bob"],
  E: ["D", "C", "alice", "bob"],
  D: ["bob", "E", "C"],
};

function backtrack(graph, current, visited, currentPath, startNode) {
  if (visited.size === Object.keys(graph).length) {
    console.log(Array.from(visited).join(" -> "));
  }

  if (
    visited.size === Object.keys(graph).length &&
    graph[current].includes(startNode)
  ) {
    currentPath.push(Array.from(visited));
    return true; 
  }


  const neighbors = graph[current];
  const unvisitedNeighbors = neighbors.filter(
    (neighbor) => !visited.has(neighbor),
  );

  while (unvisitedNeighbors.length > 0) {
 
    const randomIndex = Math.floor(Math.random() * unvisitedNeighbors.length);
    const randomNeighbor = unvisitedNeighbors[randomIndex];


    visited.add(randomNeighbor);


    if (backtrack(graph, randomNeighbor, visited, currentPath, startNode)) {
      return true;
    }

   
    visited.delete(randomNeighbor);


    unvisitedNeighbors.splice(randomIndex, 1);
  }

  return false; 
}

// Example usage:
const startNode = "alice";
const visited = new Set([startNode]);
const currentPath = [];
backtrack(graph, startNode, visited, currentPath, startNode);

console.log(
  `
        const graph = {
          alice: ["D", "C", "E"],
          bob: ["E", "D", "C"],
          C: ["E", "alice", "D", "bob"],
          E: ["D", "C", "alice", "bob"],
          D: ["bob", "E", "C", ],
        };
    `,
);
console.log(currentPath);

describe("backtrack function with various starting points", () => {
  const graph = {
    alice: ["D", "C", "E"],
    bob: ["E", "D", "C"],
    C: ["E", "alice", "D", "bob"],
    E: ["D", "C", "alice", "bob"],
    D: ["bob", "E", "C", "alice"],
  };

  test.skip('it finds a valid path starting from "alice"', () => {
    const startNode = "alice";
    const visitedNodes = new Set();
    visitedNodes.add(startNode);
    const resultPaths = [];

    const result = backtrack(
      graph,
      startNode,
      visitedNodes,
      resultPaths,
      startNode,
    );

    expect(result).toBe(true);
    expect(resultPaths.length).toBeGreaterThan(0);

    resultPaths.forEach((path) => {
      expect(path[0]).toBe(startNode); // Path starts with the specified start node
      const lastNode = path[path.length - 1];
      expect(graph[lastNode]).toContain(startNode); // Last node is a neighbor of the start node
      // Add more assertions if needed based on your requirements
    });
  });

  test.skip('it finds a valid path starting from "bob"', () => {
    const startNode = "bob";
    const visitedNodes = new Set();
    visitedNodes.add(startNode);
    const resultPaths = [];

    const result = backtrack(
      graph,
      startNode,
      visitedNodes,
      resultPaths,
      startNode,
    );

    expect(result).toBe(true);
    expect(resultPaths.length).toBeGreaterThan(0);

    resultPaths.forEach((path) => {
      expect(path[0]).toBe(startNode); // Path starts with the specified start node
      const lastNode = path[path.length - 1];
      expect(graph[lastNode]).toContain(startNode); // Last node is a neighbor of the start node
      // Add more assertions if needed based on your requirements
    });
  });

  test.skip('it finds a valid path starting from "C"', () => {
    const startNode = "C";
    const visitedNodes = new Set();
    visitedNodes.add(startNode);
    const resultPaths = [];

    const result = backtrack(
      graph,
      startNode,
      visitedNodes,
      resultPaths,
      startNode,
    );

    expect(result).toBe(true);
    expect(resultPaths.length).toBeGreaterThan(0);

    resultPaths.forEach((path) => {
      expect(path[0]).toBe(startNode); // Path starts with the specified start node
      const lastNode = path[path.length - 1];
      expect(graph[lastNode]).toContain(startNode); // Last node is a neighbor of the start node
      // Add more assertions if needed based on your requirements
    });
  });

  // Add more tests as needed
});