TL;DR

Double-checking the solution to a puzzle with brute force.

So I had a puzzle equivalent to the following:

Consider a display with $N$ digits in base $b$. A random value id shown on the display; each possible value is equiprobable. What is the expected number of missing digit values?

As an example, suppose that we consider base-4 digits (i.e. 0 to 3) and a display that has 6 slots. An example value shown on the display would be 232133, which includes digits 1, 2, and 3 but not digit 0. In this arrangement, digit 0 is considered missing. Similarly, in arrangement 111111 there are three missing digits, namely 0, 2, and 3.

# To the whiteboard!

To calculate the expected value, we have to know two things:

• what are the possible values $m$ that this quantity can take;
• what is the probability $P_m$ of each of those values.

When we know these two, we can calculate the expected values as follows:

$E_{\mathbf{missing}} = \sum_{m} P_m m$

In our case, each value on the display will show at least 1 digit and at most the minimum between $N$ and $b$, so:

• if $N >= b$, the number of missing digits will range from 0 (because all digits might appear at the same time on the display) to $b - 1$;
• otherwise, the display is short and the number of missing digits will range from $b - N$ to $b - 1$.

In summary, $m_i$ is an integer whose minimum value is $max(0, b - N)$ and whose the maximum value is $b - 1$, so our expected value formula becomes:

$E_{\mathbf{missing}} = \sum_{m = max(0, b-N)}^{b-1} P_m m$

So… we’re just left with figuring out the probabilities!

# Brute force, at least

In the specific puzzle I had to solve, I did it with pen-and-pencil and came out with the answer ($\frac{2916}{4096} = \frac{729}{1024}$).

Then I thought… better double check with some code! So I used the following code in Raku:

#!/usr/bin/env raku
use v6;
subset PositiveInt of Int where * > 0;
sub MAIN (PositiveInt:D :display-size($ds)!, PositiveInt:D :$base!) {
my $total =$base ** $ds; my %count-for; for 0 ..^$total -> $i { my$display = (('0' x $ds) ~$i.base($base)).substr(*-$ds);
my $n-present = set($display.comb).elems;
%count-for{$base -$n-present}++; # increase "absents" count
}
my $num = reduce({$^a + $^b.key *$^b.value}, 0, %count-for.Slip);
put "$num /$total ≅ {$num /$total}";
}


Let’s see:

$raku missing.raku --display-size=6 --base=4 2916 / 4096 ≅ 0.711914  So I was right! But what are we doing exactly? Brute-forcing, of course! We generate all possible configurations for the display and count the number of missing digit values, keeping a tally of how many this count appears. So it’s the same count we did before, only at a much lower level. To generate all possible values we just count from$0$to$b^N - 1$. The display is then generated by converting the iteration value into base$b$, adding leading 0 characters in order to fill in all slots in the display (to do this, we add$b$leading 0 character, then take the last$b$characters from the resulting string. Crude but effective). The display is then split digit by digit (using .comb), then the digits are fit into a set, so that we can later count (.elem) how many digit values do appear ($n-present). To get the missing ones, we subtract this amount from $b$ and we are done.

The last part calculates the expected value. All probabilities are the counts we accumulated divided by $total, so we first calculate the numerator in $num and then divide it at the end. The reduce function is perfect here, because we want to do a sum but also do some calculation for getting the right value to add.

Well it’s been funny… for me 😄 I hope you enjoyed it too!