#! /usr/bin/perl
use strict;

my ($peg_count, $disk_count) = @ARGV;
my $peg = 'A';
my @list;
push @list, $peg++ for 1..$peg_count;

solve(\@list, [reverse 1..$disk_count]);
exit(0);

# Per peg and number of disks, how many moves to solve the puzzle.
my %cost;
# Per number of pegs and disks, how many will not go on the last peg.
my %use_some_for;
sub strategize {
  my ($pegs, $disks) = @_;
  if (defined($use_some_for{$pegs}[$disks])) {
    # Already solved
  }
  elsif ($disks < 2) {
    $cost{$pegs}[0] = 0;
    $use_some_for{$pegs}[0] = 0;
    $cost{$pegs}[1] = 1;
    $use_some_for{$pegs}[1] = 1;
  }
  elsif (3 == $pegs) {
    strategize($pegs, $disks - 1);
    $cost{$pegs}[$disks] = 1 + 2*$cost{$pegs}[$disks - 1];
    $use_some_for{$pegs}[$disks] = 1;
  }
  else {
    strategize($pegs, $disks - 1);
    my $lower_some = $use_some_for{$pegs}[$disks - 1];
    strategize($pegs - 1, $lower_some + 1);

    my $lower_cost = 2*$cost{$pegs}[$disks - $lower_some]
                   + $cost{$pegs - 1}[$lower_some];
    my $upper_cost = 2*$cost{$pegs}[$disks - $lower_some - 1] 
                   + $cost{$pegs - 1}[$lower_some + 1];

    if ($lower_cost < $upper_cost) {
      $cost{$pegs}[$disks] = $lower_cost;
      $use_some_for{$pegs}[$disks] = $lower_some;
    }
    else {
      $cost{$pegs}[$disks] = $upper_cost;
      $use_some_for{$pegs}[$disks] = $lower_some + 1;
    }
  }
  return $use_some_for{$pegs}[$disks];
}

sub solve {
  my ($peg_list, $disk_list) = @_;
  if (0 == @$disk_list) {
    return; # No steps
  }
  elsif (1 == @$disk_list) {
    print "$disk_list->[0]: $peg_list->[0] -> $peg_list->[1]\n";
  }
  else {
    my $pegs = @$peg_list;
    my $last_disk = $#$disk_list;
    my $cutoff = strategize($pegs, 1 + $last_disk);
    die "No cutoff found for $pegs, $last_disk\n"
      unless defined($cutoff);

    my $from = shift @$peg_list;
    my $to = shift @$peg_list;
    my $hold = pop @$peg_list;

    solve([$from, $hold, $to, @$peg_list], [@$disk_list[$cutoff..$last_disk]]);
    solve([$from, $to, @$peg_list], [@$disk_list[0..($cutoff-1)]]);
    solve([$hold, $to, $from, @$peg_list], [@$disk_list[$cutoff..$last_disk]]);
  }
}