10 [ [0, 0], [1, 0], [2, 0], [3, 0] ], # horiz i
11 [ [0, 1], [1, 1], [2, 1], [1, 0], [1, 2] ], # x
12 [ [0, 0], [1, 0], [2, 0], [2, 1], [2, 2] ], # v
13 [ [0, 0], [0, 1], [0, 2], [0, 3] ], # vert i
14 [ [0, 0], [0, 1], [1, 0], [1, 1] ], # o
26 sub can_move($unit, $vect) {
27 # say "can_move $vect->[0] $vect->[1]";
29 my @dst = ($pt->[0] + $vect->[0], $pt->[1] + $vect->[1]);
30 return 0 if $dst[0] < 0 || $dst[0] >= $w;
31 return 0 if $dst[1] < 0;
32 return 0 if $map[$dst[1]-$map_top][$dst[0]];
38 my $u = $units[$units % @units];
39 # say "unit $units h=$h";
41 my ($x, $y) = (2, $h+3);
43 my $m = $moves[$move++];
45 $move = 0 if $move > $#moves;
47 $x++ if can_move($u, [$x+1, $y]);
49 $x-- if can_move($u, [$x-1, $y]);
51 if (can_move($u, [$x, $y-1])) {
58 $map[$y + $pt->[1] - $map_top][$x + $pt->[0]] = 1;
59 $h = 1 + $y + $pt->[1] if $h < 1 + $y + $pt->[1];
60 while (@map > $max_map) {
71 my $state = join(' ', $units % @units, $move);
72 for my $y (0 .. $#map) {
74 for my $x (0 .. $w-1) {
76 $n |= 1 if $map[$y][$x];
78 $state .= sprintf(" %02x", $n);
81 my ($first_u, $first_h) = $seen{$state} =~ /(\d+) (\d+)$/;
82 my $u_diff = $units - $first_u;
83 my $h_diff = $h - $first_h;
84 # say "$state $units $h\n$seen{$state}\n\n";
85 my $n = int((1000000000000-$units)/$u_diff);
87 $map_top += $n * $h_diff;
88 $units += $n * $u_diff;
89 while ($units < 1000000000000) {
94 $seen{$state} = $state . " $units $h";