Little Puzzlers–Fun With Random Number Generators

June 8, 2015 · 1 min read

I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.

Problem 1

Let’s play with narrowing down a random number generator evenly.

Assume you are given a random-number generation function called Rand4() that generates a random number from 1 to 4 inclusively (i.e. 1, 2, 3, or 4) with equal probability and eventually even distribution.  That is, you may get several 3s in a row, but over the long term the number of 1s, 2s, 3s, and 4s are the same.

Given the Rand4() function, create a Rand3() function that also has equal probability and distribution for numbers from 1 to 3 inclusively.

Problem 2

Now, let’s go the other way and expand!

Given a Rand5() that generates a random number from 1 to 5 inclusively with equal probability and eventually even distribution, create a Rand7() function that also has equal probability and distribution for numbers from 1 to 7 inclusively.

Note

Remember!  The primary focus on both of these we want to preserve the equal probability and even distribution.  That said, we also want to preserve the “randomness” as well.  Of course, efficiency is preferable as well, but not at the cost of these other traits.

Spoiler Alert!

Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below. Read at your own risk.

This article is part of the GWB Archives. Original Author: James Michael Hare

New on Geeks with Blogs

  • We Won The One Award I Actually Care About

    Full Scale made the Inc. 5000 for the fifth year straight, the 12th listing across my three companies. Here is why the one award you cannot buy is worth stopping for.

  • Your Customers Build the Features Now

    I let a tool I liked sit dead for a year rather than build the features I wanted. An MCP server meant I never had to, and your customers can do the same to your product.

  • Get the Size of a Directory in Linux the Easy Way

    du -sh for the quick answer, ncdu for the cleanup, df for the disk itself: every command for checking directory size in Linux, plus why du and df never agree.

  • Vim Search and Replace: The Ultimate Guide

    One :%s command replaces every match in a file before a find dialog would even open. The Vim substitute patterns worth the muscle memory: flags, ranges, capture groups, and multi-file edits.