Multidimensional Objects - Help with Searching through them and saving the path

Hey Campers -

Got an interesting challenge going on and am stuck trying to figure out how to save a path to a value in a multidimensional object.

Here is the object:

let newYorkCity = {
    'Manhattan': {
        'Uptown': {
            'Washington Heights': 'Daniel',
            'UWS': 'Cathy'
        },
        'Midtown': {
            'Madison Square': 'Susan',
            'Theater District': ['Robert', 'Latisha']
        },
        'Downtown': {
            'Tribeca': 'Billy',
            'Financial District': {
                'Fullstack': {
                    '11th floor': ['David', 'Nimit'],
                    '25th floor': 'Ashi'
                }
            }
        }
    },
    'Brooklyn': {
        'Bushwick': 'Marilyn',
        'Bed-Stuy': ['Juan', 'Denice']
    },
    'Queens': {
        'Astoria': 'Ella',
        'Flushing': 'Eric'
    },
    'Bronx': {
        'Fordham': 'Aaron',
        'Melrose': 'Krysten'
    },
    'Staten Island': {
        'Arlington': ['Nadine', 'Mose'],
        'Elm Park': 'Arthur'
    }
};

Now, Iā€™ve written code already that searches through the objects and finds a specific person, but Iā€™m having trouble figuring out how to save the specific path to the person. For example: when I search for ā€˜Nimitā€™, I want to return the path: [ā€˜Manhattanā€™, ā€˜Downtownā€™, ā€˜Financial Districtā€™, ā€˜Fullstackā€™, ā€˜11th floorā€™]

Currently, I am pushing the path to an array as I do the search but Iā€™m ending up with an array like this:

[ 'Manhattan',
  'Uptown',
  'Midtown',
  'Theater District',
  'Downtown',
  'Financial District',
  'Fullstack',
  '11th floor' ]

As you can see, the array is saving extra paths it searches down that I donā€™t need. It saves Uptown, Midtown, etc., which are paths the program searches but are not needed for the final array.

Iā€™m having a lot of difficulty trying to figure out a way to ā€œfilterā€ or ā€œsortā€ this properly. Iā€™ve been trying to figure out a way to push one item onto the array at a time and then delete that item, but it ends up with only the first and last item, since thereā€™s no way I know of to setup a conditional that saves one item from each branch.

This code is also dynamic so I canā€™t simply hard-code this line in, the object isnā€™t always going to be New York City and the keys names in the object are going to change. Iā€™m using recursion on this, which works well, however without being able to setup a proper conditional statement to ā€œsaveā€ only the keys I want - Iā€™m getting stuck.

Any suggestions or if anyone has any code that can do what Iā€™m asking, that would be appreciated. This is not an FCC challenge, so you can post answers here.

Thanks.

This is where recursion is the easiest solution (with some caveats because of the shape of the data). You donā€™t really want to sort or filter.

So naĆÆvely, you have a function, say find that takes the needle (what youā€™re looking for), the haystack (the object) and a stack, which starts as an empty array.

You loop over the keys/values - you can use Object.entries for this, which gives you an array of key/value pairs, so like

for (let [key, value] of Object.entries(haystack)) {

You push the key into the stack.

If the value is the needle, then the current stack is your path. If it isnā€™t (ie itā€™s an object), call find again, recursively, but with the haystack now set to the current value.

If you reach the end of the current branch and you canā€™t find the value, pop the stack.

The loop goes onto the next branch and so on.


The caveat is that the loop wonā€™t just stop if you use return, it wonā€™t return a value, because you are in a recursive set of function calls, loops within loops. If you console.log the stack on the ā€œfoundā€ bit of the function, youā€™ll be able to see the path is correctly found, but the whole function will run to completion, visiting every branch and eventually returning undefined.

This is a possible solution; personally, Iā€™d say try to get something like what Iā€™ve described working first before peeking, but hey ho

function findPathToValue(needle, haystack) {
  // Set up the stack, this will be populated
  // with the path (if found):
  let stack = []
  // Sentinal value used to ensure all loops are
  // broken out of if necessary:
  let found = false;
  
  // Recursive function used to walk the object:
  function loop(haystack, stack) {
    // Start looping through the current level of the tree:
    for (const [location, v] of Object.entries(haystack)) {
      stack.push(location);
      if (v === needle || (Array.isArray(v) && v.includes(needle))) {
        // If found, the current stack is the path. Just breaking
        // here will not work, as we are likely to be a few levels
        // deep into nested loops:
        found = true;
        break;
      } else if (!Array.isArray(v) && typeof v === 'object') {
        // If there is another level of nesting, walk that branch...
        loop(v, stack);
        // ...but make sure to break if correct path has been found:
        if (found) break;
      }
      // Otherwise, just pop the stack (discard the last path) and
      // continue onwards.
      stack.pop()
    }
  }
  // Running the loop directly modifies the `stack` variable
  // declared at the top of the function...
  loop(haystack, stack);
  // So return that at the end. Note it will just return an
  // empty array if the person isn't found, so may want
  // some logic to handle that eventuality.
  return stack;
}
1 Like

Thanks Dan - you described that very well.

I think I can write this without looking. Iā€™ll find out soon!

Thanks @DanCouper

I finally figured this out. I did end up having to peak at yours. The main issue I was having was that I didnā€™t write an inner function. I was simply calling the main function, but writing a closure inner function made a big difference.

It allowed me to use the flag variables without having to make them global also.

Thanks for the insight!