Evaluate Division

                                            
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> graph;
        for (int i = 0; i < equations.size(); ++i) {
            graph[equations[i][0]][equations[i][1]] = values[i];
            graph[equations[i][1]][equations[i][0]] = 1.0 / values[i];
        }
        
        vector<double> result;
        for (const auto& query : queries) {
            unordered_set<string> visited;
            double res = dfs(query[0], query[1], graph, visited);
            result.push_back(res);
        }
        
        return result;
    }
    
    double dfs(string start, string end, unordered_map<string, unordered_map<string, double>>& graph, unordered_set<string>& visited) {
        if (graph.find(start) == graph.end() || visited.count(start)) {
            return -1.0;
        }
        if (start == end) {
            return 1.0;
        }
        
        visited.insert(start);
        for (const auto& neighbor : graph[start]) {
            if (visited.count(neighbor.first)) {
                continue;
            }
            double temp = dfs(neighbor.first, end, graph, visited);
            if (temp != -1.0) {
                return temp * neighbor.second;
            }
        }
        
        return -1.0;
    }
};

                                            
import java.util.*;

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        
        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);
            double val = values[i];
            
            graph.putIfAbsent(a, new HashMap<>());
            graph.get(a).put(b, val);
            
            graph.putIfAbsent(b, new HashMap<>());
            graph.get(b).put(a, 1.0 / val);
        }
        
        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            result[i] = dfs(queries.get(i).get(0), queries.get(i).get(1), graph, new HashSet<>());
        }
        
        return result;
    }
    
    private double dfs(String start, String end, Map<String, Map<String, Double>> graph, Set<String> visited) {
        if (!graph.containsKey(start) || !graph.containsKey(end)) {
            return -1.0;
        }
        if (start.equals(end)) {
            return 1.0;
        }
        
        visited.add(start);
        for (Map.Entry<String, Double> neighbor : graph.get(start).entrySet()) {
            if (!visited.contains(neighbor.getKey())) {
                double result = dfs(neighbor.getKey(), end, graph, visited);
                if (result != -1.0) {
                    return neighbor.getValue() * result;
                }
            }
        }
        
        return -1.0;
    }
}

                                            
class Solution(object):
    def calcEquation(self, equations, values, queries):
        graph = {}
        for (dividend, divisor), value in zip(equations, values):
            if dividend not in graph:
                graph[dividend] = {}
            if divisor not in graph:
                graph[divisor] = {}
            graph[dividend][divisor] = value
            graph[divisor][dividend] = 1 / value
        
        def dfs(start, end, visited):
            if start not in graph or end not in graph:
                return -1.0
            if start == end:
                return 1.0
            visited.add(start)
            for neighbor in graph[start]:
                if neighbor not in visited:
                    result = dfs(neighbor, end, visited)
                    if result != -1.0:
                        return result * graph[start][neighbor]
            visited.remove(start)
            return -1.0
        
        results = []
        for dividend, divisor in queries:
            results.append(dfs(dividend, divisor, set()))
        
        return results

                                            
public class Solution {
    public double[] CalcEquation(IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        Dictionary<string, Dictionary<string, double>> graph = new Dictionary<string, Dictionary<string, double>>();
        for (int i = 0; i < equations.Count; i++) {
            string dividend = equations[i][0];
            string divisor = equations[i][1];
            double quotient = values[i];

            if (!graph.ContainsKey(dividend)) {
                graph[dividend] = new Dictionary<string, double>();
            }
            if (!graph.ContainsKey(divisor)) {
                graph[divisor] = new Dictionary<string, double>();
            }

            graph[dividend].Add(divisor, quotient);
            graph[divisor].Add(dividend, 1 / quotient);
        }

        double[] results = new double[queries.Count];
        for (int i = 0; i < queries.Count; i++) {
            string dividend = queries[i][0];
            string divisor = queries[i][1];
            if (!graph.ContainsKey(dividend) || !graph.ContainsKey(divisor)) {
                results[i] = -1.0;
            } else {
                HashSet<string> visited = new HashSet<string>();
                results[i] = Dfs(graph, dividend, divisor, 1.0, visited);
            }
        }

        return results;
    }

    private double Dfs(Dictionary<string, Dictionary<string, double>> graph, string start, string end, double current, HashSet<string> visited) {
        if (start == end) {
            return current;
        }
        visited.Add(start);

        foreach (var neighbor in graph[start]) {
            if (!visited.Contains(neighbor.Key)) {
                double result = Dfs(graph, neighbor.Key, end, current * neighbor.Value, visited);
                if (result != -1.0) {
                    return result;
                }
            }
        }

        return -1.0;
    }
}

                                            
var calcEquation = function(equations, values, queries) {
    const graph = new Map();
    const weight = new Map();
    
    for(let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        if(!graph.has(a)) {
            graph.set(a, new Map());
            weight.set(a, new Map());
        }
        if(!graph.has(b)) {
            graph.set(b, new Map());
            weight.set(b, new Map());
        }
        graph.get(a).set(b, values[i]);
        graph.get(b).set(a, 1 / values[i]);
        weight.get(a).set(b, values[i]);
        weight.get(b).set(a, 1 / values[i]);
    }
    
    const dfs = (curr, target, visited) => {
        if(curr === target) return 1.0;
        if(visited.has(curr)) return -1.0;
        
        visited.add(curr);
        
        const neighbors = graph.get(curr);
        for(const neighbor of neighbors.keys()) {
            const value = neighbors.get(neighbor);
            const result = dfs(neighbor, target, visited);
            if(result !== -1.0) {
                const w = weight.get(curr).get(neighbor);
                return w * result;
            }
        }
        
        return -1.0;
    };
    
    const results = [];
    for(const [src, dest] of queries) {
        if(!graph.has(src) || !graph.has(dest)) {
            results.push(-1.0);
        } else {
            results.push(dfs(src, dest, new Set()));
        }
    }
    
    return results;
};

                                            
function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
    const graph = new Map<string, Map<string, number>>();
    
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        const val = values[i];
        
        if (!graph.has(a)) graph.set(a, new Map());
        if (!graph.has(b)) graph.set(b, new Map());
        
        graph.get(a)!.set(b, val);
        graph.get(b)!.set(a, 1 / val);
    }
    
    const dfs = (curr: string, target: string, visited: Set<string>): number => {
        if (!graph.has(curr)) return -1;
        if (curr === target) return 1;
        
        visited.add(curr);
        
        for (const [neighbor, val] of graph.get(curr)!) {
            if (visited.has(neighbor)) continue;
            
            const result = dfs(neighbor, target, visited);
            if (result !== -1) {
                return val * result;
            }
        }
        
        return -1;
    };
    
    const result: number[] = [];
    
    for (const [dividend, divisor] of queries) {
        result.push(dfs(dividend, divisor, new Set<string>()));
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param String[][] $equations
     * @param Float[] $values
     * @param String[][] $queries
     * @return Float[]
     */
    function calcEquation($equations, $values, $queries) {
        $graph = [];
        for ($i = 0; $i < count($equations); $i++) {
            list($dividend, $divisor) = $equations[$i];
            $graph[$dividend][$divisor] = $values[$i];
            $graph[$divisor][$dividend] = 1 / $values[$i];
        }

        $results = [];
        foreach ($queries as $query) {
            $results[] = $this->dfs($query[0], $query[1], $graph, []);
        }

        return $results;
    }

    function dfs($start, $end, $graph, $visited) {
        if (!array_key_exists($start, $graph) || in_array($start, $visited)) {
            return -1.0;
        }

        if ($start == $end) {
            return 1.0;
        }

        $visited[] = $start;
        foreach ($graph[$start] as $node => $value) {
            $result = $this->dfs($node, $end, $graph, $visited);
            if ($result != -1.0) {
                return $value * $result;
            }
        }

        return -1.0;
    }
}

                                            
class Solution {
    func calcEquation(_ equations: [[String]], _ values: [Double], _ queries: [[String]]) -> [Double] {
        var graph = [String: [(String, Double)]]()
        
        for i in 0..<equations.count {
            let (a, b) = (equations[i][0], equations[i][1])
            let (value, reverseValue) = (values[i], 1 / values[i])
            
            if graph[a] == nil {
                graph[a] = [(b, value)]
            } else {
                graph[a]?.append((b, value))
            }
            
            if graph[b] == nil {
                graph[b] = [(a, reverseValue)]
            } else {
                graph[b]?.append((a, reverseValue))
            }
        }
        
        func dfs(_ start: String, _ end: String, _ visited: inout Set<String>) -> Double? {
            if start == end {
                return 1.0
            }
            
            visited.insert(start)
            
            if let neighbors = graph[start] {
                for (neighbor, value) in neighbors {
                    if !visited.contains(neighbor) {
                        if let result = dfs(neighbor, end, &visited) {
                            return result * value
                        }
                    }
                }
            }
            
            return nil
        }
        
        var results = [Double]()
        
        for query in queries {
            let (start, end) = (query[0], query[1])
            
            if graph[start] == nil || graph[end] == nil {
                results.append(-1.0)
            } else {
                var visited = Set<String>()
                if let result = dfs(start, end, &visited) {
                    results.append(result)
                } else {
                    results.append(-1.0)
                }
            }
        }
        
        return results
    }
}

                                            
class Solution {
    fun calcEquation(equations: List<List<String>>, values: DoubleArray, queries: List<List<String>>): DoubleArray {
        val graph = mutableMapOf<String, MutableMap<String, Double>>()
        for (i in equations.indices) {
            val (from, to) = equations[i]
            val value = values[i]
            
            graph.computeIfAbsent(from) { mutableMapOf() }[to] = value
            graph.computeIfAbsent(to) { mutableMapOf() }[from] = 1 / value
        }
        
        fun dfs(start: String, end: String, visited: MutableSet<String>): Double {
            if (start !in graph || end !in graph) return -1.0
            if (start == end) return 1.0
            
            visited.add(start)
            val neighbors = graph[start] ?: return -1.0
            for ((neighbor, value) in neighbors) {
                if (neighbor == end) return value
                if (neighbor !in visited) {
                    val result = dfs(neighbor, end, visited)
                    if (result != -1.0) {
                        return value * result
                    }
                }
            }
            return -1.0
        }
        
        return queries.map { query ->
            val (start, end) = query
            dfs(start, end, mutableSetOf())
        }.toDoubleArray()
    }
}

                                            
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    graph := make(map[string]map[string]float64)
    for i, eq := range equations {
        if _, ok := graph[eq[0]]; !ok {
            graph[eq[0]] = make(map[string]float64)
        }
        if _, ok := graph[eq[1]]; !ok {
            graph[eq[1]] = make(map[string]float64)
        }
        graph[eq[0]][eq[1]] = values[i]
        graph[eq[1]][eq[0]] = 1.0 / values[i]
    }

    var dfs func(curr, dest string, visited map[string]bool) float64
    dfs = func(curr, dest string, visited map[string]bool) float64 {
        if _, ok := graph[curr]; !ok {
            return -1.0
        }
        if curr == dest {
            return 1.0
        }
        visited[curr] = true
        for next, val := range graph[curr] {
            if !visited[next] {
                if res := dfs(next, dest, visited); res != -1.0 {
                    return val * res
                }
            }
        }
        visited[curr] = false
        return -1.0
    }

    results := make([]float64, len(queries))
    for i, query := range queries {
        results[i] = dfs(query[0], query[1], make(map[string]bool))
    }
    return results
}

                                            
def calc_equation(equations, values, queries)
    graph = {}
    
    equations.each_with_index do |eq, idx|
        a, b = eq
        value = values[idx]
        
        graph[a] ||= {}
        graph[b] ||= {}
        
        graph[a][b] = value
        graph[b][a] = 1.0 / value
    end
    
    result = []
    
    queries.each do |query|
        result << dfs(query[0], query[1], 1.0, graph, Set.new)
    end
    
    result
end

def dfs(curr, target, product, graph, visited)
    return -1.0 if !graph[curr] || visited.include?(curr)
    return product if curr == target
    
    visited.add(curr)
    
    graph[curr].each do |neighbor, value|
        result = dfs(neighbor, target, product * value, graph, visited)
        return result if result != -1.0
    end
    
    return -1.0
end

                                            
use std::collections::HashMap;

impl Solution {
    pub fn calc_equation(equations: Vec<Vec<String>>, values: Vec<f64>, queries: Vec<Vec<String>>) -> Vec<f64> {
        let mut graph: HashMap<String, HashMap<String, f64>> = HashMap::new();
        
        for i in 0..equations.len() {
            let (a, b) = (&equations[i][0], &equations[i][1]);
            let value = values[i];
            
            graph.entry(a.to_string()).or_insert(HashMap::new()).insert(b.to_string(), value);
            graph.entry(b.to_string()).or_insert(HashMap::new()).insert(a.to_string(), 1.0 / value);
        }
        
        let mut results = Vec::new();
        
        for query in queries {
            let mut visited = HashMap::new();
            let result = Self::dfs(&graph, &query[0], &query[1], 1.0, &mut visited);
            results.push(result);
        }
        
        results
    }
    
    fn dfs(graph: &HashMap<String, HashMap<String, f64>>, start: &String, end: &String, value: f64, visited: &mut HashMap<String, bool>) -> f64 {
        if let Some(edges) = graph.get(start) {
            if start == end {
                return value;
            }
            
            visited.insert(start.clone(), true);
            
            for (next, edge_value) in edges.iter() {
                if !visited.contains_key(next) {
                    let result = Self::dfs(graph, next, end, value * edge_value, visited);
                    if result != -1.0 {
                        return result;
                    }
                }
            }
            
            visited.remove(start);
        }
        
        -1.0
    }
}

To solve this coding challenge, we need to evaluate division expressions based on a set of given equations and their corresponding values. We will employ a graph-based approach to represent the relationships between variables, ensuring we can traverse the graph to respond to queries.

Explanation

The main approach involves constructing a graph where each variable is a node, and an edge exists between two nodes if an equation directly relates them. The edge will store the given division value between these variables. For instance, the equation "a / b = 2.0" means there should be an edge from node 'a' to node 'b' with a weight of 2.0, and an edge from node 'b' to node 'a' with a weight of 0.5. After constructing the graph:

We'll use Depth First Search (DFS) or Breadth First Search (BFS) to find the path between the variable pairs in the queries.
If the path exists, we calculate the result by multiplying the weights of the edges along the path.
If there is no path between the variables or the variable does not exist, we return -1.0.

Step-by-Step Explanation

Graph Construction :

For each equation, create edges in both directions with appropriate weights.

Query Evaluation using DFS/BFS :

For each query, traverse the graph to find a path between the specified variables.
Multiply the weights along the path to get the division result.

Detailed Steps in Pseudocode

Graph Construction

                                            
initialize empty dictionary called graph

for equation, value in equations and values:
element1, element2 = equation

if element1 not in graph:
add element1 to graph with an empty dictionary as its value
if element2 not in graph:
add element2 to graph with an empty dictionary as its value

add element2 to graph[element1] with value
add element1 to graph[element2] with 1/value

Query Evaluation using DFS

                                            
define function dfs(start, end, visited):
if start not in graph or end not in graph:
return -1.0
if start == end:
return 1.0

add start to visited

for neighbor in graph[start]:
if neighbor not in visited:
result = dfs(neighbor, end, visited)
if result != -1.0:
return result * graph[start][neighbor]

remove start from visited
return -1.0

Main Function to Compute Results

                                            
define function calcEquation(equations, values, queries):
graph = construct_graph(equations, values) # call the graph construction code

results = empty list

for query in queries:
start, end = query
result = dfs(start, end, empty set)
append result to results

return results

Recap of Core Concepts:

Graph Representation : Each variable is a node. Equations define the bidirectional edges with given weights.
Graph Traversal : DFS is used to explore possible paths between nodes, accumulating the product of edge weights to compute the result.
Handling Edge Cases : If no path exists or the variables are undefined, return -1.0.

This approach efficiently handles the constraints provided, ensuring all queries are processed to deliver accurate division results based on the given equations.