Programming Challenge: Convert between units

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

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.

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

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

#!/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

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.

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