Resolve Path recursively

user_1469261 0
Viewed 126

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();
    }
algorithm java
1 Answers

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);
            }
        }
    }
}
user_15407490
Related