CODEWITHSUNDEEP
javascripttreereduce
testing_22
testing_22

Reputation: 2585

Reducing a tree of paths to all combinations of paths using reduce function

I'm trying to implement a function using JavaScript's reduce method to process a tree-like string indented by tabs. Consider that the input is always correctly tab-indented. I know it can be done using backtrack, but I was wondering if that was possible with reduce. My code is shown below, but I can't reach the desired output. Can anyone help me understand what I'm doing wrong and how I can fix this problem?

Given the input:

/wp-content/
    /uploads
    /plugins/
        /akismet/
    /themes/
        /twentyeleven/
            /colors/

I expect the output to be a list of combinations of paths, one per line, including intermediate paths (e.g. /wp-content/ and /wp-content/plugins):

/wp-content/
/wp-content/uploads
/wp-content/plugins/
/wp-content/plugins/akismet/
/wp-content/themes/
/wp-content/themes/twentyeleven/
/wp-content/themes/twentyeleven/colors

However, my code is not working as expected as I'm getting repeated output instead:

/wp-admin/wp-content/plugins/akismet/themes/twentyeleven/colors 
/wp-admin/wp-content/plugins/akismet/themes/twentyeleven/images 
/wp-admin/wp-content/uploads 
/wp-admin/wp-content/plugins/akismet/themes/twentyeleven/colors 
/wp-admin/wp-content/plugins/akismet/themes/twentyeleven/images 
/wp-admin/wp-content/uploads

Here's what I've tried

rm = (s, ch='\t') => s?.replaceAll(ch,'')
count = (s, ch='\t') => s?.match(new RegExp(ch,'g'))?.length
wrapper = (arr, fun, start) => arr.reduce(fun, start)

function fn(acc, curr, i, self){
  x = count(curr) 
    y = count(self[i+1])
  curr = rm(curr)
  acc = rm(acc)
  selfi = rm(self[i+1]) 
  if(!selfi) return acc
  
  if(curr.at(-1) === '/' && acc.at(0) === '/') {
     curr = curr.slice(0,-1)
  } // ends and start with /
    if(x===y){
            console.log(acc+curr)
      return acc
    } else { 
      idx = self.indexOf(self.slice(0,i+1).filter(k => count(k) === x)[0]) 
      if(!idx) idx = -1
      wrapper(self.slice(i,idx), fn, acc) 
      return acc+curr
  }
}

wrapper(ar, fn, '/wp-admin')

Upvotes: 0

Views: 95

Answers (2)

trincot
trincot

Reputation: 350760

As indicated by others, this is typically solved with a stack.

But for one input line, the stack may need to get rid of more than one item, while it should always get a new entry.

I have added a few more lines to your example input to illustrate this:

function paths(input, prefix = "") {
    const stack = [{length: -1, name: prefix}];
    return Array.from(input.matchAll(/^(.*?)(\S.+?)(\/?)\s*$/gm), 
        ([, {length}, name, tail]) => {
            while (stack.at(-1).length >= length) stack.pop();
            stack.push({ length, name });
            return stack.map(({ name }) => name).join("") + tail;
        }
    );
}

console.log(paths(`\
/wp-content/
    /uploads
    /plugins/
        /akismet/
    /themes/
        /twentyeleven/
            /colors/
    /images/
        /thumbnails/
/other-content/`, "/wp-admin"));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 2

back2basics
back2basics

Reputation: 11

Using a stack makes this incredibly easy. Notice that for each line, we have the following cases:

  • indentation is greater than the last line
  • indentation is less than the last line
  • indentation is the same as the last line

We can decide what to do with the stack and current line based on these 3 cases. If the indentation is greater, then that means we've gone down a folder, and so we should push the current line onto the stack. If the indentation is smaller, then we've gone up a folder. If the indentation is the same, we are still in the same parent directory, so we do not modify the stack.

There is only one edge case, where the stack is empty. In that case, all you need to do is add the current line (since it is the root folder).

After this, to get the path of the current line, you just join the stack together. Pretty nice, right?

Here's my implementation of the above:

function paths(input, prefix = "/") {
    const lines = input.split("\n");
    
    const stack = [];
    const paths = [];
    
    lines.forEach((line) => {
        // matching the indentation and name separately
        const [, indentation, name] = line.match(/^(\s*)(.+)$/);
        const parent = stack.at(-1);

        if (parent) {
            // if this has more indentation, then add to the stack
            if (parent.indentation.length < indentation.length) stack.push({ indentation, name });
        
            // if it has less indentation, remove from the stack
            if (parent.indentation.length > indentation.length) stack.pop();
        // no parent, add this since it's the root
        } else stack.push({ indentation, name });

        // join the stack together (replacing "//" with "/")
        paths.push([prefix, ...stack.map(({ name }) => name)].join("").replaceAll("//", "/"));
    });
    
    return paths;
}

console.log(paths(`\
/wp-content/
    /uploads
    /plugins/
        /akismet/
    /themes/
        /twentyeleven/
            /colors/`, "/wp-admin"));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 1

Related Questions