#!/usr/bin/perl -w
use strict;
# A board is a string of 35 characters showing current positions
# and last move or two (so we don't just undo the last move):
# ,----. ,----. ,----. ,----. ,----. ,----. ,----. ,----.
# |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB|
# |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB|
# | HH | |HH< | |HH2 | |HH2 | |HH>2| |HH42| |HH42| |HH4v|
# |C12D| |C12D| |C1^D| |C14D| |C14D| |C1^D| |C1D<| |C1D2|
# |C34D| |C34D| |C34D| |C3^D| |C3 D| |C3 D| |C3D<| |C3D |
# `----' `----' `----' `----' `----' `----' `----' `----'
#        H<     H<2^   H<2^4^ ...
# On the end of the board we keep all the moves needed.
# We start with just one board and build the list of boards
# we can get with one more move.

$|= 1;
my $start= "#####AXXB#AXXB# HH #C12D#C34D######";
my @boards= $start;
my %double;
@double{ qw( A< A> B< B> C< C> D< D> H^ Hv X< X> X^ Xv ) }
    = (1) x 14;
my %offset= qw( < -1 > +1 ^ -5 v +5 );
my %size= qw( 1 1 2 1 3 1 4 1 A 2 B 2 C 2 D 2 H 2 X 4 );
my %back= qw( < > > < ^ v v ^ );
$back{' '}= ' ';
my @MovedX;
my $moves= 0;
my $dupCount= 1;
my %uniq;

while(  1  ) {
    @MovedX= ();
    print "Considering ", 0+@boards,
        " of $dupCount boards after $moves moves...\n";
    Dump( @boards )   if  @ARGV;
    @boards= map MoveAny($_), @boards;
    $dupCount= @boards;
    @boards= grep {
        my $board= substr( $_, 0, 35 );
        $board =~ tr[<>^v1234ABCDH]
                    [    OOOO||||=];
        ! $uniq{$board}++;
    } @boards;
    $moves++;
    # Dump( @MovedX );
}

sub MoveAny
{
    my( $board )= @_;
    my @boards;
    $board =~ /[<>v^ ]/g or die $board;  my @gap= pos($board)-1;
    $board =~ /[<>v^ ]/g or die $board;  push @gap, pos($board)-1;
    my %can;
    for my $gap (  @gap  ) {
        my $skip= $back{substr($board,$gap,1,' ')};
        for my $dir (  keys %offset  ) {
            next   if  $skip eq $dir;
            my $off= $offset{$dir};
            my $block= substr($board,$gap-$off,1);
            next   if  ! $size{$block};
            if(     ! $double{$block.$dir}
                ||  2 <= ++$can{$block.$dir}
            ) {
                push @boards, MoveThis( $board, $block, $dir, $off );
            }
        }
    }
    return @boards;
}

sub MoveThis
{
    my( $board, $block, $dir, $off )= @_;
    my @pos;
    while(  $board =~ /$block/g  ) {
        last   if  30 < pos($board);
        push @pos, pos($board)-1;
    }
    substr( $board, $_, 1, $dir )   for  @pos;
    substr( $board, $_+$off, 1, $block )   for  @pos;
    $board .= $block . $dir;
    Win($board)   if  $board =~ /XX[^#]##/;
    if(  "X" eq $block  ) {
        push @MovedX, $board;
    }
    return $board;
}

sub Dump
{
    my( @all )= @_;
    while(  @all  ) {
        my @boards= splice( @all, 0, 8 );
        for my $line (  0 .. 6  ) {
            for my $board (  @boards  ) {
                print " #", substr($board,5*$line,5);
            }
            print $/;
        }
        if(  1 == @boards  ) {
            print " ", substr($boards[0],35);
        } else {
            for my $board (  @boards  ) {
                printf " %-6s", substr(substr($board,35),-6);
            }
        }
        print $/;
    }
}

my $won;
sub Win
{
    return   if  $won++;
    my( $board )= @_;
    my @moves= substr($board,35) =~ /(..)/g;
    print "\n @moves\n\n";
    $board= $start;
    my @boards= $board;
    for my $move (  @moves  ) {
        my( $block, $dir )= $move =~ /(.)(.)/;
        substr( $board, 35 )= '';
        $board =~ tr/<>^v/    /;
        $board= MoveThis( $board, $block, $dir, $offset{$dir} );
        push @boards, $board;
    }
    Dump( @boards );
    exit 0;
}

##</code><code>##

 > perl MoveBlocks.pl2
Considering 1 of 1 boards after 0 moves...
Considering 6 of 6 boards after 1 moves...
Considering 12 of 20 boards after 2 moves...
Considering 20 of 35 boards after 3 moves...
Considering 33 of 70 boards after 4 moves...
Considering 32 of 91 boards after 5 moves...
Considering 31 of 96 boards after 6 moves...
Considering 29 of 74 boards after 7 moves...
Considering 25 of 49 boards after 8 moves...
Considering 26 of 51 boards after 9 moves...
Considering 34 of 62 boards after 10 moves...
Considering 35 of 73 boards after 11 moves...
Considering 29 of 72 boards after 12 moves...
Considering 25 of 59 boards after 13 moves...
Considering 23 of 43 boards after 14 moves...
Considering 30 of 43 boards after 15 moves...
Considering 38 of 58 boards after 16 moves...
Considering 41 of 74 boards after 17 moves...
Considering 38 of 83 boards after 18 moves...
Considering 42 of 92 boards after 19 moves...
Considering 54 of 109 boards after 20 moves...
Considering 51 of 116 boards after 21 moves...
Considering 46 of 107 boards after 22 moves...
Considering 45 of 92 boards after 23 moves...
Considering 41 of 88 boards after 24 moves...
Considering 53 of 103 boards after 25 moves...
Considering 59 of 117 boards after 26 moves...
Considering 54 of 119 boards after 27 moves...
Considering 45 of 111 boards after 28 moves...
Considering 46 of 116 boards after 29 moves...
Considering 53 of 131 boards after 30 moves...
Considering 52 of 121 boards after 31 moves...
Considering 49 of 99 boards after 32 moves...
Considering 63 of 102 boards after 33 moves...
Considering 85 of 131 boards after 34 moves...
Considering 118 of 204 boards after 35 moves...
Considering 144 of 287 boards after 36 moves...
Considering 177 of 351 boards after 37 moves...
Considering 204 of 407 boards after 38 moves...
Considering 248 of 493 boards after 39 moves...
Considering 271 of 590 boards after 40 moves...
Considering 291 of 666 boards after 41 moves...
Considering 328 of 720 boards after 42 moves...
Considering 344 of 751 boards after 43 moves...
Considering 347 of 722 boards after 44 moves...
Considering 366 of 732 boards after 45 moves...
Considering 371 of 772 boards after 46 moves...
Considering 375 of 804 boards after 47 moves...
Considering 380 of 826 boards after 48 moves...
Considering 390 of 842 boards after 49 moves...
Considering 427 of 892 boards after 50 moves...
Considering 441 of 966 boards after 51 moves...
Considering 446 of 958 boards after 52 moves...
Considering 455 of 919 boards after 53 moves...
Considering 493 of 984 boards after 54 moves...
Considering 537 of 1080 boards after 55 moves...
Considering 585 of 1183 boards after 56 moves...
Considering 623 of 1297 boards after 57 moves...
Considering 614 of 1360 boards after 58 moves...
Considering 625 of 1405 boards after 59 moves...
Considering 592 of 1391 boards after 60 moves...
Considering 511 of 1233 boards after 61 moves...
Considering 470 of 1094 boards after 62 moves...
Considering 458 of 1023 boards after 63 moves...
Considering 431 of 966 boards after 64 moves...
Considering 420 of 935 boards after 65 moves...
Considering 398 of 897 boards after 66 moves...
Considering 350 of 826 boards after 67 moves...
Considering 322 of 734 boards after 68 moves...
Considering 313 of 708 boards after 69 moves...
Considering 282 of 640 boards after 70 moves...
Considering 265 of 567 boards after 71 moves...
Considering 235 of 531 boards after 72 moves...
Considering 222 of 504 boards after 73 moves...
Considering 190 of 438 boards after 74 moves...
Considering 154 of 357 boards after 75 moves...
Considering 140 of 304 boards after 76 moves...
Considering 118 of 272 boards after 77 moves...
Considering 113 of 253 boards after 78 moves...
Considering 92 of 218 boards after 79 moves...
Considering 80 of 194 boards after 80 moves...
Considering 66 of 158 boards after 81 moves...
Considering 60 of 130 boards after 82 moves...
Considering 56 of 116 boards after 83 moves...
Considering 64 of 130 boards after 84 moves...
Considering 62 of 141 boards after 85 moves...
Considering 73 of 155 boards after 86 moves...
Considering 79 of 159 boards after 87 moves...
Considering 95 of 175 boards after 88 moves...
Considering 103 of 209 boards after 89 moves...
Considering 117 of 244 boards after 90 moves...
Considering 131 of 270 boards after 91 moves...
Considering 138 of 276 boards after 92 moves...
Considering 162 of 303 boards after 93 moves...
Considering 184 of 356 boards after 94 moves...
Considering 210 of 433 boards after 95 moves...
Considering 218 of 466 boards after 96 moves...
Considering 255 of 497 boards after 97 moves...
Considering 280 of 570 boards after 98 moves...
Considering 284 of 620 boards after 99 moves...
Considering 266 of 600 boards after 100 moves...
Considering 263 of 581 boards after 101 moves...
Considering 248 of 544 boards after 102 moves...
Considering 238 of 528 boards after 103 moves...
Considering 218 of 506 boards after 104 moves...
Considering 206 of 477 boards after 105 moves...
Considering 191 of 458 boards after 106 moves...
Considering 164 of 413 boards after 107 moves...
Considering 154 of 366 boards after 108 moves...
Considering 151 of 324 boards after 109 moves...
Considering 149 of 314 boards after 110 moves...
Considering 146 of 321 boards after 111 moves...

##</code><code>##

 H< 2^ 2> H> C^ 3< 4< D< 2v H> 1^ 4^ 3> Cv 1< H<
 Bv 2v Bv X> A> 1^ 1^ C^ C^ 4< 3< D< 2< 2^ Bv H>
 D^ 3> 3> Dv Av 1> C^ 4^ D< Av Av 4> 4^ H< H< B^
 3> 2v B< 3^ 2> Bv H> Cv 1< 4^ H> A^ A^ B< 3< 3v
 Hv Xv 4> 1> C^ 4> 1> A^ D^ B^ 3< 3< 2< 2< Hv Xv
 1v 1> A> B^ B^ X< 1v 4v 1v 4v A> B> C> D^ D^ X<
 4< 1^ H^ 2> 3> 2> 3> Xv 4< 4< 1< 1< H^ 3^ 3> X>

##</code><code>##

 ###### ###### ###### ###### ###### ###### ###### ######
 #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB#
 #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB#
 # HH # #HH< # #HH2 # #HH>2# #>HH2# #CHH2# #CHH2# #CHH2#
 #C12D# #C12D# #C1^D# #C1 D# #C1 D# #C1 D# #C1 D# #C1 D#
 #C34D# #C34D# #C34D# #C34D# #C34D# #^34D# #3<4D# #34<D#
 ###### ###### ###### ###### ###### ###### ###### ######
        H<     2^     2>     H>     C^     3<     4<
 ###### ###### ###### ###### ###### ###### ###### ######
 #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB#
 #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB# #AXXB#
 #CHH2# #CHHv# #C>HH# #C1HH# #C1HH# #C1HH# #v1HH# #1<HH#
 #C1D<# #C1D2# #C1D2# #C^D2# #C4D2# #C4D2# #C4D2# #C4D2#
 #34D<# #34D # #34D # #34D # #3^D # #>3D # #C3D # #C3D #
 ###### ###### ###### ###### ###### ###### ###### ######
 D<     2v     H>     1^     4^     3>     Cv     1<
 ###### ###### ###### ###### ###### ###### ###### ######
 #AXXB# #AXXv# #AXX # #AXX # #A>XX# #>AXX# # AXX# #1AXX#
 #AXXB# #AXXB# #AXXB# #AXXv# #A>XX# #>AXX# #1AXX# #^AXX#
 #1HH<# #1HHB# #1HHB# #1HHB# #1HHB# #1HHB# #^HHB# # HHB#
 #C4D2# #C4D2# #C4Dv# #C4DB# #C4DB# #C4DB# #C4DB# #C4DB#
 #C3D # #C3D # #C3D2# #C3D2# #C3D2# #C3D2# #C3D2# #C3D2#
 ###### ###### ###### ###### ###### ###### ###### ######
 H<     Bv     2v     Bv     X>     A>     1^     1^
 ###### ###### ###### ###### ###### ###### ###### ######
 #1AXX# #1AXX# #1AXX# #1AXX# #1AXX# #1AXX# #1AXX# #1AXX#
 # AXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX#
 #CHHB# #CHHB# #CHHB# #CHHB# #CHHB# #CHHB# #CHHB# #CHHv#
 #C4DB# #^4DB# #4<DB# #4 DB# #4D<B# #4D B# #4D2B# #4D2B#
 #^3D2# # 3D2# # 3D2# #3<D2# #3D<2# #3D2<# #3D^ # #3D B#
 ###### ###### ###### ###### ###### ###### ###### ######
 C^     C^     4<     3<     D<     2<     2^     Bv
 ###### ###### ###### ###### ###### ###### ###### ######
 #1AXX# #1AXX# #1AXX# #1AXX# #1AXX# #1vXX# #>1XX# #C1XX#
 #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX#
 #C>HH# #CDHH# #CDHH# #CDHH# #CvHH# #CAHH# #CAHH# #^AHH#
 #4D2B# #4D2B# #4D2B# #4D2B# #4D2B# #4D2B# #4D2B# #4D2B#
 #3D B# #3^ B# #>3 B# # >3B# # D3B# # D3B# # D3B# # D3B#
 ###### ###### ###### ###### ###### ###### ###### ######
 H>     D^     3>     3>     Dv     Av     1>     C^
 ###### ###### ###### ###### ###### ###### ###### ######
 #C1XX# #C1XX# #C1XX# #C1XX# #C1XX# #C1XX# #C1XX# #C1XX#
 #CAXX# #CAXX# #CvXX# #C XX# #C XX# #C4XX# #C4XX# #C4XX#
 #4AHH# #4AHH# #4AHH# #4vHH# #>4HH# # ^HH# # HH<# #HH< #
 #^D2B# #D<2B# #DA2B# #DA2B# #DA2B# #DA2B# #DA2B# #DA2B#
 # D3B# #D<3B# #D 3B# #DA3B# #DA3B# #DA3B# #DA3B# #DA3B#
 ###### ###### ###### ###### ###### ###### ###### ######
 4^     D<     Av     Av     4>     4^     H<     H<
 ###### ###### ###### ###### ###### ###### ###### ######
 #C1XX# #C1XX# #C1XX# #C1XX# #C1XX# #C1XX# #C1XX# #C1XX#
 #C4XX# #C4XX# #C4XX# #C4XX# #C4XX# #C4XX# #C4XX# #C4XX#
 #HH B# #HH B# #HH B# #HHB<# #HHB # #HHB # #HHv # #>HH #
 #DA2B# #DA2B# #DAvB# #DAB<# #DAB3# #DAB3# #DAB3# #DAB3#
 #DA3^# #DA>3# #DA23# #DA23# #DA2^# #DA>2# #DAB2# #DAB2#
 ###### ###### ###### ###### ###### ###### ###### ######
 B^     3>     2v     B<     3^     2>     Bv     H>
 ###### ###### ###### ###### ###### ###### ###### ######
 #v1XX# #1<XX# #14XX# #14XX# #14XX# #14XX# #14XX# #14XX#
 #C4XX# #C4XX# #C^XX# #C XX# #C XX# #CAXX# #CAXX# #CAXX#
 #CHH # #CHH # #CHH # #C>HH# #CAHH# #CAHH# #CAHH# #CAHH#
 #DAB3# #DAB3# #DAB3# #DAB3# #DAB3# #D^B3# #DB<3# #DB3<#
 #DAB2# #DAB2# #DAB2# #DAB2# #D^B2# #D B2# #DB<2# #DB 2#
 ###### ###### ###### ###### ###### ###### ###### ######
 Cv     1<     4^     H>     A^     A^     B<     3<
 ###### ###### ###### ###### ###### ###### ###### ######
 #14XX# #14XX# #14vv# #1>4 # #>14 # #C14 # #C1>4# #C>14#
 #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX#
 #CAHH# #CAvv# #CAXX# #CAXX# #CAXX# #^AXX# # AXX# # AXX#
 #DBv # #DBHH# #DBHH# #DBHH# #DBHH# #DBHH# #DBHH# #DBHH#
 #DB32# #DB32# #DB32# #DB32# #DB32# #DB32# #DB32# #DB32#
 ###### ###### ###### ###### ###### ###### ###### ######
 3v     Hv     Xv     4>     1>     C^     4>     1>
 ###### ###### ###### ###### ###### ###### ###### ######
 #CA14# #CA14# #CA14# #CA14# #CA14# #CA14# #CA14# #CA14#
 #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX# #CAXX#
 # ^XX# #D XX# #DBXX# #DBXX# #DBXX# #DBXX# #DBXX# #DBXX#
 #DBHH# #DBHH# #DBHH# #DBHH# #DBHH# #DBHH# #DBHH# #DBvv#
 #DB32# #^B32# # ^32# # 3<2# #3< 2# #3 2<# #32< # #32HH#
 ###### ###### ###### ###### ###### ###### ###### ######
 A^     D^     B^     3<     3<     2<     2<     Hv
 ###### ###### ###### ###### ###### ###### ###### ######
 #CA14# #CAv4# #CA 4# #C>A4# #C A4# #CBA4# #CBA4# #CBA4#
 #CAvv# #CA1 # #CA>1# #C>A1# #CBA1# #CBA1# #CBA1# #CBAv#
 #DBXX# #DBXX# #DBXX# #DBXX# #DBXX# #D^XX# #DXX<# #DXX1#
 #DBXX# #DBXX# #DBXX# #DBXX# #D^XX# #D XX# #DXX<# #DXX #
 #32HH# #32HH# #32HH# #32HH# #32HH# #32HH# #32HH# #32HH#
 ###### ###### ###### ###### ###### ###### ###### ######
 Xv     1v     1>     A>     B^     B^     X<     1v
 ###### ###### ###### ###### ###### ###### ###### ######
 #CBAv# #CBA # #CBA # #CB>A# #C>BA# #>CBA# # CBA# #DCBA#
 #CBA4# #CBA4# #CBAv# #CB>A# #C>BA# #>CBA# #DCBA# #DCBA#
 #DXX1# #DXXv# #DXX4# #DXX4# #DXX4# #DXX4# #DXX4# #^XX4#
 #DXX # #DXX1# #DXX1# #DXX1# #DXX1# #DXX1# #^XX1# # XX1#
 #32HH# #32HH# #32HH# #32HH# #32HH# #32HH# #32HH# #32HH#
 ###### ###### ###### ###### ###### ###### ###### ######
 4v     1v     4v     A>     B>     C>     D^     D^
 ###### ###### ###### ###### ###### ###### ###### ######
 #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA#
 #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA#
 #XX<4# #XX4<# #XX41# #XX41# #XX41# #XX41# #XX41# #XX41#
 #XX<1# #XX 1# #XX ^# #XXHH# #XXHH# #XXHH# #XXHH# #XXHH#
 #32HH# #32HH# #32HH# #32^^# #3>2 # #>32 # # 3>2# # >32#
 ###### ###### ###### ###### ###### ###### ###### ######
 X<     4<     1^     H^     2>     3>     2>     3>
 ###### ###### ###### ###### ###### ###### ###### ######
 #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA#
 #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA# #DCBA#
 #vv41# # 4<1# #4< 1# #4 1<# #41< # #41HH# #41HH# #41HH#
 #XXHH# #XXHH# #XXHH# #XXHH# #XXHH# #XX^^# #XX3 # #XX>3#
 #XX32# #XX32# #XX32# #XX32# #XX32# #XX32# #XX^2# #XX 2#
 ###### ###### ###### ###### ###### ###### ###### ######
 Xv     4<     4<     1<     1<     H^     3^     3>
 ######
 #DCBA#
 #DCBA#
 #41HH#
 #>XX3#
 #>XX2#
 ######
 X>