Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 175
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

You are given a starting state `start`, a list of transition probabilities for a Markov chain, and a number of steps `num_steps`. Run the Markov chain starting from `start` for `num_steps` and compute the number of times we visited each state.

For example, given the starting state `a`, number of steps `5000`, and the following transition probabilities:
```
[
  ('a', 'a', 0.9),
  ('a', 'b', 0.075),
  ('a', 'c', 0.025),
  ('b', 'a', 0.15),
  ('b', 'b', 0.8),
  ('b', 'c', 0.05),
  ('c', 'a', 0.25),
  ('c', 'b', 0.25),
  ('c', 'c', 0.5)
]
```
One instance of running this Markov chain might produce `{ 'a': 3012, 'b': 1656, 'c': 332 }`.

Pull request:
Day175
Resolves #363.

Patch:
diff --git a/README.md b/README.md
index eede14d..7d0b448 100644
--- a/README.md
+++ b/README.md
@@ -185,6 +185,7 @@ problems from
 * [Day 171](https://github.com/vaskoz/dailycodingproblem-go/issues/356)
 * [Day 172](https://github.com/vaskoz/dailycodingproblem-go/issues/358)
 * [Day 173](https://github.com/vaskoz/dailycodingproblem-go/issues/360)
+* [Day 175](https://github.com/vaskoz/dailycodingproblem-go/issues/363)
 * [Day 176](https://github.com/vaskoz/dailycodingproblem-go/issues/364)
 * [Day 177](https://github.com/vaskoz/dailycodingproblem-go/issues/365)
 * [Day 178](https://github.com/vaskoz/dailycodingproblem-go/issues/367)
diff --git a/day175/problem.go b/day175/problem.go
new file mode 100644
index 0000000..ebe0dcc
--- /dev/null
+++ b/day175/problem.go
@@ -0,0 +1,55 @@
+package day175
+
+import (
+	"math/rand"
+	"time"
+)
+
+// State represents states in the Markov chain.
+type State string
+
+// Transition represents the probabilities of transitions.
+type Transition map[State]map[State]float64
+
+type probabilities map[State][]threshold
+
+type threshold struct {
+	s State
+	p float64
+}
+
+// RunMarkovChain runs the Markov chain from the start state for numSteps.
+// The result is the number of times each state occurred.
+func RunMarkovChain(start State, states Transition, numSteps int) map[State]int {
+	result := make(map[State]int)
+	probs := buildProbabilities(states)
+	r := rand.New(rand.NewSource(time.Now().UnixNano()))
+	for i := 0; i < numSteps; i++ {
+		p := r.Float64()
+		d := probs[start]
+		var last float64
+		for _, t := range d {
+			if p > last && p < t.p {
+				result[t.s]++
+				start = t.s
+				break
+			}
+			last = t.p
+		}
+	}
+	return result
+}
+
+func buildProbabilities(states Transition) probabilities {
+	result := make(probabilities)
+	for s1, sub := range states {
+		var data []threshold
+		var p float64
+		for s2, fl := range sub {
+			p += fl
+			data = append(data, threshold{s2, p})
+		}
+		result[s1] = data
+	}
+	return result
+}


Test patch:
diff --git a/day175/problem_test.go b/day175/problem_test.go
new file mode 100644
index 0000000..ca5c92c
--- /dev/null
+++ b/day175/problem_test.go
@@ -0,0 +1,66 @@
+package day175
+
+import "testing"
+
+var testcases = []struct {
+	start             State
+	states            Transition
+	numSteps          int
+	expected          map[State]int
+	expectedTolerance int
+}{
+	{"a", Transition{
+		"a": {
+			"a": 0.9,
+			"b": 0.075,
+			"c": 0.025,
+		},
+		"b": {
+			"a": 0.15,
+			"b": 0.8,
+			"c": 0.05,
+		},
+		"c": {
+			"a": 0.25,
+			"b": 0.25,
+			"c": 0.5,
+		},
+	}, 5000, map[State]int{
+		"a": 3100,
+		"b": 1500,
+		"c": 300,
+	}, 500},
+}
+
+func TestRunMarkovChain(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := RunMarkovChain(tc.start, tc.states, tc.numSteps); !close(result, tc.expected, tc.expectedTolerance) {
+			t.Errorf("Expected %v, got %v", result, tc.expected)
+		}
+	}
+}
+
+func BenchmarkRunMarkovChain(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			RunMarkovChain(tc.start, tc.states, tc.numSteps)
+		}
+	}
+}
+
+func close(a, b map[State]int, tolerance int) bool {
+	for s, cnt := range a {
+		if abs(cnt-b[s]) > tolerance {
+			return false
+		}
+	}
+	return true
+}
+
+func abs(a int) int {
+	if a < 0 {
+		return -a
+	}
+	return a
+}