TL;DR

On with Advent of Code puzzle 17 from 2021: throwing stuff around.

This day’s puzzle is about throwing stuff around. The physics model is a bit… inaccurate, because it seems that the drag from water in the X coordinates is sort of different than that in Y.

The first part is straightforward with some maths. Looking at the solutions from a few people this might not necessarily be the case, but it seems that it works for common puzzle inputs.

The key insight is that whatever goes up eventually comes down; in this case, it does this in an integer number of seconds. Not only this: the speed will also be the same, but pointing downwards.

So in this case our question is: what’s the maximum Y speed that will make it still get the patch? It’s the lowest point of the patch: anything greater (in absolute value) will make us miss the patch for good.

That is the speed after having reached back the zero level, so the step before will be one value less. That speed downwards must be the same upwards when starting, i.e. the absolute value of the bottom of the patch less 1. The maximum height will be the sum of all numbers from that down to 1… that is the same going up from 1 to that number, also known as a triangular number for which there’s a know formula:

\[H = \frac{k \cdot (k + 1)}{2} = \frac{(m - 1) \cdot (m - 1 + 1)}{2} = \frac{(m - 1) \cdot m}{2}\]

In Raku terms:

sub part1 ($inputs) {
   my $m = $inputs[1]».abs.max;
   return $m * ($m - 1) / 2;
}

The second part might have some quick formula but I could not find anything immediate, so I decided to go brute force:

sub part2 ($inputs) {
   my $count = 0;
   my @all = $inputs».List.flat;
   my $m = $inputs[1]».abs.max;
   for 0 .. $inputs[0][1] -> $vx {
      print '.';
      for -$m .. $m -> $vy {
         ++$count if hits($vx, $vy, @all);
      }
   }
   ''.put;
   return $count;
}

The pseudo trick here is to limit the search to a range dependent from the position of the patch. So for the speed in the X coordinate we try from 0 up to the maximum value along that line: anything greater will surely miss.

For the Y coordinate, though, we will try everything within the bounds we already discussed: anything more will make us miss the target; for this reason, our range here is -$m .. $m.

The actual check is performed in a separate function hits:

sub hits ($vx is copy, $vy is copy, @limits) {
   my ($min-x, $max-x, $min-y, $max-y) = @limits;
   my ($x, $y) X= 0;
   while $vy >= 0 || $y >= $min-y {
      $x += $vx;
      $y += $vy;
      return 1 if $min-x <= $x <=  $max-x
               && $min-y <= $y <=  $max-y;
      --$vx if $vx > 0;
      --$vy;
   }
   return 0;
}

I admit that I should probably know better than this… but whatever, it works!

Stay safe people… plese protect yourself and thos earound you!