#!/usr/bin/perl -w
# Fri Nov  7 12:32:17 EST 2003
# Provides solutions to win the Peg Game
#

my $starting_peg   = 0;
my $show_losses    = 0;
my $show_board     = 0;
my $machine_format = 1;
my $pause_on_win   = 0;

my @available_paths;

my $won_games;
my $history;

my %OCCUPIED;
my %ROUTES;

$ROUTES{1} = "6,3;4,2";
$ROUTES{2} = "9,5;7,4";
$ROUTES{3} = "10,6;8,5";
$ROUTES{4} = "13,8;11,7";
$ROUTES{5} = "14,9;12,8";
$ROUTES{6} = "15,10;13,9;4,5;1,3";
$ROUTES{7} = "2,4;9,8";
$ROUTES{8} = "3,5;10,9";
$ROUTES{9} = "7,8;2,5";
$ROUTES{10} = "8,9;3,6";
$ROUTES{11} = "4,7;13,12";
$ROUTES{12} = "5,8;14,13";
$ROUTES{13} = "6,9;15,14;11,12";
$ROUTES{14} = "12,13;5,9";
$ROUTES{15} = "13,14;6,10";

while ( 1 ) {
  init_board();

  while ( 1 ) {
    build_route_table();

    show_board() if ($show_board);

   if (@available_paths) {
      $max_paths = @available_paths;
      $choice = int(rand $max_paths);

      move_peg($available_paths[$choice]);
    } else {
      last;
    }
  }

  chop($history) if ($machine_format);

  $peg_count = get_total_pegs();

  if ($peg_count == 1) {
    if ($machine_format) {
      print "$peg_count $history\n";
    } else {
      print "-= Won! =- $history: $peg_count pegs left.\n";
    }

    if ($pause_on_win) {
      print "\n<< PRESS RETURN TO CONTINUE >>\n";
      <STDIN>;
    }
  } else {
    if ($show_losses) {
      if ($machine_format) {
        print "$peg_count $history\n";
      } else {
        print "Lost       $history: $peg_count pegs left.\n";
      }
    }
  }
}

sub init_board
{
  my ($count);

  for ( $count = 1 ; $count < 16 ; $count++ ) {
    $OCCUPIED{$count} = 1;
  }

  if ($starting_peg) { 
    $rand = $starting_peg;
  } else {
    $rand = int(rand 14) + 1 
  }

  $OCCUPIED{$rand} = 0;

  if ($machine_format) {
    $history = "";
  } else {
    $history = "Removed Peg: $rand: "; 
  }
}

sub get_total_pegs
{
  my ($count,$peg_count);

  for ( $count = 1 ; $count < 16 ; $count++ ) {
    if ($OCCUPIED{$count} == 1) {
      $peg_count++;
    }
  }
  return($peg_count);
}

sub build_route_table
{
  my ($count,@free_pegs,$rand);

  @available_paths = ();

  @free_pegs = get_free_pegs();

  foreach $count (@free_pegs) {
    @array = split(';',$ROUTES{$count});
    
    foreach $element (@array) {
      if ($path = check_available_path($count,$element)) {
        push(@available_paths,$path);
      }
    }
  }
}

sub move_peg
{
  my $move = shift;
  my ($start,$mid,$end) = split(',',$move);
 
  if ($machine_format) { 
    $history .= "$start->$mid->$end,";
  } else { 
    $history .= "$start->$mid->$end ";
  }

  $OCCUPIED{$start} = 0;
  $OCCUPIED{$mid}   = 0;
  $OCCUPIED{$end}   = 1;
}

sub check_available_path
{
  my ($dest,$path) = @_;

  ($start,$mid) = split(',',$path);

  if ($OCCUPIED{$start} && $OCCUPIED{$mid}) {
    return("$start,$mid,$dest");
  } else {
    return(0);
  }
}

sub get_free_pegs 
{
  my ($count,@free_pegs);

  for ( $count = 1 ; $count < 16 ; $count++ ) {
    if ($OCCUPIED{$count} == 0) {
      push(@free_pegs,$count);
    }
  }

  return(@free_pegs);
}

sub show_board
{
print <<EOBOARD;

           1                    $OCCUPIED{1}
         2   3                $OCCUPIED{2}   $OCCUPIED{3}
       4   5   6            $OCCUPIED{4}   $OCCUPIED{5}   $OCCUPIED{6}
     7   8   9  10        $OCCUPIED{7}   $OCCUPIED{8}   $OCCUPIED{9}   $OCCUPIED{10}
  11   12  13  14  15   $OCCUPIED{11}   $OCCUPIED{12}   $OCCUPIED{13}   $OCCUPIED{14}   $OCCUPIED{15}

EOBOARD
}