"""

John Rachlin
DS 2000: Intro to Programming with Data

Filename: list_algorithms
    
Description: A variety of algorithms

    
"""

import random as rnd
num_games = 162
redsox_win = 0.600


#%%

# Create a list of 162 games
# Using the probability of winning


games = []
for i in range(num_games):
    coinflip = rnd.random()
    if coinflip < redsox_win:
        games.append(1)
    else:
        games.append(0)
        
games
sum(games) / 162

#%%

# Comment 1: The i isn't doing anything

for _ in range(num_games):
    pass
    # so i can be "anonymous"
   
#%% concise vs. readable - which is better?

games = []
for _ in range(num_games):
    games.append(int(rnd.random()<redsox_win))
    
games
sum(games) / 162


#%% List comprehensions will blow your mind!
# Describe a process for building a list

games = [int(rnd.random()<redsox_win) for _ in range(num_games)]
games

#%% Other list comprehensions 

squares = [x ** 2 for x in range(10)]
squares


even_squares = [x ** 2 for x in range(10) if x % 2 == 0]
even_squares

words = ['hello', 'world', 'this', 'is', 'a', 'test']
wordlen = [len(w) for w in words]
wordlen



#%% Our first algorithm:  (Not really because I snuck in
# other algorithms in earlier lectures!)
# Find the maximum value in a list

L = [rnd.randint(0,1000) for _ in range(10)]
print(L)

# simple approach - use a built in function
print(max(L))


# educational approach - write your own algorithm!

maximum = L[0]
for i in range(1,len(L)): # This assumes that the list has at least 2 elements!
    if L[i] > maximum:
        maximum = L[i]
print(maximum)



# What if we want to find both the maximum AND the location of the maximum?
maxi = 0
maximum = L[0]
for i in range(1,len(L)):
    if L[i] > maximum:
        maximum = L[i]
        maxi = i
print(maximum,"at index", maxi)
        

# What if we have two lists
likes = [rnd.randint(0,1000) for _ in range(10)]
titles = ['Saving Private Ryan', 
          'Star Wars', 
          'The Life of Pi', 
          'Amadeus', 
          'Casablanca', 
          'Kill Bill', 
          'Field of Dreams', 
          'Interstellar', 
          'Star Trek Wrath of Khan', 
          'Gravity']

# Return the MOVIE with the most likes
print(likes)
maxlikes = max(likes)
maxi = likes.index(maxlikes) # Find the index of a value (first instance)
best_movie = titles[maxi]
best_movie


#%% Back to the red sox!

num_games = 162
redsox_win = 0.602
games = [int(rnd.random()<redsox_win) for _ in range(num_games)]

# Best win streak?  Worst losing streak 
max_win_streak = 0
max_lose_streak = 0
win_streak = 0
lose_streak = 0
for g in games:
    if g == 1:
        win_streak += 1
        lose_streak = 0
    else:
        win_streak = 0
        lose_streak += 1
        
    if win_streak > max_win_streak:
        max_win_streak = win_streak
        
    if lose_streak > max_lose_streak:
        max_lose_streak = lose_streak
    

print("Max wins in a row:", max_win_streak)
print("Max losses in a row:", max_lose_streak)


#%% Slicing

before_allstar = games[:81]  # games from 0 to 80 (81 games total)
after_allstar = games[81:]   # games from 81 to end of list
middle = games[40:60] # games from index 40 to 59  (20 games total)
middle

#%% Sorting a list - INSERTION SORT

size = 10000

L = [rnd.randint(0,1000) for _ in range(size)]


for i in range(1, len(L)):
    j = i
    while L[j] < L[j-1] and j>0: 
        temp = L[j-1]
        L[j-1] = L[j]
        L[j] = temp
        j -= 1

print(L)

#%% Using built in function - wow the built-in algorithm is really fast!!

size = 1000000
L = [rnd.randint(0,1000) for _ in range(size)]
L.sort()
print(L)


#%% A sorting experiment


total_swaps = []

for exp in range(5):
    size = 10 ** exp
    L = [rnd.randint(0,1000) for _ in range(size)]

    swaps = 0
    for i in range(1, len(L)):
        j = i
        while L[j] < L[j-1] and j>0: 
            temp = L[j-1]
            L[j-1] = L[j]
            L[j] = temp
            j -= 1
            swaps += 1
    print(size, swaps)
    total_swaps.append(swaps)
            
#%% The amount of work to sort a list is going up as the SQUARE of the size 
# of the list!   

import math
import matplotlib.pyplot as plt

plt.title("Swaps as a function of size")
plt.xlabel("list size")
plt.ylabel("# swaps")
plt.ylim(0,25000000)
plt.xlim(0,10000)
plt.grid()
plt.plot([x**2 * 1/4 for x in range(0,10000)])
plt.scatter([10**exp for exp in range(5)], total_swaps, marker='o')