5 use feature 'multidimensional';
8 my ($tx, $ty) = (11,718);
11 sub gi2el($gi) { ($gi + $depth) % 20183 }
15 sub can_use($x, $y, $gear) {
17 $type{$x,$y} == 0 && $gear
18 || $type{$x,$y} == 1 && ($gear == 0 || $gear == 2)
19 || $type{$x,$y} == 2 && ($gear == 0 || $gear == 1);
24 for my $n (0 .. 6*($tx + $ty)) {
28 if (($x == 0 && $y == 0) || ($x == $tx && $y == $ty)) {
31 $gi{$x,$y} = 16807*$x;
33 $gi{$x,$y} = 48271*$y;
35 $gi{$x,$y} = $el{$x-1,$y} * $el{$x,$y-1};
37 $el{$x,$y} = gi2el($gi{$x,$y});
38 $type{$x,$y} = $el{$x,$y} % 3;
44 my @q = ([0, 0, 0, 1]);
49 say "walking the graph";
53 while (@q && $q[0]->[0] <= $now) {
54 push @current_minute, shift @q;
56 say scalar(@current_minute), " states in $now";
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;
66 if ($x == $tx && $y == $ty) {
67 say "Target reached at $now";
70 $map{$x,$y,$tool} = $now if !defined $map{$x,$y,$tool}
71 || $map{$x,$y,$tool} > $now;
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;
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;
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;
94 for my $v ([-1, 0], [0, -1], [1, 0], [0, 1]) {
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;
107 say join(',', $map{$tx,$ty,0}, $map{$tx,$ty,1}, $map{$tx,$ty,2});