+#!/usr/bin/perl -w
+
+use strict;
+use v5.16;
+
+my %items;
+while (<>) {
+ while (/(\w+) gener/g) {
+ $items{"G$1"} = $.;
+ }
+ while (/(\w+)-compat/g) {
+ $items{"M$1"} = $.;
+ }
+}
+
+if (1) {
+$items{Gelerium} = 1;
+$items{Melerium} = 1;
+$items{Gdilithium} = 1;
+$items{Mdilithium} = 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;
+
+use Array::Heap;
+
+my $prev_w = 0;
+ENTRY:
+while (@q) {
+ my $entry = pop_heap @q;
+ my ($w, $steps, $floor, $itm) = @$entry;
+
+ my $key = join('', $floor, map { $itm->{$_} } @sorted);
+ say "$w $steps $key" if $w != $prev_w;
+ $prev_w = $w;
+ next if $seen{$key}++;
+
+ 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;
+ next if $floor == 4 && $itm_i =~ /\AM/;
+ for my $j ($i .. $#sorted) {
+ my $itm_j = $sorted[$j];
+ next if $itm->{$itm_j} != $floor;
+ next if $floor == 4 && $itm_i ne $itm_j;
+ next if $itm_i =~ /\AG/ && $itm_j =~ /\AM/
+ && substr($itm_i, 1) ne substr($itm_j, 1);
+ my %nitm = %$itm;
+ # say "moving $itm_i $itm_j from $floor to $nf steps $steps+1";
+ $nitm{$itm_i} = $nf;
+ $nitm{$itm_j} = $nf;
+ next if !valid_f($nf, \%nitm);
+ next if !valid_f($floor, \%nitm);
+ my $nw = 2*$steps;
+ $nw += 4 - $nitm{$_} for keys %nitm;
+ push_heap @q, [ $nw, $steps+1, $nf, \%nitm ];
+ }
+ }
+ }
+}
+
+
+
+
+