Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 325
Good morning! Here's your coding interview problem for today.

This problem was asked by Jane Street.

The United States uses the imperial system of weights and measures, which means that there are many different, seemingly arbitrary units to measure distance. There are 12 inches in a foot, 3 feet in a yard, 22 yards in a chain, and so on.

Create a data structure that can efficiently convert a certain quantity of one unit to the correct amount of any other unit. You should also allow for additional units to be added to the system.

Pull request:
Day325
Resolves #660.

Patch:
diff --git a/README.md b/README.md
index 2970460..d5171eb 100644
--- a/README.md
+++ b/README.md
@@ -328,3 +328,4 @@ problems from
 * [Day 322](https://github.com/vaskoz/dailycodingproblem-go/issues/654)
 * [Day 323](https://github.com/vaskoz/dailycodingproblem-go/issues/656)
 * [Day 324](https://github.com/vaskoz/dailycodingproblem-go/issues/658)
+* [Day 325](https://github.com/vaskoz/dailycodingproblem-go/issues/660)
diff --git a/day325/problem.go b/day325/problem.go
new file mode 100644
index 0000000..014b6c5
--- /dev/null
+++ b/day325/problem.go
@@ -0,0 +1,63 @@
+package day325
+
+import (
+	"errors"
+)
+
+// Unit represents a unit of measure.
+type Unit string
+
+// Converter knows how to convert from/to different
+// units of measure.
+type Converter struct {
+	table map[Unit]map[Unit]float64
+}
+
+// ErrConversionImpossible returns the error given when a conversion
+// isn't possible.
+func ErrConversionImpossible() error {
+	return errConversionImpossible
+}
+
+var errConversionImpossible = errors.New("conversion is impossible between these units")
+
+// Convert attempts to convert a value from one unit to another.
+// Uses a DFS algorithm to find a path to that conversion.
+func (c *Converter) Convert(val float64, from, to Unit) (float64, error) {
+	visited := make(map[Unit]struct{})
+	return c.convert(val, from, to, visited)
+}
+
+func (c *Converter) convert(val float64, from, to Unit, visited map[Unit]struct{}) (float64, error) {
+	if factor, found := c.table[from][to]; found {
+		return val * factor, nil
+	}
+	for nextTo, factor := range c.table[from] {
+		if _, seen := visited[nextTo]; seen {
+			continue
+		}
+		visited[nextTo] = struct{}{}
+		if result, err := c.convert(val*factor, nextTo, to, visited); err == nil {
+			return result, nil
+		}
+		delete(visited, nextTo)
+	}
+	return 0.0, ErrConversionImpossible()
+}
+
+// AddConversion adds a new conversion rule to the table in both directions.
+func (c *Converter) AddConversion(factor float64, from, to Unit) {
+	if _, exists := c.table[from]; !exists {
+		c.table[from] = make(map[Unit]float64)
+	}
+	if _, exists := c.table[to]; !exists {
+		c.table[to] = make(map[Unit]float64)
+	}
+	c.table[from][to] = factor
+	c.table[to][from] = 1.0 / factor
+}
+
+// NewConverter returns a pointer to a new Converter.
+func NewConverter() *Converter {
+	return &Converter{make(map[Unit]map[Unit]float64)}
+}


Test patch:
diff --git a/day325/problem_test.go b/day325/problem_test.go
new file mode 100644
index 0000000..b4822d8
--- /dev/null
+++ b/day325/problem_test.go
@@ -0,0 +1,81 @@
+package day325
+
+import (
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	val       float64
+	from, to  Unit
+	expected  float64
+	err       error
+	tolerance float64
+}{
+	{
+		10.0,
+		"in", "cm",
+		25.4,
+		nil,
+		0.05,
+	},
+	{
+		10.0,
+		"in", "km",
+		0.000254,
+		nil,
+		0.0000005,
+	},
+	{
+		10.0,
+		"in", "km",
+		0.000254,
+		nil,
+		0.0000005,
+	},
+	{
+		10.0,
+		"in", "ml",
+		0.0,
+		ErrConversionImpossible(),
+		0.0,
+	},
+}
+
+func TestConverter(t *testing.T) {
+	t.Parallel()
+	c := NewConverter()
+	c.AddConversion(12.0, "ft", "in")
+	c.AddConversion(5280.0, "mi", "ft")
+	c.AddConversion(1.609, "mi", "km")
+	c.AddConversion(1000, "km", "m")
+	c.AddConversion(100, "m", "cm")
+	c.AddConversion(3.0, "yd", "ft")
+	c.AddConversion(22.0, "chain", "yd")
+	for _, tc := range testcases {
+		if result, err := c.Convert(tc.val, tc.from, tc.to); err != tc.err || abs(result-tc.expected) > tc.tolerance {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.expected, tc.err, result, err)
+		}
+	}
+}
+
+func BenchmarkConverter(b *testing.B) {
+	c := NewConverter()
+	c.AddConversion(12.0, "in", "ft")
+	c.AddConversion(5280.0, "ft", "mi")
+	c.AddConversion(1.609, "mi", "km")
+	c.AddConversion(0.001, "km", "m")
+	c.AddConversion(0.01, "m", "cm")
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			c.Convert(tc.val, tc.from, tc.to) // nolint
+		}
+	}
+}
+
+func abs(a float64) float64 {
+	if a < 0 {
+		return -a
+	}
+	return a
+}