Uber interview question: cardinal constraints

cardinalConstraints.js

// Problem description: https://interviewcache.com/blog/direction-validation/

function areCardinalConstraintsValid(rules) {
  console.log(rules);
  console.log(_areCardinalConstraintsValid(rules));
  console.log();
}

function _areCardinalConstraintsValid(rules) {
  // We choose N-S and E-W instead of S-N and W-E because of the English idioms "north to south" and "east to west",
  // so they are more natural to say.
  let ns = {};
  let ew = {};
  rules.forEach(rule => {
    const [a, dir, b] = rule.split(/\s+/);

    {
      let v, w;
      if (/^N/i.test(dir)) {
        [v, w] = [a, b]; // Nodes with higher latitudes point to nodes with lower latitudes
      } else if (/^S/i.test(dir)) {
        [v, w] = [b, a];
      }
      if (v !== undefined) {
        ns[v] = ns[v] || {adj: []};
        ns[v].adj.push(w);
      }
    }

    {
      let v, w;
      if (/E$/i.test(dir)) {
        [v, w] = [a, b]; // Nodes with greater longitudes point to nodes with lesser longitudes
      } else if (/W$/i.test(dir)) {
        [v, w] = [b, a];
      }
      if (v !== undefined) {
        ew[v] = ew[v] || { adj: [] };
        ew[v].adj.push(w);
      }
    }
  });

  // Note: mutates input graph so can only be run once
  function isAcyclic(g, v = null) {
    if (!v) {
      return Object.keys(g).every(k => isAcyclic(g, k));
    }

    if (!g || !g[v]) {
      return true;
    }
    let n = g[v];

    // If given node is already in the path, then we have a cycle
    if (n.inPath) {
      return false;
    }

    // Don't re-search the same sub-graph
    if (n.visited) {
      return true;
    }
    n.visited = true;

    try {
      n.inPath = true;
      return n.adj.every(w => isAcyclic(g, w));
    } finally {
      n.inPath = false;
    }
  }

  return isAcyclic(ns) && isAcyclic(ew);
}

/*
 * Tests
 */

let rules;

rules = [
  'A NW B',
  'A N B',
];
areCardinalConstraintsValid(rules);

rules = [
  'A N B',
  'B NE C',
  'C N A',
];
areCardinalConstraintsValid(rules);