#!/usr/bin/perl -w

use strict;
use MyNode;
use SearchTree;

my @state = generateRandomBoardState();
until (isSolvable(@state)) {
	@state = generateRandomBoardState();
}
print @state, "\n";

my $rootNode = MyNode->new(board => \@state);
my $breadthPath = SearchTree::breadthFirst( root    => $rootNode,
					    depth   => 5,
					    VERBOSE => 1 );

if (@$breadthPath) {
	print "Here's a path to the goal:\n";
	foreach my $node (@$breadthPath) { print $node->asText() . "\n"; }
}

my $depthPath = SearchTree::depthFirst(	root    => $rootNode,
					depth   => 5,
					VERBOSE => 2 );

if (@$depthPath) {
	print "Here's a path to the goal:\n";
	foreach my $node (@$depthPath) { print $node->asText() . "\n"; }
}

#===========================================================#
# SUBROUTINE DEFINITIONS BELOW HERE

sub generateRandomBoardState {
	# Generate a random configuration of puzzle pieces

	my @temp = (0..8);
	my ($piece_index, $piece);
	my @pieces = ();

	foreach (0..8) {
		$piece_index = int(rand(@temp));
		$piece = $temp[$piece_index];
		push(@pieces, $piece);
		foreach ($piece_index..@temp-2) {
			$temp[$_] = $temp[$_+1];
		}
		pop @temp;
	}
	return @pieces;
}

sub isSolvable {
	# Verify that the pieces are in a solvable state

	my @board = @_;
	my $blankIndex;
	foreach (0..8) {
		$blankIndex = $_ if $board[$_] == 0;
	}

	my $boardInOrder = 0;
	my $pairwiseSwaps = 0;
	until ($boardInOrder) {
		my $temp;
		foreach (0..8) {
			unless ($_ == $board[$_]) {
				$temp = $board[$_];
				$board[$_] = $board[$temp];
				$board[$temp] = $temp;
				$pairwiseSwaps++;
			}
		}
		$boardInOrder = 1;
		foreach (0..8) {
			$boardInOrder = 0 if $_ != $board[$_];
		}
	}

	return 1 if ($blankIndex % 2 == 0 && $pairwiseSwaps % 2 == 0);
	return 1 if ($blankIndex % 2 == 1 && $pairwiseSwaps % 2 == 1);
	return 0;
}


__END__
#===========================================================#
# Generate some code that solves the problem...

until ($pass > 10) {

	# Calculate heuristic ($H) for the problem
	$H = 0;
	foreach (0..8) {
		if ($pieces[$_] != 0) {
			$H += manhattan_distance($_, $pieces[$_]);
		}
	}
	print "Heuristic(total move distance): $H\n";

	# Pick the best move and take it
	$lowest_cost = 2;
	foreach (@movable_blocks) {
		print "Checking $pieces[$_]...\n";
		$cost1 = manhattan_distance($_, $pieces[$_]);
		$cost2 = manhattan_distance($blank_index, $pieces[$_]);
		print "Current Lowest Cost: $lowest_cost\n";
		print "Total Cost Change: ", $cost2-$cost1, "\n";
		if ($cost2-$cost1 < $lowest_cost) {
			print "This is lower than lowest_cost\n";
			if ($pieces[$_] != $last_piece_moved) {
				print "$pieces[$_] != $last_piece_moved\n";
				$lowest_cost = $cost2-$cost1;
				$best_move = $_;
			}
		}
	}
	print "Best move is $pieces[$best_move] => 0\n";
	$last_piece_moved = $pieces[$best_move];

	$pieces[$blank_index] = $pieces[$best_move];
	$pieces[$best_move] = 0;

	print "After moving...\n";
	display_board(@pieces);

	# Test if goal state has been reached
	$goal_reached = 1;
	foreach (0..8) {
		if ($_ != $pieces[$_]) { $goal_reached = 0; }
	}
}

sub manhattan_distance {
	($A, $B) = @_;
	$i = 0;
	if ($A < $B) {
		foreach ($A+1..$B) { if ($_%3 == 0) { $i++; } }
	} else {
		foreach ($B+1..$A) { if ($_%3 == 0) { $i++; } }
	}
	$vertical_moves = $i;
	$horizontal_moves = abs(abs($A-$B)-$i*3);
	return $vertical_moves + $horizontal_moves;
}
