#!/usr/bin/perl -w
use v5.38;
+use List::Util 'uniq';
+
+chomp(my $steps = <>);
+my @steps = split //, $steps;
+
+scalar <>;
-$/ = "\n\n";
my %dirs;
-my @steps = split //, scalar <>;
-pop @steps;
-pop @steps;
-my $l = <>;
-for (split /\n/, $l) {
- my @x = /[A-Z0-9]{3}/g;
+while (<>) {
+ my @x = /\w{3}/g;
$dirs{$x[0].'L'} = $x[1];
$dirs{$x[0].'R'} = $x[2];
}
-my %seen;
-my %now = map { substr($_, 0, 3) . $steps[0] => 1 } grep { /^..A/ } keys %dirs;
-my @now = keys %now;
-say join(' ', @now);
-
sub walk {
- my $node = shift;
+ my $now = shift;
my $i = 0;
- my $n;
- while ($node !~ /^..Z/) {
- $i++;
- $i = 0 if $i >= @steps;
- $node = $dirs{$node} . $steps[$i];
- $n++;
+ while ($now !~ /Z$/) {
+ $now = $dirs{$now . ($steps[$i++ % @steps])};
+ }
+ return $i;
+}
+
+sub gcd {
+ my ($x, $y) = @_;
+ ($x, $y) = ($y, $x) if $y > $x;
+ while ($y) {
+ ($x, $y) = ($y, $x % $y);
}
- return $n;
+ return $x;
}
-my %f;
-use List::Util qw(product);
-for (@now) {
- my $st = walk($_);
- my $l = `factor $st`;
- $l =~ s/.*://;
- for my $n ($l =~ /\d+/g) {
- $f{$n}++;
+# using LCM is incorrect in general case,
+# but it works on the actual puzzle input
+my $p;
+for (uniq grep { /A$/ } map { substr($_, 0, 3) } keys %dirs) {
+ my $steps = walk($_);
+ if (defined $p) {
+ $p *= $steps/gcd($p, $steps);
+ } else {
+ $p = $steps;
}
}
-say product keys %f;
+say $p;