Good Data Structure for Unit Conversion? [closed]

Question

StackOverflow crowd. I have a very open-ended software design question.

I've been looking for an elagant solution to this for a while and I was wondering if anyone here had some brilliant insight into the problem. Consider this to be like a data structures puzzle.

What I am trying to do is to create a unit converter that is capable of converting from any unit to any unit. Assume that the lexing and parsing is already done. A few simple examples:

Convert("days","hours")           // Yields 24
Convert("revolutions", "degrees") // Yields 360

To make things a little more complicated, it must smoothly handle ambiguities between inputs:

Convert("minutes","hours")        // Yields (1/60)
Convert("minutes","revolutions")  // Yields (1/21600)

To make things even more fun, it must handle complex units without needing to enumerate all possibilities:

Convert("meters/second","kilometers/hour")
Convert("miles/hour","knots")
Convert("Newton meters","foot pounds")
Convert("Acre feet","meters^3")

There's no right or wrong answer, I'm looking for ideas on how to accomplish this. There's always a brute force solution, but I want something elegant that is simple and scalable.

Answer 1

I would start with a hashtable (or persisted lookup table - your choice how you implement) that carries unit conversions between as many pairs as you care to put in. If you put in every possible pair, then this is your brute force approach.

If you have only partial pairs, you can then do a search across the pairs you do have to find a combination. For example, let's say I have these two entries in my hashtable:

Feet|Inches|1/12
Inches|Centimeters|2.54

Now if I want to convert feet to centimeters, I have a simple graph search: vertices are Feet, Inches, and Centimeters, and edges are the 1/12 and 2.54 conversion factors. The solution in this case is the two edges 1/12, 2.54 (combined via multiplication, of course). You can get fancier with the graph parameters if you want to.

Another approach might be applying abductive reasoning - look into AI texts about algebraic problem solvers for this...

Edit: Addressing Compound Units

Simplified problem: convert "Acres" to "Meters^2"

In this case, the keys are understanding that we are talking about units of length, so why don't we insert a new column into the table for unit type, which can be "length" or "area". This will help performance even in the earlier cases as it gives you an easy column to pare down your search space.

Now the trick is to understand that length^2 = area. Why not add another lookup that stores this metadata:

Area|Length|Length|*

We couple this with the primary units table:

Meters|Feet|3.28|Length
Acres|Feet^2|43560|Area

So the algorithm goes:

• Solution is m^2, which is m * m, which is a length * length.
• Input is acres, which is an area.
• Search the meta table for m, and find the length * length mapping. Note that in more complex examples there may be more than one valid mapping.
• Append to the solution a conversion Acres->Feet^2.
• Perform the original graph search for Feet->M.

Note that:

• The algorithm won't know whether to use area or length as the basic domain in which to work. You can provide it hints, or let it search both spaces.
• The meta table gets a little brute-force-ish.
• The meta table will need to get smarter if you start mixing types (e.g. Resistance = Voltage / Current) or doing something really ugly and mixing unit systems (e.g. a FooArea = Meters * Feet).