-
Notifications
You must be signed in to change notification settings - Fork 32
/
problem.go
55 lines (48 loc) · 1.13 KB
/
problem.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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
}