# ETOOBUSY đźš€ minimal blogging for the impatient

# AoC 2016/11 - New heuristic

**TL;DR**

On with Advent of Code puzzle 11 from 2016: a new heuristic for evaluating our distance to the end goal.

While we are at it, itâ€™s also time to take a closer look at the
*heuristic* function that we use to guess how far we are from the
destination.

To stress this fact, we will name the function as `distance_to_goal`

;
although it takes two states as input, the goal state is actually
ignored here because we will assume that itâ€™s always to bring everything
down to the lowest octet in both `generators`

and `microchips`

.

As already observed in New algorithm: A*, the *heuristic*
is a good one for A* only if itâ€™s either correct, or it
*underestimates* the distance. Otherwise, we would risk finding a
sub-optimal solution, which would spoil the fun in this puzzle.

Withouth further ado, hereâ€™s the `distance_to_goal`

function that we
will adopt:

```
1 sub distance_to_goal ($node, $goal) { # we *know* what the goal is
2 my ($g, $m) = $node->@{qw< generators microchips >};
3 my $d = 0;
4 my $mask = 0x80000000;
5 my $count = 0;
6 for my $w (3, 2, 1) {
7 for (1 .. 8) {
8 $count++ if $g & $mask;
9 $count++ if $m & $mask;
10 $mask >>= 1;
11 }
12 next unless $count;
13 $d++; # at least one movevement with one or two items
14 $d += 2 * ($count - 2) if $count > 2; # back and forth for the rest
15 } ## end for my $w (3, 2, 1)
16 return $d;
17 } ## end sub distance_to_goal
```

We are counting how many steps it would take us to complete the puzzle
if we had no constraint on the simultaneous placement of generators and
microchips. This ensures that we have an *underestimation*, because that
added constraint is what requires us to take extra steps.

At each floor (line 6) we count the number of generators and the number
of chips that we have, by using a moving bit in `$mask`

(lines 7 to 11).
We will assume that the elevator starts from floor 1, but it will not
determine moves until we find something.

Next, we count how many steps it would take us to bring all the microchips and generators from the current floor to the next one. This is only done if there are any, of course (line 12), and proceeds like this:

- we have to take at least one step to bring one or two items, which accounts for line 13;
- whatever goes beyond two items will be transported singularly (because the elevator must go back to take anything else) and will determine a back-and-forth, hence two steps as shown in line 14.

When this has been done, `$count`

is ready to be potentially
*incremented* with the items that were already in the destination floor,
i.e. we are ready for the next iteration of the loop in line 6.

After scanning all three floors like thisâ€¦ we can return the total minimum distance found so far (line 16).

I hope it was all clear! Possibly it might be smarterâ€¦ but itâ€™s better
than before, *admissible* and for the time being we can just wait to use
it!

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