#!/usr/bin/perl
use v5.35.0;
use Data::Dumper;
use List::Util 'sum';

# Read garden as an array

my $width;
my @garden;
while (<>) {
	$width //= length;
	push @garden, split //;
}

# Use flood-fills to assign each plot to a region.
#
# Each region is represented as a hash containing
# its area, perimeter, fence count, and a reference
# to a list of its constituent plots.
#
# Plots derived from line terminators become hidden
# regions where only uninteresting \Weeds grow, neatly
# breaking what would otherwise appear to be adjacency
# between plots on left and right edges.

my @regions;
my @region_of;
my %to_do;
@to_do{(0 .. $#garden)} = ();
while (my ($plot) = %to_do) {
	my ($area, $perimeter, @plots);
	my @queue = $plot;
	while (@queue) {
		my $plot = shift @queue;
		next unless exists $to_do{$plot};
		delete $to_do{$plot};
		$area++;
		$perimeter += 4;
		push @plots, $plot;
		for my $offset (-$width, 1, $width, -1) {
			my $neighbour = $plot + $offset;
			next unless 0 <= $neighbour <= $#garden;
			next unless $garden[$neighbour] eq $garden[$plot];
			$perimeter--;
			push @queue, $neighbour if exists $to_do{$neighbour};
		}
	}
	my $region = {
		area => $area,
		perimeter => $perimeter,
		sides => 0,
	       	plots => \@plots
	};
	@region_of[@plots] = ($region) x @plots;
	push @regions, $region unless $garden[$plot] =~ /\W/;
}

# We're supposed to be counting straight fence edges, but
# for any polygon the number of corners is the same, and those
# are a lot easier to identify.
#
# Scan the entire garden with a 2x2 patch of plots that's allowed
# to overhang the edge by one plot, and use any corners found
# at its centre to bump the sides counts of their respective regions.

my $edge = {sides => 0};
for my $patch (-$width - 1 .. $#garden) {

	my $p = $patch;	my $nw = 0 <= $p <= $#garden? $region_of[$p]: $edge;
	$p += 1; 	my $ne = 0 <= $p <= $#garden? $region_of[$p]: $edge;
	$p += $width;	my $se = 0 <= $p <= $#garden? $region_of[$p]: $edge;
	$p -= 1;	my $sw = 0 <= $p <= $#garden? $region_of[$p]: $edge;

	my $nm = $nw == $ne;	# Evaluate region matches on
	my $sm = $sw == $se;	# north, south, east and west
	my $em = $ne == $se;	# sides of 2x2 patch
	my $wm = $sw == $nw;

	# If there's a complete set of paired side
	# matches, nobody gets a corner.
	# Cases covered:
	# aa	ab	aa
	# bb	ab	aa
	next if (($nm && $sm) || ($em && $wm));

	# Now that the case where all four plots are in
	# the same region has been ruled out, if we see
	# e.g. both a north and a west match at this point
	# then we know that the southeast corner *doesn't*
	# match, so the region containing the nw, ne and sw
	# plots forms an interior corner here.
	#
	# Conversely, if we see neither a north match nor
	# a west one, the region with the nw plot in it has
	# an exterior corner here.
	#
	# Pleasingly, both those cases can be covered just
	# by checking whether the north match and the west
	# match have the same truth value. Same pattern
	# applies to all four plots in the patch.

	$$nw{sides}++ if $nm eq $wm;
	$$ne{sides}++ if $nm eq $em;
	$$sw{sides}++ if $sm eq $wm;
	$$se{sides}++ if $sm eq $em;
}

#print Dumper \@regions;
say 'Fencing price:      ', sum map {$$_{area} * $$_{perimeter}} @regions;
say 'With bulk discount: ', sum map {$$_{area} * $$_{sides}} @regions;