New exercise idea: Unit conversions

This post is kept largely language-agnostic so that other tracks can use the exercise if they want. The implementation details for the Julia exercise can be found in a PR once the general exercise idea has been refined.

The exercise idea is based on the article Google Interview Problems: Ratio Finder by Alex Golec (scroll down to "The Question" to find the problem).

General idea: Given a list of conversion rates between different units, find a way to convert between them.

In the post, he uses distances as an example. The solver has to convert 1 hand to light years given the following conversion rates:

1 hand = 4 inch
4 inches = 1/3 feet
1/3 feet = 6.3125e-5 american miles
6.3125e-5 american miles = 1.0737e-17 light years

His solution builds a graph from the given conversions and a search algorithm to find the conversion rate. For more details and an example implementation in Python, I suggest reading the post.

In an exercism adaptation of this problem, we could also use different kinds of units, e.g. mass or currency rates (the latter is also mentioned in the article). A few story ideas that immediately came to my mind:

You're on vacation in a country that uses obscure units such as miles or yards and need to figure out what they mean.
You want to translate a cooking recipe and it uses a variety of units for mass/volume, such as cups, mugs or oz.

Distance would have the advantage that there's a handy video guide the readme could link to and that there is a huge amount of obscure and less obscure ways to represent distances.

One important question: Is this exercise about modelling the problem, i.e. recognising to use a graph to represent the conversions, or implementing a solution, i.e. writing the search algorithm and graph? In the first case, it's probably helpful to mention that the students are encouraged to use relevant libraries to solve this exercise. In the second case, the exercise description should contain more information on how to approach the problem. Of course, forcing a certain way isn't necessary, but it may influence how the description is written.

Tests

There are a number of edge cases to consider when solving the exercise and creating a test suite:

Does the solution minimise the amount of conversions needed to reduce rounding errors?
The given problem may not have a unique solution.
What format are the conversions given in?
How to handle rounding errors in the test cases?
How are missing conversions handled?

This is meant as a base to start the discussion, so feel free to take apart everything and perhaps we end up with a completely different, but better, exercise idea :)

Input range problem

I think it's important to decide the structure of the underlying graph. Will it have one or more cycles? Will it have multiple connected components? Should the solution accept units not given in the graph?

My personal pick would be no cycles and single connected component. The main reasons are:

The solution is guaranteed to be unique as long as both units exist in the graph
- If there is a cycle and the cycle's product is different from 1, there are infinitely many possible answers
- If there are multiple connected components, no solution is possible even if both units are present
- For the single kind of measure (in this case, length), this is closest to real-life scenarios (IMO)
The amount of conversions is fixed, unless an edge is traversed back and forth

Missing conversions might be fine, as many languages can handle it by null values or option types.

Handling rounding errors in test cases

This is usually done using absolute/relative error margin. For this particular problem, relative error should be sufficient since 1) all input/output/intermediate values must be positive and 2) only multiplication and division are used. The test roughly looks like this:

# test if `actual` is close to `expected` within `threshold` (relative error)
assert (1 - threshold) * expected <= actual <= (1 + threshold) * expected
# test if `actual` is close to `expected` within `threshold` (absolute error)
assert expected - threshold <= actual <= expected + threshold

Common choice of threshold is 1e-6.

(Another option would be to return the sequence of units involved in the conversion, though it slightly obscures the intent of the problem.)

Input format

The most sensible choice would be a list of triples [unit_from, unit_to, ratio], presented in the most natural data type for each language.

Modeling vs. Implementation

My position is slightly towards modeling rather than implementation. Students are free to use an existing library or solve without one, and IMO neither should be considered superior to the other.

I think it's important to decide the structure of the underlying graph. Will it have one or more cycles? Will it have multiple connected components? Should the solution accept units not given in the graph?

I don't like forcing a certain implementation/model upon the student, so I don't think that's something we have to decide.

However, test cases could be arranged in increasing complexity, e.g. the first tests have input that can be followed linearly to convert the units, then more complex test inputs for a more "realistic" exercise.

My personal pick would be no cycles and single connected component.

I feel like if this was a "real world" problem, cycles would be rather common in input data, so I'm not sure I agree on not having them, at least for more complex test cases.

A single connected component seems fine to me to keep the exercise simple. If a student solves that case, they're probably "fluent" enough to adapt it to handle multiple components anyway.

The most sensible choice would be a list of triples [unit_from, unit_to, ratio], presented in the most natural data type for each language.

For easier testing across tracks, it might be useful to store them in a simple text file and then provide the student with a parser in the stub files or generate the representation in code from that.

I'll put together an example implementation and some tests in Julia in the next few days.

exercism / julia