#!/usr/bin/perl -w
########
# 
# Search for a solution to an NxN version of the 8-puzzle, 
# in which neighbor tiles can slide into the empty square.  
# The solved position looks like this.
#
#   -------------
#   |   | 1 | 2 |
#   -------------
#   | 3 | 4 | 5 |
#   -------------
#   | 6 | 7 | 8 |
#   -------------
#
# which will be stored as a one dimensional array 
# [0, 1, 2, 3, 4, 5, 6, 7, 8]
#
#
# Note that "vmmap <process>" can be used from the
# command line to look at allocated memory. (on Darwin, anyway)
# Also see "vm_stat 3".
#
###########
package NxN;
use strict;
my $VERSION=0.1;

my  @adjacentTable = ( 0, [1,3],
                       1, [0,2,4],
                       2, [1,5],
                       3, [0,4,6],
                       4, [1,3,5,7],
                       5, [2,4,8],
                       6, [3,7],
                       7, [4,6,8],
                       8, [5,7],
                     );
# I need to write something to calculate this for the larger case
# rather than just using a lookup table.
sub adjacentSquares {
  my ($which) = @_;
  return $adjacentTable[2*$which+1];
}


sub clone {
  my $self=shift;
  my $itsBoard = $self->{board};
  my @boardCopy = @$itsBoard;
  my $cloneSelf = NxN->new();
  $cloneSelf->{board} = \@boardCopy;
  return $cloneSelf;
}
  
our $gridSize  = 3;   # default size (3x3 with a hole is classic 8-puzzle)
our $arraySize = $gridSize**2;
our $empty     = 0;   # This value marks the unique "empty" square.

sub new {
  my ($class) = shift;
  my $self = { @_ };
  return bless $self, $class;
}

sub isGoal {
  my $self = shift;
  for (my $i=0; $i<$arraySize; $i++){
    return 0 if $self->{board}[$i] != $i;
  }
  return 1;
}

# generate list of nodes below this one.
sub expand {
  my $self = shift;
  for (my $i=0; $i<$arraySize; $i++){
    return $self->newNodesFromNeighbors($i) if $self->{board}[$i] == $empty;
  }
}

sub newNodesFromNeighbors {
  my $self = shift;
  my ($emptySquare) = @_;
  my $neighbors = adjacentSquares($emptySquare);
  my $result = [];
  foreach my $neighbor (@$neighbors) {
    push @$result, $self->newNodeFromSwap($emptySquare, $neighbor);
  }
  return $result;
}

sub areEqual {
  my $self = shift;
  my ($other) = @_;
  for (my $i=0; $i<$arraySize; $i++){
    return 0 if $self->{board}[$i] != $other->{board}[$i];
  }
  return 1;
}

sub newNodeFromSwap {
  my $self = shift;
  my ($i,$j) = @_;
  my $newNode = $self->clone;
  my $tmp = $newNode->{board}[$i];
  $newNode->{board}[$i] = $newNode->{board}[$j];
  $newNode->{board}[$j] = $tmp;
  return $newNode;
}

sub asText {
  my $self = shift;
  my $result =   "\n ---------------\n";
  $result .=     " | ".$self->{board}[$_]." " for (0..2);
  $result .=     "|\n";
  $result .=      " ---------------\n";
  $result .=     " | ".$self->{board}[$_]. " " for (3..5);
  $result .=     "|\n";
  $result .=      " ---------------\n";
  $result .=     " | ".$self->{board}[$_]. " " for (6..8);
  $result .=     "|\n";
  $result .=      " ---------------\n";
  return $result;
}

# randN(n) returs a random integer from 0 to n-1.
sub randN {
  return int($_[0]*rand());
}

## Simple test of randN.
#my $sum=0.0;
#my $howMany=20;
#for my $i (1..$howMany){
#  my $r = randN(6);
#  print "$i $r\n";
#  $sum+=$r;
#}
#print " average of $howMany is " . $sum/$howMany . "\n";
#exit;

sub randomSequence {
  my ($size) = @_;
  my @digits = 0..($size-1);
  my @nums = ();
  for (my $n=$size; $n>0; $n--){
    my $r=randN($n);
    my $tmp=$digits[$r];
    $digits[$r]=$digits[0];
    $digits[0]=$tmp;
    push @nums, (shift @digits);
  }
  return @nums;
}

#my @test;
#@test = randomPuzzle(6), print "random sequence =  @test \n" for 1..10;

# === breadth first search ===============================================
use SearchTree;

use Time::HiRes qw( gettimeofday tv_interval );
my $time = [gettimeofday];

## Here's how to create a random puzzle.
## You'll have a 50/50 chance of getting an unsolvable one.
# my $root = NxN->new( board=>[ randomSequence($arraySize) ]);

## This one is 8 moves from the solved position.
my $root = NxN->new( board=>[ 6, 2, 5, 
			      1, 3, 4, 
			      7, 8, 0 ] );

print "Here's the root node :\n" . $root->asText . "\n";

#print "Here are its neighbors :\n";
#my $neighbors = $root->expand;
#foreach my $node (@$neighbors){
#  print $node->asText . "\n\n";
#}
#exit;

print " Searching breadthFirst for a path to the solved position...\n";
my $answerPath = SearchTree::breadthFirst(  root    => $root,
					    depth   => 8,
					    VERBOSE => 1,
                                         );

my $elapsed = tv_interval($time);
print "\n elapsed time = $elapsed seconds \n";
if (@$answerPath){
  print " Answer: \n";
  foreach my $node (@$answerPath){
    print $node->asText;
  }
}
else {
  print "\n No answer found.\n";
}

# ==  depth first search ==================================================

$time = [gettimeofday];
$root = NxN->new( board=>[ 6, 2, 5, 
			   1, 3, 4, 
			   7, 8, 0 ] );

print "\n\n";
print "Here's the root node again :\n" . $root->asText . "\n";

print " Searching depthFirst, maxDepth=12 ";
print " for a path to the solved position...\n";

$answerPath = SearchTree::depthFirst(  root    => $root,
				       depth   => 15,
				       VERBOSE => 1,
				    );

$elapsed = tv_interval($time);
print "\n Elapsed time = $elapsed seconds \n";
if (@$answerPath){
  print " Answer: \n";
  foreach my $node (@$answerPath){
    print $node->asText;
  }
}
else {
  print "\n No answer found.\n";
}


