use warnings;
use strict;
use Time::HiRes qw( gettimeofday tv_interval );

my $maxflips = 0;
my @max_sequence;

for my $num ( 1 .. 10 ) {
    my @start_time = gettimeofday();
    @max_sequence = ();
    print "Pfannkuchen($num) = " . fannkuch( [ 1 .. $num ] ) . " for:\n";
    print sort @max_sequence;
    my @end_time = gettimeofday();
    print tv_interval ( \@start_time, \@end_time ), " elapsed seconds.\n\n";
}

sub fannkuch {
    my ( $aref, $level ) = ( @_, 0 );
    my ( $index, $copy, $ok ) = ( $level, [@$aref], $level + 1 == @$aref );
    do {
        if ($ok) {
            if ( $copy->[0] != 1 and $copy->[-1] != @$copy ) {
                my @q = @$copy;
#                my ( $i, $k, $flips );
                my ( $k, $flips );
                for ( $flips = 0 ; ( $k = $q[0] ) != 1 ; $flips++ ) {
#                    for ( $k--, $i = 0 ; $i < $k ; $i++, $k-- ) {
#                       @q[ $i, $k ] = @q[ $k, $i ];
#                    }
                    @q[ 0 .. $k-1 ] = reverse @q[ 0 .. $k-1 ];
                }
                if ( $flips > $maxflips ) {
                    $maxflips     = $flips;
                    @max_sequence = ();
                }
                push @max_sequence, join '', @$copy, "\n"
                  if ( $maxflips == $flips );
            }
        }
        else {
            fannkuch( $copy, 1 + $level );
        }
        @$copy[ $index - 1, $index ] = @$copy[ $index, $index - 1 ]
          if $index != 0;

    } while $index-- > 0;
    return $maxflips;
}