2016/21.pl

   1 #!/usr/bin/perl -w
   2
   3 use strict;
   4 use v5.30;
   5
   6 my %items;
   7 while (<>) {
   8         while (/(\w+) gener/g) {
   9                 $items{"G$1"} = $.;
  10         }
  11         while (/(\w+)-compat/g) {
  12                 $items{"M$1"} = $.;
  13         }
  14 }
  15
  16 my @q = ([ 0, 0, 1, \%items ]);
  17
  18 sub valid_f {
  19         my ($f, $itm) = @_;
  20         my %g_cur = map { substr($_, 1) => 1 }
  21                 grep { $_ =~ /^G/ && $itm->{$_} == $f } keys %$itm;
  22         return 1 if !keys %g_cur;
  23         for my $c (grep { $_ =~ /^M/ && $itm->{$_} == $f } keys %$itm) {
  24                 return undef if !$g_cur{ substr($c, 1) };
  25         }
  26         return 1;
  27 }
  28
  29 my @sorted = sort keys %items;
  30 my %seen;
  31 ENTRY:
  32 while (@q) {
  33         my $entry = shift @q;
  34         my ($w, $steps, $floor, $itm) = @$entry;
  35
  36         my $key = join('|', $floor, map { $itm->{$_} } @sorted);
  37         say "$key";
  38         next if $seen{$key}++;
  39
  40         for (1 .. 4) {
  41                 next ENTRY if !valid_f($_, $itm);
  42         }
  43         say "valid";
  44
  45         if (!grep { $itm->{$_} != 4 } keys %$itm) {
  46                 say "$steps";
  47                 last;
  48         }
  49
  50         for my $nf ($floor+1, $floor-1) {
  51                 next if $nf < 1 || $nf > 4;
  52                 for my $i (0 .. $#sorted) {
  53                         my $itm_i = $sorted[$i];
  54                         next if $itm->{$itm_i} != $floor;
  55                         for my $j ($i .. $#sorted) {
  56                                 my $itm_j = $sorted[$j];
  57                                 next if $itm->{$itm_j} != $floor;
  58                                 my %nitm = %$itm;
  59                                 say "moving $itm_i $itm_j from $floor to $nf steps $steps+1";
  60                                 $nitm{$itm_i} = $nf;
  61                                 $nitm{$itm_j} = $nf;
  62                                 push @q, [ 0, $steps+1, $nf, \%nitm ];
  63                         }
  64                 }
  65         }
  66 }
  67
  68
  69
  70
  71