bigjocker's den

FiveThirtyEight – The Puzzle Of The Monsters’ Gems

I follow FiveThirtyEight on twitter (and so should you if you like stats and math in general). They publish a weekly puzzle every Friday, and the submission deadline is Sunday 11:59pm. I’ve tried to solve a few of them, but have never submitted a response. This is my response for this week’s puzzle which you can read here. Please continue reading for my (most likely wrong) solution.

The problem reads:

A video game requires you to slay monsters to collect gems. Every time you slay a monster, it drops one of three types of gems: a common gem, an uncommon gem or a rare gem. The probabilities of these gems being dropped are in the ratio of 3:2:1 — three common gems for every two uncommon gems for every one rare gem, on average. If you slay monsters until you have at least one of each of the three types of gems, how many of the most common gems will you end up with, on average?

I’m no mathematician, and even though I love Numberphile in youtube (I’ve probably watched every video a couple of times, I usually download them and watch them in long flights) I’m not sure I can tackle this puzzle just using math. So my solution is to create a simulation and run it a bazillion times and see what the average is.

The idea of the simulation is simple: generate a random number and use the 3:2:1 ratio to decide whether a common, uncommon, or rare gem was dropped. The Math.random() method is used to generate the random number (the random number is between 0 and 1), and the following block is used to decide the gem type:

if (gem < VideoGame.COMMON_RATIO) {
	common++;
} else if (gem < VideoGame.UNCOMMON_RATIO) {
	uncommon++;
} else {
	rare++;
}

Where VideoGame.COMMON_RATIO and VideoGame.UNCOMMON_RATIO are defined as:

COMMON_RATIO = 5.0/10.0;
UNCOMMON_RATIO = (5.0 + 20.0 / 6.0) / 10.0;

This is found by converting the ratios to the 0..1 range:

// c -> 3*10/6 = 5
// u -> 2*10/6 = 20/6
// r -> 1*10/6 = 10/6

The simulation output is in the format iteration_count,average_of_common_gems_dropped (and then outputs the grand total, with a beautiful floating point rounding up error included), which makes it easier to feed into gnuplot or any similar software to get a chart. The program runs the simulation 10,000 times, and each time it simulates 100,000 games. So after 1,000,000,000 games the average was:

Average: 3.6499951070000125

UPDATE: Turns out I have the correct result

The scatter plot makes it look like I know what I’m doing:

Which I’m pretty sure must mean something important.

Here’s the full source code for the program:

package com.bigjocker.fivethirtyeight;

public class VideoGame {
	// 3:2:1 (c:u:r) expressed in base 10 is:
	//
	// c -> 3*10/6 = 5
	// u -> 2*10/6 = 20/6
	// r -> 1*10/6 = 10/6
	
	public static final double COMMON_RATIO = 5.0/10.0;
	public static final double UNCOMMON_RATIO = (5.0 + 20.0 / 6.0) / 10.0;

	private int common = 0;
	private int uncommon = 0;
	private int rare = 0;

	public VideoGame() {
	}

	public void reset() {
		common = 0;
		uncommon = 0;
		rare = 0;
	}

	public void execute() {
		while (common == 0 || uncommon == 0 || rare == 0) {
			double gem = Math.random();

			if (gem < VideoGame.COMMON_RATIO) {
				common++;
			} else if (gem < VideoGame.UNCOMMON_RATIO) {
				uncommon++;
			} else {
				rare++;
			}
		}
	}
	
	public static double runSimulation(long iterations) {
		double commonTotal = 0;
		double count = 0;
		
		VideoGame game = new VideoGame();
		for (int i = 0; i < iterations; i++) {
			game.reset();
			game.execute();

			commonTotal += game.common;
			count++;
		}

		return commonTotal/count;
	}

	public static void main(String[] args) {
		double commonTotal = 0;
		double count = 0;
		for (int i = 0 ; i < 10000 ; i++) {
			double result = VideoGame.runSimulation(100000);
			System.out.println(i + "," + result);
			
			commonTotal += result;
			count++;
		}
		
		System.out.println("Average: " + (commonTotal / count));
	}
}

1 comment for “FiveThirtyEight – The Puzzle Of The Monsters’ Gems

  1. Sam Fahey
    May 23, 2016 at 8:24 pm

    Thanks for the sanity check! From the math, I got an average number of 7.3 drops needed. 7.3*(50% Common gems) = 3.65. If you want to work out the solution before it’s posted on Friday, I used logic very similar to that described here: http://math.stackexchange.com/questions/28905/expected-time-to-roll-all-1-through-6-on-a-die

Leave a Reply

Your email address will not be published. Required fields are marked *