Performing unit conversions using intermediate conversions

Question

Challenge:

Two input files are given The first contains |N| ratios in the form of two labels and a ratio:

1. USD, GBP, 0.69
2. Meter, Yard, 1.09
3. YEN, EUR, 0.0077
4. GBP, YEN, 167.75
5. Horsepower, Watt, 745.7

Each line A, B, C means that C is a conversion factor from A to B. In other words, multiply by C to go from A to B, and 1 A is worth C B's.

Example: USD, GBP, 0.69 means that 1 USD = 0.69 GBP, so multiplying by 0.69 converts an amount from USD to GBP.

And the expected output is a file with the query and the ratio value filled in.

1. USD, EUR, 0.89
2. Yard, Meter, 0.91

Write a program that reads both input files and produces the expected output

USD-EUR can be found by multiplying 0.69*167*0.0077=0.89 (Approx)

My Approach: These inputs can be represented as a weighted bi-directional graph

     0.69      167        0.0077
USD------->GBP------->YEN------->EUR
   <------    <-------   <-------
     1.449      0.0059    129.87

If we represent this format the problem reduces to finding shortest path between two nodes which can be done using Dijkstra. Instead of writing graph code from scratch i found a library from https://pypi.org/project/Dijkstar/ which reduced my code to

>>> from dijkstar import Graph,find_path
>>> graph=Graph()
>>> graph.add_edge('USD','GBP',{'cost':0.69})
>>> graph.add_edge('GBP','YEN',{'cost':167})
>>> graph.add_edge('YEN','EUR',{'cost':0.0077})
>>> graph.add_edge('EUR','YEN',{'cost':129.87})
>>> graph.add_edge('YEN','GBP',{'cost':0.0059})
>>> graph.add_edge('GBP','USD',{'cost':1.449})
>>> cost_func=lambda u,v,e,prev_e:e['cost']
>>> t=find_path(graph,'USD','EUR',cost_func=cost_func)
>>> print(t.costs)
[0.69,167,0.0077]
>>> from functools import reduce
>>> ans=reduce(lambda x, y: x*y, t.costs)
>>> print(round(ans,2))
0.89

I think the time complexity should be O(|V|+|E|).

Can I optimize this further? Is there a better or another way to solve this problem ?

Answer 1

The post (and the original assignment!) are a bit confused about these concepts:

1. the ratio between two units of measurement

2. the exchange rate between two currencies

3. the weight of an edge in a graph

The confusion is understandable because we sometimes use the word "cost" for all three concepts. But there are some important differences:

1. When combining ratios or exchange rates, you multiply them, but when combining weights you add them.

2. When converting units of measurement, it doesn't matter what path you take.

   For example, here's a possible set of inputs to your program:

   yard, foot, 3
   chain, foot, 66
   mile, chain, 80
   mile, yard, 1760
   

   If you need to use this to convert a mile into feet, it doesn't matter whether you take the path mile → yard → foot or mile → chain → foot, the answer is the same (5280) either way. Different paths can only yield different results if there are errors in the input.

   However, when exchanging currency, it might be better value to take one route rather than another. Due to arbitrage the difference between paths is likely to be small in the real world, but it can exist and so ought to be taken into account in any computer model.

This has some consequences:

1. Converting currencies and converting units of measurement are two different problems, and you shouldn't expect to be able to write one program that handles both.

2. A general graph is the wrong data structure for units of measurement, because it could have multiple paths between pairs of units, which means you would have to worry about data inconsistency. A better data structure would be a forest, so that there is at most one path between any pair of units and the data cannot be inconsistent.

3. If you are going to represent a collection of ratios as a weighted graph, then the weights need to be the logarithms of the ratios, so that the total weight of a path (the sum of the weights of the edges) is the log of the product of the ratios, as required.

4. Logarithms of ratios below 1 are negative, and Dijkstra's algorithm doesn't work with negative edge weights.

5. A graph with some negative edge weights might have a cycle with a negative sum. This means that there is no path of lowest weight in the graph. For example, suppose that you can exchange 2 marks for a crown, 2 guilders for a mark, and 2 crowns for a guilder. Then you can get arbitrary amounts of money by going around this cycle as often as you like. The program will need to have some way of handling this case—for example, maybe it indicates an error in the input.