# ETOOBUSY ðŸš€ minimal blogging for the impatient

# AoC 2016/11 - Initial algorithm: Dijkstra

**TL;DR**

On with Advent of Code puzzle 11 from 2016: using Dijkstra Algorithm as an initial solution.

In the last post of this series (AoC 2016/11 - Initial data structure)
we left with two data structures populated for the task: the *initial
state* and the *goal state*.

In itself, the problem can be thought as a search over a directed graph.
Each *state* is represented as a **node** in the graph, while
*transitions* are represented by **edges**. In our case, we have to find
the length of the *shortest path* from the initial to the goal state.

Does this ring a bell?

Thereâ€™s a whole host of algorithms on shortest paths, and one of the most celebrated has been described by Edsger
Dijkstra. This is interesting because this algorithm applies to the
cases where we want some *locality*, i.e. it deals with a *single source*
and a *customizable set of goals* (that is, one in our case).

I recently wrote about my implementation DijkstraFunction in cglib (see Dijkstra Algorithm - as functions only for the details), and that is the one we will reuse here:

```
use DijkstraFunction 'dijkstra';
...
my $outcome = dijkstra(
start => \@start,
goals => [\@goal],
distance => sub { 1 },
successors => \&successors_for,
identifier => \&id_of,
);
say $outcome->{distance_to}->(\@goal);
```

The output of the function is a hash with two keys. The one we are
actually interested into here is only `distance_to`

, because itâ€™s what the
puzzle asks us. We might also print out the whole solution using
`path_to`

, though.

The function requires us a few input parameters:

`start`

: this is easy because we can provide our starting state as a reference to the array`@start`

, which we built in the previous post in this series;`goals`

: this is a reference to an array containing a list of goals we are interested into. In our case, we just provide one, that is a reference to array`@goal`

;`distance`

: in the algorithm, edges between nodes might have a variable weight. In our case, two adjacent nodes represent states that are separated by a single step of the elevator, so the cost of each action is always`1`

;`successors`

: a reference to a sub that takes a state as input, and provides back a list of states that can be reached. In graph terms, it provides all nodes that can be reached from a specific node (remember, the graph is directed!);`identifier`

: each node in the graph must be recognized by an*identifier*, so that we can properly track when we land on the same node time and again. This function takes care to look into a node/state and produce a suitable identifier that is always consistent (i.e. identical states yield the same identifier, even if they come from two different underlying arrays).

At this pointâ€¦ we only lack `successors_for`

and `id_of`

, right? This
will be meat for future posts!

Before concluding, anyway, a little word on the choice of the algorithm.
The A* Algorithm might just as well address our concerns, and in
a more efficient way. Butâ€¦ that algorithm requires us to build
a *heuristic* on our estimation of how distant we are from the solution,
and this must also be either exact (in which case we would already have
the solution!) or *underestimate* the actual value. Which meansâ€¦ more
work for the programmer! Hence, at this stage we keep it simpler and stick
with Dijkstra Algorithm instead.