#Skeleton file for HW4 - Spring 2015-2016 - Extended Intro to CS

#Add your implementation to this file

#You may add other utility functions to this file,
#but you may NOT change the signature of the existing ones.

#Change the name of the file to hw4_IDnumber (extension .py).

import random


############
# QUESTION 1
############

def max22(L, left, right):
    pass #replace this with your code


def max_list22(L):
    return max22(L, 0, len(L)-1)


############
# QUESTION 2
############

def change_fast(amount, coins):
    pass #replace this with your code


############
# QUESTION 3
############

def optimal_cruise(ship_prices):
    pass #replace this with your code

def optimal_cruise_seasick(toilet_prices):
    pass #replace this with your code


############
# QUESTION 4
############

# replace each "replace string with code" string with appropriate code
# do not modify the code's structure or change any of the existing code

def comp(s1,s2):
    if "replace string with code":
        return True
    if len(s1)==0 or len(s2)==0:
        return False
    if s1[0]=="+":
        return "replace string with code"
    if s1[0]=="*":
        return "replace string with code"
    if "replace string with code":
        return False
    return "replace string with code"


############
# QUESTION 6
############

def naive(num_of_coins):
    """
    naive strategy:
    uniformly pick a non-empty pile
    uniformly pick the number of coins to remove
    """
    pass #replace this with your code
    
def compete(num_of_piles, init_num_of_coins, s1, s2):
    """
    simulates a single game
    """
    pass #replace this with your code
    
def compare(num_of_piles, init_num_of_coins, s1, s2, num_of_games):
    """
    compares strategies over multiple games
    """
    pass #replace this with your code
        
def silly(num_of_coins):
    """
    a silly strategy
    """
    pass #replace this with your code
    
def winning(num_of_coins):
    """
    winning strategy
    """
    
    assert sum(num_of_coins)!=0
    
    num_of_piles = len(num_of_coins)
    # get binary representations of bins heights
    binary_reps = [bin(e)[2:] for e in num_of_coins]
    # pad with zeros to achieve equal representation lengths
    maxlen = max([len(e) for e in binary_reps])
    binary_reps = ["0"*(maxlen-len(e))+e for e in binary_reps]
    # compute bitwise xor of pile heights
    xor_of_num_of_coins = "".join([str(sum([int(binary_reps[i][j]) for i in range(num_of_piles)])%2) 
                                    for j in range(maxlen)])
    
    # if bitwise XOR encodes for 0, resort to naive strategy
    if int(xor_of_num_of_coins, 2)==0:
        naive(num_of_coins)
        return
    
    # find index of most significant bit in xor_of_num_of_coins    
    mostsign = xor_of_num_of_coins.index("1")
    # find a pile whose binary representation includes "1" in this index
    pile = [i for i in range(num_of_piles) if binary_reps[i][mostsign]=="1"][0]
    # compute binary representation of the number of coins we should leave in this pile
    xor_of_coins_to_remain = [str((int(a)+int(b))%2) for a,b in zip(binary_reps[pile], xor_of_num_of_coins)]
    # convert to int, modify pile
    coins_to_remain = int("".join(xor_of_coins_to_remain), 2)
    num_of_coins[pile] = coins_to_remain

    assert all(e>=0 for e in num_of_coins), "number of coins turned negative"
    

########
# Tester
########

def test():

    # Q1 basic tests
    if max_list22([1,20,3]) != 20:
        print("error in max22()")
    if max_list22([1,20,300,400]) != 400:
        print("error in max22()")
        
    # Q2 basic tests
    if change_fast(10, [1,2,3]) != 14:
        print("error in change_fast()")

    # Q3 basic tests
    if optimal_cruise([[0, 20, 30], [0, 0, 60]]) != 30:
        print("error in optimal_cruise()")
    if optimal_cruise([[0, 20, 3000], [0, 0, 60]]) != 80:
        print("error in optimal_cruise()")
    if optimal_cruise_seasick([10, 200, 30, 100]) != 130:
        print("error in optimal_cruise_seasick()")
    if optimal_cruise_seasick([10, 20, 30, 100]) != 120:
        print("error in optimal_cruise_seasick()")

    # Q4 basic tests
    if comp("ab", "ab")!=True:
        print("error in comp()")
    if comp("", "")!=True:
        print("error in comp()")
    if comp("a", "ab")!=False:
        print("error in comp()")
    if comp("+", "a")!=True:
        print("error in comp()")
    if comp("+", "")!=False:
        print("error in comp()")
    if comp("a+b", "axb")!=True:
        print("error in comp()")
    if comp("a+b", "axxb")!=False:
        print("error in comp()")
    if comp("a*xyz", "abcxyz")!=True:
        print("error in comp()")
    if comp("a*", "a")!=False:
        print("error in comp()")