teryror

/*******************************************************************************
Author: Tristan Dannenberg
Notice: No warranty is offered or implied; use this code at your own risk.
********************************************************************************
Approximate algorithm for generating length-limited prefix codes.

I came up with this idea while working on an animation of Huffman's algorithm,
and had a convincing informal argument for it being optimal.

Comparison with Package/Merge shows this to be false for heavily skewed symbol

teryror

Unbiased Range Reduction of Pseudo-Random Numbers

Suppose you're working on a virtual board game and want to simulate the roll of a die. The first programming book I ever owned suggested the following:

int result = rand() % 6;

If you've spent any time reading about random numbers in computer science, you've probably heard that this is a bad idea. The reason that's usually given is that rand() (just like the standard RNGs of many other languages, such as

teryror

Monte-Carlo Permutation Testing

Near the end of my first statistics class, I was introduced to the concept of a hypothesis test: given two sample sets, determine the probability that they were drawn from the same population. If this is less than your desired p-value (typically 5% or less, depending on your field), you can reject the [null-hypothesis][1] and accept the alternative hypothesis that the two samples are indeed from different populations.

This was presented to me in the context of social sciences, but it comes up in

teryror

Random Sampling Without Replacement

Last time we talked about rolling unbiased virtural dice, now let's turn to opening virtual booster packs in a collectible card game. If you're a nerd like me, you may be interested in reading about the specifics of how cards are distributed in [Magic: The Gathering][2] and [Yu-Gi-Oh!][3], but our main concern here is to randomly select n items from an array of N options. I'm told that it's also useful in scientific computing or whatever.

teryror

/*

Based on Frank Karsten's "How Many Colored Mana Sources" simulation code
(see his article [1], original source code found at [2]).

[1]: https://strategy.channelfireball.com/all-strategy/channelmagic/channelmagic-articles/how-many-colored-mana-sources-do-you-need-to-consistently-cast-your-spells-a-guilds-of-ravnica-update/
[2]: https://pastebin.com/9P5kwqt1

Updated to account for the London Mulligan rule change, and expanded to
account for more restrictive casting costs and different land counts.

teryror

use rand::prelude::*;
use std::collections::HashMap;
use std::fmt::Write;

#[derive(Copy, Clone, PartialEq, Eq)]
enum CardType {
    NonLand,
    Land,
    GoodLand,
}

teryror

use num_bigint::BigUint;
use num_traits::ToPrimitive;

// calculate the binomial coefficient `n choose k`
fn binomial_coefficient(n: u32, k: u32) -> u64 {
    let mut result = BigUint::from(1u32);
    for i in 0..k {
        result = (result * (n - i)) / (i + 1);
    }
    result.to_u64().unwrap()

teryror

Redesigning coca's Storage Abstraction

This post was written primarily to organize my thoughts during the design process. I'll explain the thought process that led me to each point in the design space we visit, then point out any issues, which will lead into the next iteration. Along the way, I made a few errors, which I'll try to rectify in the (Side Notes).

Here we go!

Introduction: The Status Quo

teryror

fn binomial_coefficient(n: u32, k: u32) -> u128 {
    let mut res = 1u128;
    for i in 0..k {
        res = (res * (n - i) as u128) / (i + 1) as u128;
    }
    res
}

fn neg_binom_pmf(k: u32, r: u32, p: f64) -> f64 {
    assert!(r > 0);

teryror

fn binomial_coefficient(n: u32, k: u32) -> u128 {
    let mut res = 1u128;
    for i in 0..k {
        res = (res * (n - i) as u128) / (i + 1) as u128;
    }
    res
}

fn neg_binom_pmf(k: u32, r: u32, p: f64) -> f64 {
    assert!(r > 0);