#!/usr/bin/perl
use v5.35.0;

=pod

Here is a keypad:

 +---+---+---+
 | 7 | 8 | 9 |
 +---+---+---+
 | 4 | 5 | 6 |
 +---+---+---+
 | 1 | 2 | 3 |
 +---+---+---+
     | 0 | A |
     +---+---+

Keypads have buttons. There are two important things about a button: what
does, and where it is relative to its neighbouring buttons.

A keypad also has a goal: create a loop of button visits that starts from
A and ends there as well, having performed a preset list of button presses
along the way.

That can be broken down into subgoals: for each step along the preset list,
find the shortest paths that get there.

The shortest path from any button to its neighbour is just 1, and keypad
shapes are given as inputs, so perhaps we could *specify* a keypad as an
initial collection of shortest paths and let the code expand on that as
required. It would probably be useful to include the direction of travel
from the button to its neighbour as part of that shortest path. So the
initial spec for the keypad above might look like

 7>8, 7v4, 8>9, 8v5, 8<7, 9v6, 9<8, 4^7, 4>5, 4v1, 5^8, 5>6, 5v2, 5<4, 6^9,
 6v3, 6<5, 1^4, 1>2, 2^5, 2>3, 2v0, 2<1, 3^6, 3vA, 3<2, 0^2, 0>A, A^3, A<0

In Perl that would be just a list of strings, or maybe even just a single
string that gets split into a list on whitespace.

If we already have a shortest path from button x to button y, the reverse
path is also a shortest path and can be calculated by switching the ends and
complementing all the movement operators. That lets us cut down the initial
keypad spec by removing redundancies:

 7>8, 7v4, 8>9, 8v5, 9v6, 4>5, 4v1, 5>6, 5v2, 6v3, 1>2, 2>3, 2v0, 3vA, 0>A

I like this representation. It's essentially content addressing, and it gets
rid of all those pesky coordinates that one might otherwise be tempted to
assign to keypad buttons.

So a path from button A to button 2 on the only keypad defined so far could
be represented as A<^2. From 2 to 9 would be 2^^>9 and so forth. Those paths
can be built on demand and added to the list representing the keypad.

When we come to representing the directional keypads we're going to end up
with some horrible looking path strings unless we rein this insanity in right
now. Even though the *ends* of a path string are always button labels and the
middle parts are movement codes, and Perl would have no trouble keeping these
straight, I am not Perl and I definitely would.  So I'm going to use LRUD
instead of <>^v for the button labels on remote keypads and if that causes
inefficiencies down the track, so be it.

Here's the remote control keypad layout, with that convention:

     +---+---+
     | U | A |
 +---+---+---+
 | L | D | R |
 +---+---+---+

In our representation that translates to

 U>A, UvD, AvR, L>D, D>R

Generating the complementary moves adds

 A<U, D^U, R^A, D<L, R<D

To build a path from say button A to button 8 if there isn't already one
defined, we could start at both ends and work toward the middle. We start
with all the paths from A, which are just all the strings that start with
A, and all the paths to 8, which are just all the strings that end with 8.
If we can't find a path that starts at the button we want to start at, we
make one by finding a path that ends there and complementing it. Likewise
for ends. If we cant find one from the first set whose ending matches one
from the second, we extend that collection by constructing intermediate
paths from both ends until we *do* manage to match a prefix with a suffix.
At which point we clip off the shared prefix and suffix, jam the bleeding
ends together, and toss the result into our now extended keypad definition
along with all those intermediates.

At some point we're going to need to work out a total cost for any given
way to press a sequence of buttons on the main keypad. The fact that the
directional remote control keypads are themselves keypads means that there's
a movement cost for each change of direction on the controlled pad, and from
moving to a button to pressing it, and those costs are not all equal. So
we're going to need to translate a button press sequence spec for any given
keypad, such as 029A on the main keypad, into a spec for the remote that
controls it, and ultimately it's the lengths of those specs that we care
about minimizing.

We still don't need any structure more complicated than a string for that.
Every button press on a controlled keypad translates to an A in the sequence
spec for its controller, and any movement operation required to get from
one button to the next can just get tr/<>^>/LRUD/ applied and passed along.
Can probs do the whole lot in a single tr/// with a bit of thought.

I don't think we need to worry about non-shortest controlled keypad paths
becoming parts of shortest controlling keypad sequence specs, like 5>v<2
somehow ending up cheaper than 5v2 after multiple levels of translation.
These keypads are all laid out on grids, so the only way for a path from
one button to another to be non-optimal is if it contains paired, redundant
moves, and those can only add expense, never remove it. But there may well
be a cost difference between e.g. 2^>6 and 2>^6, so we do have to translate
*all* the shortest paths instead of just picking one arbitrarily.

Some shortest paths are always going to be more economical under multiple
levels of remote control than others. 0^^^>9 and 0>^^^9 both beat 0^>^^9
and 0^^>^9, for example, because repeated presses of a directional button
are themselves cheaper for the upstream remote than switching directions.
If there isn't a super natural way to generate those preferentially, though,
it might be better just to test all the generated sequences explicitly and
discard those that work less well. Likewise, making assumptions such as that
keypads will never be laid out in ways that resemble mazes probably amounts
to premature optimization. Let's just try to avoid premature pessimization
and call it good.

=cut

# A cheap and cheerful little data dumper, a lot less verbose than Dumper

sub guts {
	return '-' unless @_;
	if (@_ == 1) {
		my $arg = $_[0] // 'und';
		my $ref = ref($arg);
		if ($ref eq 'ARRAY') {
			return '['.join(' ', map {guts($_)} @$arg).']';
		} elsif ($ref eq 'HASH') {
			return '{'.join(' ', map {$_.': '.guts($$arg{$_})} sort keys %$arg).'}';
		} elsif ($arg eq '') {
			return "''";
		} else {
			return $arg;
		}
	}
	return '(' . join(' ', map {guts($_)} @_) . ')';
}



# Return a reference to a hash, whose keys are length-2 strings representing
# a pair of buttons to be moved from and to, and whose values are references
# to lists of the minimal-length movement paths needed to do that. Spec format
# is as discussed above.
#
# Keypads are small so it's not going to take too much work or space to fill
# out all the possible paths within one at creation time, rather than trying
# to do it on demand later.
#
# As a side effect, construct a big hash keyed by all paths generated
# regardless of their beginning and ending buttons, which make no difference
# to the cost to achieve any given movement pattern using directional keypad
# control. Each value in that hash is a reference to a list of costs to get
# the button at the end of the path in its key pressed, indexed by the number
# of levels of remote control used to get that done. As built, these will
# only contain results for 0 (no) remotes, i.e. a human pushing the buttons;
# all of those are just 1, because the human doesn't need to traverse a path
# before pressing a button.

my %costs;

sub make_keypad($spec) {
	# Collect all the specified and implied paths
	my @paths = split '\s', $spec;
	my %neighbours;
	/^(.)(.+.)$/ && push @{$neighbours{$1}}, $2
       		for @paths, map {scalar reverse tr/<>^v/><v^/r} @paths; 

	# The empty paths from buttons to themselves are the shortest
	@paths = map {$_.$_} keys %neighbours;

	# Explore all the paths extending outward from all buttons in length
	# order until all the shortest paths between buttons have been found
	my %keypad;
	for (@paths) {
		/^(.)(.*)(.)$/;
		next if exists $keypad{$1.$3} &&
			length $keypad{$1.$3}[0] < length $2;
		push @{$keypad{$1.$3}}, $2;
		$costs{$2} = [1] unless exists $costs{$2};
		push @paths, map {$1.$2.$_} @{$neighbours{$3}};
	}
	return \%keypad;
}

# Gonna need a few of those. Let's keep them in a list in order of
# remoteness.

my @control_chain = (
	(make_keypad('U>A UvD AvR L>D D>R')) x 26,
	make_keypad('7>8 7v4 8>9 8v5 9v6 4>5 4v1 5>6 5v2 6v3 1>2 2>3 2v0 3vA 0>A')
);

# It's all very well knowing the shortest paths to move from button to
# button, but the only reason those are interesting is as a guide to
# what we really want to know, which is the lowest-cost ways to generate
# button presses over multiple levels of remote control.
#
# Costs for level 0 (no indirection) for all paths encountered were filled
# in while the keypads were being created. Now calculate the costs for
# those paths for the remaining levels.

for my $level (1 .. $#control_chain) {
	my $keypad = $control_chain[$level];
	my $controller = $control_chain[$level - 1];
	for my $buttons (keys %$keypad) {
		my $paths = $$keypad{$buttons};

		# Walk the list of shortest paths linking the first button in
		# $buttons to the second, calculating the cost of each by
		# adding up the costs for each step in the sequence of button
		# presses that this keypad's controlling directional keypad
		# would need to use to get it done.
		#
		# For example: if $keypad holds a reference to the final
		# numeric pad, and the button pair under consideration is 8A,
		# then make_keypad() would have made $$keypad{'8A'} yield the
		# list reference ['vvv>', 'vv>v', 'v>vv', '>vvv'] - these being
		# all of the *shortest* paths connecting button 8 to button A.
		#
		# Some of those are also the shortest paths connecting button
		# 7 to button 0 ('vvv>' doesn't work because of the gap in the
		# bottom left corner) and they will cost the same to perform
		# whether stepping from 8 to A or 7 to 0. This is why the
		# %costs hash is keyed purely by movement paths, independent
		# of buttons. If we've already worked out the cost for 'vv>v'
		# while examining button pair 70, there's no point doing that
		# all over again for 8A when we could just look it up instead.
		#
		# The cost to perform 'vv>v' on a controlling directional
		# keypad is the cost to step from the starting point at A
		# to the button at D and then press that, plus the cost to
		# step to and press D from there (cheap because already
		# there, only the press is required) plus the cost to step
		# to and press R, plus step to and press D, plus step to and
		# press A. In other words, it's the sum of the costs for the
		# loop A->D->D->R->D->A on the next keypad back toward the
		# start of the control chain.
		#
		# That controller keypad has a *list* of paths that it could
		# use to perform each of those steps, and that list might
		# have more than one entry (for example, make_keypad would
		# have made $$controller{'AD'} contain ['<v', 'v<']) but
		# rather than get into the weeds to decide which of those
		# to use for cost calculation, we just pick the first one
		# i.e. $$controller{'AD'}[0]. Those lists get pruned as we
		# go, so only the actually cheapest (as opposed to merely
		# shortest) paths end up remaining in them.

		my $cheapest = 'inf';
		for my $path (@$paths) { 
			my $cost = $costs{$path}[$level];
			unless (defined $cost) {
				my $loop = 'A' . $path =~ tr/<>^v/LRUD/r . 'A';
				while ($loop =~ /(?=(..))/g) {
					my $cpath = $$controller{$1}[0];
					$cost += $costs{$cpath}[$level - 1];
				}
				$costs{$path}[$level] = $cost;
			}
			$cheapest = $cost if $cheapest > $cost;
		}

		# Remove all but the cheapest paths from this keypad entry so that
		# when the costs for this level are used to compute those for the
		# next one, the assumption relied upon above (that the first path
		# listed for any button pair in a keypad is as cheap as any) stays
		# true.
		#
		# A side effect of @control_chain containing many references to
		# the *same* make_keypad() output for the directional keypad is
		# that only one instance of that keypad's hash table actually
		# exists, so if the pruning we do here is on a directional keypad,
		# it also affects all of those further along the control chain.
		# This could have been a bug, but in fact it just saves work by
		# reducing the lengths of the lists the code above needs to walk
		# while calculating costs at higher levels of indirection. You'd
		# almost think I'd done it deliberately.

		if ($#$paths) {
			my $last_cheap = -1;
			for my $path (@$paths) { 
				if ($costs{$path}[$level] == $cheapest) {
					$$paths[++$last_cheap] = $path;
				}
			}
			$#$paths = $last_cheap;
		}
	}
}

# Should be in good shape to deal with inputs now

my $total = 0;
my $level = $#control_chain;
my $keypad = $control_chain[$level];
while (<>) {
	no warnings 'numeric';
	my $numeric_part = 0 + $_;
	my $cost = 0;
	substr($_, 0, 0) = 'A';
	while (/(?=(..))/g) {
		$cost += $costs{$$keypad{$1}[0]}[$level];
	}
	$total += $cost * $numeric_part;
}
say $total;