Weighted 🏋️ Random generator in Typescript (with Test Driven Development 🧪)

Post contents

You can find a video version of this article on my YouTube Channel.

Intro

Today we're building together a weighted random generator. You may also know it as a random loot table generator, or gacha system.

In short, what it does is extract a random object considering its weight. An object with a higher weight is more likely to be picked up than an item with a smaller weight (or call it chance).

As a side quest, we're going to keep code coverage at 100% ✅

• Intro
  • Output
• Development
  • Typing
  • Core class
  • Validation
  • Standalone
  • Going further

An embedded webpage:Test Driven Development (TDD) Example - RANDOM LOOT TABLE

Output

The final result is already available on GitHub (there are open issues to pick up!).

You can also install it from npm and deno.

If you're on node, you can install it with npm i wrand and you can use it like so:

const picker = new RandomPicker(items);const result = picker.pick();const results = picker.pickMany(3);

Development

As seen in the preview, we're going to build a generator (with a class) that takes an array of objects in the constructor and will spit out randomly picked items with two methods: pick and pickMany.

Typing

As we're in Typescript, let's start by giving a type definition to our input.

export type WeightedItem<T> = {  original: T;  weight: number;};

Our type will have two fields, one to keep the original items we passed in, and the other to store its weight (or chance, probability). A heavier weight means more likely to be picked up.

Core class

To add some more informative content, we'll build this up with a little bit of Test Driven Development (TDD).

We can create a new file, randomGenerator.ts with the skeleton of the final product.

export class RandomPicker<T> {  constructor(private items: WeightedItem<T>[]) { }  pick(): T {    throw new Error("Not Implemented!");  }  pickMany(amount: number): T[] {    throw new Error("Not Implemented!");  }}

Before writing the implementation, we have to write the tests! This approach helps write code that is more reliable and with fewer bugs as you focus on the business logic first, and only after that on the implementation.

In this case, I'm using Jest, so npm i jest to have it running.

In my tests, I want to make sure that:

1. The class is instantiated properly.
2. A random item is picked and comes from my list.
3. N random items are picked, exactly the amount I requested and all of them are in the list.
4. Works not only with strings but also with objects.

const items = [  { original: "Bronze", weight: 20 },  { original: "Silver", weight: 10 },  { original: "Gold", weight: 3 },  { original: "Platinum", weight: 1 },];describe("RandomPicker", () => {  it("should be created with a list of items with their weight", () => {    const picker = new RandomPicker(items);    expect(picker).toBeDefined();  });  it("should be able to pick an item", () => {    const picker = new RandomPicker(items);    const pickedItem = picker.pick();    expect(items.some((i) => i.original === pickedItem)).toBeTruthy();  });  it("should be able to pick N items", () => {    const picker = new RandomPicker(items);    const picked = picker.pickMany(3);    expect(picked.length).toBe(3);    expect(      picked.every((p) => items.some((i) => i.original === p))    ).toBeTruthy();...

Note: To improve the tests even more, there's an open issue about passing a custom random generator. This could allow to set a generator with a specific seed (Math.random can't do that) and make the tests predictable, rather than entirely random.

Now that the tests are written, we can proceed with the implementation.

export class RandomPicker<T> {  constructor(private items: WeightedItem<T>[]) {    this.updateTotalWeight();  }  pick(): T {    const random = Math.random() * this.totalWeight;    let currentWeight = 0;    for (const item of this.items) {      currentWeight += item.weight;      if (random < currentWeight) {        return item.original;      }    }    /* istanbul ignore next */    throw new Error(      "No idea why this happened, get in touch with the wrand developer!"    );  }  pickMany(amount: number): T[] {    const items = [];    for (let i = 0; i < amount; i++) {      items.push(this.pick());    }    return items;  }...

If we run the test now, they're all green and 100% code coverage ✅

Validation

Let's add some validation to our input. As usual, tests first!

This time we want to check that:

1. The list is not empty
2. There are no duplicates
3. There are no negative weights

  it("should throw an error if created with a wrong set of items", () => {    // Duplicate item    expect(      () => new RandomPicker([...items, { original: "Platinum", weight: 5 }])    ).toThrow();    // Empty list    expect(() => new RandomPicker([])).toThrow();    // Negative weight    expect(      () => new RandomPicker([{ original: "Wood", weight: -5 }])    ).toThrow();  });

Tests are looking good, we can implement the validation method.

  private validate(items: WeightedItem<T>[]) {    if (items.length === 0) {      throw new Error("Items list is empty!");    }    const set = new Set();    for (const item of items) {      if (item.weight <= 0) {        throw new Error(          `All weights must be positive! ${item.original} has weight ${item.weight}`        );      }      if (set.has(item.original)) {        throw new Error(`Items must be unique! ${item.original} is duplicate!`);      }      set.add(item.original);    }  }

npm run test and it's all green and 100% again! ✅

Standalone

With the current implementation, to pick one item only you need to explicitly create the RandomGenerator instance and call pick on it.

As we're building a library, it might be useful to also provide some standalone methods that do everything under the hood so that one can directly call pick or pickMany without seeing the logic behind it.

export const pick = <T>(items: WeightedItem<T>[]) =>  new RandomPicker(items).pick();export const pickMany = <T>(items: WeightedItem<T>[], amount: number) =>  new RandomPicker(items).pickMany(amount);

Going further

The core implementation is done and the requested functionalities described at the beginning are already working.

As I mentioned, the library is Open Source and the code is available on GitHub. I'm repeating it because this means it's open to contributions and for example, you're free to pick up some of the open issues.

In the meantime, the library has been extended with more utility methods (getItems, getWeights, getTotalWeight, getCount) and also an extra standalone method to flatten the items in case you have duplicates and you want to aggregate their weights.

Feel free to jump on GitHub and extend it, even more, I'm waiting for your Pull Requests! :)

An embedded webpage:Test Driven Development (TDD) Example - RANDOM LOOT TABLE

Thanks for reading this post, I hope you find it interesting! Feel free to follow me to get notified when new articles are out ;)

Leonardo Montini

113 articles • 89,288 words

View profile

Awarded GitHub Star since 2023 ⭐️ and Microsoft MVP since 2024 🔷 I talk about Open Source, GitHub, and Web Development. I also run a YouTube channel called DevLeonardo, see you there!

You can also follow me on your favourite platform!