2023/16.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.38;
   4 use List::Util 'uniq';
   5
   6 chomp(my $steps = <>);
   7 my @steps = split //, $steps;
   8
   9 scalar <>;
  10
  11 my %dirs;
  12 while (<>) {
  13         my @x = /\w{3}/g;
  14         $dirs{$x[0].'L'} = $x[1];
  15         $dirs{$x[0].'R'} = $x[2];
  16 }
  17
  18 sub walk {
  19         my $now = shift;
  20         my $i = 0;
  21         while ($now !~ /Z$/) {
  22                 $now = $dirs{$now . ($steps[$i++ % @steps])};
  23         }
  24         return $i;
  25 }
  26
  27 sub gcd {
  28         my ($x, $y) = @_;
  29         ($x, $y) = ($y, $x) if $y > $x;
  30         while ($y) {
  31                 ($x, $y) = ($y, $x % $y);
  32         }
  33         return $x;
  34 }
  35
  36 # using LCM is incorrect in general case,
  37 # but it works on the actual puzzle input
  38 my $p;
  39 for (uniq grep { /A$/ } map { substr($_, 0, 3) } keys %dirs) {
  40         my $steps = walk($_);
  41         if (defined $p) {
  42                 $p *= $steps/gcd($p, $steps);
  43         } else {
  44                 $p = $steps;
  45         }
  46 }
  47 say $p;