2018/44.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.36;
   4 use strict;
   5 use feature 'multidimensional';
   6
   7 my $depth = 11739;
   8 my ($tx, $ty) = (11,718);
   9
  10 my %gi;
  11 sub gi2el($gi) { ($gi + $depth) % 20183 }
  12 my %el;
  13 my %type;
  14
  15 sub can_use($x, $y, $gear) {
  16         return 1 if
  17                 $type{$x,$y} == 0 && $gear
  18                 || $type{$x,$y} == 1 && ($gear == 0 || $gear == 2)
  19                 || $type{$x,$y} == 2 && ($gear == 0 || $gear == 1);
  20         return 0;
  21 }
  22
  23 my $sum = 0;
  24 for my $n (0 .. 6*($tx + $ty)) {
  25         my $y = 0;
  26         my $x = $n;
  27         for my $i (0 .. $n) {
  28                 if (($x == 0 && $y == 0) || ($x == $tx && $y == $ty)) {
  29                         $gi{$x,$y} = 0;
  30                 } elsif ($y == 0) {
  31                         $gi{$x,$y} = 16807*$x;
  32                 } elsif ($x == 0) {
  33                         $gi{$x,$y} = 48271*$y;
  34                 } else {
  35                         $gi{$x,$y} = $el{$x-1,$y} * $el{$x,$y-1};
  36                 }
  37                 $el{$x,$y} = gi2el($gi{$x,$y});
  38                 $type{$x,$y} = $el{$x,$y} % 3;
  39                 $y++;
  40                 $x--;
  41         }
  42 }
  43
  44 my @q = ([0, 0, 0, 1]);
  45
  46 my %map;
  47 $map{0,0,1} = 0;
  48
  49 say "walking the graph";
  50 my $now = 0;
  51 while (@q) {
  52         my @current_minute;
  53         while (@q && $q[0]->[0] <= $now) {
  54                 push @current_minute, shift @q;
  55         }
  56         say scalar(@current_minute), " states in $now";
  57
  58         for my $state (@current_minute) {
  59                 my ($time, $x, $y, $tool) = @$state;
  60                 say "state $x,$y,$tool";
  61                 next if !defined $type{$x,$y};
  62                 $map{$x,$y,$tool} = $now
  63                         if !defined $map{$x,$y,$tool}
  64                                 || $map{$x,$y,$tool} > $now;
  65
  66                 if ($x == $tx && $y == $ty) {
  67                         say "Target reached at $now";
  68                         exit 0;
  69                 }
  70                 $map{$x,$y,$tool} = $now if !defined $map{$x,$y,$tool}
  71                         || $map{$x,$y,$tool} > $now;
  72
  73                 if ($tool != 0 && can_use($x, $y, 0)
  74                         && (!defined $map{$x,$y,0}
  75                                 || ($map{$x,$y,0} > $now+7))) {
  76                         push @q, [ $now+7, $x, $y, 0];
  77                         $map{$x,$y,$0} = $now+7;
  78                 }
  79
  80                 if ($tool != 1 && can_use($x, $y, 1)
  81                         && (!defined $map{$x,$y,1}
  82                                 || ($map{$x,$y,1} > $now+7))) {
  83                         push @q, [ $now+7, $x, $y, 1];
  84                         $map{$x,$y,1} = $now+7;
  85                 }
  86
  87                 if ($tool != 2 && can_use($x, $y, 2)
  88                         && (!defined $map{$x,$y,2}
  89                                 || ($map{$x,$y,2} > $now+7))) {
  90                         push @q, [ $now+7, $x, $y, 2];
  91                         $map{$x,$y,2} = $now+7;
  92                 }
  93
  94                 for my $v ([-1, 0], [0, -1], [1, 0], [0, 1]) {
  95                         my ($dx, $dy) = @$v;
  96                         next if $x+$dx < 0 || $y+$dy < 0;
  97                         next if !can_use($x+$dx, $y+$dy, $tool);
  98                         next if defined $map{$x+$dx,$y+$dy,$tool}
  99                                 && $map{$x+$dx,$y+$dy,$tool} <= $now+1;
 100                         unshift @q, [ $now+1, $x+$dx, $y+$dy, $tool ];
 101                         $map{$x+$dx,$y+$dy,$tool} = $now+1;
 102                 }
 103         }
 104         $now++;
 105 }
 106
 107 say join(',', $map{$tx,$ty,0}, $map{$tx,$ty,1}, $map{$tx,$ty,2});
 108
 109