9 lines "Floyd–Warshall" in Python


  • 51

    A variation of Floyd–Warshall, computing quotients instead of shortest paths. An equation A/B=k is like a graph edge A->B, and (A/B)*(B/C)*(C/D) is like the path A->B->C->D. Submitted once, accepted in 35 ms.

    def calcEquation(self, equations, values, queries):
        quot = collections.defaultdict(dict)
        for (num, den), val in zip(equations, values):
            quot[num][num] = quot[den][den] = 1.0
            quot[num][den] = val
            quot[den][num] = 1 / val
        for k, i, j in itertools.permutations(quot, 3):
            if k in quot[i] and j in quot[k]:
                quot[i][j] = quot[i][k] * quot[k][j]
        return [quot[num].get(den, -1.0) for num, den in queries]
    

    Variation without the if (submitted twice, accepted in 68 and 39 ms):

    def calcEquation(self, equations, values, queries):
        quot = collections.defaultdict(dict)
        for (num, den), val in zip(equations, values):
            quot[num][num] = quot[den][den] = 1.0
            quot[num][den] = val
            quot[den][num] = 1 / val
        for k in quot:
            for i in quot[k]:
                for j in quot[k]:
                    quot[i][j] = quot[i][k] * quot[k][j]
        return [quot[num].get(den, -1.0) for num, den in queries]
    

    Could save a line with for i, j in itertools.permutations(quot[k], 2) but it's longer and I don't like it as much here.


  • 1

    your answers are always most trenchant, concise and enlightening! Thanks man!


  • 0
    C

    same idea here

    but I wrote 10+ lines code to do the "search". Great use of itertools.permutations


  • 0
    This post is deleted!

  • 0

    @mzchen "the values are positive". Zero is not positive. Your input is invalid.


  • 0
    This post is deleted!

  • 0

    @StefanPochmann
    Sorry you are right. I didn't notice that statement.


  • 0
    This post is deleted!

  • 1
    A

    Java version similar with your idea

    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, HashMap<String, Double>> map = new HashMap<>();
            for(int i=0; i<equations.length; i++) {
                String[] eq = equations[i]; 
                if(!map.containsKey(eq[0]))
                    map.put(eq[0], new HashMap<>());
                if(!map.containsKey(eq[1]))
                    map.put(eq[1], new HashMap<>());
                
                HashMap<String, Double> map0 = map.get(eq[0]);
                HashMap<String, Double> map1 = map.get(eq[1]);
                map0.put(eq[1], values[i]);
                map1.put(eq[0], 1/values[i]);
                
                insert(map, eq[0], eq[1], values[i]);
            }
            int len = queries.length;
            double[] re = new double[len];
            for(int i=0; i<len; i++) {
                String[] qu = queries[i];
                if(!map.containsKey(qu[0]) || !map.get(qu[0]).containsKey(qu[1]))
                    re[i] = -1;
                else {
                    re[i] = map.get(qu[0]).get(qu[1]);
                }
            }
            return re;
        }
        
        private void insert(HashMap<String, HashMap<String, Double>> map, String a, String b, double value) {
            HashMap<String, Double> map0 = map.get(a);
            HashMap<String, Double> map1 = map.get(b);
            for( String key : map1.keySet()) {
                double val = map1.get(key)*value;
                if(!map0.containsKey(key)){
                    map0.put(key, val);
                    map.get(key).put(a, 1/val);
                    insert(map, a, key, val);
                }
            }
            for( String key : map0.keySet()) {
                double val = map0.get(key)/value;
                if(!map1.containsKey(key)){
                    map1.put(key, val);
                    map.get(key).put(b, 1/val);
                    insert(map, b, key, val);
                }
            }
        }
    }
    

  • 2
    T

    Hi, I have a question about this part and any reply or explanation is appreciated! Thanks!

     for k, i, j in itertools.permutations(quot, 3):
            if k in quot[i] and j in quot[k]:
                quot[i][j] = quot[i][k] * quot[k][j]
    

    this part works on all 3 - permutations of nodes in graph, trying to connect i -> k -> j, if k is connected with i and j. I was wondering whether the sequence of the permutation appears matters. Take this example:
    3 edge 4 nodes : a -> b, b->c, c->d.
    and if the permutation i, k, j goes as :

    1. a , b , d (d not in quot[b])
    2. a , c , d (c not in quot[a])
    3. d , b , a (b not in quot[d])
    4. d , c , a (a not in quot[c])
      ......
      If in this order, no new connection will be established in the first 4 rounds, and I think a and d will never have a chance to be connected afterward, right? so how does this algorithm guarantee to connect a and d? If I have misunderstanding somewhere, please correct me. Thanks!

  • 3

    @therealoneisneo You are right, the order matters. k needs to be "the outer loop" like my second version is doing more explicitly. But that's why I use for k, i, j in permutations instead of for example for i, k, j in permutations. The documentation of the function says "Permutations are emitted in lexicographic sort order", so I do get that "outer loop" effect that way and it's all fine.

    But very good question. I btw remember not being sure about that myself and then being delighted to see that the lexicographic order is not just what the implementation happens to do but that it's explicitly specified to be like that.


  • 0
    T

    @StefanPochmann Thank you so much for the explanation! The solution is clear to me now! your code is always surprisingly concise and nice! Thanks!


  • 0

    @therealoneisneo You're welcome. Especially since you didn't just ask whether the order matters, but actually created and showed that example. Much appreciated.


  • 0
    W

    Nice solution. This is a floyd-warshall-y solution because of the triple nested loops. However it is difficult for me to understand it following the floyd-warshall reasoning. I will share my $.02 here. Correct me if I'm wrong.

    Concretely the triple loops create a complete graph. For the first node, connect every pair of its neighbors, a complete sub-graph containing the first node. then the second, then the third, .... so after the loops, all related variables will be in one big complete graph.


  • 2
    P

    Can anyone explain

    for k in quot:
        for i in quot[k]:
            for j in quot[k]:
                quot[i][j] = quot[i][k] * quot[k][j]
    

    I understand that it's trying to propagate the unstated quotient relationship among different variables, but still not able to see why this would be effective. For example, isn't "k" the key of quot instead of key of quot[i]? and why would i able to be used as key of quot ? I'm getting confused here


  • 1
    T

    It seems that quot[num][num] = quot[den][den] = 1.0 is not necessary.


  • 0
    S

    Is it okay to iterate through quot and modify it at the same time?

    never mind. i and j must have occurred as key values so the loop will not create new key values in the dictionary.


  • 0
    B

    @StefanPochmann Hi, I also have a little question.
    I run your code on python 3.5 in this example

    equations = [ ["a","d"],["b","c"],['d','b'],['c','e'] ]
    values    = [2.0,3.0,4.0,5.0]
    queries   = [ ["a","c"],["b","c"],["e","a"],["a","a"],["x","x"] ]
    

    I found the result may vary each time, so I print the quot
    when quot =

    defaultdict(<class 'dict'>, {'d': {'a': 0.5, 'd': 1.0, 'b': 4.0}, 'e': {'e': 1.0, 'c': 0.2}, 'a': {'a': 1.0, 'd': 2.0}, 'b': {'d': 0.25, 'b': 1.0, 'c': 3.0}, 'c': {'e': 5.0, 'b': 0.3333333333333333, 'c': 1.0}})
    

    the result will be[24.0, 3.0, -1, 1.0, -1], which is wrong
    and when quot=

    defaultdict(<class 'dict'>, {'e': {'e': 1.0, 'c': 0.2}, 'c': {'e': 5.0, 'c': 1.0, 'b': 0.3333333333333333}, 'b': {'c': 3.0, 'd': 0.25, 'b': 1.0}, 'd': {'b': 4.0, 'd': 1.0, 'a': 0.5}, 'a': {'d': 2.0, 'a': 1.0}})
    

    the result is [24.0, 3.0, 0.008333333333333333, 1.0, -1]
    It seems that the result is relative to the dict order,and in python 3.5, the order may vary at each time


  • 0

    @beautifeng I can't reproduce it. Ran the solution with your input over 200 times (in separate runs of the script), always got [24.0, 3.0, 0.008333333333333333, 1.0, -1.0]. Can you show a complete script that I can run which produces different outputs for you?


  • 0
    B

    @StefanPochmann
    my fault, as you said before, the middle node must set in the outer loop

    import itertools
    import collections
    class Solution(object):
        def calcEquation(self, equations, values, queries):
            """
            :type equations: List[List[str]]
            :type values: List[float]
            :type queries: List[List[str]]
            :rtype: List[float]
            """
            visitCost = collections.defaultdict(dict)
            for (s,e),v in zip(equations,values):
                visitCost[s][s]=1.0
                visitCost[e][e]=1.0
                visitCost[s][e]=v
                visitCost[e][s]=1.0/v
            print(visitCost)
            #Permutations are emitted in lexicographic sort order
            #should be for m,s,e
            for s,m,e in itertools.permutations(visitCost,3):
                #print(s,m,e)
                if m in visitCost[s] and e in visitCost[m]:
                    visitCost[s][e]=visitCost[s][m]*visitCost[m][e]
            print(visitCost)
            #print('another')
            # another solution
            # !!!! the order is important
            #for m in visitCost:
            #    for s in visitCost[m]:
            #        for e in visitCost[m]:
            #            print(s,m,e)
            #            visitCost[s][e]=visitCost[s][m]*visitCost[m][e]
    
            res = []
            for s,e in queries:
                res.append(visitCost[s].setdefault(e,-1))
            return res
    
    
    #equations = [ ["a","b"],["b","c"] ]
    #values    = [2.0,3.0]
    #queries   = [ ["a","c"],["b","c"],["a","e"],["a","a"],["x","x"] ]
    equations = [ ["a","d"],["b","c"],['d','b'],['c','e'] ]
    values    = [2.0,3.0,4.0,5.0]
    queries   = [ ["a","c"],["b","c"],["e","a"],["a","a"],["x","x"] ]
    
    print(Solution().calcEquation(equations,values,queries))
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.