#!/usr/bin/env python
# coding: utf-8

# # Appendix: An interactive Jupyter notebook session to accompany: "Penney's game odds from no-arbitrage" by Miller, J.B. (2019)
# 
# 
# 
# see https://github.com/joshua-benjamin-miller/penneysgame for .ipynb and .py files.
# 
# 
# 
# This interactive notebook explores an algorithm that solves a generalized version of Penney's pattern-matching game for a q-sided die ($q\geq 3$), with potentially unequal probabilities.
# 
# The solution implements a generalized version of Conway's leading number algorithm , and cross-validates it via simulation.
# 
# References
# 1. Miller, J.B. (2019) "Penney's game odds from no-arbitrage", OSF [PDF Download](https://osf.io/47u5a/)
# 2. Li, Shuo-Yen Robert. (1980) A martingale approach to the study of occurrence of sequence patterns in repeated experiments." _the Annals of Probability_, 8(6) 1171-1176. [PDF Download](https://projecteuclid.org/euclid.aop/1176994578)
# 3. Guibas, L. J. & Odlyzko, A. M. (1981), "String overlaps, pattern matching, and nontransitive games",
#  _Journal of Combinatorial Theory, Series A_ 30(2), 183--208. [PDF Download](https://core.ac.uk/download/pdf/81142890.pdf)
# 2. 

# ### Third party modules and directory check

# In[1]:


import time
import os        #for benchmarking
import numpy as np
#in case we need to update user-defined code e.g. importlib.reload(diffP)
import importlib


# In[32]:


current_dir=os.getcwd()
print(current_dir)
for file in os.listdir(current_dir):
    if file[-3:]=='.py':
        print(file)


# ### Desciption of code in "conway.py"

# In[2]:


import conway  #The programs live here
importlib.reload(conway)
#help(conway)
print('Locked and loaded')


# ## Inspect functions

# ### Let's test the generalized Conway leading number
# 
# note: In the speccial case of a fair coin flip, this is $2\times \text{Conway Leading Number}$
# 
# Conway leading number is an (asymmetric) measure of overlap between two patterns A and B.
# 
# AB measures how the leading numbers of B overlap with the trailing numbers of A, as B is shifted to the right (assuming B is not a subpattern of A)
# 
# Here is the function:

# In[6]:


help(conway.payoff_to_B_bettors_if_A_occurs_first)


# If A=THH comes first, how much does a player who, on each trial, initiates a asequence of bets on characters according to B=HHH, get paid?
# 
# The players that arrive at time T-1 and time T walk out with \$4 and \$2 respectively, for a total of \$6
# 

# In[17]:


distribution={'H':.5, 'T':.5}
A = "THH"
B = "HHH"
print(conway.payoff_to_B_bets_if_A_occurs_first(A, B, distribution))


# ### Let's test the generalized Conway leading number algorithm
# 
# Here is the function:

# In[18]:


help(conway.oddsAB)


# What are the odds that that pattern A=HTH precedes pattern B=TTH?
# 
# In the case that A occurs before B, i.e we compare the trailing characters of $A\cdot$
# * $AA=8+0+2=10$        (the $A$-bets initiated at $T-2$ and $T$ are winners)
# * $AB=0+0+0=0$    (the $B$-bets never win)
# 
# In the case that B occurs before A, i.e we compare the trailing characters of $B\cdot$
# * $BB=8+0+0=8$ (the $B$-bet inititiated at $T-2$ is a winner)
# * $BA=0+0+2=2$        (the $A$-bet initiated at $T$ is a winner)
# 
# so odds against $A$ occuring before $B$ are ${AA-AB}:{BB-BA} = 10:6$, or $5:3$
# 
# this translates to a probability that $A$ occurs first equal to $3/8$
# 
# Let's check this below:

# In[19]:


distribution={'H':.5, 'T':.5}
A = "HTH"
B = "TTH"
print('odds against A = [chances against, chances in favor] = ',conway.oddsAB(A, B, distribution))

print('probability A occurs before B = ', conway.probAB(A, B, distribution))


# ## Cross-Validating the code.
# 
# 

# ### Replicating original Penney's Game odds (patterns of length 3)
# 

# Let's create the table, the probability the row pattern comes before the column pattern, and cross-validate with table from Gardner
# 

# In[97]:


from fractions import Fraction

pH = .5
pT = 1-pH
distribution={'H':pH, 'T':pT}

k = 3
#initialize the globals within the module
conway.list_pattern=['-']*k
conway.patterns = []

#build the patterns
help(conway.all_patterns)
conway.all_patterns(k,distribution)

patterns = conway.patterns

print("all patterns of length",k,"= ",patterns)


row = 0
print("-" * 70)
print("", end='\t')
print(*patterns, sep='\t')

while row < 8:
    col = 0
    print(patterns[row],end='\t')
    while col <= 7:
        r='\t'
        if col ==7:
            r='\n'
        if patterns[row]==patterns[col]:
           print('', end=r) 
        else:
            o=conway.oddsAB(patterns[row],patterns[col], distribution)
            F = Fraction(int(o[1]),int(o[0]+o[1]))
            N = F.numerator
            D = F.denominator
            print(N,"/",D,end=r)
        col += 1
    row += 1
print("-" * 70)



# Gardner's table (they match):

# 
# 
# <img src="Gardner-penney-table.PNG" align="left" alt="drawing" width="450"/>

# ### Cross-validate the odds function by simulation
# 
# here is the simulation function:

# In[11]:


help(conway.simulate_winrates_penney_game)


# Cross-validate the simple case

# In[258]:


distribution={'H':.5, 'T':.5}
A = "HTH"
B = "TTH"


p = conway.probAB(A,B,distribution)
wait = conway.expected_waiting_time(A,B,distribution)

N=10000
np.random.seed(0)
prop, average_n_flips= conway.simulate_winrates_penney_game(A,B,distribution,N)

print('Pr(A<B)   = ', "%.3f" %p , '   (Theoretical Probability)')
print('Prop(A<B) = ', "%.3f" %prop[0], '   (Simulation with N =', N, ' trials)\n')
print('E[number of flips] = ', "%.2f" %wait , '        (Theoretical Expectation)') 
print('Average number of flips = ', "%.2f" %average_n_flips, '   (Simulation with N =', N, ' trials)')


# Let's cross validate generalized Conway w/small alphabet & unequal probalities:
# 
# The simulation validates the formula

# In[259]:


distribution={'H':.75, 'T':.25}
A = "HTH"
B = "TTH"

p = conway.probAB(A,B,distribution)
wait = conway.expected_waiting_time(A,B,distribution)

N=10000
np.random.seed(0)
prop, average_n_flips= conway.simulate_winrates_penney_game(A,B,distribution,N)

print('Pr(A<B)   = ', "%.3f" %p , '   (Theoretical Probability)')
print('Prop(A<B) = ', "%.3f" %prop[0], '   (Simulation with N =', N, ' trials)\n')
print('E[number of flips] = ', "%.2f" %wait , '        (Theoretical Expectation)') 
print('Average number of flips = ', "%.2f" %average_n_flips, '   (Simulation with N =', N, ' trials)')


# Let's cross validate Conway for longer patterns:
# 
# The simulation validates the formula

# In[260]:


distribution={'H':.5, 'T':.5}
A = "HTHT"
B = "TTTH"

p = conway.probAB(A,B,distribution)
wait = conway.expected_waiting_time(A,B,distribution)

N=10000
np.random.seed(0)
prop, average_n_flips= conway.simulate_winrates_penney_game(A,B,distribution,N)

print('Pr(A<B)   = ', "%.3f" %p , '   (Theoretical Probability)')
print('Prop(A<B) = ', "%.3f" %prop[0], '   (Simulation with N =', N, ' trials)\n')
print('E[number of flips] = ', "%.2f" %wait , '        (Theoretical Expectation)') 
print('Average number of flips = ', "%.2f" %average_n_flips, '   (Simulation with N =', N, ' trials)')


# Let's cross validate generalized Conway w/with longer alphabet, unequal probabilities, and longer patterns
# 
# The simulation validates the formula
# 

# In[262]:


distribution={'a':.5, 'b':.25, 'c':.25}
A = "aaac"
B = "abba"

p = conway.probAB(A,B,distribution)
wait = conway.expected_waiting_time(A,B,distribution)

N=10000
np.random.seed(0)
prop, average_n_flips= conway.simulate_winrates_penney_game(A,B,distribution,N)

print('Pr(A<B)   = ', "%.3f" %p , '   (Theoretical Probability)')
print('Prop(A<B) = ', "%.3f" %prop[0], '   (Simulation with N =', N, ' trials)\n')
print('E[number of flips] = ', "%.2f" %wait , '        (Theoretical Expectation)') 
print('Average number of flips = ', "%.2f" %average_n_flips, '   (Simulation with N =', N, ' trials)')


# Waiting time for COVFEFE vs. other patterns.

# In[13]:


import string
uppercase_alphabet = dict.fromkeys(string.ascii_uppercase, 0)
distribution = {x: 1/26 for x in uppercase_alphabet}

A = 'COVFEFE'
B = 'CCOVFEF'

p = conway.probAB(A,B,distribution)
print('Pr(',A,'<',B,')   = ', "%.3f" %p , '   (Theoretical Probability)')
print('------------------')
wait = conway.expected_waiting_time(A,B,distribution)
print('E[number of flips until',A,'or',B,'] = ', "%.2f" %wait , '        (Theoretical Expectation)') 



# # Application
# 
# What is the first mover's probability of winner if the second mover best responds, as a function of the probability of heads.

# In[76]:


import matplotlib.pyplot as plt
import numpy as np

k = 3
#initialize the globals within the module
conway.list_pattern=['-']*k
conway.patterns = []

#build the patterns
conway.all_patterns(k,distribution)
patterns=conway.patterns

pHs = [i/100 for i in range(1,100)]

min_prob_each_pattern = [] 

#plt.gca().set_prop_cycle(None)

for pH in pHs:
    pT = 1-pH
    distribution={'H':pH, 'T':pT}
    
    min_probs = []
    for A in patterns:
        probABs = []
        for B in patterns:
            if A != B:
                probABs.append(conway.probAB(A,B,distribution))
            else:
                probABs.append(None)

        min_probAB = min(p for p in probABs if p is not None)
        min_probs.append(min_probAB)
    min_prob_each_pattern.append(min_probs)
    

#plt.figure(figsize=(8, 6),facecolor="white") 

#don't include gray borders
plt.figure(facecolor="white")
#plt.style.use('grayscale')

#don't incude negative x-axis
plt.xlim(0, 1)



#plot each graph
i = 0
for pattern in patterns:
         
        #make list x/y-values for plotting
        min_probs = [min_prob_each_pattern[j][i] for j in range(len(pHs)) ]
        plt.plot(pHs,min_probs,label=pattern)
        i +=1


#plot axis labels
#plt.ylabel('Expected Proportion')
#plt.xlabel('Number of shots')

#plot reference lines
plt.plot([0, 100], [.5, .5], 'k--',lw=.75)

#plot legend
plt.legend(bbox_to_anchor=(1, 1), loc=2,prop={'size': 8})


#plot axis labels
plt.ylabel('Probability wins worst match-up')
plt.xlabel('Probability of Heads')


#save figure
filename = 'win_worst_case_'+str(k)+'.pdf'
plt.savefig(filename, bbox_inches="tight");  

#plt.axis([0, 6, 0, 20])


# What is the expected waiting time for the game to end given the first mover's strategy (when second mover best responds) vs. if the first mover were waiting alone for the pattern.

# In[108]:


import matplotlib.pyplot as plt
import numpy as np
#help(conway)

#Difference in waiting time for each pattern, as a function of probability.

k = 3
#initialize the globals within the module
conway.list_pattern=['-']*k
conway.patterns = []

#build the patterns
pH =.5
pT = 1-pH
distribution={'H':pH, 'T':pT}
conway.all_patterns(k,distribution)
patterns=conway.patterns

pHs = [i/1000 for i in range(300,701)]
#print(pHs)
diff_wait_time = []

#plt.gca().set_prop_cycle(None)

for pH in pHs:
    pT = 1-pH
    distribution={'H':pH, 'T':pT}

    

    diff_waiting_time_A = []
    for A in patterns:
        probABs = []
        for B in patterns:
            if A != B:    
                probABs.append(conway.probAB(A,B,distribution))
            else:
                probABs.append(None)

      

        waiting_time_A = conway.expected_waiting_time(A,A,distribution) 
        
        #in case of times
        min_probAB = min(p for p in probABs if p is not None)
        min_indices = [i for i in range(len(probABs)) if probABs[i]==min_probAB]
        waiting_times_AminB =[]
        for i in min_indices:
            waiting_times_AminB.append(conway.expected_waiting_time(A,patterns[i],distribution))
        
        waiting_time_AB = min(waiting_times_AminB)
        
        diff_waiting_time_A.append(waiting_time_AB-waiting_time_A)
    
    diff_wait_time.append(diff_waiting_time_A)

#print(wait_time_pairs)


#plt.figure(figsize=(8, 6),facecolor="white") 

#don't include gray borders
#plt.figure(facecolor="white")
#plt.style.use('grayscale')

#don't incude negative x-axis
#plt.xlim(0, 50)



#plot each graph
i = 0
#plot each graph
i = 0
for pattern in patterns:
         
        #make list x/y-values for plotting
        y = [diff_wait_time[j][i] for j in range(len(pHs)) ]
        plt.plot(pHs,y,label=pattern)
        i +=1
        
        


#plot axis labels
#plt.ylabel('Expected Proportion')
#plt.xlabel('Number of shots')

#plot reference lines
plt.plot([.3, .7], [0, 0], 'k--',lw=.75)

#plot legend
plt.legend(bbox_to_anchor=(1, 1), loc=2,prop={'size': 8})


#plot axis labels
plt.ylabel('E[time game ends] - E[time of pattern]')
plt.xlabel('Probability of Heads')


#save figure
filename = 'waiting_time'+str(k)+'.pdf'
plt.savefig(filename, bbox_inches="tight");