use strict;
use warnings;

use Data::Dumper;

my $BOARD_SIZE = 8;
my $BOARD_BLACK = 1;
my $BOARD_WHITE = 2;
my $NO_PIECE = 0;
my $INVALID_PIECE_NUMBER = -1; # not all positions are allowed for putting a piece
my $BLACK_NORMAL = 1;
my $BLACK_KING = 2;
my $WHITE_NORMAL = 3;
my $WHITE_KING = 4;
my $STEP_TO_KING = 1;

my $NORMAL_MOVE = 1;
my $NORMAL_JUMP = 2;
my %symbols = 
	(0 => '-', 1 => 'x', 2 => 'X', 3 => 'o', 4 => 'O',); 
	
my ($board, $file);
$file =  "first_position.txt";
$board = init_board_with_file($BOARD_SIZE, $file);
while (<>) {
	chomp;
	last if (/^[qQ]/);
	if (/(\d+)-(\d+)/) {
		my $jump = move_piece($board, $1, $2);
		if (!defined $jump) {
			print "Invalid move. Please try again.\n";
		} else {
			$board = copy_board($jump->{board});
			print_board($board);
		}
		next;
	}
	if (/^[pP]/) {
		print_board($board);
		next;
	}
	if (/^[Ss](ave)?\s+(.*)/) {
		save_board_to_file($board, $2);
		next;
	}
}
exit(0);

# board initialization, copying, saving and printing

sub init_board
{
	my ($size) = (@_);
	my $board;
	$board->{size} = $BOARD_SIZE;
	for (my $i=1; $i<= $BOARD_SIZE*$BOARD_SIZE/2; $i++) {
		$board->{pieces}->[$i] = $NO_PIECE;
		$board->{pieces}->[$i] = $NO_PIECE;
	}
	my $piece_count;
	$piece_count = $BOARD_SIZE/2*($BOARD_SIZE/2-1); 
	for (my $i=1; $i<= $piece_count; $i++) {
		$board->{pieces}->[$i] = $WHITE_NORMAL;
	}
	for (my $i=1; $i<= $piece_count; $i++) {
		$board->{pieces}->[$BOARD_SIZE*$BOARD_SIZE/2-$i+1] = $BLACK_NORMAL;
	}
	return $board;
}

sub empty_board
{
	my ($board) = (@_);
	# we often assume black is at the bottom for the time being
	my $piece_count;
	$piece_count = $BOARD_SIZE/2*($BOARD_SIZE/2-1); 
	for (my $i=1; $i<= $BOARD_SIZE*$BOARD_SIZE/2; $i++) {
		$board->{pieces}->[$i] = $NO_PIECE;
	}
}

# row N: If N is odd, then only even column has piece, and piece number is col/2+(row-1)*($BOARD_SIZE/2)
# row N: If N is even, then only odd column has piece, and piece number is (col+1)/2+(row-1)*($BOARD_SIZE/2)
sub print_board
{
	my ($board) = (@_);
	print "    1 2 3 4 5 6 7 8\n";
	for (my $row=1; $row <= $BOARD_SIZE; $row++) {
		print $row . "  ";
		for (my $col=1; $col <= $BOARD_SIZE; $col++) {
			my $piece_number; 
			$piece_number = get_piece_number_from_row_col($row, $col);
			if ($piece_number == $INVALID_PIECE_NUMBER) {
				print "  ";
			} else {
				my $piece_type;
				$piece_type = $board->{pieces}->[$piece_number];
				print " " . $symbols{$piece_type};
			}
		}
		print "    " . $row*$BOARD_SIZE/2 . "\n";
	}
}

# Default is to return the standard 8x8 board in the starting position
sub init_board_with_file
{
	my ($size, $file) = (@_);
	my $board = {};
	if (!$size or !$file) {
		$board = init_board($BOARD_SIZE);
		return $board;
	}
	empty_board($board);
	my $fh;
	open $fh, "$file" or die "Cannot open $file\n";
	while (<$fh>) {
		next unless (/^\s*(.):\s+(.+)\s*$/); 
		# Initialize with the right color
		my $color = $1;
		my $pieces = $2;
		my @pos;
		@pos = split(/,\s*/, $pieces);
		foreach my $p (@pos) {
			$p =~ s/^\s+//;
			$p =~ s/\s+$//;
			next unless ($p =~ /^(\d+)(k?)$/);
			# $1 is piece #, $2 is king or not
			if (uc($color) eq 'B') {
				if ($2) {
					$board->{pieces}->[$1] = $BLACK_KING;
				} else {
					$board->{pieces}->[$1] = $BLACK_NORMAL;
				}
			} else {
				# white
				if ($2) {
					$board->{pieces}->[$1] = $WHITE_KING;
				} else {
					$board->{pieces}->[$1] = $WHITE_NORMAL;
				}
			}

		}
	}
	close($fh);
	return $board;
}

# Helper functions to do conversions between (row,col) and piece_number

sub get_row_col_from_piece_number
{
	my ($piece_number) = (@_);
	if ($piece_number<1 or $piece_number>$BOARD_SIZE*$BOARD_SIZE/2) {
		return (0, 0);
	}
	my $row =  int(($piece_number-1)/($BOARD_SIZE/2))+1;
	my $col = ($piece_number-1)%($BOARD_SIZE/2); # 0-3, 0-3
	if ($row%2==1) {
		$col = 2*($col+1);
	} else {
		$col = 2*$col+1;
	}
	return ($row, $col);
}

# row is 1-8, col is 1-8
sub get_piece_number_from_row_col
{
	my ($row, $col) = (@_);
	my $piece_number;
	if ($row<1 or $row>$BOARD_SIZE) {
		return $INVALID_PIECE_NUMBER;
	}
	if ($col<1 or $col>$BOARD_SIZE) {
		return $INVALID_PIECE_NUMBER;
	}
	if ($row % 2 == 1) { # odd rows
		if ($col %2 ==0) { # even column
			$piece_number = $col/2+($row-1)*($BOARD_SIZE/2);
		} else {
			$piece_number = $INVALID_PIECE_NUMBER;
		}
	} else { # even rows
		if ($col %2 ==1) { # odd column
			$piece_number = ($col+1)/2+($row-1)*($BOARD_SIZE/2);
		} else {
			$piece_number = $INVALID_PIECE_NUMBER;
		}
	}
	return $piece_number;
}

sub move_piece
{
	my ($board, $start_piece, @locations) = (@_);
	my $moves;
	my $last_loc;
	$last_loc = $#locations;
	$moves = get_all_moves($board, $start_piece);
	foreach my $move (@$moves) {
		if ($move->{end} == $locations[$last_loc]) {
			return $move;
		}
	}
	return undef;
}

# Get the next moves that we can move to (no jumps)
sub get_next_move_neighbors
{
	my ($board, $piece) = (@_);
	my @neighbors;
	my @moves;
	@neighbors = get_neighbor_pieces($piece);
	foreach my $next (@neighbors) {
		if ($board->{pieces}->[$next] == $NO_PIECE) {
			my $piece_type = $board->{pieces}->[$piece];
			if (is_move_direction_allowed($board, $piece, $next)) {
				my $move;
				$move->{type} = $NORMAL_MOVE;
				$move->{start} = $piece;
				$move->{end} = $next;
				$move->{board} = copy_board($board);
				$move->{board}->{pieces}->[$piece] = $NO_PIECE;
				$move->{board}->{pieces}->[$next] = $piece_type;
				my ($row, $col);
				($row, $col) = get_row_col_from_piece_number($next);
				if ((($piece_type == $BLACK_NORMAL) or 
					($piece_type == $WHITE_NORMAL)) and 
					(($row == 1) or ($row == $BOARD_SIZE))) {
					$move->{board}->{pieces}->[$next] += $STEP_TO_KING;
					$move->{final} = 1;
				}
				push @moves, $move;
			}
		}
	}
	return \@moves;
}

# this includes both moves and jumps
# If there exist both moves & jumps, then only jumps are allowed
sub get_all_moves
{
	my ($board, $piece) = (@_);
	my $moves;
	my $jumps;
	my @allmoves;
	$jumps = get_all_next_jumps($board, $piece);
	if (@$jumps > 0) {
		return $jumps;
	}
	$moves = get_next_move_neighbors($board, $piece);
	return $moves;
}

sub copy_move
{
	my ($move) = (@_);
	my $newmove;
	$newmove->{type} = $move->{type};
	$newmove->{start} = $move->{start};
	$newmove->{end} = $move->{end};
	$newmove->{steps} = [ @{$move->{steps}}];
	$newmove->{board} = copy_board($move->{board});
	if ($move->{final}) {
		$newmove->{final} = $move->{final};
	}
	return $newmove;
}

# this is a helper function that just deals with one jump in a complete move
# it returns a list of one-step jumps
sub get_next_jump_neighbors
{
	my ($board, $piece) = (@_);
	my @neighbors;
	my @moves;
	@neighbors = get_neighbor_pieces($piece);
	foreach my $next (@neighbors) {
		if ($board->{pieces}->[$next] != $NO_PIECE) {
			my $piece3;
			$piece3 = get_next_step_in_jump($board, $piece, $next);
			if ($piece3 != $INVALID_PIECE_NUMBER) {
				my $piece_type;
				my $move;
				$move->{type} = $NORMAL_JUMP;
				$move->{start} = $piece;
				$move->{end} = $piece3;
				$move->{steps} = [$next];
				# copy and update the board;
				$move->{board} = copy_board($board);
				$piece_type = $board->{pieces}->[$piece];
				$move->{board}->{pieces}->[$piece3] = $piece_type;
				$move->{board}->{pieces}->[$piece] = $NO_PIECE;
				$move->{board}->{pieces}->[$next] = $NO_PIECE;
				# check $piece3: If it is at the last row and the $piece is
				# not king, then it should crowned and the move ends
				my ($row, $col) = get_row_col_from_piece_number($piece3);
				if ((($piece_type == $BLACK_NORMAL) or 
					($piece_type == $WHITE_NORMAL)) and 
					(($row == 1) or ($row == $BOARD_SIZE))) {
					$move->{board}->{pieces}->[$piece3] += $STEP_TO_KING;
					# This should also mark this one as final
					$move->{final} = 1;
				}
				push @moves, $move;
			}
		}
	}
	return \@moves;
}

sub get_neighbor_pieces
{
	my ($piece_number) = (@_);
	my (@neighbors);
	my $neighbor;
	my ($row, $col);
	if ($piece_number<1 or $piece_number>$BOARD_SIZE*$BOARD_SIZE/2) {
		return @neighbors;
	}
	($row, $col) = get_row_col_from_piece_number($piece_number);
	$neighbor = get_piece_number_from_row_col($row-1, $col-1);
	if ($neighbor != $INVALID_PIECE_NUMBER) {
		push @neighbors, $neighbor;
	}
	$neighbor = get_piece_number_from_row_col($row-1, $col+1);
	if ($neighbor != $INVALID_PIECE_NUMBER) {
		push @neighbors, $neighbor;
	}
	$neighbor = get_piece_number_from_row_col($row+1, $col-1);
	if ($neighbor != $INVALID_PIECE_NUMBER) {
		push @neighbors, $neighbor;
	}
	$neighbor = get_piece_number_from_row_col($row+1, $col+1);
	if ($neighbor != $INVALID_PIECE_NUMBER) {
		push @neighbors, $neighbor;
	}
	return @neighbors;
}

# This applies to both move and jump 
sub is_move_direction_allowed
{
	my ($board, $from, $to) = (@_);
	my $type;
	$type = $board->{pieces}->[$from];
	if (($type == $BLACK_KING) or 
		($type == $WHITE_KING) or 
		(($type == $BLACK_NORMAL) and ($from > $to)) or
		(($type == $WHITE_NORMAL) and ($from < $to))) {
		return 1;
	}
	return 0;
}

sub get_next_step_in_jump
{
	my ($board, $piece1, $piece2) = (@_);
	my ($type1, $type2);
	my $piece3;
	$type1 = $board->{pieces}->[$piece1];
	$type2 = $board->{pieces}->[$piece2];
	$piece3 = $INVALID_PIECE_NUMBER;
	if (( (($type1 < $WHITE_NORMAL) and ($type2 > $BLACK_KING)) or
		(($type2 < $WHITE_NORMAL) and ($type1 > $BLACK_KING))) and 
		(is_move_direction_allowed($board, $piece1, $piece2))) {
		# They are of different color and we may be able to jump
			my (@rows, @cols);
			($rows[0], $cols[0]) =  get_row_col_from_piece_number($piece1);
			($rows[1], $cols[1]) =  get_row_col_from_piece_number($piece2);
			$rows[2] = 2*$rows[1]-$rows[0];
			$cols[2] = 2*$cols[1]-$cols[0];
			$piece3 = get_piece_number_from_row_col($rows[2], $cols[2]);
	}
	if ($piece3 == $INVALID_PIECE_NUMBER) {
		return $INVALID_PIECE_NUMBER;
	}
	if ($board->{pieces}->[$piece3] != $NO_PIECE) {
		return $INVALID_PIECE_NUMBER;
	}
	return $piece3;
}

sub copy_board
{
	my ($board) = (@_);
	my $newboard;
	my $i = 0;
	$newboard->{size} = $board->{size};
	foreach my $piece (@{$board->{pieces}}) {
		$newboard->{pieces}->[$i++] = $piece;
	}
	return $newboard;
}

sub get_all_next_jumps
{
	my ($board, $piece) = (@_);
	my $jumps;
	my @alljumps;
	$jumps = get_next_jump_neighbors($board, $piece);
	if (@$jumps == 0) {
			return []; # no jumps
	}
	foreach my $jump (@$jumps) {
		if ($jump->{final}) {
			push @alljumps, $jump;
			next;
		}
		my $partial_jumps = get_all_next_jumps($jump->{board}, $jump->{end});
		if (@$partial_jumps == 0) {
			push @alljumps, $jump;
			next;
		}
		foreach my $partial_jump (@$partial_jumps) {
			my $newjump;
			$newjump = copy_move($jump);
			$newjump->{end} = $partial_jump->{end};
			push @{$newjump->{steps}}, $jump->{end};
			push @{$newjump->{steps}}, @{$partial_jump->{steps}};
			$newjump->{board} = copy_board($partial_jump->{board});
			push @alljumps, $newjump;
		}
	}
	return \@alljumps;
}

# This helps to set up the recursion
sub get_next_jumps_helper
{
	my ($jumps) = (@_);
	my @alljumps;
	if (@$jumps == 0) {
			return []; # no jumps
	}
	foreach my $jump (@$jumps) {
		if ($jump->{final}) {
			push @alljumps, $jump;
			next;
		}
		# The jump is not necessarily final
		my $morejumps;
		$morejumps = get_next_jump_neighbors($jump->{board}, $jump->{end});
		if (@$morejumps == 0) {
			push @alljumps, $jump;
			next;
		}
		# They are one more jump from $jump
		my @newjumps;
		foreach my $morejump (@$morejumps) {
			my $newjump;
			$newjump = copy_move($jump);
			$newjump->{end} = $morejump->{end};
			push @{$newjump->{steps}}, $jump->{end};
			push @{$newjump->{steps}}, @{$morejump->{steps}};
			$newjump->{board} = copy_board($morejump->{board});
			push @newjumps, $newjump;
		}
		my $newjumps = get_next_jumps_helper(\@newjumps);
		push @alljumps, @$newjumps;
	}
	return \@alljumps;
}

sub save_board_to_file
{
	my ($board, $file) = (@_);
	my $fh;
	unless(open $fh, ">$file") {
		warn "Cannot save board information to file $file: $!\n";
		return;
	}
	my $i = 0;
	my @white_pieces;
	my @black_pieces;
	foreach my $piece (@{$board->{pieces}}) {
		if (!defined $piece) {
			$i++;
			next;
		}
		if ($piece == $BLACK_KING) {
			push @black_pieces, $i . "k"; 
		} elsif ($piece == $BLACK_NORMAL) {
			push @black_pieces, $i; 
		} elsif ($piece == $WHITE_KING) {
			push @white_pieces, $i . "k"; 
		} elsif ($piece == $WHITE_NORMAL) {
			push @white_pieces, $i; 
		}
		$i++;
	}
	print $fh "W: " . join(", ", @white_pieces) . "\n";
	print $fh "B: " . join(", ", @black_pieces) . "\n";
	close($fh);
}

# debug functions

sub check_piece_number
{
	foreach (my $row=1; $row<=$BOARD_SIZE; $row++) {
		foreach (my $col=1; $col<=$BOARD_SIZE; $col++) {
			my $piece_number = get_piece_number_from_row_col($row, $col);
			print "$piece_number ";
		}
		print "\n";
	}
}

sub check_row_col
{
	for (my $i=1; $i<= $BOARD_SIZE*$BOARD_SIZE/2; $i++) {
		my ($row, $col)  = get_row_col_from_piece_number($i);
		print "$i: $row, $col\n";
	}
}

sub check_neighbors
{
	for (my $i=1; $i<=$BOARD_SIZE*$BOARD_SIZE/2; $i++) {
		my @neighbors = get_neighbor_pieces($i);
		print "Piece $i: ";
		foreach my $n (@neighbors) {
			print "$n ";
		}
		print "\n";
	}
}

sub print_moves
{
	my ($moves) = (@_);
	foreach my $move (@$moves) {
		print_move($move);
	}
}

sub print_move
{
	my ($move) = (@_);
	if ($move->{type} == $NORMAL_JUMP) {
		print "It is a normal jump\n";
	} else {
		print "It is a normal move\n";
	}
	print "Detailed move/jump: ";
	print $move->{start};
	foreach my $step (@{$move->{steps}}) {
		print "-" . $step;
	}
	print "-";
	print $move->{end};
	print "\n";
	print "Board after move/jump:\n";
	print_board($move->{board});
}

1;