Evaluate Division

evaluate_division.cpp

class ValType {
public:
    double val;
    string sym;

    ValType () {
        this->val = 1.0;
        this->sym = "";
    }

    ValType (double v, string s) {
        this->val = v;
        this->sym = s;
    }
};

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {

        set<string> numers, denoms, vars;
        map<string, ValType> vals;

        for (auto &p: equations) {
            vars.insert(p.first);
            vars.insert(p.second);
            numers.insert(p.first);
            denoms.insert(p.second);
        }

        // initialize `lone` denominators: only appears as a denominator
        vector<string> lone_denoms;
        for (string s: denoms)
            if (numers.find(s) == numers.end())
                lone_denoms.push_back(s);

        // set vals
        for (string s: lone_denoms)
            setVals(vals, equations, values, vars.size(), s);

        vector<double> results;
        for (auto &p: queries) {
            string num = p.first, den = p.second;
            if (vals.find(num) == vals.end() || vals.find(den) == vals.end() || vals[num].sym != vals[den].sym)
                results.push_back(-1.0);
            else
                results.push_back(vals[num].val / vals[den].val);
        }

        return results;
    }

private:
    void setVals(map<string, ValType> &vals,
                 vector<pair<string, string> > &equations,
                 vector<double> &values,
                 int len,
                 string key) {
        if (vals.size() == len)
            return ;

        if (vals.find(key) == vals.end()) {
            vals[key] = ValType(1.0, key);
            setVals(vals, equations, values, len, key);
            return ;
        }

        for (int i = 0; i < equations.size(); ++i) {
            auto p = equations[i];
            ValType v = vals[key];

            if (key == p.second && vals.find(p.first) == vals.end()) {
                vals[p.first] = ValType(v.val * values[i], v.sym);
                setVals(vals, equations, values, len, p.first);
            } else if (key == p.first && vals.find(p.second) == vals.end()) {
                vals[p.second] = ValType(v.val / values[i], v.sym);
                setVals(vals, equations, values, len, p.second);
            }
        }
    }
};

evaluate_division.py

## function naming is not very pythonic though :(

class ValType(object):
    def __init__(self, val=1.0, sym=''):
        self.val = val
        self.sym = sym
        

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]
        """
        
        numers = {r[0] for r in equations}
        denoms = {r[1] for r in equations}
        
        num_vars = len(numers | denoms)
        start_vars = denoms - numers
        vals = dict()
        
        # use dfs to set vals for each variable
        for var in start_vars:
            self.setVals(vals, var, num_vars, equations, values)
            
            
        # calc result
        result = []
        for q in queries:
            numer = vals.get(q[0])
            denom = vals.get(q[1])
            if not (numer and denom) or numer.sym != denom.sym:
                result.append(-1.0)
            else:
                result.append(numer.val / denom.val)
                
        return result
        
    def setVals(self, vals, var,
                num_vars, equations, values):
        if len(vals) == num_vars:
            return
        
        if not vals.get(var):
            vals[var] = ValType(1.0, var)
            self.setVals(vals, var, num_vars, equations, values)
            return
        
        for (numer, denom), val in zip(equations, values):
            if numer == var and not vals.get(denom):
                vals[denom] = ValType(vals[var].val / val, vals[var].sym)
                self.setVals(vals, denom, num_vars, equations, values)
            elif denom == var and not vals.get(numer):
                vals[numer] = ValType(vals[var].val * val, vals[var].sym)
                self.setVals(vals, numer, num_vars, equations, values)