#!/usr/bin/perl -w

use v5.36;
use strict;
use feature 'multidimensional';

my $depth = 11739;
my ($tx, $ty) = (11,718);

my %gi;
sub gi2el($gi) { ($gi + $depth) % 20183 }
my %el;
my %type;

sub can_use($x, $y, $gear) {
	return 1 if
		$type{$x,$y} == 0 && $gear
		|| $type{$x,$y} == 1 && ($gear == 0 || $gear == 2)
		|| $type{$x,$y} == 2 && ($gear == 0 || $gear == 1);
	return 0;
}

my $sum = 0;
for my $n (0 .. 6*($tx + $ty)) {
	my $y = 0;
	my $x = $n;
	for my $i (0 .. $n) {
		if (($x == 0 && $y == 0) || ($x == $tx && $y == $ty)) {
			$gi{$x,$y} = 0;
		} elsif ($y == 0) {
			$gi{$x,$y} = 16807*$x;
		} elsif ($x == 0) {
			$gi{$x,$y} = 48271*$y;
		} else {
			$gi{$x,$y} = $el{$x-1,$y} * $el{$x,$y-1};
		}
		$el{$x,$y} = gi2el($gi{$x,$y});
		$type{$x,$y} = $el{$x,$y} % 3;
		$y++;
		$x--;
	}
}

my @q = ([0, 0, 0, 1]);

my %map;
$map{0,0,1} = 0;

say "walking the graph";
my $now = 0;
while (@q) {
	my @current_minute;
	while (@q && $q[0]->[0] <= $now) {
		push @current_minute, shift @q;
	}
	say scalar(@current_minute), " states in $now";

	for my $state (@current_minute) {
		my ($time, $x, $y, $tool) = @$state;
		say "state $x,$y,$tool";
		next if !defined $type{$x,$y};
		$map{$x,$y,$tool} = $now
			if !defined $map{$x,$y,$tool}
				|| $map{$x,$y,$tool} > $now;

		if ($x == $tx && $y == $ty) {
			say "Target reached at $now";
			exit 0;
		}
		$map{$x,$y,$tool} = $now if !defined $map{$x,$y,$tool}
			|| $map{$x,$y,$tool} > $now;

		if ($tool != 0 && can_use($x, $y, 0)
			&& (!defined $map{$x,$y,0}
				|| ($map{$x,$y,0} > $now+7))) {
			push @q, [ $now+7, $x, $y, 0];
			$map{$x,$y,$0} = $now+7;
		}
	
		if ($tool != 1 && can_use($x, $y, 1)
			&& (!defined $map{$x,$y,1}
				|| ($map{$x,$y,1} > $now+7))) {
			push @q, [ $now+7, $x, $y, 1];
			$map{$x,$y,1} = $now+7;
		}

		if ($tool != 2 && can_use($x, $y, 2)
			&& (!defined $map{$x,$y,2}
				|| ($map{$x,$y,2} > $now+7))) {
			push @q, [ $now+7, $x, $y, 2];
			$map{$x,$y,2} = $now+7;
		}
			
		for my $v ([-1, 0], [0, -1], [1, 0], [0, 1]) {
			my ($dx, $dy) = @$v;
			next if $x+$dx < 0 || $y+$dy < 0;
			next if !can_use($x+$dx, $y+$dy, $tool);
			next if defined $map{$x+$dx,$y+$dy,$tool}
				&& $map{$x+$dx,$y+$dy,$tool} <= $now+1;
			unshift @q, [ $now+1, $x+$dx, $y+$dy, $tool ];
			$map{$x+$dx,$y+$dy,$tool} = $now+1;
		}
	}
	$now++;
}

say join(',', $map{$tx,$ty,0}, $map{$tx,$ty,1}, $map{$tx,$ty,2});


