#!/usr/bin/perl -w
#------------------------------------------------------------#
# Final Project: Propositional Logic in the Wumpus World
# Class: Artificial Intelligence
# Semester: Spring 2003
# Author: Gary W. Johnson, Jr.
#------------------------------------------------------------#
#  This is the package definition for the wumpus world game.
#  Here, the Environment and Agent objects are defined
#  and fully commented for your enjoyment.
#
#  This module is used by wumpustest.pl, which acts as a
#  command-line interface to implement the various functions
#  defined here and demonstrate to the user the step by step
#  realizations that can come from the use of propositional
#  logic, given some basic rules of understanding from which
#  conclusions may be drawn.
#
#  Example1: A STENCH in this room implies that there must be
#            a WUMPUS in a room adjacent to this one.
#  Example2: A BREEZE in this room implies that there must be
#            a PIT in a room adjacent to this one.
#
#------------------------------------------------------------#

use strict;

#==========================================================#
package Environment;
#==========================================================#

# called: $myEnvironment = new Environment($rows, $cols);
sub new {
	my $package = shift;
	my $rows = shift || 4;	# max rows in the WumpusWorld
	my $cols = shift || 4;	# max cols in the WumpusWorld
	my @state = ();		# matrix representation of the WumpusWorld

	# Initialize all cells in the @state array to ''
	for my $i (0..$rows-1) {
		for my $j (0..$cols-1) {
			$state[$i][$j] = '';
		}
	}

	# Assign 20% of all cells to contain a PIT
	# Place a BREEZE in each adjacent cell that does not already contain a PIT
	for my $i (0..$rows-1) {
		for my $j (0..$cols-1) {
			next if $i==0 && $j==0;
			if (int(rand(10))+1 <= 2) {
				$state[$i][$j] = 'PIT';
				if ($i+1 < $rows) { $state[$i+1][$j] = 'BREEZE' if $state[$i+1][$j] ne 'PIT'; }
				if ($j+1 < $cols) { $state[$i][$j+1] = 'BREEZE' if $state[$i][$j+1] ne 'PIT'; }
				if ($i-1 >= 0)    { $state[$i-1][$j] = 'BREEZE' if $state[$i-1][$j] ne 'PIT'; }
				if ($j-1 >= 0)    { $state[$i][$j-1] = 'BREEZE' if $state[$i][$j-1] ne 'PIT'; }
			}
		}
	}

	# Place the WUMPUS in a random cell other than 0,0
	# Place a STENCH in each adjacent cell that does not already contain a PIT
	my ($i, $j) = (0,0);
	until ($i != 0 || $j != 0) {
		($i, $j) = (int(rand($rows)), int(rand($cols)));
	}
	$state[$i][$j] .= 'WUMPUS';
	if ($i+1 < $rows) { $state[$i+1][$j] .= 'STENCH' if $state[$i+1][$j] ne 'PIT'; }
	if ($j+1 < $cols) { $state[$i][$j+1] .= 'STENCH' if $state[$i][$j+1] ne 'PIT'; }
	if ($i-1 >= 0)    { $state[$i-1][$j] .= 'STENCH' if $state[$i-1][$j] ne 'PIT'; }
	if ($j-1 >= 0)    { $state[$i][$j-1] .= 'STENCH' if $state[$i][$j-1] ne 'PIT'; }

	# Place the GOLD in a random cell other than 0,0
	($i, $j) = (0,0);
	until ($i != 0 || $j != 0) {
		($i, $j) = (int(rand($rows)), int(rand($cols)));
	}
	$state[$i][$j] .= 'GOLD';

	# Create the environment object and return it
	my $self = {
		state => \@state,
		rows => $rows,
		cols => $cols,
		agentRow => 0,
		agentCol => 0,
		agentOrient => 'E',
		wumpusState => 'ALIVE',
	};
	bless($self, $package);
	return $self;
}

# called: $myEnvironment->displayState();
sub displayState {
	my $self = shift;

	print "\nWumpus World:\n\n";
	my $rowContents;
	for (my $i=$self->{rows}-1; $i>=0; $i--) {
		for (my $j=0; $j<$self->{cols}; $j++) {
			$rowContents = '|';
			if (${$self->{state}}[$i][$j] =~ /WUMPUS/) {
				if ($self->{wumpusState} eq 'ALIVE') { $rowContents .= 'W'; }
				else { $rowContents .= 'w'; }
			}
			$rowContents .= 'P' if (${$self->{state}}[$i][$j] =~ /PIT/);
			$rowContents .= 'G' if (${$self->{state}}[$i][$j] =~ /GOLD/);
			$rowContents .= 'S' if (${$self->{state}}[$i][$j] =~ /STENCH/);
			$rowContents .= 'B' if (${$self->{state}}[$i][$j] =~ /BREEZE/);
			$rowContents .= ' ' if (${$self->{state}}[$i][$j] eq '');
			if ($self->{agentRow} == $i && $self->{agentCol} == $j) {
				if    ($self->{agentOrient} eq 'N') { $rowContents .= '^'; }
				elsif ($self->{agentOrient} eq 'E') { $rowContents .= '>'; }
				elsif ($self->{agentOrient} eq 'S') { $rowContents .= 'v'; }
				elsif ($self->{agentOrient} eq 'W') { $rowContents .= '<'; }
			}
			for (1..7-length($rowContents)) { $rowContents .= ' '; }
			print $rowContents;
		}
		print "|\n";
	}
	print "\n";
}

#==========================================================#
package Agent;
#==========================================================#

# called: $myAgent = new Agent();
sub new {
	my $package = shift;
	my @state = ();
	my @knowledgeBase = ();

	foreach my $i (0..4) {
		foreach my $j (0..4) {
			$state[$i][$j] = '';
		}
	}

	my $self = {
		state => \@state,
		KB => \@knowledgeBase,
		row => 0,
		col => 0,
		orient => 'E',
		arrow => '1',
		bump => 0,
	};
	bless($self, $package);
	return $self;
}

# called: $myAgent->getPercepts($myEnvironment);
sub getPercepts {
	my $self = shift;
	my $environment = shift;
	my ($row, $col) = ($self->{row}, $self->{col});
	my ($envRows, $envCols) = ($environment->{rows}, $environment->{cols});
	my ($stench, $breeze, $glitter, $bump, $scream, $pit, $wumpus) = (0,0,0,0,0,0,0);

	# Check the current room for a STENCH, BREEZE, GOLD, PIT, or WUMPUS.
	# If you ran into a wall, you should feel a bump.
	# If you shot the wumpus, you should hear a scream.

	$stench = 1  if ${$environment->{state}}[$row][$col] =~ /STENCH/;
	$breeze = 1  if ${$environment->{state}}[$row][$col] =~ /BREEZE/;
	$glitter = 1 if ${$environment->{state}}[$row][$col] =~ /GOLD/;
	$bump = 1    if $self->{bump} == 1;
	$scream = 1  if $environment->{wumpusState} eq 'SHOT';
	$pit = 1     if ${$environment->{state}}[$row][$col] =~ /PIT/;
	$wumpus = 1  if ${$environment->{state}}[$row][$col] =~ /WUMPUS/;

	# Give some response so the user knows what you've perceived.

	if ($stench)  { print "I smell a stench.\n"; }
	if ($breeze)  { print "I feel a breeze.\n"; }
	if ($glitter) { print "I see a glitter.\n"; }
	if ($bump)    { print "I bumped into a wall.\n"; }
	if ($scream)  { print "I heard a scream.\n"; }
	if ($pit)     { print "Oops! I fell down a pit.\nGAME OVER\n"; exit; }
	if ($wumpus) { 
		if ($environment->{wumpusState} eq 'ALIVE') { print "Aah! The wumpus ate me.\nGAME OVER\n"; exit; }
		else { print "I see a dead wumpus.\n"; }
	}

	## Insert statements into the KB (knowledge base) concerning what you have perceived
	## in the room and have therefore deduced about its adjacent rooms.
	## Example: S11 implies W10vW12vW21vW01
	## Example: B11 implies P10vP12vP21vP01
	## Example: ~S11 implies ~W10 ^ ~W12 ^ ~W21 ^ ~W01
	## Example: ~B11 implies ~P10 ^ ~P12 ^ ~P21 ^ ~P01

	my @statements = ();
	if ($stench)  {
		@statements = ();
		if ($row+1 < $envRows) { push(@statements, join('','W',$row+1,$col)); }
		if ($col+1 < $envCols) { push(@statements, join('','W',$row,$col+1)); }
		if ($row-1 >= 0)       { push(@statements, join('','W',$row-1,$col)); }
		if ($col-1 >= 0)       { push(@statements, join('','W',$row,$col-1)); }

		$self->tellKB(join('v', @statements));
	} else {
		if ($row+1 < $envRows) { $self->tellKB(join('','~W',$row+1,$col)); }
		if ($col+1 < $envCols) { $self->tellKB(join('','~W',$row,$col+1)); }
		if ($row-1 >= 0)       { $self->tellKB(join('','~W',$row-1,$col)); }
		if ($col-1 >= 0)       { $self->tellKB(join('','~W',$row,$col-1)); }
	}
	if ($breeze)  {
		@statements = ();
		if ($row+1 < $envRows) { push(@statements, join('','P',$row+1,$col)); }
		if ($col+1 < $envCols) { push(@statements, join('','P',$row,$col+1)); }
		if ($row-1 >= 0)       { push(@statements, join('','P',$row-1,$col)); }
		if ($col-1 >= 0)       { push(@statements, join('','P',$row,$col-1)); }

		$self->tellKB(join('v', @statements));
	} else {
		if ($row+1 < $envRows) { $self->tellKB(join('','~P',$row+1,$col)); }
		if ($col+1 < $envCols) { $self->tellKB(join('','~P',$row,$col+1)); }
		if ($row-1 >= 0)       { $self->tellKB(join('','~P',$row-1,$col)); }
		if ($col-1 >= 0)       { $self->tellKB(join('','~P',$row,$col-1)); }
	}
	if ($glitter) {
		$self->tellKB("G$row$col");
	}
	if ($bump) {
		$self->{bump} = 0;
	}
	if ($scream) {
		$environment->{wumpusState} = 'DEAD';
	}
	if ($pit) {
		$self->tellKB("P$row$col");
	} else {
		$self->tellKB("~P$row$col");
	}
	if ($wumpus) {
		$self->tellKB("W$row$col");
	} else {
		$self->tellKB("~W$row$col");
	}
}

# called: $myAgent->tellKB($newEntry);
sub tellKB {
	my $self = shift;
	my $newEntry = shift;
	my $repeat = 0;

	# Insert a new entry into the KB if it is not already in there.

	foreach my $entry (@{$self->{KB}}) {
		if ($entry eq $newEntry) { $repeat = 1; last; }
	}
	push(@{$self->{KB}}, $newEntry) unless $repeat;
}

# called: $myAgent->askKB($proposition);
sub askKB {
	my $self = shift;
	my $proposition = shift;

	# Return 1 if the proposition is already in the KB
	# Otherwise, return 0

	foreach my $element (@{$self->{KB}}) {
		return 1 if $element eq $proposition;
	}
	return 0;
}

# called: $myAgent->updateKB();
sub updateKB {
	my $self = shift;
	my @KB = @{$self->{KB}};
	my @propositions;
	my $proposition;
	my $itemsRemoved = 0;

	# Remove elements of a disjunction that are negated atomically elsewhere in the KB.
	# Example: P12vP33 ^ ~P33 --> P12 ^ ~P33

	for (my $i=0; $i<@KB; $i++) {
		if ($KB[$i] =~ /v/) {
			@propositions = ();
			foreach $proposition (split(/v/, $KB[$i])) {
				push(@propositions, $proposition);
				for (my $j=0; $j<@KB; $j++) {
					if ($KB[$j] !~ /v/) {
						if ($KB[$j] eq "~$proposition") {
							pop @propositions;
							last;
						}
					}
				}
			}
			$KB[$i] = join('v', @propositions);
		}
	}

	# Remove repeated propositions from the KB (leave one copy, of course)
	# Example: P33 ^ W21 ^ P12vP01vP32 ^ P33 ... --> W21 ^ P12vP01vP32 ^ P33 ...

	for (my $i=0; $i<@KB-1; $i++) {
		for (my $j=$i+1; $j<@KB; $j++) {
			if ($KB[$i] eq $KB[$j]) {
				for (my $k=$j; $k<@KB-1; $k++) {
					$KB[$k] = $KB[$k+1];
				}
				$itemsRemoved++;
			}
		}
	}
	for (my $i=0; $i<$itemsRemoved; $i++) { pop @KB; }

	# If there is a positive atom concerning WUMPUSes, remove all other positive references to them.
	# If two disjunctions concerning WUMPUSes have the same atomic member, add that atom
	# to the KB and remove the two disjunctions.
	# Example1: W21 ^ W12vW21 --> W21
	# Example2: W21vW33 ^ W12vW21 --> W21

	for (my $i=0; $i<@KB; $i++) {
		if ($KB[$i] =~ /W.*v/) {
			@propositions = ();
			foreach $proposition (split(/v/, $KB[$i])) {
				push(@propositions, $proposition);
				for (my $j=0; $j<@KB; $j++) {
					if ($i != $j && $KB[$j] =~ /W/) {
						if ($KB[$j] =~ /v/) {
							foreach my $statement (split(/v/, $KB[$j])) {
								if ($statement eq $proposition) {
									$KB[$i] = $KB[$j] = $statement;
									last;
								}
							}
						} else {
							if ($KB[$j] eq $proposition) {
								$KB[$i] = $KB[$j];
							}
						}
					}
				}
			}
		}
	}

	# If any single proposition of a disjunction is atomically negated elsewhere in the KB,
	# remove that proposition from the disjunction.
	# Example: P12vP01vP03 ^ ~P01 --> P12vP03 ^ ~P01

	my ($text, $row, $col);
	for (my $i=0; $i<@KB; $i++) {
		if ($KB[$i] =~ /P.*v/) {
			@propositions = ();
			foreach $proposition (split(/v/, $KB[$i])) {
				push(@propositions, $proposition);
				($text, $row, $col) = split(//, $proposition);
				if    ($self->askKB(join('', '~B', $row+1, $col))) { pop @propositions; }
				elsif ($self->askKB(join('', '~B', $row, $col+1))) { pop @propositions; }
				elsif ($self->askKB(join('', '~B', $row-1, $col))) { pop @propositions; }
				elsif ($self->askKB(join('', '~B', $row, $col-1))) { pop @propositions; }
			}
			$KB[$i] = join('v', @propositions);
		}
	}

	# Put the local KB copy back into the agent object
	$self->{KB} = \@KB;
}

# called: $myAgent->updateState();
sub updateState {
	my $self = shift;

	# Clear the current world state

	foreach my $i (0..3) {
		foreach my $j (0..3) {
			${$self->{state}}[$i][$j] = '';
		}
	}

	# First enter atomic statements (both positive and negative) into the state
	# Example: P12 --> $state[1][2] = 'P'
	# Example: ~W22 --> $state[2][2] = '~W'

	my ($neg, $text, $row, $col);
	foreach my $entry (@{$self->{KB}}) {
		if ($entry !~ /v/) {
			if (length($entry) == 3) {
				($text, $row, $col) = split(//, $entry);
				unless (${$self->{state}}[$row][$col] =~ $text) { ${$self->{state}}[$row][$col] .= $text; }
			} else {
				($neg, $text, $row, $col) = split(//, $entry);
				unless (${$self->{state}}[$row][$col] =~ $text) { ${$self->{state}}[$row][$col] .= "$neg$text"; }
			}
		}
	}

	# Next enter disjunctions into the state as individual questions
	# Example: P11vP22vP13 --> $state[1][1] = 'P?' ^ $state[2][2] = 'P?' ^ $state[1][3] = 'P?'
	# Example: W11vW22vW13 --> $state[1][1] = 'W?' ^ $state[2][2] = 'W?' ^ $state[1][3] = 'W?'

	foreach my $entry (@{$self->{KB}}) {
		if ($entry =~ /v/) {
			foreach (split(/v/, $entry)) {
				if (length($_) == 3) {
					($text, $row, $col) = split(//, $_);
					unless (${$self->{state}}[$row][$col] =~ $text) { ${$self->{state}}[$row][$col] .= "$text?"; }
				} else {
					($neg, $text, $row, $col) = split(//, $_);
					unless (${$self->{state}}[$row][$col] =~ $text) { ${$self->{state}}[$row][$col] .= "$neg$text?"; }
				}
			}
		}
	}
}

# called: $myAgent->displayState($myEnvironment);
sub displayState {
	my $self = shift;
	my $environment = shift;

	## Print out a padded matrix of the agent's state array

	print "\nAgent State:\n\n";
	my $rowContents;
	for (my $i=$environment->{rows}-1; $i>=0; $i--) {
		for (my $j=0; $j<$environment->{cols}; $j++) {
			$rowContents = '|';
			$rowContents .= ${$self->{state}}[$i][$j];
			if ($self->{row} == $i && $self->{col} == $j) {
				if    ($self->{orient} eq 'N') { $rowContents .= '^'; }
				elsif ($self->{orient} eq 'E') { $rowContents .= '>'; }
				elsif ($self->{orient} eq 'S') { $rowContents .= 'v'; }
				elsif ($self->{orient} eq 'W') { $rowContents .= '<'; }
			}
			for (1..6-length($rowContents)) { $rowContents .= ' '; }
			print $rowContents;
		}
		print "|\n";
	}

	## Print out the agent's KB (knowledge base)

	print "\nKnowledge Base:\n\n";
	foreach (@{$self->{KB}}) { print "$_ "; }
	print "\n\n";
}

# called: $myAgent->shootArrow($myEnvironment);
sub shootArrow {
	my $self = shift;
	my $environment = shift;

	# If you don't have an arrow, say that and return.
	# Otherwise remove the arrow from your arsenal and say that you shot it.

	if ($self->{arrow} == 0) {
		print "I don't have an arrow to shoot.\n";
		return;
	}
	print "I shot the arrow.\n";
	$self->{arrow} = 0;

	# If the wumpus is in a cell on the row or column down which you facing,
	# then set the wumpusState to 'SHOT'.

	if ($self->{orient} eq 'N') {
		for (my $i=$self->{row}; $i<$environment->{rows}; $i++) {
			if (${$environment->{state}}[$i][$self->{col}] =~ /WUMPUS/) {
				$environment->{wumpusState} = 'SHOT';
			}
		}
	} elsif ($self->{orient} eq 'E') {
		for (my $i=$self->{col}; $i<$environment->{cols}; $i++) {
			if (${$environment->{state}}[$self->{row}][$i] =~ /WUMPUS/) {
				$environment->{wumpusState} = 'SHOT';
			}
		}
	} elsif ($self->{orient} eq 'S') {
		for (my $i=$self->{row}; $i>=0; $i--) {
			if (${$environment->{state}}[$i][$self->{col}] =~ /WUMPUS/) {
				$environment->{wumpusState} = 'SHOT';
			}
		}
	} elsif ($self->{orient} eq 'W') {
		for (my $i=$self->{col}; $i>=0; $i--) {
			if (${$environment->{state}}[$self->{row}][$i] =~ /WUMPUS/) {
				$environment->{wumpusState} = 'SHOT';
			}
		}
	}
}

# called: $myAgent->grabGold($myEnvironment);
sub grabGold {
	my $self = shift;
	my $environment = shift;

	# If the gold is in the same cell as you, then say that you got the gold and exit the game.
	# Otherwise, say that there is no gold here.

	if (${$environment->{state}}[$self->{row}][$self->{col}] =~ /GOLD/) {
		print "I got the gold!\nGAME OVER\n";
		exit;
	} else {
		print "There is no gold here.\n";
	}
}

# called: $myAgent->turnLeft($myEnvironment);
sub turnLeft {
	my $self = shift;
	my $environment = shift;

	# Change your orientation (N,E,S,W) 90 degrees to the left (W,N,E,S)

	my $orient;
	if ($self->{orient} eq 'N') {
		$orient = 'W';
	} elsif ($self->{orient} eq 'E') {
		$orient = 'N';
	} elsif ($self->{orient} eq 'S') {
		$orient = 'E';
	} elsif ($self->{orient} eq 'W') {
		$orient = 'S';
	}

	$self->{orient} = $orient;
	$environment->{agentOrient} = $orient;
}

# called: $myAgent->turnRight($myEnvironment);
sub turnRight {
	my $self = shift;
	my $environment = shift;

	# Change your orientation (N,E,S,W) 90 degrees to the right (E,S,W,N)

	my $orient;
	if ($self->{orient} eq 'N') {
		$orient = 'E';
	} elsif ($self->{orient} eq 'E') {
		$orient = 'S';
	} elsif ($self->{orient} eq 'S') {
		$orient = 'W';
	} elsif ($self->{orient} eq 'W') {
		$orient = 'N';
	}

	$self->{orient} = $orient;
	$environment->{agentOrient} = $orient;
}

# called: $myAgent->stepForward($myEnvironment);
sub stepForward {
	my $self = shift;
	my $environment = shift;

	# If the square in front of you (+1 in the direction you are facing)
	# is on the board, move forward one step.
	# Otherwise, stay where you are and record a bump percept.

	if ($self->{orient} eq 'N') {
		if ($self->{row}+1 < $environment->{rows}) {
			$self->{row} += 1;
			$environment->{agentRow} += 1;
		} else {
			$self->{bump} = 1;
		}
	} elsif ($self->{orient} eq 'E') {
		if ($self->{col}+1 < $environment->{cols}) {
			$self->{col} += 1;
			$environment->{agentCol} += 1;
		} else {
			$self->{bump} = 1;
		}
	} elsif ($self->{orient} eq 'S') {
		if ($self->{row}-1 >= 0) {
			$self->{row} -= 1;
			$environment->{agentRow} -= 1;
		} else {
			$self->{bump} = 1;
		}
	} elsif ($self->{orient} eq 'W') {
		if ($self->{col}-1 >= 0) {
			$self->{col} -= 1;
			$environment->{agentCol} -= 1;
		} else {
			$self->{bump} = 1;
		}
	}
}

1;
