Show problems as
Classic problem #399MediumArrayStringDepth-First SearchBreadth-First SearchUnion-FindGraph TheoryShortest PathBellman–Ford AlgorithmFloyd–Warshall Algorithm

Evaluate Division

Real-world version: Gear Train Ratios
Tracked in this browser only
Read Evaluate Division on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstExpression Evaluation · Stacks & Queues, animated step by step

A workshop is documenting a gear train. You are given meshes, where meshes[i] = [driver, driven] names two gears that mesh, together with ratios, where ratios[i] is how many turns driver makes for one single turn of driven.

Each entry of queries is a pair [top, bottom] asking how many turns top makes for one single turn of bottom. A gear that meshes with a chain of others turns in step with all of them, so a query can be settled whenever the two gears are linked through any run of meshes, in either direction.

Return one answer per query, in the order the queries are given, each rounded to 5 decimal places. Answer -1.0 when the query cannot be settled: either one of the two gears is absent from meshes, or both are present but no run of meshes links them. A gear named twice in one query turns exactly once per one of its own turns, so the answer is 1.0 when that gear appears in meshes and -1.0 when it does not.

Examples

Example 1

Input
meshes = [["crank", "spool"], ["spool", "drum"]], ratios = [3.0, 0.5], queries = [["crank", "drum"], ["drum", "crank"], ["crank", "crank"], ["hub", "hub"], ["crank", "hub"]]
Output
[1.5, 0.66667, 1.0, -1.0, -1.0]

The crank makes 3 turns per spool turn and the spool makes 0.5 turns per drum turn, so the crank makes 1.5 turns per drum turn and the drum makes 0.66667 turns per crank turn. The hub is never mentioned in the meshes, so both queries naming it are unsettled.

Example 2

Input
meshes = [["cam", "idler"]], ratios = [4.0], queries = [["idler", "cam"], ["cam", "idler"], ["idler", "idler"]]
Output
[0.25, 4.0, 1.0]

The recorded mesh reads forward, so reading it backward gives the idler 0.25 turns per cam turn.

Example 3

Input
meshes = [["a1", "b2"], ["c3", "d4"]], ratios = [2.0, 5.0], queries = [["a1", "d4"], ["a1", "b2"], ["d4", "c3"], ["b2", "z9"]]
Output
[-1.0, 2.0, 0.2, -1.0]

Two separate trains are documented. Gears in different trains are not linked, so that query is unsettled, and z9 is not documented at all.

Constraints

  • 1 <= meshes.length <= 20
  • meshes[i].length == 2
  • 1 <= meshes[i][0].length, meshes[i][1].length <= 5
  • meshes[i][0] != meshes[i][1]
  • ratios.length == meshes.length
  • 0.0 < ratios[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= queries[i][0].length, queries[i][1].length <= 5
  • Gear names hold lowercase English letters and digits
  • The recorded meshes never contradict one another, so a linked pair of gears has one well defined ratio
  • Each answer is rounded to 5 decimal places

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def gear_ratios(meshes: list[list[str]], ratios: list[float], queries: list[list[str]]) -> list[float]:
Java
public double[] gearRatios(List<List<String>> meshes, double[] ratios, List<List<String>> queries)

More on the same topics