Opportunity to write some idiomatic Julia code

My entry for “most readable”:

struct Roll{R} end
LowRoll  = Union{Roll{1},Roll{2},Roll{3}}
HighRoll = Union{Roll{4},Roll{5},Roll{6}}

roll() = Roll{rand(1:6)}()

O6()   = D6(roll())
O6(r0) = (r0 == 1 || r0 == 6) ? D6(r0, roll(), r0, "") : (r0, "")

O6(::LowRoll,   ::HighRoll, result, mark) = (result, mark)  # stop rolling
O6(::HighRoll,  ::LowRoll,  result, mark) = (result, mark)  # stop rolling
O6(::Roll{1},   ::Roll{1},  result, mark) = D6(Roll{1}(), roll(), result-1, "fumble")
O6(::Roll{6},   ::Roll{6},  result, mark) = D6(Roll{6}(), roll(), result+1, "critical")
O6(::LowRoll,  r::LowRoll,  result, mark) = D6(r, roll(), result-1, mark)
O6(::HighRoll, r::HighRoll, result, mark) = D6(r, roll(), result+1, mark)

Obviously that’s painfully slow. Assuming external packages are allowed, this one is much faster while still being quite readable:

using MLStyle

roll() = rand(1:6)

@active LowRoll(roll)   roll ≤ 3
@active HighRoll(roll)  roll ≥ 4

O6() = O6(roll())
O6(first_roll) = @match first_roll begin
    1 || 6 => O6(first_roll, roll(), first_roll)
    _      => (first_roll, nothing)
end

O6(r1, r2, result, mark=nothing) = @match (r1, r2) begin
    (1, 1)                   => O6(1,  roll(), result-1, Some("fumble"))
    (6, 6)                   => O6(6,  roll(), result+1, Some("critical"))
    (LowRoll(), LowRoll())   => O6(r2, roll(), result-1, mark)
    (HighRoll(), HighRoll()) => O6(r2, roll(), result+1, mark)
    _                        => (result, mark)
end
1 Like

I think I got the loopless version working. The mark probability can be seen as a function of the number of modifying steps. In this way, it is similar to the probability of getting two heads in a row after n throws of an unfair coin (in this case 1/3 heads, 2/3 tails). This probability I took from (Two Heads in A Row: With Unequal Probability | ELEC424 Wiki | Fandom), although there’s not a derivation so I’m not entirely sure it’s correct. Nonetheless, here’s my revised code.

using Distributions
D(x) = rand(1:x)
P(m) = m <= 1 ? 0 : P(m - 1) + (1 - P(m - 1)) / 3 - (1 - P(m - 2)) * (2 / 9)
function O(x) 
    roll, modifier = D(x), rand(Geometric(0.5))
    if (roll == x || roll == 1) && rand() <= P(modifier)
        println(roll == x ? "$(roll + modifier) critical" : "$(roll - modifier) fumble")
    else
        println(roll == x ? roll + modifier : roll == 1 ? roll - modifier : roll)
    end
end

Unfortunately, it’s still not smaller than the looped version, and it certainly makes it less readable, so not sure if there’s any real benefit to this version

2 Likes

Thanks. This was really instructive for me. I am new to Julia but attracted to it for various reasons. This thread pushed my motivation to go deeper into Julia. BTW (it’s my GitHub repo - the O6 is a way for me to learn new languages).

10 Likes

Oh, also, just for kicks – here’s one which is (i) more compact than the Forth example, (ii) arguably much more readable, and (iii) quite fast (BenchmarkTools.jl gives it a median runtime of ~21ns):

using MLStyle

O6() = O6(rand(1:6))                                                               
O6(r0) = (r0 == 1 || r0 == 6) ? O6(r0, rand(1:6), r0) : (r0, nothing)
O6(r1, r2, result, mark=nothing) = @match (r1, r2) begin                         
    if r1 ≤ 3 && r2 ≤ 3 end => O6(r2, rand(1:6), result-1, r1 == r2 == 1 ? Some("fumble") : mark)
    if r1 ≥ 4 && r2 ≥ 4 end => O6(r2, rand(1:6), result+1, r1 == r2 == 6 ? Some("critical") : mark)
    _                       => (result, mark)
end
4 Likes

My entry for most compact code. I combined everything into one giant ternary statement, and since that felt like cheating, I split the line for (marginally) easier to read code

using Distributions
P(m) = m <= 1 ? 0 : P(m - 1) + (1 - P(m - 1)) / 3 - (1 - P(m - 2)) * (2 / 9)
function O(x) 
    r, m = rand(1:x), rand(Geometric(0.5))
    println(r == x ? (rand() <= P(m) ? "$(r + m) critical" : r + m) : 
        (r == 1 ? (rand() <= P(m) ? "$(r - m) fumble" : r - m) : r))
end
2 Likes

And another version of the same length, but not using any packages

rand_geometric(x = 0) = rand(Bool) ? rand_geometric(x + 1) : x
P(m) = m <= 1 ? 0 : P(m - 1) + (1 - P(m - 1)) / 3 - (1 - P(m - 2)) * (2 / 9)
function O(x) 
    r, m = rand(1:x), rand_geometric()
    println(r == x ? (rand() <= P(m) ? "$(r + m) critical" : r + m) : 
        (r == 1 ? (rand() <= P(m) ? "$(r - m) fumble" : r - m) : r))
end

Won’t the median runtime be counting only the cases where the first throw is 2-5 (because this accounts for more than 50% of the cases and they are the fastest cases)? If so, it’s not a very meaningful metric to look at because it excludes almost all of the code.

3 Likes

On a general note, one can treat all rolls beyond 1 and 6 in the same loop, with a roll of 4-6 adding 1 to an accumulating “open” score and only afterwards checking if that accumulated open score is to be treated as an addition or subtraction to the original dice roll (if the original dice roll was a 1, subtract the accumulated open score and add if the original roll was a 6). The same goes for Criticals and Fumbles, two consecutive 6s is a Critical if the original roll was a 6 and a Fumble if the original roll was a 1 (but remember to then treat the original roll of 1 as a “6” for this purpose). This is how I wrote the FOCAL program (for the HP-41 calculator).

Yes, several of the implementations above do this, e.g. this one.

I like this, this almost reads like Haskell :wink:

Conditional on the first draw being 1 or 6, the subsequent sequence length has geometric distribution with p = 1/2, but no simple closed form solution occurs to me for the probability of “critical” or “fumble” (eg conditional on the sequence length).

A standard trick would be formulating it as an absorbing Markov chain with the state being the current roll and whether critical/fumble has happened.

I know - just wanted to make it into a general note.

1 Like

I like this, this almost reads like Haskell 

I want to get into Haskell - would you like to make a Haskell-attempt on this?

Also what is the “Some” in "Some(“fumble”) do?

Damn, how do I blockquote correctly here (with the person I reply to included)?

I’ll have a look but I am currently overloaded with other stuff :see_no_evil:

Some resembles an “option type”. Such things are quite usual in functional languages to model data which might or might not be there/returned. This way you can write fluid and type safe code (chaining functions into each other) without any explicit error checking layers.

1 Like

I implemented the probabalistic implementation, including the modifier being a geometric distribution, here: Opportunity to write some idiomatic Julia code - #11 by Ian_Slagle . The question of whether a “fumble” or “critical” happening is formulated as the chance of two heads being flipped in a row in a biased coin (1/3 for heads).

Since that, I reworked it to be a little smaller here: Opportunity to write some idiomatic Julia code - #15 by Ian_Slagle

Using an Absorbing Markov Chain as its own type might be far more idiomatic, though

1 Like

Just select the text you want to quote, and click the “Quote” button that pops up. See the “quoting” section in these discourse tips.

1 Like

Merged. Thanks.

I am impressed by the Julia community here. Thanks for the learning opportunity.

6 Likes

I am not sure, that’s just brute-forcing the problem. I did not find a derivation of the formula you use here, and currently I don’t have the bandwidth to play around with combinatorics (as much as I love to), but if there is a neat closed form, then the whole thing can be done like this:

  1. first draw: branch on 1, 6, or anything else
  2. 1 and 6 are symmetric, so only one of them needs to be handled. the number of additional draws n follows a geometric distribution with p = 1/2
  3. if there is a closed-form expression for critical/fumble conditional on n, just generate a flag with that

In any case, this is just an interesting math exercise, and should not be considered a solution to the original one — it is my understanding that it is meant to display various languages coding the same algorithm.

2 Likes