# ETOOBUSY đźš€ minimal blogging for the impatient

# AoC 2022/24 - These elves require a lot of patience...

**TL;DR**

On with Advent of Code puzzle 24 from 2022: these elves can beâ€¦

Iâ€™m always happy when I can use Astar.raku and, believe it or not, this was one of those occasions.

Of course, this is only one tiny part, where the really challenging part is about finding a proper representation that can be fed to the A* module.

## Field representation

Letâ€™s start with the representation of the field. I called this class
`Field1`

, anticipating some need for a different representation for part
2, only to discover that it was OK for both with little modifications.

Letâ€™s start with the member variables:

```
class Field1 {
has $!size-x is built;
has $!size-y is built;
has @!layers is built;
has @!permutations;
has @!state-at;
has $!period;
has @!adjacents-for;
```

The field itself is kept as an array, with all rows putâ€¦ in a row.
Each possible â€śmovementâ€ť will then be encoded as a specfici
`@!permutation`

over the array.

Each blizzard points in a single direction and is basically independent
of other blizzards. It makes sense to separate blizzards going in the
four directions into separate `@!layers`

, so that the movement
permutation applied to each layer is always the same and only depending
on the (unchanging) direction.

Each direction is necessarily periodic; the overall structure has a
`$!period`

that is equal to the *minimum common multiple* of the two
periods in the two directions. This allows us caching the different
possible `@!state-at`

different times, to reuse them after the period
has been used (in case of need).

Last, member variable `@!adjacents-for`

lets us pre-compute all adjacent
positions for each field position, taking into account the topology and
assuming that:

- the starting position is in slot 0
- the final position is in the last slot.

This are the functions to calculate the different permutations for moving the field in the different directions:

```
sub l-perm ($x, $y) { (^$y).map({ (|(1..^$x), 0) Â«+Â» $_ * $x }).flat }
sub r-perm ($x, $y) { (^$y).map({ ($x - 1, |^($x - 1)) Â«+Â» $_ * $x }).flat }
sub u-perm ($x, $y) { |($x..($x * $y - 1)), |^$x }
sub d-perm ($x, $y) { |(^$x Â«+Â» ($x * $y - $x)), |^($x * $y - $x) }
```

Next, we take a look at the initialization functions. I still have to
get a *real* hang of it, but I thought that I can fake it until I make
it, right? So Iâ€™m defining `create`

as a surrogate `submethod`

for
creating a new object (instead of `new`

) and a `TWEAK`

to do the actual
initialization from the inside of the object itself.

```
submethod create ($lines) {
my $size-x = $lines[0].chars - 2;
my $size-y = $lines.elems - 2;
my @array = $lines[1 .. $size-y].join('').subst('#', '', :g).comb;
my @layers = '<>^v'.comb.map({ True, |(@array Â«neÂ» $_), True });
return Field1.new(:$size-x, :$size-y, :@layers);
}
submethod TWEAK {
@!permutations = (&l-perm, &r-perm, &u-perm, &d-perm).map: -> &inner {
(0, |(&inner($!size-x, $!size-y) Â«+Â» 1), 1 + $!size-x * $!size-y)
}
my ($A, $B) = $!size-x, $!size-y;
($A, $B) = $B % $A, $A while $A; # GCD
$!period = $!size-x * $!size-y div $B; # LCM
@!state-at.push: self!squash;
my $inner = $!size-x * $!size-y;
@!adjacents-for.push: [0, 1];
for 1 .. $inner -> $p {
my @adjacents = $p; # wait
@adjacents.push: $p - 1 if ($p - 1) % $!size-x; # left, consider 1-offset
@adjacents.push: $p + 1 if $p % $!size-x; # right
@adjacents.push: $p - $!size-x if $p > $!size-x; # up
@adjacents.push: $p + $!size-x if $p + $!size-x <= $inner; # down
@!adjacents-for.push: @adjacents;
}
@!adjacents-for[1].push: 0; # for going back...
@!adjacents-for[$inner].push: $inner + 1;
@!adjacents-for.push: [ $inner + 1, $inner ]; # for going back...
#for @!adjacents-for.kv -> $i, $v { say "$i. ($v)" }
say "period is $!period";
}
```

The `squash`

method allows merging the different layers together and can
be expressed very synthetically thanks to hyperoperators. Each slot is
forced into a boolean value, indicating whether the specific location is
a good candidate for hosting the moving people or not. Method
`stringify`

is a helper for debugging.

```
method !squash { @!layers.reduce({ $^a Â«&Â» $^b })Â».so }
method stringify ($n = Nil) {
(
gather {
my $global = self.state-at($n // @!state-at.end);
my $hborder = '-' x ($!size-x - 1);
my @range = 1 .. $!size-x;
take "+ {$hborder}+";
for ^$!size-y {
take '|' ~ $global[@range].map({ $_ ?? ' ' !! '#' }).join('') ~ '|';
@range Â«+=Â» $!size-x;
}
take "+{$hborder} +";
}
).join: "\n";
}
```

As anticipated, the states at different points in time cycle
periodically. The method `state-at`

acts as a wrap around `@!state-at`

to take advantage of this periodicity; it also takes care to add more
states in the cache in case of need (using the `while`

loop):

```
method state-at ($n is copy) {
$n %= $!period;
while @!state-at.end < $n {
@!layers[$_] = @!layers[$_][|@!permutations[$_]] for ^4;
@!state-at.push: self!squash;
}
return @!state-at[$n];
}
```

Last, we have three methods that will support our A* search more or
less directly. Method `target`

tells us the identifier of the target
position, that is the last one. Method `adjacents`

gives us the allowed
adjacent positions at step `$step`

starting from position `$p`

, based on
the specific state at the given `$step`

.

```
method target { $!size-x * $!size-y + 1 }
method adjacents ($step, $p) {
my $state = self.state-at($step);
@!adjacents-for[$p].grep: { $state[$_] };
}
```

Last, the `manhattan`

method implements the calculation of the
[Manhattan distance][] between two different positions `$p`

and `$q`

,
taking into consideration the specific representation for the different
positions.

```
method manhattan ($p is copy, $q is copy) {
my $value = 0;
if $p == 0 { ++$value; ++$p }
if $q == self.target { ++$value; --$q }
--$p; --$q;
return $value +
(($p mod $!size-x) - ($q mod $!size-x)).abs + # delta-x
(($p div $!size-x) - ($q div $!size-x)).abs; # delta-y
}
}
```

## Part 1

With the `Field1`

at hand, we can now easily define the solution for
part 1:

```
sub part1 ($inputs) {
class Field1 { ... };
class Astar { ... };
my $field = Field1.create($inputs);
# graph is defined with nodes as pairs [$step, $position]
# distance between adjacent nodes is 1
# heuristic is Manhattan
my $target = $field.target;
my $nav = Astar.new(
identifier => -> $v { $v[1] == $target ?? 'TARGET' !! $v.join(',') },
distance => -> $v, $w { 1 },
heuristic => -> $v, $w { $field.manhattan($v[1], $w[1]) },
successors => -> $v {
my $position = $v[1];
return if $position == $target; # avoid bothering
my $step = $v[0] + 1;
$field.adjacents($step, $position).map: { [$step, $_] };
},
);
my @path = $nav.best-path((0, 0), (Nil, $target));
return @path.end;
}
```

The A* class only requires a few functions, that rely upon what is
provided by `Field1`

. After calculating the optimal path in `@path`

,
the last index of this path is the same as the number of steps needed to
complete the task.

## Part 2

The second part of the challenge can be addressed easily with what we already have; it suffices to drive the search in the right way, keeping the state from previous iterations as we go.

```
sub part2 ($inputs, $start) {
class Field1 { ... };
class Astar { ... };
my $field = Field1.create($inputs);
# graph is defined with nodes as pairs [$step, $position]
# distance between adjacent nodes is 1
# heuristic is Manhattan
my $target = 0;
my $nav = Astar.new(
identifier => -> $v { $v[1] == $target ?? 'TARGET' !! $v.join(',') },
distance => -> $v, $w { 1 },
heuristic => -> $v, $w { $field.manhattan($v[1], $w[1]) },
successors => -> $v {
my $position = $v[1];
return if $position == $target; # avoid bothering
my $step = $v[0] + 1;
$field.adjacents($step, $position).map: { [$step, $_] };
},
);
say "start at $start";
my @return = $nav.best-path(($start, $field.target), (Nil, $target));
$target = $field.target;
my @go-again = $nav.best-path((@return[*-1][0], 0), (Nil, $target));
#.say for @path;
return @go-again[*-1][0];
}
```

We might spare some time and reuse the calculation from part 1, of
course. Here we do something midway, by creating a new object but going
ahead up to the `$start`

state that we got from part 1.

## Conclusion

This has been an interesting challenge. To some extent, the puzzle is like a tridimensional maze, where itâ€™s only possible to move ahead in one of the dimensions (itâ€™s time, after all!).

The computation of the programâ€¦ takes some time. I suspect that my A* implementation can use a lot of optimizations, but to be honest I donâ€™t know which!

Cheers everybody!

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