1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5.  
  6. use feature         qw(say);
  7. use List::AllUtils  qw(sum indexes);
  8.  
  9. use Math::Vector::Real;
  10.  
  11. my ($y,$x) = Math::Vector::Real->canonical_base(2);
  12. my @Dirs = ($y, $x, -$y, -$x);
  13.  
  14. # Read in grid, adding sentinel 99s to right and bottom
  15. my @Grid = map { chomp; [map {int} split(//), 99] } <>;
  16. push( @Grid, [(99) x $Grid[0]->@*] );
  17.  
  18. sub grid_at ($) { my $p = shift; return ($Grid[$p->[0]][$p->[1]]) }
  19.  
  20. # Get trailheads
  21. my @trailheads;
  22. foreach my $y (0 .. @Grid - 2) {
  23.     push( @trailheads, map {V($y,$_)} indexes {$_ == 0} $Grid[$y]->@* );
  24. }
  25.  
  26. # Recurse on pos, return is hash of trail ends => number of routes
  27. sub recurse {
  28.     my ($pos) = @_;
  29.     my $next  = grid_at($pos) + 1;
  30.  
  31.     return ($pos => 1)  if ($next == 10);   # found 1 route to pos
  32.  
  33.     my %ret;
  34.     foreach my $dir (@Dirs) {
  35.         my $npos = $pos + $dir;
  36.         if (grid_at($npos) == $next) {
  37.             my %routes = &recurse( $npos );
  38.             $ret{$_} += $routes{$_} foreach (keys %routes); # accumulate routes
  39.         }
  40.     }
  41.  
  42.     return (%ret);
  43. }
  44.  
  45. my $part1 = 0;
  46. my $part2 = 0;
  47.  
  48. foreach my $head (@trailheads) {
  49.     my %res = &recurse( $head );
  50.  
  51.     $part1 += scalar keys %res;
  52.     $part2 += sum values %res;
  53. }
  54.  
  55. say "Part 1: $part1";
  56. say "Part 2: $part2";
  57.