Resolve Path recursively-CodePudding

I am trying to solve the problem which goes like this -

Given a map of key-value mapping

["Intro",  "Hello My Name is %S% and I am x %Y old"]
["S", "Tom %N"]
["N", "Johnson"]
["Y", "Year"]

Now resolve a String Give Your %Intro %S

I am struggling to know what would be the best and optimized way to solve this. I can think of simple recursion but I don't know if that is the best way. I am also struggling to understand time complexity of a problem. Please note this can go to any depth.

What I did

 String resolve(String s, HashMap<String, String> m) {
        String[] st = s.split(" ");
        for(String word : st) {
            if(m.get(word) != null) {
                word = m.get(word);
            }
            if(word.contains("%")) {
                String p = resolve(parse(word), m);
                m.put(word, p);
            }
        }

        StringBuilder b = new StringBuilder();
        for(String word : st) {
            if(st.contains("%")) {
                b.append(m.get(word)   " ");
            } else {
                b.append(word   " ");
            }
        }
        return b.toString();
    }

CodePudding user response：

If you have a lot of expressions and dependencies and you must to update and get values frequently you need a dependency graph

(For simplicity a variable is declared as "My %var% is ..." not "My %var is ...")

Let the next Var class containing a variable (your [name, expr])

@Getter
@Setter
@AllArgsConstructor
static class Var {
    String name;
    String[] parts; // Const1,  Var1, Const2,   Var2, ...
                    // Hello... `S`   and I am  `Y`   old ...
    String computed;

    Stream<String> getUsedVarNames() {
        // we are interested only in Var# not Const# then
        // we traverse the odd indexes
        return IntStream
           // for i=1,2,3,...,N/2-1
           .range(1, parts.length / 2)
           // get the var `2*i-1` that is 1,3,5,...
           .mapToObj(i -> parts[2 * i - 1]);
    }

    void updateValue(Map<String, Var> vars) {
        System.out.println("          Computing: "   name);
        // update the value is concat all
        //    Const1   Var1   Const2   Var2, ...
        // then
        computed = IntStream
                // for i=0,1,2,...,N-1
                .range(0, parts.length)
                // if is even (i%2==0) take the Const-i
                // if is odd           take the Var-i value
                .mapToObj(i -> i % 2 == 0 ? parts[i] : vars.get(parts[i]).getComputed())
                // and concatenate all
                .collect(joining());
    }
}

where

name is the var name S, N, ...
parts are the constants "Hello My..." in positions 0, 2, 4, ... and variable names "S" in positions 1, 3, 5, ... (for simplicity)
computed is the last computed value
getUsedVarNames get the used var names (1, 3, 5, ... positions)
updateValue recompute the computed value given a map of vars.

then, a basic dependency graph management is basically

static class Graph {
    Map<String, Var> vars = new HashMap<>();
    Map<String, Set<String>> deps = new HashMap<>();

    String value(String name) {
        return vars.get(name).getComputed();
    }

    String add(String name, String expr) {
        remove(name);

        Var current = new Var(name, expr.split("%"), null);

        // add current dependencies
        current.getUsedVarNames().forEach(dep -> deps.get(dep).add(name));

        // add var
        vars.put(name, current);
        if(!deps.containsKey(name))
            deps.put(name, new HashSet<>());

        // compute
        updateDeps(name);

        return current.getComputed();
    }

    private void updateDeps(String name) {
        vars.get(name).updateValue(vars);
        deps.get(name).forEach(this::updateDeps);
    }

    void remove(String name) {
        if (vars.containsKey(name)) {
            vars.get(name).getUsedVarNames().forEach(dep -> deps.get(dep).remove(name));
            vars.remove(name);
        }
    }
}

where

vars the varName => the var.
deps map parentVars => where are used.
value simply get the computed value for a var name.
add remove the var if exists and set dependencies.
updateDeps walk the deps graph updating dependencies.
remove remove var and dependencies.

then, as an example you can write

Graph g = new Graph();

System.out.println(g.add("Y", "Year"));
System.out.println(g.add("N", "Johnson"));
System.out.println(g.add("S", "Tom %N%"));
System.out.println(g.add("Intro", "Hello My Name is %S% and I am x %Y% old"));

// if you change `S` only two expression are recomputed (the updated `S` and their dependencies)
System.out.println(g.add("S", "Peter %N%"));

System.out.println(g.value("Intro"));

with output

          Computing: Y
Year
          Computing: N
Johnson
          Computing: S
Tom Johnson
          Computing: Intro
Hello My Name is Tom Johnson and I am x Year old
          Computing: S
          Computing: Intro
Peter Johnson
Hello My Name is Peter Johnson and I am x Year old

where only required expressions will be recomputed.

This is a very basic Dependency Graph management (i.e. if a var not exists you get a null)

(Aside, full example code)

package com.computermind.sandbox.algorithms;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.Setter;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import static java.util.stream.Collectors.joining;

public class DependencyGraph {

    public static void main(String... args) {

    Graph g = new Graph();

    System.out.println(g.add("Y", "Year"));
    System.out.println(g.add("N", "Johnson"));
    System.out.println(g.add("S", "Tom %N%"));
    System.out.println(g.add("Intro", "Hello My Name is %S% and I am x %Y% old"));

    // if you change `S` only two expression are recomputed (the updated `S` and their dependencies)
    System.out.println(g.add("S", "Peter %N%"));

    System.out.println(g.value("Intro"));

    }

    @Getter
    @Setter
    @AllArgsConstructor
    static class Var {
        String name;
        String[] parts;
        String computed;

        Stream<String> getUsedVarNames() {
            return IntStream.range(1, parts.length / 2).mapToObj(i -> parts[2 * i - 1]);
        }

        void updateValue(Map<String, Var> vars) {
            System.out.println("          Computing: "   name);
            computed = IntStream.range(0, parts.length)
                    .mapToObj(i -> i % 2 == 0 ? parts[i] : vars.get(parts[i]).getComputed())
                    .collect(joining());
        }
    }

    static class Graph {
        Map<String, Var> vars = new HashMap<>();
        Map<String, Set<String>> deps = new HashMap<>();

        String value(String name) {
            System.out.println("          Computing: "   name);
            return vars.get(name).getComputed();
        }

        String add(String name, String expr) {
            remove(name);

            Var current = new Var(name, expr.split("%"), null);

            // add current dependencies
            current.getUsedVarNames().forEach(dep -> deps.get(dep).add(name));

            // add var
            vars.put(name, current);
            if(!deps.containsKey(name))
                deps.put(name, new HashSet<>());

            // compute
            updateDeps(name);

            return current.getComputed();
        }

        private void updateDeps(String name) {
            vars.get(name).updateValue(vars);
            deps.get(name).forEach(this::updateDeps);
        }

        void remove(String name) {
            // remove current dependencies
            if (vars.containsKey(name)) {
                vars.get(name).getUsedVarNames().forEach(dep -> deps.get(dep).remove(name));
                vars.remove(name);
            }
        }
    }
}