#!/usr/bin/perl

#Configuration Variables;

# If running incrementally under cron, with feedback to students
$ModeShowWrongSamples = 0;
$PrintLineFeedbackPerGradee = 0;
$AppendReportFiles = 1;
$ScrapShadow = 0;
$Debug = 0;
$ProfessOrNot = 1;
$LiveMail = 1;
$QualitativeGradingOrNot = 1;

# If running and testing, with no feedback to students
$ModeShowWrongSamples = 1;
$PrintLineFeedbackPerGradee = 1;
$AppendReportFiles = 0;
$ScrapShadow = 1;
$Debug = 0;
$ProfessOrNot = 0;
$LiveMail = 0;
$QualitativeGradingOrNot = 0;

$Md5SumProgram = 'md5sum ';

$StudentEmail{'studentlogin'} = 'Firstname.Lastname@tufts.edu';
$StudentEmail{'secondstudent'} = 'Another.Name@tufts.edu';


sub kmyerror { local($Number, $String) = @_;
	       print "ERROR[$Login, $FileName, $Number]: ", $String, "\n";
}


sub transition {
    local($Auton, $State, $Read, $Next) = @_;
    print "Reading Transition $Auton, $State, $Read, $Next\n";
    $Read =~ s/\s//g;
    local(@Read) = split(/,/, $Read);
    foreach $Read (@Read) {
	if (length($Read) > 1 && $Read ne 'null') {
	    &kmyerror(476, "String transition found ");
	} else {
	    push(@{$Automaton{$Auton}{'Transition'}{$State}{$Read}}, $Next);
	    $Automaton{$Auton}{'Alphabet'}{$Read} = 1;
	    if ($#{$Automaton{$Auton}{'Transition'}{$State}{$Read}}) {
		$Automaton{$Auton}{'NonDeterminismFound'} = 1;
	    }
	}
    }
    return '';
}


sub makestate {
    local($Auton, $State, $Label, $Initial, $Final) = @_;
    print "Making New State $Auton, $State, <<$Label>>, $Initial, $Final\n";
    $Automaton{$Auton}{'NumStates'} = $State+1; # since we can have automata with holes in state sets.
    # we don't use the label.
    if ($Initial) {
	$Automaton{$Auton}{'InitStateIndex'} = $State; ######`
    }
    if ($Final) {
	push(@{$Automaton{$Auton}{'FinalStateList'}}, $State);
    }
    return '';
}

sub clearallautomata {
    %Automaton = ();
}

sub clearoneautomaton { 
    local($Auton) = @_;
    %{$Automaton{$Auton}} = ();
}

sub readxmlfile {
    local($FileName, $Auton) = @_;
    local($OldNumState, $DeadStateExists, %AlphabetSoup);
    &clearoneautomaton($Auton);
    $Automaton{$Auton}{'NonDeterminismFound'} = 0;
    open(FILE, "< $FileName") ||
	&kmyerror(100, "Could not open the file");

    $XML = join('', <FILE>);

    unless ($XML =~ /<type>fa<\/type>/) {
	&kmyerror(2093, "This is not a finite automaton");
    }

    $XML =~ s/&#13;//g;

    $XML =~ s/<state id="(\d+)">\s*<x>-?\d+\.\d+<\/x>\s*<y>-?\d+\.\d+<\/y>\s*(<label>(.*)<\/label>)?\s*(<initial\/>)?\s*(<final\/>)?\s*<\/state>/&makestate($Auton, $1, $3, $4, $5)/ge;

    $XML =~ s/<transition>\s*<from>(\d+)<\/from>\s*<to>(\d+)<\/to>\s*<read>([^<]*)<\/read>\s*<\/transition>/&transition($Auton, $1, $3, $2)/ge;

    # now to do some sanity checks ensuring completeness
    $DeadStateExists = 0;
    $OldNumStates = $Automaton{$Auton}{'NumStates'};
    foreach $State (0..$OldNumStates-1) { 
	foreach $Alph (sort keys %{$Automaton{$Auton}{'Alphabet'}}) {
	    if ($#{$Automaton{$Auton}{'Transition'}{$State}{$Alph}} == -1) {
		unless ($DeadStateExists) {
		    $Automaton{$Auton}{'NumStates'}++;
		    foreach $AlphIn (sort keys %{$Automaton{$Auton}{'Alphabet'}}) {
			&transition($Auton,
				    $Automaton{$Auton}{'NumStates'}-1,
				    $AlphIn,
				    $Automaton{$Auton}{'NumStates'}-1
				    );
		    }
		    $DeadStateExists = 1;
		}
		&transition($Auton,$State,$Alph,
                            $Automaton{$Auton}{'NumStates'}-1);
	    }
	}
    }
}


sub readfile {
    local($FileName, $Auton) = @_;
    local($OldNumState, $DeadStateExists, %AlphabetSoup);
    &clearoneautomaton($Auton);

    $Automaton{$Auton}{'NonDeterminismFound'} = 0;

    open(FILE, "< $FileName") ||
	&kmyerror(100, "Could not open the file");
    $Ln = <FILE>; 
    if ($Ln !~ /^One-Way-FSA\r?\n$/) { 
	&kmyerror(1,"First line is not a OneWayFSA -- it is $Ln"); 
    }
    $Ln = <FILE>; 
    if ($Ln =~ /^(\d+)\r?\n$/) { 
	$Automaton{$Auton}{'NumStates'} = $1; ######
    }
    $Ln = <FILE>; 
    if ($Ln !~ /^\#\r?\n$/) { &kmyerror(5,"Don't have the hash break"); }
    $Ln = <FILE>; 
    if ($Ln =~ /^(\d+)\r?\n$/) { 
	$Automaton{$Auton}{'InitStateIndex'} = $1; ######
    } else {
	&kmyerror("7,fourth line does not have init state index");
    }
    $Ln = '';
    $Ln = <FILE>; 
    if ($Ln =~ /^(\d+\s+)+0\r?\n$/) { 
	@{$Automaton{$Auton}{'FinalStateList'}} = split(/\s+/, $Ln);
	pop(@{$Automaton{$Auton}{'FinalStateList'}});
    } else {
	&kmyerror(8,"Seventh line does not have final state index");
    }

    %Transition = ();

    foreach $State (1..$Automaton{$Auton}{'NumStates'}) {
	$Ln = '';
	$Ln = <FILE>; 
	if ($Ln =~ /^((\S+\s\d+\s)*)EOL\r?\n$/) { 
	    $Ln =~ s/(\S+)\s(\d+)\s/&transition($Auton,$State,$1,$2)/ge;
	} else {
	    &kmyerror(9,"Transition Line $State is bad");
	}
    }
    close FILE;	

    # now to do some sanity checks ensuring completeness
    $DeadStateExists = 0;
    $OldNumStates = $Automaton{$Auton}{'NumStates'};
    foreach $State (1..$OldNumStates) {
	foreach $Alph (sort keys %{$Automaton{$Auton}{'Alphabet'}}) {
	    if ($#{$Automaton{$Auton}{'Transition'}{$State}{$Alph}} == -1) {
		unless ($DeadStateExists) {
		    $Automaton{$Auton}{'NumStates'}++;
		    foreach $AlphIn (sort keys %{$Automaton{$Auton}{'Alphabet'}}) {
			&transition($Auton,
				    $Automaton{$Auton}{'NumStates'},
				    $AlphIn,
				    $Automaton{$Auton}{'NumStates'}
				    );
		    }
		    $DeadStateExists = 1;
		}
		&transition($Auton,$State,$Alph,
                            $Automaton{$Auton}{'NumStates'});
	    }
	}
    }
}


sub printautomaton {
    local($Auton) = @_;

    print "Printing Automaton: $Auton\n";
    print "Nondeterminism: ", $Automaton{$Auton}{'NonDeterminismFound'}, "\n";
    print "NumberOfStates: ", $Automaton{$Auton}{'NumStates'}, "\n";
    print "InitStateIndex: ", $Automaton{$Auton}{'InitStateIndex'}, "\n";

    print "FinalStateList: ";
    foreach $Elt (@{$Automaton{$Auton}{'FinalStateList'}}) {
	print $Elt, ' ';
    }
    print "\n";
    @Alphabet = keys %{$Automaton{$Auton}{'Alphabet'}};
    print " InputAlphabet: ";
    foreach $Read (@Alphabet) {
	print $Read, ' ';
    }
    print "\n";
    
    foreach $State (0..$Automaton{$Auton}{'NumStates'}-1) {
	foreach $Read (@Alphabet) {
	    foreach $Trans (@{$Automaton{$Auton}{'Transition'}{$State}{$Read}}) {
		print "$State x $Read --> $Trans\n";
	    }
	}
    }
}



sub reachableacceptdfa { # algorithm courtesy theorem 4.4 sipser
    local($AutonP) = @_;
    local(@ReachableAccept, @Evidence);
    local($State, $AState, $NewStateMarked, $NextState,
	  %Marked, %Parent, %AlphaTo, @StateString, );
    # parts are identical and then tells you whether the two
    %Marked = (); %Parent = (); %AlphaTo = ();
    $Marked{$Automaton{$AutonP}{'InitStateIndex'}} = 1;
    $Parent{$Automaton{$AutonP}{'InitStateIndex'}} = -1;
    do {
	$NewStateMarked = 0;
	foreach $State (keys %Marked) {
	    foreach $Alph (keys %{$Automaton{$AutonP}{'Transition'}{$State}}) {
		foreach $NextState (@{$Automaton{$AutonP}{'Transition'}{$State}{$Alph}}) {
		    if (!$Marked{$NextState}) {
			$Marked{$NextState} = 1;
			$Parent{$NextState} = $State;
			$AlphaTo{$NextState} = $Alph;
			$NewStateMarked = 1;
			# print "Tamale Parent of $NextState is $State, via $Alph\n";
		    }
		}
	    }
	}
    } while ($NewStateMarked);

    # now check @Marked and @{$Automaton{$AutonP}{'FinalStateList'}} for intersection and decide
    @ReachableAccept = ();
    @Evidence = ();
    foreach $State (keys %Marked) {
	if ($Marked{$State}) {
	    if (grep(/^$State$/, @{$Automaton{$AutonP}{'FinalStateList'}})) {
		# print "Tamale IsMarked and final $State\n";
		# print "Tamale IsMarked accept states = ", join('_', @{$Automaton{$AutonP}{'FinalStateList'}}), "\n";
		push(@ReachableAccept, $State);
		@StateString = ();
		$AState = $State;
		while ($Parent{$AState} != -1) {
		    # print "Tamale AState=$AState, AlphaTo=$AlphaTo{$AState}\n";
		    push(@StateString, $AlphaTo{$AState});
		    $AState = $Parent{$AState};
		}
		$NewStateMarked = join('', reverse(@StateString));
		push(@Evidence, $NewStateMarked);
	    }
	}
    }
    # foreach $A (@Evidence) { print "Evidence: $A\n"; }
    return @Evidence; # arrays don't intersect, the language is empty
    # This is an insignificant return
    # Caller should test for emptiness.
}



#########################################################INCOMPLETE
sub epsilonexpand {
    local($AutonP, @StateList) = @_;
    local($State, $AState, $NewStateMarked,
	  %Marked, @StateString, @Ret);
    # parts are identical and then tells you whether the two
    %Marked = ();
    foreach $State (@StateList) { $Marked{$State} = 1; }
    do {
	$NewStateMarked = 0;
	foreach $State (keys %Marked) {
	    foreach $AState (@{$Automaton{$AutonP}{'Transition'}{$State}{'null'}}) {
		# print "we get into the null\n";
		if (!$Marked{$AState}) {
		    $Marked{$AState} = 1;
		    $NewStateMarked = 1;
		}
	    }
	}
    } while ($NewStateMarked);
    @Ret = ();
    foreach $State (keys %Marked) {
	push(@Ret, $State);
    }
    return @Ret;
}



sub nfatodfa {
    local($AutonN, $AutonD) = @_;

    &clearoneautomaton($AutonP);    
    $Automaton{$AutonD}{'NumStates'} = 
	2 ** $Automaton{$AutonD}{'NumStates'};

    $Automaton{$AutonP}{'InitStateIndex'} = 1;

}
#########################################################ENDINCOMPLETE






sub productdfa { # constructs cross product to recognize the symmetric difference
    # algorithm courtesy theorem 4.5 sipser

    local($Todo, $AutonA, $AutonB, $AutonP) = @_;

    &clearoneautomaton($AutonP);

    $BLen = $Automaton{$AutonB}{'NumStates'};

    $Automaton{$AutonP}{'NumStates'} = 
	$Automaton{$AutonA}{'NumStates'} *
	    $Automaton{$AutonB}{'NumStates'};
    # print "Product Number of states A = ", $Automaton{$AutonA}{'NumStates'}, "\n";
    # print "Product Number of states B = ", $Automaton{$AutonB}{'NumStates'}, "\n";
    # print "Product Number of states P = ", $Automaton{$AutonP}{'NumStates'}, "\n";

    $Automaton{$AutonP}{'InitStateIndex'} = 1 +
	( $Automaton{$AutonA}{'InitStateIndex'} - 1 ) * $BLen
	    + ( $Automaton{$AutonB}{'InitStateIndex'} - 1);

    # print "Product start state = ", $Automaton{$AutonP}{'InitStateIndex'}, "\n";

    foreach $AIndex (1..$Automaton{$AutonA}{'NumStates'}) {
	foreach $BIndex (1..$Automaton{$AutonB}{'NumStates'}) {
	    $AIsAccept = grep(/^$AIndex$/, @{$Automaton{$AutonA}{'FinalStateList'}});
	    $BIsAccept = grep(/^$BIndex$/, @{$Automaton{$AutonB}{'FinalStateList'}});
	    # print "Product accept states A = ", join('_', @{$Automaton{$AutonA}{'FinalStateList'}}), "\n";
	    # print "Product accept states B = ", join('_', @{$Automaton{$AutonB}{'FinalStateList'}}), "\n";
	    # print "Product AIndex=$AIndex BIndex=$BIndex AIsAccept=$AIsAccept BIsAccept=$BIsAccept\n";
	    if ($Todo eq 'asetminusb') {
		if ( $AIsAccept && !$BIsAccept) {
		    push(@{$Automaton{$AutonP}{'FinalStateList'}}, 1+($AIndex-1)*$BLen+($BIndex-1));
		}
	    } elsif ($Todo eq 'bsetminusa') {
		if ( !$AIsAccept &&  $BIsAccept) {
		    push(@{$Automaton{$AutonP}{'FinalStateList'}}, 1+($AIndex-1)*$BLen+($BIndex-1));
		}
	    } elsif ($Todo eq 'union') {
		if ( $AIsAccept || $BIsAccept) {
		    push(@{$Automaton{$AutonP}{'FinalStateList'}}, 1+($AIndex-1)*$BLen+($BIndex-1));
		}
	    } elsif ($Todo eq 'intersection') {
		if ( $AIsAccept &&  $BIsAccept) {
		    push(@{$Automaton{$AutonP}{'FinalStateList'}}, 1+($AIndex-1)*$BLen+($BIndex-1));
		}
	    } else {
		die "Wrong value of todo = $Todo used in productdfa\n";
	    }
	}
    }
    # print "Product accept states = ", join('_', @{$Automaton{$AutonP}{'FinalStateList'}}), "\n";

    foreach $AIndex (1..$Automaton{$AutonA}{'NumStates'}) {
	foreach $BIndex (1..$Automaton{$AutonB}{'NumStates'}) {
	    # print "AIndex=$AIndex BIndex=$BIndex\n";
	    foreach $AAlph (keys %{$Automaton{$AutonA}{'Alphabet'}}) {
		# print "AIndex=$AIndex BIndex=$BIndex AAlph=$AAlph\n";
		foreach $BAlph (keys %{$Automaton{$AutonB}{'Alphabet'}}) {
		    # print "AIndex=$AIndex BIndex=$BIndex AAlph=$AAlph BAlph=$BAlph\n";
		    if ($AAlph eq $BAlph) {
			# print "AIndex=$AIndex BIndex=$BIndex AAlph=$AAlph == BAlph=$BAlph\n";
			@TmpA = @{$Automaton{$AutonA}{'Transition'}{$AIndex}{$AAlph}};
			foreach $ADState (@TmpA) {

			    # print "ADState=$ADState\n";
			@TmpB = @{$Automaton{$AutonB}{'Transition'}{$BIndex}{$BAlph}};
			    foreach $BDState (@TmpB) {

				# print "                BDState=$BDState\n";
				&transition($AutonP,
					    1+($AIndex-1)*$BLen+($BIndex-1),
					    $AAlph,
					    1+($ADState-1)*$BLen+($BDState-1)
					    );
			    }
			}
		    }
		}
	    }
	}
    }

    # &printautomaton($AutonA);
    # &printautomaton($AutonB);
    # &printautomaton($AutonP);
}






sub dohalt { local($String) = @_;
	     print "\n\nInput=$String\n";
	     if ($CurState == -1) {
		 print "System REJECTED, because of unspecified transition.\n";
	     }
	 }


sub printstate { 
    foreach $Char (0..$#TMTape) { 
	($Char == $HeadPos ? print 'V' : print ' ');
    }
    print "\n";
    foreach $Char (@TMTape) { print $Char; }
    print "\n";
    print "St=$CurState Rd=$Read Nx=$Next Wr=$Write Mv=$Move\n";
    print "\n\n";
}




sub intersection {
    local(*A, *B) = @_;
    local(@I);
    @I = ();
    foreach $Elt (@A) {
	foreach $Elto (@B) {
	    if ($Elt == $Elto) {
		push(@I, $Elt);
	    }
	}
    }
    return @I;
}



sub printstates {
    local($String, @Arr) = @_;
    print $String, '>  ';
    foreach $A (@Arr) {
	print $A, ' ';
    }
    print "\n";
}






sub simulatenordfa { 
    local($String, $Auton) = @_;

    local($Debugger) = 0;

    local(@CurState);

    @CurState = ($Automaton{$Auton}{'InitStateIndex'});
    @CurState = &epsilonexpand($Auton, @CurState);

    if ($Debugger) { &printstates('.', @CurState); }
    foreach $Char (split(//, $String)) {
	%Pot = ();
	foreach $ACurState (@CurState) {
	    foreach $AState (@{$Automaton{$Auton}{'Transition'}{$ACurState}{$Char}}) {
		$Pot{$AState} = 't';
	    }
	}
	@CurState = sort keys %Pot;
	if ($Debugger) { &printstates($Char, @CurState); }
	@CurState = &epsilonexpand($Auton, @CurState);
	if ($Debugger) { &printstates('_', @CurState); }
	if ($#CurState < 0) {
	    if ($Debugger) { print "Input terminated\n"; }
	    return(2);
	}
    }

    @Other = @{$Automaton{$Auton}{'FinalStateList'}};

    @Intersection = &intersection( *CurState, *Other );
    if ($Debugger) {
	print 'Intersection >>>', join('*', @Intersection), "\n"; 
    }
    if (@Intersection) { # @CurState contains an accept state
	if ($Debugger) { print "Input accepted\n"; }
	return(0);
    } else {
	if ($Debugger) { print "Input rejected\n"; }
	return(1);
    }
}



sub comparedfas {
    local($Reference, $Gradee) = @_;
    local($String, $FeedIns);

    $FeedIns = '';

    &productdfa('asetminusb', $Reference, $Gradee, 'asetminusb');
    # &printautomaton('reference');
    # &printautomaton('gradee');
    # &printautomaton('asetminusb');
    @AMinusBEvidence = &reachableacceptdfa('asetminusb');

    if (@AMinusBEvidence) {
	$FeedIns .= "Your automaton should accept the following but does not:\n";
	foreach $String (@AMinusBEvidence) {
	    $FeedIns .= $String."\n";
	}
	$FeedIns .= "\n\n";
    } else {
	$FeedIns .= "Your automaton accepts every string that it should -- GOOD !!!\n";
    }



    &productdfa('bsetminusa', $Reference, $Gradee, 'bsetminusa');
    # &printautomaton('bsetminusa');
    @BMinusAEvidence = &reachableacceptdfa('bsetminusa');
    if (@BMinusAEvidence) {
	$FeedIns .= "Your automaton should reject the following but does not:\n";
	foreach $String (@BMinusAEvidence) {
	    $FeedIns .= $String."\n";
	}
	$FeedIns .= "\n\n";
    } else {
	$FeedIns .= "Your automaton rejects every string that it should -- GOOD !!!\n";
    }

    return $FeedIns;
}




sub gradedfa {
    local($Person, $Submission, $FileName, $ShortFileName)  = @_;

    local($Points);

    $RScore = 0;
    $RTotal = 0;
    $AScore = 0;
    $ATotal = 0;


    &readxmlfile($FileName, 'gradee');
    $Feedback = '';
    $Feedback .= "________________________________________________________________________\n";
    $Feedback .= "\n     LOGIN = $Person\n";
    $Feedback .= "SUBMISSION = $Submission\n";
    $Feedback .= "      FILE = $ShortFileName\n\n";



############################################################
### TEMPORARILY REMOVED QUALITATIVE GRADING SECTION

    if ($QualitativeGradingOrNot) {
    $Feedback .= "
Qualitative Grading Section
---------------------------

This section uses a grading technique for which I don't give any
points or take any points off, because it can find more faults or
fewer faults depending on how you design your machine.  It can also
tell you if your machine is perfect.  Bottom line: you don't get any
credit for this section of the grading.  If your machine is perfect
according to this section, it will be perfect according to the second
section too.

";

#    $Feedback .= &comparedfas('reference', 'gradee');

############################################################
}

    $Feedback .= "

Quantitative Grading Section
----------------------------

In this section everybody gets points taken off for exactly the same
reasons, regardless of how their machine was designed.  I test your
machine on a number of strings (choose the same strings for everyone,
and I make up the set of strings before looking at the automata).  You
can get a perfect score on this section with luck, even if your
machine is not correct.

";

    $Feedback .= "  <InputString> Behavior Verdict Score\n";
    open(FILE, "< $TestFile");
    $CountEleven = 0; $Deb1 = $Deb2 = $Deb3 = $Deb4 = $Deb5 = 0;
    while($Ln = <FILE>