diamondDependency.js

import fs from "fs";

const input = JSON.parse(fs.readFileSync("test.in.json"));

function hasDiamondDependency(testCase) {
  const graph = {};

  for (const lib of testCase) {
    graph[lib.libraryName] = lib.libraryDependencies || [];
  }

  const libraries = Object.keys(graph);

  for (let i = 0; i < libraries.length; i++) {
    for (let j = 0; j < libraries.length; j++) {
      if (i !== j) {
        const paths = findAllPaths(graph, libraries[i], libraries[j]);
        if (paths.length >= 2) {
          return true;
        }
      }
    }
  }

  return false;
}

function findAllPaths(
  graph,
  start,
  end,
  visited = new Set(),
  currentPath = [],
) {
  if (visited.has(start)) {
    return [];
  }

  visited.add(start);
  currentPath.push(start);

  if (start === end) {
    const result = [[...currentPath]];
    visited.delete(start);
    currentPath.pop();
    return result;
  }

  const allPaths = [];
  const dependencies = graph[start] || [];

  for (const dep of dependencies) {
    const paths = findAllPaths(graph, dep, end, visited, currentPath);
    allPaths.push(...paths);
  }

  visited.delete(start);
  currentPath.pop();

  return allPaths;
}

function main() {
  const results = [];

  for (let i = 0; i < input.testCases.length; i++) {
    const testCase = input.testCases[i].dependencyLists;
    const hasDiamond = hasDiamondDependency(testCase);
    results.push(hasDiamond);
    console.log(
      `Test case ${i + 1}: ${hasDiamond ? "Diamond dependency found" : "No diamond dependency"}`,
    );
  }

  return results;
}

main();