# 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
0.2011684m
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
``````

1. DataWraith
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...

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.

``````require 'bigdecimal'
require 'set'

# Define conversions
CONVERSIONS = [
# 1e9nm in a meter
[BigDecimal(1_000_000_000), "nm", "m"],

# 10cm in a decimeter
[BigDecimal(10), "cm", "dm"],

# 10decimeter in a meter
[BigDecimal(10), "dm", "m"]

# Inserting all conversions is left as an exercise for the reader
]

# Define unit mapping (name => integer)
UNITS = CONVERSIONS.flat_map { |c| c[1, 2] }.uniq.map.with_index { |c, idx| [c, idx]}.to_h

# Create graph
graph = Array.new(UNITS.size) { Array.new(UNITS.size, nil) }

# Fill graph with conversions
CONVERSIONS.each do |multiplier, to, from|
graph[UNITS[from]][UNITS[to]] = multiplier
graph[UNITS[to]][UNITS[from]] = BigDecimal(1) / multiplier
end

# Do a BFS for the right unit
def convert(graph, quantity, from, to)
q = [[UNITS[from], quantity]]
s = Set.new

while q.size > 0
cur_unit, cur_value = q.shift
return cur_value if cur_unit == UNITS[to]
s << cur_unit

graph[cur_unit].each_with_index do |to, idx|
next if to.nil?
next if s.include?(idx)
q << [idx, cur_value * to]
end
end

nil
end

print "10 nm in nm: "
puts convert(graph, BigDecimal(10), "nm", "nm").to_s("10F") # 10

print "100 cm in m: "
puts convert(graph, BigDecimal(100), "cm", "m").to_s("10F") # 1

print "1cm in nm: "
puts convert(graph, BigDecimal(1), "cm", "nm").to_s("10F") # 10000000
``````
2. 
Ripsta
(edited )
Have every unit of distance convert 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...

Have every unit of distance convert 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.

1. unknown user
(edited )
Here is a Go version, using the fancy new Go 1.13 number literals with underscores (and loving it!): https://play.golang.org/p/Xs7H905N9lv. It only has a few units, and one could add more...

Here is a Go version, using the fancy new Go 1.13 number literals with underscores (and loving it!): 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!

2. 
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...

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.

1. 
unknown user
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...

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.

1 vote
1. 
Comment deleted by author
1. Soptik
Yeah, that’s it. Thanks for clarifucation, I could’ve wrote it better.

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

1 vote
2. unknown user
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...

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.

1 vote
2. jgb
Wien's displacement law!  https://en.wikipedia.org/wiki/Wien's_displacement_law

How do I convert meters to kelvin

Wien's displacement law!

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

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

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

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

1 vote
3. Staross
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...

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.

``````julia> 1u"kg" == 1000u"g"
true

julia> uconvert(μm/(m*Ra), 9μm/(m*K))
5//1 μm m^-1 Ra^-1
``````
4. onyxleopard
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...

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).

``````#!/usr/bin/env python3

from collections import namedtuple

Unit = namedtuple('Unit', ['value', 'unit'])

# distance_units are defined in terms of SI meters.
# Additional units can be derived such as for inches:
# 1 inch is 0.0254 meters so we solve for x in:
# 10^x = 0.0254
# log10(10^x) = log10(0.0254)
# log10(10^x) = -1.5951662833800617
# x * log10(10) = -1.5951662833800617
# x = -1.5951662833800617
# so we would register distance_units.update({'inch': -1.5951662833800617})
distance_units = {
'yoctometer': -24,
'zeptometer': -21,
'attometer': -18,
'femtometer': -15,
'picometer': -12,
'angstrom': -10,
'nanometer': -9,
'micrometer': -6,
'millimeter': -3,
'centimeter': -2,
'decimeter': -1,
'meter': 0,
'inch': -1.5951662833800617,
'yard': -0.03884478501945988,
'decameter': 1,
'hectometer': 2,
'kilometer': 3,
'megameter': 6,
'gigameter':  9,
'terameter': 12,
'petameter': 15,
'exameter': 18,
'zettameter': 21,
'yottameter': 24,
}

distances = {
unit: Unit(1.0, unit) for unit in distance_units
}

def convert(from_unit, to_unit, units=distance_units):
assert (from_unit.unit in units and to_unit.unit in units)
exponent = units[from_unit.unit] - units[to_unit.unit]
return Unit(
value=from_unit.value * 10 ** exponent,
unit=to_unit.unit
)

def convert_distance(from_value, from_unit, to_unit):
from_unit = from_unit._replace(value=from_value)
converted = convert(from_unit, to_unit, units=distance_units)
print(
f'{from_unit.value:0.3f} {from_unit.unit}'
f' is {converted.value:0.3f} {converted.unit}'
)
return converted

if __name__ == '__main__':
millimeter = Unit(1.0, 'millimeter')
centimeter = Unit(1.0, 'centimeter')
inch = Unit(1.0, 'inch')
meter = Unit(1.0, 'meter')
yard = Unit(1.0, 'yard')
kilometer = Unit(1.0, 'kilometer')
convert_distance(25, millimeter, inch)
convert_distance(1, inch, millimeter)
convert_distance(8, centimeter, inch)
convert_distance(0.001, kilometer, meter)
convert_distance(1, kilometer, yard)
``````
``````./units.py
25.000 millimeter is 0.984 inch
1.000 inch is 25.400 millimeter
8.000 centimeter is 3.150 inch
0.001 kilometer is 1.000 meter
1.000 kilometer is 1093.565 yard
``````
5. cstby
(edited )
Clojure solution that handles mixed unit types and rates: ;; (universal-convert 25 :km :m ) => 25000 ;; (universal-convert 60 :min :sec ) => 3600 ;; (universal-convert 5000 :m :sec :km :sec) => 5...

Clojure solution that handles mixed unit types and rates:

``````;; (universal-convert 25 :km :m )            => 25000
;; (universal-convert 60 :min :sec )         => 3600
;; (universal-convert 5000 :m :sec :km :sec) => 5
;; (universal-convert 5000 :m :sec :km :hr)  => 18000

(def unit-map
{:distance {:m  1
:cm 0.01
:km 1000}
:time     {:sec 1
:min 60
:hr  3600}})

(defn q-map
"Returns the quantity map for the two units
or nil if the units measure different quantities."
[u1 u2]
(first (filter (fn [m] (and (contains? m unit1)
(contains? m unit2)))
(vals unit-map))))

(defn universal-convert
"Takes a number and a combination of units and converts it."
([n u1 u3]
(universal-convert n u1 nil u3 nil))
([n u1 u2 u3 u4]
(let [u->ratio (merge (q-map u1 u3)
(q-map u2 u4))]
(if (nil? u->ratio)
(throw (AssertionError. "Units are not compatible!"))
(cond->> (* (u->ratio u1) (/ n (u->ratio u3)))
u2 (* (u->ratio u4))
u4 (* (u->ratio u2)))))))
``````

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