#!/usr/bin/perl -w

use v5.36;
use strict;

my %map;
my $base = 1_000_000;
my @el;

my $y = $base;
while (<>) {
	chomp;
	my $x = $base;
	for my $pt (split //) {
		if ($pt eq '#') {
			$map{"$x,$y"} = 1;
			push @el, [ $x, $y, 0 ];
		}
		$x++;
	}
	$y++;
}

sub occupied($map, $x, $y) {
	return $map->{"$x,$y"};
}

my ($xmin, $xmax, $ymin, $ymax);

my $moved = 1;
my $round = 0;
while (1) {
	say "round ", ++$round;
	my %prop;
	my @prop;
	for my $i (0 .. $#el) {
		my ($x, $y, $state) = @{ $el[$i] };
		my $prop;
		my $sum = -1;
		for my $x1 ($x-1 .. $x+1) {
			for my $y1 ($y-1 .. $y+1) {
				$sum++ if $map{"$x1,$y1"};
			}
		}
		next if !$sum;
		DIR:
		for my $add (0 .. 3) {
			my $dir = ($add + $state) % 4;
			if ($dir == 0) {
				for my $x1 ($x-1 .. $x+1) {
					next DIR if occupied(\%map, $x1, $y-1);
				}
				$prop = [ $x, $y-1, 1, $i ];
				last;
			} elsif ($dir == 1) {
				for my $x1 ($x-1 .. $x+1) {
					next DIR if occupied(\%map, $x1, $y+1);
				}
				$prop = [ $x, $y+1, 2, $i ];
				last;
			} elsif ($dir == 2) {
				for my $y1 ($y-1 .. $y+1) {
					next DIR if occupied(\%map, $x-1, $y1);
				}
				$prop = [ $x-1, $y, 3, $i ];
				last;
			} elsif ($dir == 3) {
				for my $y1 ($y-1 .. $y+1) {
					next DIR if occupied(\%map, $x+1, $y1);
				}
				$prop = [ $x+1, $y, 0, $i ];
				last;
			}
		}
		if ($prop) {
			$prop[$i] = $prop;
			$prop{"$prop->[0],$prop->[1]"}++;
		}
	}
	last if !@prop;
	$moved = 0;
	for my $i (0 .. $#prop) {
		my $p = $prop[$i];
		next if !defined $p;
		my ($x1, $y1) = @$p;
		my ($x, $y) = @{ $el[$i] };
		if ($prop{"$x1,$y1"} != 1) {
			#say "$i not moving $x,$y -> $x1,$y1";
			next;
		}
		$moved++;
		#say "$i moved $x,$y -> $x1,$y1";
		undef $map{"$x,$y"};
		$map{"$x1,$y1"} = 1;
		$el[$i][0] = $x1;
		$el[$i][1] = $y1;
	}
	($xmin, $xmax, $ymin, $ymax) = (undef, undef, undef, undef);
	for my $e (@el) {
		my ($x, $y) = @$e;
		$xmin = $x if !defined $xmin || $xmin > $x;
		$ymin = $y if !defined $ymin || $ymin > $y;
		$xmax = $x if !defined $xmax || $xmax < $x;
		$ymax = $y if !defined $ymax || $ymax < $y;
		$e->[2]++;
		$e->[2] %= 4;
	}
	say "$xmin .. $xmax, $ymin .. $ymax";
}

say "result $xmin .. $xmax $ymin .. $ymax";
say $round;
