# ETOOBUSY ðŸš€ minimal blogging for the impatient

# Brute forcing a puzzle

**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

missingdigit 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!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*