17
votes

# Programming Challenge: Convert between units

Hi everyone! It's been a long time since last programming challenge ^{list}, and here's a nice one I've encountered.

If you search for something like 7km to AU, you'll get your answer. But how is it done? I don't think they hardcoded all 23 units of distance and every conversion factor between them.

If you were programming a conversion system - how would you do it?

First of all, you have input in format that you can specify, for example something like this:

```
meter kilometer 1000
mile kilometer 1.609344
second minute 60
...
```

Then you should be able answer queries. For example `7 mile meter`

should convert 7 miles to meters, which is `11265.41`

.

Can you design an algorithm that will convert *any unit* into *any other unit*?

Edit: Some conversion rates I extracted from wikipedia:

```
ångström
0.1nm
astronomical unit
149597870700m
attometre
0.000000000000000001m
barleycorn
8.4m
bohr
0.00846
cable length (imperial)
185.3184m
cable length
185.2m
cable length (US)
219.456m
chain (Gunters)
20.11684m
cubit
0.5m
ell
1.143m
fathom
1.8288m
femtometre
0.00000000000001m
fermi
0.00000000000001m
finger
0.022225m
finger (cloth)
0.1143m
foot (Benoit)
0.304799735m
foot (Cape) (H)
0.314858m
foot (Clarke's) (H)
0.3047972654m
foot (Indian) (H)
0.304799514m
foot,metric
0.31622776602m
foot,metric (long)
0.3m
foot,metric (short)
0.30m
foot (International)
0.3048m
foot (Sear's) (H)
0.30479947m
foot (US Survey)
0.304800610
french
0.0003m
furlong
201.168m
hand
0.1016m
inch
0.0254m
league
4828m
light-day
25902068371200m
light-hour
107925284880m
light-minute
17987547480
light-second
299792458m
light-year
31557600light-second
line
0.002116m
link (Gunter's)
0.2011684m
link (Ramsden's; Engineer's)
0.3048m
metre
1m
m
1metre
km
1000m
mickey
0.000127
micrometre
0.000001
mil; thou
0.0000254
mil
10km
mile (geographical)
6082foot (International)
quarter
0.2286m
rod
5.0292m
rope
6.096m
shaku
0.303 0303m
span (H)
0.2286m
stick (H)
0.0508m
toise
1.949 0363m
twip
1.76310
yard
0.9144m
```

To me this sounds like a graph-search problem: I'd make every measurement unit a vertex in the graph and connect them with edges annotated with the multiplier necessary to go from one unit to the other. Then you can simply do a shortest-path search from start unit to goal unit (assuming that there is a path) and convert the initially given amount along the way.

I whipped that solution up into a quick Ruby script, but it could probably be made nicer.

Have every

unit of distanceconvert to a single standard of distance. Let's say to meters, then only have to use that conversion for the desire unit of distance.So AU > m > Miles

Instead of having to program every conversion for every unit of distance. Have the first unit convert to meters and the second unit to convert meters to itself.

I got to go to work but really wanted to reply to this. So couldn't program it. I will if no one else has by the time I get back.

Here is a Go version, using the fancy new Go 1.13 number literals with underscores (and

lovingit!): https://play.golang.org/p/Xs7H905N9lv.It only has a few units, and one could add more features, but I think it's pretty nice.

Edit:While writing this, I've finally decided to propose a change to Go, which I've been thinking about for quite some time. Thanks, @Soptik!Nice solution! But how would it cope if I mixed together different units - distance, area, volume, temperature, ... - during initialization? Some units won't have common unit, so you can't just pick arbitrary one.

How do I convert meters to kelvin? Or do you mean that a universal converter should accept both “m → ft” and “°F → °C” but not “m → °C”? If so, then a simple validation layer à la “exit with 1 if the units are from different types” should suffice.

Yeah, that’s it. Thanks for clarifucation, I could’ve wrote it better.

Ah. Then you would need to parse the operators and apply them accordingly. That is, multiply or divide by conversion ratios, until the default units are reached everywhere (e.g. m/°K) and then divide or multiply again until the desired units are reached.

Wien's displacement law!

[1] https://en.wikipedia.org/wiki/Wien's_displacement_law

I thought we were only solving for units of 'distance', not other units like temperature.

Sorry about that, I should’ve put it into example to be clear what I thought.

Julia has a pretty nice package for this, but I'm not sure what the underlying algorithm is. It seems to convert everything to SI units and then go from there, but I'll need to read the source a bit more.

For a bonus challenge, the Google unit converter even handles rates, for example:

https://www.google.com/search?q=10+meters+per+second+to+mph

https://www.google.com/search?q=10+miles+per+gallon+to+km+per+liter

I decided to define distance units in terms of the SI meter and then convert appropriately. Doing things in terms of logs makes tracking the conversions a matter of mapping unit names to the appropriate exponent in base 10 (non-SI units will then have not-so-nice exponents, but that's OK).

For SI units, this could possibly be abstracted even more to handle units of other measure besides distance, such as bits, liters, etc. This would just require keeping track of unit prefixes (but it would make working with non-SI units more cumbersome).

Clojure solution that handles mixed unit types and rates:

It all works off of a single map literal. You could extend it to include whichever units you like.

This was from that Medium post about some dude's interview question, right? Just read it last night.

Funny, I was wondering where these programming challenges went, and here's one I should be able to do after reading that blog post! But, I only vaguely remember the graph data structure and search algorithms...

Hmm..I think I'll try to reason them out on my own rather than learn how to implement them again. As elementary as they might be, I still have to think kinda hard about this stuff..