26 'g' => [ 10, 'cdefh' ],
74 'a' => [ 10, 'bcden' ],
84 for my $node (keys %g) {
85 for my $n2 (keys %{ $g{$node} }) {
86 $g{$n2}->{$node} = $g{$node}->{$n2};
107 %otherhome = (%otherhome, reverse %otherhome);
116 my @type = qw( A A B B C C D D );
119 my ($pos, $who, $dst) = @_;
121 my %rpos = map { $_ => $i++ } @$pos;
122 my $src = $pos->[$who];
123 my $mytype = $type[$who];
124 return 0 if defined $rpos{$dst}; # occupied
125 return 0 if !$home{$src} && !$home{$dst}; # cant move in a hallway
127 return 0 if $home{$dst} ne $mytype; # not own home
128 my $other = $otherhome{$dst};
129 return 0 if defined $rpos{$other} && $type[$rpos{$other}] ne $mytype;
130 return 0 if $other gt $dst && !defined $rpos{$other};
134 my $c = $g{$src}->{$dst};
138 for my $in (split //, $c->[1]) {
139 return 0 if $rpos{$in};
142 # say "can_move $who$type[$who]=>$dst ", join(',', keys %rpos);
147 my $min_cost = 100_000;
149 my ($pos, $moved, $cost, $moves) = @_;
150 my $key = join(' ', @$pos, $cost);
151 return if $pos_seen{$key}++;
153 # say "walk ", join(' ', @$pos), " cost $cost";
154 for my $i (0 .. $#$pos) {
158 } elsif ($moved->{$i} == 1) {
159 @dsts = grep { $home{$_} eq $type[$i] } keys %home;
163 for my $dst (@dsts) {
164 my $acost = can_move($pos, $i, $dst);
166 $acost *= $cost_of{$type[$i]};
167 next if $cost + $acost >= $min_cost;
172 my %nmoved = %$moved;
175 my @nmoves = @$moves;
176 push @nmoves, "$i$type[$i]=>$dst $acost";
178 walk(\@npos, \%nmoved, $cost + $acost, \@nmoves);
182 if (!$min_cost || $cost < $min_cost) {
184 say "athome = $athome cost $cost $min_cost: ",
191 walk( [qw( h k i l j o m n )], {}, 0, [ ]);
192 # walk( [qw( i o h l j m k n )], { 0 => 2, 5 => 2 }, 0, [ ]);