# RW2.py
# NAME
# DATE

from random import randint as randi
from simpleGraphicsE import *

def MakePath(n):
    """ Returns a string s that consists of the characters
    'E', 'N', 'W', and 'S'.
    
    s[k] indicates how the robot moved during step k. Thus,
    if s[7] is 'N', then in step 7 the robot moved North, i..e,
    the y-value of its location was increased by 1.
    
    PreC: n is a positive integer
    """
    # The current location of the robot is (x,y)
    x = 0
    y = 0
    # The travel string s will be built through repeated concatenation
    s = ''
    DrawDisk(x,y,.25,color=RED)
    while abs(x)<=n and abs(y)<=n:
        i = randi(1,4)
        if i==1:
            # Move east
            x=x+1
            s =s+'E'
        elif i==2:
            # Move north
            y=y+1
            s=s+'N'
        elif i==3:
            # Movewest
            x=x-1
            s=s+'W'
        else:
            # Move south
            y=y-1
            s=s+'S'
    return s

def HopsAve(n,nTrials):
    """ Returns a float that estimates the average number of hops
    that it takes for the robot to escape from a size n grid.
    The average is based on m trials.
    
    PreC: n and m are positive integers.
    """
    
    TheSum = 0
    for k in range(nTrials):
        ThePath = MakePath(n)
        # Generate a travel string. Its length is the
        # number of hops needed by the robot to escape.
        TheSum = TheSum + len(ThePath)
    ave = float(TheSum)/float(nTrials)
    return ave
    # If you double n then HopsAve increases by about 4

def isHappy(s,n):
    """ Returns a boolean that is true
    if the last playpen tile is a corner tiles
    
    PreC: s is a travel string that specifies an
    exit route in a size-n playpen and n is a
    positive int."""
    
    # The final location of the robot is (Lastc,Lasty)
    Lastx = s.count('E')-s.count('W')
    Lasty = s.count('N')-s.count('S')
    # The absolute value of one of these must be n if we have
    # a corner exit.
    LeftFromCorner = abs(Lastx)==n or abs(Lasty)==n
    return LeftFromCorner

def ProbHappy(n,nTrials):
    """ Returns a float that estimates the probability
    that an escape route in a size n playpen
    ends in a corner.
    
    PreC: n and nTrial are positive integers.
    """
    count=0
    for k in range(nTrials):
        ThePath = MakePath(n)
        if isHappy(ThePath,n):
            count +=1
    return float(count)/float(nTrials)
    # The chance of exiting through a corner gets progressively
    # worse than p = 1/(2n) as n increases.
    
def isHomesick(x,y,n):
    """ Returns True if the edge distance from (x,y)
    is strictly less than the homedistance  (x,y).
    
    PreC: x and y are flaots with the property that
    (x,y) is in asize n playpen.
    """
    return abs(x)+abs(y) > n-max(abs(x),abs(y))

def Homesick(s,n):
    """ Returns an int that is the first hop
    that results in homesickness.
    
    PreC: s is a travel string and n is an int that specifies
    the size of the playpen.
    """
    
    # (x,y) is the location of the robot BEFORE hop k
    k=0; x=0; y=0
    while not isHomesick(x,y,n):
        # The robot is still not homesick.
        # Generate the next hop
        if s[k]=='E':
            x=x+1
        elif s[k]=='N':
            y=y+1
        elif s[k]=='W':
            x=x-1
        else:
            y=y-1
        k=k+1
    # Before hop k we are at (x,y). But (x,y) is a
    # homesick location. So we want  to retun a value that is
    # one less than that.
    return k-1

def HomesickAve(n,nTrials):
    """ Returns a float that estimates the
    average number of hops it takes for a robot to
    get homesick on a size n playpen.
    
    The average is based on the number of trials specified
    by nTrials.
    
    PreC: n and nTrials are positive int
    """
    TheSum = 0
    for k in range(nTrials):
        s = MakePath(n)
        TheSum = TheSum + Homesick(s,n)
    return float(TheSum)/float(nTrials)
    # If you double n then the average goes up by about 4.
    # And roughly at the one-fifth point along the journey the
    # roboit first experiences homesickness.
    


def DrawPlaypen(n):
    """ Draws a size n playpen.
    
    n should be <=10 for the labels to be clear
    
    PreC: n is a positive int.
    """
    
    # Draw the pen and its purple boundary
    DrawRect(0,0,2*n+3,2*n+3,color=PURPLE,stroke=0)
    DrawRect(0,0,2*n+1,2*n+1,color=YELLOW,stroke=0)
    x = -n-.5
    y = -n-.5
    # Add in the vertical and horizontal grid lines.
    for k in range(2*n+2):
       DrawLineSeg(x,-n-1.5,2*n+3,90)
       DrawLineSeg(-n-1.5,y,2*n+3,0)
       x+=1
       y+=1
       

# Application Script
if __name__ == '__main__':
    n = 5
    #MakeWindow(n+2,labels=True,bgcolor='BLACK')
    #DrawPlaypen(n)
    #ShowWindow()
    

    nTrials = 1000
    n=5
    print '\nHopsAve(%2d,%2d) = %8.3f' % (n,nTrials, HopsAve(n,nTrials))
    n=10
    print 'HopsAve(%2d,%2d) = %8.3f' % (n,nTrials, HopsAve(n,nTrials))
    n=20
    print 'HopsAve(%2d,%2d) = %8.3f' % (n,nTrials, HopsAve(n,nTrials))
    
    n=5
    print '\nProbHappy(%2d,%2d) = %6.3f    p = %6.3f' % (n,nTrials, ProbHappy(n,nTrials),1/(2.*n))
    n=10
    print 'ProbHappy(%2d,%2d) = %6.3f    p = %6.3f' % (n,nTrials, ProbHappy(n,nTrials),1/(2.*n))
    n=20
    print 'ProbHappy(%2d,%2d) = %6.3f    p = %6.3f' % (n,nTrials, ProbHappy(n,nTrials),1/(2.*n))
    
    
    n=5
    print '\nHomesickAve(%2d,%2d) = %6.3f' % (n,nTrials, HomesickAve(n,nTrials))
    n=10
    print 'HomesickAve(%2d,%2d) = %6.3f' % (n,nTrials, HomesickAve(n,nTrials))
    n=20
    print 'HomesickAve(%2d,%2d) = %6.3f' % (n,nTrials, HomesickAve(n,nTrials))