Get object list of Ancestors and object list of Descendants from a list

Question

I have a JSON object with keys and the value is an ordered list of their ancestors, I would like to find a way to generate a list of ancestors and list of descendants

Input:

{
"Category 1111": ["Category 1", "Category 11", "Category 111"]
}

The output should look like

listAncestors: {
   "Category 1": [],
   "Category 11": ["Category 1"],
   "Category 111": ["Category 1", "Category 11"],
   "Category 1111": ["Category 1", "Category 11", "Category 111"]
}

listDescendants: {
   "Category 1": ["Category 11", "Category 111", "Category 1111"],
   "Category 11": ["Category 111", "Category 1111"],
   "Category 111": ["Category 1111"],
   "Category 1111": []
}

Does anyone know a similar known algorithm that I can follow or a suggested solutions

EDIT: My solution is:

const getList = () => {
  const newList = Object.keys(input).map((k) => [...input[k], k]);
  const listAns = {};
  const listDes = {};
  newList[0].forEach((k, idx) => {
    listAns[k] = newList.slice(0, idx);
    listDes[k] = newList.slice(idx + 1, newList.length);
  });
};

Thank you

Answer 1

Thank you for the edit. That helps a lot. Next time, also please explain what went wrong with your code.

I think you're on the right track. Certainly the creation of newList from the existing format is a step in the right direction. My implementation does the same thing, with slightly different code.

As to the body, you seem to be missing a level. The input structure seems to allow for multiple people with a chain of their antecedents. But you only work with one. You also have a function with no outputs -- usually a warning sign - and no inputs -- even more of one. So here is one pass of how I wrote a version of this:

const family = (youths) => {
  const chains = Object .entries (youths) .map (([k, v]) => [...v, k])

  return {
    listAncestors: Object .fromEntries (chains .flatMap (
      chain => chain .map ((c, i, a) => [c, a .slice (0, i)])
    )),
    listDescendants: Object .fromEntries (chains .flatMap (
      chain => chain .map ((c, i, a) => [c, a .slice (i + 1)])
    ))
  }
}

console .log (family ({
  "Category 1111": ["Category 1", "Category 11", "Category 111"],
  "Category abc": ["Category a", "Category b"]
}))

.as-console-wrapper {max-height: 100% !important; top: 0}

my chains is equivalent to your newList. I couldn't find a great name that suggested something like a vertical slice of a family tree. But it still feels a little more meaningful than newList. The implementation of chains is similar to yours, but Object .entries seems cleaner than Object .keys + input[k]

After that, to get ancestors, we take each chain and map over the entries, creating a two-element array, taking each person as the first entry and the list of all those before it in the chain as its ancestors. Then we use Object.fromEntries to turn this into a single object. And we do something similar for the descendants, except that we list all the ones after the person as its descendants.

This code is fine, and we could easily leave it at that. But there's some real duplication between listAncestors and listDescendants. It might be nice to factor that out. With repetition, two is the hardest number to decide. Once I hit three copies of very similar code, I always look to refactor. With two, I might leave it or I might choose to abstract it. I don't have any hard-and-fast rule. But let's look at how that might go.

This version abstracts the commonalities into a helper function:

const group = (chains, fn) => Object .fromEntries (chains .flatMap (
  chain => chain .map ((c, i, a) => [c, fn (a, i)])
))

const family = (youths) => {
  const chains = Object .entries (youths) .map (([k, v]) => [...v, k])
  
  return {
    listAncestors: group (chains, (a, i) => a .slice (0, i)),
    listDescendants: group (chains, (a, i) => a .slice (i + 1))
  }
}

We add the helper function group and use it to simplify the implementations of listAncestors and listDescendants. This doesn't really change line-count or anything like that, but the two functions are each simpler than above.

A personal preference of mine is to avoid local variables as much as I can, working without assignment (except for important functions) or in fact with no statements at all, only expressions. The reasons for this preference are important to me, but not worth spending time on here. But I might further refactor this so that chains is a defaulted parameter like this:

const family = (youths, chains = Object .entries (youths) .map (([k, v]) => [...v, k])) => ({
  listAncestors: group (chains, (a, i) => a .slice (0, i)),
  listDescendants: group (chains, (a, i) => a .slice (i + 1))
})

or, using the simple helper, const call = (fn, ...args) => fn (...args), I might write it like this:

const family = (youths) => call (
  (chains = Object .entries (youths) .map (([k, v]) => [...v, k])) => ({
    listAncestors: group (chains, (a, i) => a .slice (0, i)),
    listDescendants: group (chains, (a, i) => a .slice (i + 1))
  }))

The latter is safer than the defaulted parameter, which can fail in some circumstances, but I will use them interchangeably if I'm in control of how my function is called.