Thank you, this looks great.
515 karma · joined July 6, 2015
my public key: https://keybase.io/nathanleung; my proof: https://keybase.io/nathanleung/sigs/21RQELlB81U9ezo98QC5Ypm7DXkaUdVo--fOyCR9Gws
At the outset, `this.state` is initialized as an array of `1`s — [1, 1, 1, ... , 1] — the number of `1`s is based on the `size` parameter passed to the `Die` constructor. So for a 4-sided die, `this.state` would initially be `[1, 1, 1, 1]`.
`sum` is the accumulated sum of `this.state`, but it helped me to think of the `sum` variable as a number line. Continuing with the 4-sided die case, we'd have a number line of length 4 at initialization (sum of `[1, 1, 1, 1]`).
In the context of a number line, though, `this.state` can be thought of as giving the geometric positions of each possible result. `this.state[i]` simply gives the length of the valid region for a certain result. At initialization, each result of `1` to `4` of our four-sided die would have a length of 1 on the number line (again, `[1, 1, 1, 1]`).
In concrete terms, the region [0, 1) on the number line would yield a roll of `1`, the region [1, 2) would yield a roll of `2`, ... , the region [3, 4) would yield a roll of `4`.
With that in mind, we can think of `r` as choosing a random point on the number line between 0 and the end of the number line. At initialization, it simply chooses a point on [0, 4), since 4 is the length of our number line.
`runningSum` is our location on the number line. The code chooses a result here using the boolean expression `(r < runningSum)`, but it helped me to think of it in flipped terms: checking if `runningSum` is greater than or equal to `r`.
In essence, we're traversing the number line starting from 0.
Back to our four-sided die example: let's say `r`, the random point on the number line we got, was 2.5. At initialization we'd start by checking the region of the number line where `1` would be our result. Since `this.state[0]` (the length of the valid region for the result `1`) is 1, we can say that if we choose a point randomly on the number line [0, 4) and it is on the interval [0, 1), our roll is a 1.
However, 2.5 is not on [0, 1), so we add the length of the region where `1` is valid to `runningSum` (our location on the number line) so we can move on to the next region - the interval where `2` is our result. The length of this interval is stored in `this.state[1]`, and is also equal to 1 (`this.state` = `[1, 1, 1, 1]`). In terms of our number line, the valid interval is thus [1, 2). At this point, our location of the number line, `runningSum`, is 2: still less than 2.5.
Next, we'd get to the region for the result `3`, `this.state[2]`, and we'd be at [2, 3) on our number line. At this point, our `runningSum` (location on the number line) is 3, which is greater than `r` (the randomly chosen point on the number line), 2.5, and we have our result. (sidenote: the variable `result` being equal to `-1` is a sentinel value and prevents `4` also being considered a valid roll by virtue of it being greater than 2.5 as well. After this iteration, `result` is set to `2` - changed to `3` in the return statement).
The "magic" of the die comes in when traversing the number line over the non-valid regions, however. While we're traversing the number line, we're also resizing the valid regions for each result and extending the line for the next roll. If we go back to the example in the previous paragraphs with the 4-sided die, we saw that since `r` (our randomly chosen point on the number line), 2.5, was not on [0, 1), the result of our roll was not `1`. To increase the likelihood of `1` in the next roll, we increase the length of the number line and the region where `1` is our roll: `this.state` becomes `[2, 1, 1, 1]`, the valid region for a roll of `1` becomes [0, 2), and the size of the number line grows to 5 (however, this expansion of the number line does not apply to the current roll).
At the culmination of our first example above, `this.state` would be `[2, 2, 1, 2]` — we'd increase the size of the valid region for each result except for `3`, our result from the previous roll. For the next roll, we'd choose a random point on the number line between 0 and (2 + 2 + 2 + 1 = 7). In terms of probabilities, another `3` would be half as likely as a `1`, `2`, or `4`, independently.
roll() {
const sum = this.state.reduce((p, c) => p + c, 0)
const r = Math.random() * sum
let runningSum = 0
let result = -1
for (let i = 0; i < this.state.length; i++) {
const mark = this.state[i]
runningSum += mark
if(r < runningSum && result === -1) {
result = i
this.state[i] = 1
} else {
this.state[i]++
}
}
// Add 1, so the die roll is between 1 -> size of die
return (result + 1)
}Is there a simple way to explain CRC for someone with just a high school mathematics background?
As a current public high school student, I can assure you that the ivies are more selective than ever and kids who are being accepted nowadays are truly exceptional.
Capitalism tends towards winner-take-all systems, but not all winner-take-all systems are capitalistic. I find the example fitting.
Here's the gif: http://imgur.com/K5a7U9O.gif