50 for my $n1 (keys %g) {
53 my $n2 = chr(ord($n1)+$i);
54 for my $n3 (keys %{ $g{$n1} }) {
55 my $c = $g{$n1}->{$n3};
56 $g{$n2}->{$n3} = [ $c->[0] + $i, $c->[1].$prevnodes ];
63 for my $node (keys %g) {
64 for my $n2 (keys %{ $g{$node} }) {
65 $g{$n2}->{$node} = $g{$node}->{$n2};
77 for my $n1 (keys %home) {
79 my $n2 = chr(ord($n1)+$_);
80 $home{$n2} = $home{$n1};
98 my @type = qw( A A A A B B B B C C C C D D D D );
101 my ($pos, $who, $dst) = @_;
103 my %rpos = map { $_ => $i++ } @$pos;
104 my $src = $pos->[$who];
105 my $mytype = $type[$who];
106 return 0 if defined $rpos{$dst}; # occupied
107 return 0 if !$home{$src} && !$home{$dst}; # cant move in a hallway
110 my $c = $g{$src}->{$dst};
114 for my $in (split //, $c->[1]) {
115 return 0 if defined $rpos{$in};
118 # say "can_move $who$type[$who]=>$dst ", join(',', keys %rpos);
133 for my $i (0 .. $#$pos) {
134 $text =~ s/$pos->[$i]/$type[$i]/gxms;
136 $text =~ s/[a-z]/./gxms;
137 return join('', @$pos) . "\n" .$text;
140 sub print_pos { say gen_pos(shift) }
143 my $min_cost = 100_000;
145 my ($pos, $moved, $can_move, $free_home, $cost, $moves) = @_;
147 my $key = join(' ', @$pos, $cost);
148 return if $pos_seen{$key}++;
150 my $finished = grep { $moved->{$_} && $moved->{$_} == 2 } 0 .. $#$pos;
151 my $stepped = grep { $moved->{$_} && $moved->{$_} == 1 } 0 .. $#$pos;
152 # say "stepped $stepped, finished: $finished";
153 if ($finished == @$pos) {
154 if (!$min_cost || $cost < $min_cost) {
156 say "cost $cost $min_cost: ", @$moves;
161 my %rpos = map { $_ => $x++ } @$pos;
164 say "walk ", join(' ', @$pos), " cost $cost, can_move = ",
165 join(',', keys %$can_move),
166 " free_home = ", join(',', keys %$free_home);
170 for my $i (grep { !$moved->{$_} } keys %$can_move) {
173 my %nmoved = %$moved;
174 my %ncan_move = %$can_move;
175 my %nfree_home = %$free_home;
177 my $mypos = $pos->[$i];
178 my $mytype = $type[$i];
182 delete $ncan_move{$i};
183 my $under = chr(ord($mypos)+1);
184 if (defined $home{$under} && $home{$mypos} eq $home{$under}
185 && !$moved->{$rpos{$under}}) {
186 $ncan_move{$rpos{$under}} = 1;
188 $nfree_home{$home{$mypos}} = $mypos;
190 for my $dst (grep { !defined $rpos{$_} } 'a' .. 'g') {
191 my $acost = can_move($pos, $i, $dst);
193 $acost *= $cost_of{$type[$i]};
194 next if $cost + $acost >= $min_cost;
199 my @nmoves = @$moves;
200 push @nmoves, "$i$type[$i]$pos->[$i]=>$dst $acost\n" . gen_pos($pos) . "\n";
204 walk(\@npos, \%nmoved, \%ncan_move, \%nfree_home, $cost + $acost, \@nmoves);
208 for my $i (grep { $moved->{$_} && $moved->{$_} == 1 } keys %$moved) {
209 my $mypos = $pos->[$i];
210 my $mytype = $type[$i];
211 next if !$free_home->{$mytype};
212 my $dst = $free_home->{$mytype};
214 my $acost = can_move($pos, $i, $dst);
216 $acost *= $cost_of{$type[$i]};
217 next if $cost + $acost >= $min_cost;
219 my %nmoved = %$moved;
220 my %ncan_move = %$can_move;
221 my %nfree_home = %$free_home;
225 delete $nfree_home{$mytype};
226 my $above = chr(ord($dst)-1);
227 if ($home{$above} && $home{$above} eq $mytype) {
228 $nfree_home{$mytype} = $above;
231 delete $ncan_move{$i};
236 my @nmoves = @$moves;
237 push @nmoves, "$i$type[$i]$pos->[$i]=>$dst $acost\n" . gen_pos($pos) . "\n";
238 # say "xxx ", $nmoves[-1];
240 walk(\@npos, \%nmoved, \%ncan_move, \%nfree_home, $cost + $acost, \@nmoves);
247 # A A A A B B B B C C C C D D D D
248 walk( [qw( h o r u k n p q l m v w i j s t )],
250 { map { $_ => 1 } qw(0 8 6 15) },
253 walk( [qw( k r u w h n p q l m s v i j o t )],
255 { map { $_ => 1 } qw(4 8 6 15) },