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!

ETOOBUSY 🚀 minimal blogging for the impatient

Brute forcing a puzzle

To the whiteboard!

Brute force, at least