#!/usr/bin/perl -w

use strict;
use v5.30;

my %items;
while (<>) {
	while (/(\w+) gener/g) {
		$items{"G$1"} = $.;
	}
	while (/(\w+)-compat/g) {
		$items{"M$1"} = $.;
	}
}

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

sub valid_f {
	my ($f, $itm) = @_;
	my %g_cur = map { substr($_, 1) => 1 }
		grep { $_ =~ /^G/ && $itm->{$_} == $f } keys %$itm;
	return 1 if !keys %g_cur;
	for my $c (grep { $_ =~ /^M/ && $itm->{$_} == $f } keys %$itm) {
		return undef if !$g_cur{ substr($c, 1) };
	}
	return 1;
}

my @sorted = sort keys %items;
my %seen;
ENTRY:
while (@q) {
	my $entry = shift @q;
	my ($w, $steps, $floor, $itm) = @$entry;

	my $key = join('|', $floor, map { $itm->{$_} } @sorted);
	say "$key";
	next if $seen{$key}++;

	for (1 .. 4) {
		next ENTRY if !valid_f($_, $itm);
	}
	say "valid";

	if (!grep { $itm->{$_} != 4 } keys %$itm) {
		say "$steps";
		last;
	}

	for my $nf ($floor+1, $floor-1) {
		next if $nf < 1 || $nf > 4;
		for my $i (0 .. $#sorted) {
			my $itm_i = $sorted[$i];
			next if $itm->{$itm_i} != $floor;
			for my $j ($i .. $#sorted) {
				my $itm_j = $sorted[$j];
				next if $itm->{$itm_j} != $floor;
				my %nitm = %$itm;
				say "moving $itm_i $itm_j from $floor to $nf steps $steps+1";
				$nitm{$itm_i} = $nf;
				$nitm{$itm_j} = $nf;
				push @q, [ 0, $steps+1, $nf, \%nitm ];
			}
		}
	}
}





