Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 32
Good morning! Here's your coding interview problem for today.

This problem was asked by Jane Street.

Suppose you are given a table of currency exchange rates, represented as a 2D array. Determine whether there is a possible arbitrage: that is, whether there is some sequence of trades you can make, starting with some amount A of any currency, so that you can end up with some amount greater than A of that currency.

There are no transaction costs and you can trade fractional quantities.

Pull request description:
Day32
Resolves #72.

Patch:
diff --git a/README.md b/README.md
index cb95d25..f5a3865 100644
--- a/README.md
+++ b/README.md
@@ -43,6 +43,7 @@ problems from
 * [Day 29](https://github.com/vaskoz/dailycodingproblem-go/issues/67)
 * [Day 30](https://github.com/vaskoz/dailycodingproblem-go/issues/69)
 * [Day 31](https://github.com/vaskoz/dailycodingproblem-go/issues/71)
+* [Day 32](https://github.com/vaskoz/dailycodingproblem-go/issues/72)
 * [Day 33](https://github.com/vaskoz/dailycodingproblem-go/issues/73)
 * [Day 34](https://github.com/vaskoz/dailycodingproblem-go/issues/76)
 * [Day 35](https://github.com/vaskoz/dailycodingproblem-go/issues/77)
diff --git a/day32/problem.go b/day32/problem.go
new file mode 100644
index 0000000..97b32f8
--- /dev/null
+++ b/day32/problem.go
@@ -0,0 +1,41 @@
+package day32
+
+import "math"
+
+// Arbitrage calculates how much money is possibly made using arbitrage.
+// Assuming no transactional costs.
+// Uses Bellman-Ford Shortest Path which runs in O(N^3) time and O(N^2) space
+// due to the transformed rates table.
+func Arbitrage(rates [][]float64) bool {
+	graph := make([][]float64, len(rates))
+	for i := range graph {
+		graph[i] = make([]float64, len(rates[i]))
+		for j := range graph[i] {
+			graph[i][j] = -math.Log(rates[i][j])
+		}
+	}
+	source := 0
+	minDist := make([]float64, len(rates))
+	for i := range minDist {
+		minDist[i] = math.Inf(1)
+	}
+	minDist[source] = 0
+
+	for i := 0; i < len(graph)-1; i++ {
+		for v := range graph {
+			for w := range graph[v] {
+				if minDist[w] > minDist[v]+graph[v][w] {
+					minDist[w] = minDist[v] + graph[v][w]
+				}
+			}
+		}
+	}
+	for v := range graph {
+		for w := range graph[v] {
+			if minDist[w] > minDist[v]+graph[v][w] {
+				return true
+			}
+		}
+	}
+	return false
+}


Test patch:
diff --git a/day32/problem_test.go b/day32/problem_test.go
new file mode 100644
index 0000000..381a5ee
--- /dev/null
+++ b/day32/problem_test.go
@@ -0,0 +1,38 @@
+package day32
+
+import "testing"
+
+var testcases = []struct {
+	rates             [][]float64
+	arbitragePossible bool
+}{
+	{[][]float64{
+		{1, 0.741, 0.657, 1.061, 1.005},
+		{1.349, 1, 0.888, 1.433, 1.366},
+		{1.521, 1.126, 1, 1.614, 1.538},
+		{0.942, 0.698, 0.619, 1, 0.953},
+		{0.995, 0.732, 0.650, 1.049, 1},
+	}, true},
+	{[][]float64{
+		{1, 1, 1},
+		{1, 1, 1},
+		{1, 1, 1},
+	}, false},
+}
+
+func TestArbitrage(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := Arbitrage(tc.rates); result != tc.arbitragePossible {
+			t.Errorf("TC%d Expected %v got %v", tcid, tc.arbitragePossible, result)
+		}
+	}
+}
+
+func BenchmarkArbitrage(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			Arbitrage(tc.rates)
+		}
+	}
+}