ochikobore

# 6.00 Problem Set 6
#
# The 6.00 Word Game
#

import time
import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7

SCRABBLE_LETTER_VALUES = {
    'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}

WORDLIST_FILENAME = "words.txt"

def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    return wordlist

def get_frequency_dict(sequence):
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq


def get_word_score(word, n):
    """
    Returns the score for a word. Assumes the word is a
    valid word.

    The score for a word is the sum of the points for letters
    in the word, plus 50 points if all n letters are used on
    the first go.

    Letters are scored as in Scrabble; A is worth 1, B is
    worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.

    word: string (lowercase letters)
    returns: int >= 0
    """
    score = 0
    for letter in word:
        score += SCRABBLE_LETTER_VALUES[letter.lower()]
    if len(word) == n:
        score += 50
    return score

def display_hand(hand):
    """
    Displays the letters currently in the hand.

    For example:
       display_hand({'a':1, 'x':2, 'l':3, 'e':1})
    Should print out something like:
       a x x l l l e
    The order of the letters is unimportant.

    hand: dictionary (string -> int)
    """
    for letter in hand.keys():
        for j in range(hand[letter]):
             print letter,              # print all on the same line
    print                              # print an empty line


def deal_hand(n):
    """
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.

    Hands are represented as dictionaries. The keys are
    letters and the values are the number of times the
    particular letter is repeated in that hand.

    n: int >= 0
    returns: dictionary (string -> int)
    """
    hand={}
    num_vowels = n / 3
    
    for i in range(num_vowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]
        hand[x] = hand.get(x, 0) + 1
        
    for i in range(num_vowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1
        
    return hand


def update_hand(hand, word):
    """
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 

    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """
    freq = get_frequency_dict(word)
    newhand = {}
    for char in hand:
        newhand[char] = hand[char]-freq.get(char,0)
    return newhand
    #return dict( ( c, hand[c] - freq.get(c,0) ) for c in hand )
        

def is_valid_word(word, hand, word_list):
    """
    Returns True if word is in the word_list and is entirely
    composed of letters in the hand. Otherwise, returns False.
    Does not mutate hand or word_list.
    
    word: string
    hand: dictionary (string -> int)
    word_list: list of lower case strings
    """
    freq = get_frequency_dict(word)
    for letter in word:
        if freq[letter] > hand.get(letter, 0):
            return False
    return word in word_list


def play_hand(hand, word_list):
    """
    Allows the user to play the given hand, as follows:

    * The hand is displayed.
    
    * The user may input a word.

    * An invalid word is rejected, and a message is displayed asking
      the user to choose another word.

    * When a valid word is entered, it uses up letters from the hand.

    * After every valid word: the score for that word is displayed,
      the remaining letters in the hand are displayed, and the user
      is asked to input another word.

    * The sum of the word scores is displayed when the hand finishes.

    * The hand finishes when there are no more unused letters.
      The user can also finish playing the hand by inputing a single
      period (the string '.') instead of a word.

      hand: dictionary (string -> int)
      word_list: list of lowercase strings
    """    
    total = 0
    initial_handlen = sum(hand.values())
    time_limit = input("Enter time limit, in seconds, for players: ")*1.0
    time_remaining = time_limit
    
    while sum(hand.values()) > 0:
        
        print 'Current Hand:',
        display_hand(hand)
        
        start_time = time.time()
        
        userWord = raw_input('Enter word, or a . to indicate that you are finished: ')
        if userWord == '.':
             break
        else:
            isValid = is_valid_word(userWord, hand, word_list)

            if not isValid:
                
                print 'Invalid word, please try again.'
                
            else:
                end_time = time.time()
                total_time = end_time - start_time
            
                time_remaining = time_remaining - total_time
                
                if time_remaining <= 0.0:

                    print 'It took %0.2f seconds to provide an answer.' % total_time
                    print 'Total time exceeds %d seconds. You scored %d points' % (time_limit, total)
                    break
            
                print 'It took %0.2f seconds to provide an answer.' % total_time
                print 'You have %0.2f seconds remaining.' % time_remaining
                
                points = get_word_score(userWord, initial_handlen)
                total += points    
                print '%s earned %d points. Total: %d points' % (userWord, points, total)
                hand = update_hand(hand, userWord)
                
    print 'Total score: %d points.' % total



def play_game(word_list):
    """
    Allow the user to play an arbitrary number of hands.

    * Asks the user to input 'n' or 'r' or 'e'.

    * If the user inputs 'n', let the user play a new (random) hand.
      When done playing the hand, ask the 'n' or 'e' question again.

    * If the user inputs 'r', let the user play the last hand again.

    * If the user inputs 'e', exit the game.

    * If the user inputs anything else, ask them again.
    """

    hand = deal_hand(HAND_SIZE) # random init
    while True:
        cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
        if cmd == 'n':
            hand = deal_hand(HAND_SIZE)
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'r':
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'e':
            break
        else:
            print "Invalid command."

def get_words_to_points(word_list):
    """
    Basically takes word_list and turns it into a dictionary list where the elements are the words
    and the values are the points of each word.

    Returns the dictionary of words and points.
    """
    
    points_dict = {}

    for i in xrange(len(word_list)):
        
        points_dict[word_list[i]] = get_word_score(word_list[i], HAND_SIZE)

    return points_dict

def pick_best_word(hand, points_dict):
    """
    Selects the best word based on points within a set of letters.
    hand = list of your letters
    """
    
    hand_freq = get_frequency_dict(hand)

    bestWord = ""
    
    for word in points_dict:
        
        hasAllLetters = True
        
        word_freq = get_frequency_dict(word)

        #check if 
        for letter in word_freq:

            if word_freq[letter] > hand.count(letter):
                hasAllLetters = False
                break

        if hasAllLetters:
            if points_dict[word] > get_word_score(bestWord,HAND_SIZE):
                bestWord = word
                
    return bestWord

def get_time_limit(points_dict, k):
    """
    Return the time limit for the computer player as a funciton of the multiplier k.
    """

    start_time = time.time()
    for word in points_dict:
        get_frequency_dict(word)
        get_word_score(word, HAND_SIZE)
    end_time = time.time()

    return (end_time - start_time) * k
    
    

##if __name__ == '__main__':
##    word_list = load_words()
##    play_game(word_list)

# Problem Set 5: Ghost
# Name: Andrew
# Collaborators: CuriousReef
# Time: 
#

import random

# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
import string

WORDLIST_FILENAME = "words.txt"

def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    return wordlist

def get_frequency_dict(sequence):
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq


# (end of helper code)
# -----------------------------------



# Actually load the dictionary of words and point to it with 
# the wordlist variable so that it can be accessed from anywhere
# in the program.

# TO DO: your code begins here!

def isWordFrag(current, wordList): #returns True if input1 is on the road to making a word.
    for i in wordList:
        if i[0:len(current)] == current:
            return True
    return False



word_list = load_words()

currentTurn = 1

while True:
    
    currentFrag = ''
    gameOver = False
    
    while gameOver == False:
        while currentTurn == 1 and gameOver == False:
            currentFrag += raw_input("Player 1 says letter: ").lower()

            if currentFrag in word_list:
                if len(currentFrag) > 3:
                    print "Player 1 loses because",currentFrag,"is a word!"
                    currentTurn = 2
                    gameOver = True
                    break


            if not isWordFrag(currentFrag,word_list):
                print "Player 1 loses because no word begins with",currentFrag
                gameOver = True
                currentTurn = 2
                break
            currentTurn = 2
        
        while currentTurn == 2 and gameOver == False:
            currentFrag += raw_input("Player 2 says letter: ").lower()

            if currentFrag in word_list:
                print "Player 2 loses because",currentFrag,"is a word!"
                currentTurn = 1
                gameOver = True
                break


            if not isWordFrag(currentFrag,word_list):
                print "Player 2 loses because no word begins with",currentFrag
                currentTurn = 1
                gameOver = True
                break
            currentTurn = 1

    print "Player",currentTurn,"wins!"
    print("continue? (y/n)")
    playAgain = raw_input()
    if playAgain == 'n':
        break
    

# Problem Set 5: 6.00 Word Game
# Name: 
# Collaborators: 
# Time: 
#

import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7

SCRABBLE_LETTER_VALUES = {
    'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}

# -----------------------------------
# Helper code
# (you don't need to understand this helper code)

WORDLIST_FILENAME = "words.txt"

def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    return wordlist

def get_frequency_dict(sequence):
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq


# (end of helper code)
# -----------------------------------

#
# Problem #1: Scoring a word
#
def get_word_score(word, n):
    """
    Returns the score for a word. Assumes the word is a
    valid word.

    The score for a word is the sum of the points for letters
    in the word, plus 50 points if all n letters are used on
    the first go.

    Letters are scored as in Scrabble; A is worth 1, B is
    worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.

    word: string (lowercase letters)
    returns: int >= 0
    """
    totalPoints = 0
    for letter in word:
        totalPoints += SCRABBLE_LETTER_VALUES[letter.lower()]

    if len(word) == n:
        totalPoints += 50

    return totalPoints

#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
    """
    Displays the letters currently in the hand.

    For example:
       display_hand({'a':1, 'x':2, 'l':3, 'e':1})
    Should print out something like:
       a x x l l l e
    The order of the letters is unimportant.

    hand: dictionary (string -> int)
    """
    for letter in hand.keys():
        for j in range(hand[letter]):
            print letter,              # print all on the same line
    print                              # print an empty line

#
# Make sure you understand how this function works and what it does!
#
def deal_hand(n):
    """
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.

    Hands are represented as dictionaries. The keys are
    letters and the values are the number of times the
    particular letter is repeated in that hand.

    n: int >= 0
    returns: dictionary (string -> int)
    """
    hand={}
    num_vowels = n / 3
    
    for i in range(num_vowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]
        hand[x] = hand.get(x, 0) + 1
        
    for i in range(num_vowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1
        
    return hand

#
# Problem #2: Update a hand by removing letters
#
def update_hand(hand, word):
    """
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 

    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.

    Has no side effects: does not mutate hand.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """

    copy = dict(hand)
    
    for letter in word:
        copy[letter] = copy.get(letter,0) - 1
        if copy[letter] < 1:
            del copy[letter]
    return copy

#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, word_list):
    """
    Returns True if word is in the word_list and is entirely
    composed of letters in the hand. Otherwise, returns False.
    Does not mutate hand or word_list.
    
    word: string
    hand: dictionary (string -> int)
    word_list: list of lowercase strings
    """
    # TO DO ...

    ##is the word in word list?
    ##do you have the right letters?

    if word not in word_list:
        print "The word is not in the dictionary, stop making words up!"
        return False

    cache = dict(hand)
    for letter in word:
        if cache[letter] > 0:
            cache[letter] -= 1
        else:
            print "You don't have the right letters for this!"
            return False

    return True
            

#
# Problem #4: Playing a hand
#
def play_hand(hand, word_list):
    """
    Allows the user to play the given hand, as follows:

    * The hand is displayed.
    
    * The user may input a word.

    * An invalid word is rejected, and a message is displayed asking
      the user to choose another word.

    * When a valid word is entered, it uses up letters from the hand.

    * After every valid word: the score for that word and the total
      score so far are displayed, the remaining letters in the hand 
      are displayed, and the user is asked to input another word.

    * The sum of the word scores is displayed when the hand finishes.

    * The hand finishes when there are no more unused letters.
      The user can also finish playing the hand by inputing a single
      period (the string '.') instead of a word.

    * The final score is displayed.

      hand: dictionary (string -> int)
      word_list: list of lowercase strings
    """
    # TO DO ...
    display_hand(hand)
    player1score = 0
    
    word = raw_input("Enter word, or a '.' to indicate that you are finished. ")
    
    while word != '.':
        while not is_valid_word(word, hand, word_list):
            word = raw_input("Enter word, or a '.' to indicate that you are finished. ")
            if word == '.':
                break
        if word == '.':
            break
        print "You get",get_word_score(word,7),"points for",word+"."
        player1score += get_word_score(word,7)
        print "Player 1:",player1score
        print

        hand = update_hand(hand,word)

        if not len(hand):
            break
        display_hand(hand)
        
        word = raw_input("Enter word, or a '.' to indicate that you are finished. ")
        
    print "Final score:",player1score            
    
#
# Problem #5: Playing a game
# Make sure you understand how this code works!
# 
def play_game(word_list):
    """
    Allow the user to play an arbitrary number of hands.

    * Asks the user to input 'n' or 'r' or 'e'.

    * If the user inputs 'n', let the user play a new (random) hand.
      When done playing the hand, ask the 'n' or 'e' question again.

    * If the user inputs 'r', let the user play the last hand again.

    * If the user inputs 'e', exit the game.

    * If the user inputs anything else, ask them again.
    """
    # TO DO ...
    
    ## uncomment the following block of code once you've completed Problem #4
    hand = deal_hand(HAND_SIZE) # random init
    while True:
        cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
        if cmd == 'n':
            hand = deal_hand(HAND_SIZE)
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'r':
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'e':
            break
        else:
            print "Invalid command."

#
# Build data structures used for entire session and play game
#

if __name__ == '__main__':
    word_list = load_words()
    play_game(word_list)
    

#Problem Set 1
#Name: Andrew
#Collaborators: CuriousReef
#Time: 
from math import *

#problem 1
def isPrime(num):

    if num < 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    for i in range(3,int(ceil(sqrt(num)))+1,2):
        if num % i == 0:
            return False
    return True

def primeFinder(num):
    primesFound = 0
    test = 0 #number we're testing
    
    while primesFound < num:
        test += 1
        
        if isPrime(test):
            primesFound += 1
            
    return test

#problem 2

def sumLogPrime(num):
    primesFound = 0
    test = 0
    total = 0
    
    while primesFound < num:
        test += 1
        
        if isPrime(test):
            total += log(test)
            primesFound += 1
    print "The sum of the log of the primes:",total
    print "The number n:",num
    print "The ratio of these two quantities:",float(total)/float(num)        
    return total

###prints sum of log of primes. n. and the ratio of those two. 

if __name__ == "__main__":
    sumLogPrime(1000)

# Problem Set 4
# Name: Andrew
# Collaborators: CuriousReef
# Time: 12 hours

#
# Problem 1
#

def nestEggFixed(salary, save, growthRate, years):

    yearlyAcct = []

    for i in range(years):
        if not yearlyAcct: #if empty do this
            yearlyAcct.append(salary * save * 0.01)
        else:
            yearlyAcct.append(yearlyAcct[i-1] * (1 + 0.01 * growthRate) + salary * save * 0.01)

    return yearlyAcct

def testNestEggFixed():
    salary     = 10000
    save       = 10
    growthRate = 15
    years      = 5
    savingsRecord = nestEggFixed(salary, save, growthRate, years)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995]

    # TODO: Add more test cases here.

#
# Problem 2
#

def nestEggVariable(salary, save, growthRates):

    yearlyAcct = []
    
    for growthRate in growthRates:
        if not yearlyAcct:
            yearlyAcct.append(salary * save * 0.01)
        else:
            yearlyAcct.append(yearlyAcct[-1] * (1 + 0.01 * growthRate) + salary * save * 0.01)

    return yearlyAcct

def testNestEggVariable():
    salary      = 10000
    save        = 10
    growthRates = [3, 4, 5, 0, 3]
    savingsRecord = nestEggVariable(salary, save, growthRates)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2040.0, 3142.0, 4142.0, 5266.2600000000002]

    # TODO: Add more test cases here.

#
# Problem 3
#
def postRetirement(savings, growthRates, expenses):
    """
    - savings: the initial amount of money in your savings account.
    - growthRate: a list of the annual percent increases in your investment
      account (an integer between 0 and 100).
    - expenses: the amount of money you plan to spend each year during
      retirement.
    - return: a list of your retirement account value at the end of each year.
    """
    # TODO: Your code here.
    yearlyAcct = []

    if len(growthRates) < 1:
        return []

    yearlyAcct = [savings * (1 + 0.01 * growthRates[0]) - expenses]
    for growthRate in growthRates[1:]:
        yearlyAcct.append(yearlyAcct[-1] * (1 + 0.01 * growthRate) - expenses)
    
    return yearlyAcct

def testPostRetirement():
    savings     = 100000
    growthRates = [10, 5, 0, 5, 1]
    expenses    = 30000
    savingsRecord = postRetirement(savings, growthRates, expenses)
    print savingsRecord
    # Output should have values close to:
    # [80000.000000000015, 54000.000000000015, 24000.000000000015,
    # -4799.9999999999854, -34847.999999999985]

    # TODO: Add more test cases here.

#
# Problem 4
#

def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,
                    epsilon):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - preRetireGrowthRates: a list of annual growth percentages on investments
      while you are still working.
    - postRetireGrowthRates: a list of annual growth percentages on investments
      while you are retired.
    - epsilon: an upper bound on the absolute value of the amount remaining in
      the investment fund at the end of retirement.
    """
    # TODO: Your code here.

    savings = nestEggVariable(salary, save, preRetireGrowthRates)[-1]

    minimum = 0
    maximum = savings
    expenses = (minimum + maximum)*0.5

    while not abs(postRetirement(savings, postRetireGrowthRates, expenses)[-1]) < epsilon:

        if postRetirement(savings, postRetireGrowthRates, expenses)[-1] > 0:
            minimum = expenses
            expenses = (minimum + maximum)*0.5

        elif postRetirement(savings, postRetireGrowthRates, expenses)[-1] < 0:
            maximum = expenses
            expenses = (minimum + maximum)*0.5

    return expenses
        

def testFindMaxExpenses():
    salary                = 10000
    save                  = 10
    preRetireGrowthRates  = [3, 4, 5, 0, 3]
    postRetireGrowthRates = [10, 5, 0, 5, 1]
    epsilon               = .01
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)
    print expenses
    # Output should have a value close to:
    # 1229.95548986

    # TODO: Add more test cases here.

def main():
    testFindMaxExpenses()

if __name__ == "__main__":
    main()

#Problem Set 3
#Name: Andrew
#Time: 12 hours
#Collaborators: Curious Reef

from string import *

#  target strings

target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

# key strings

key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'

#problem 1
def countSubStringMatch(target,key):
    count = 0
    for i in range(len(target)):
        if find(target,key,i) == i:
            count += 1
    return count

def countSubStringMatchRecursive (target, key):
    """ Recursively counts the number of times a term appears in a string"""
    if find(target, key) != -1:
        return 1 + countSubStringMatchRecursive(target[find(target, key)+1:], key)
    return 0

#problem 2
def subStringMatchExact(target, key):
    counts = ()
    for i in range(len(target)):
        if find(target,key,i) == i:
            counts += i,
    
    return counts

#problem 3
def constrainedMatchPair(firstMatch, secondMatch, length):
    places = ()
    for i in firstMatch:
        for j in secondMatch:
            if i + length + 1 == j:
                places += (i,)
    return places

def subStringMatchOneSub(key,target):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    print 'target:',target
    print 'key:',key
    print ''
    for miss in range(0,len(key)):
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]
        print 'breaking key','\''+key+'\'','into','key1: '+'\''+key1+'\''+' and key2: '+'\''+key2+'\''
        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)
        # when we get here, we have two tuples of start points
        # need to filter pairs to decide which are correct
        filtered = constrainedMatchPair(match1,match2,len(key1))
        print 'here is filtered:',filtered
        allAnswers = allAnswers + filtered
        print 'match1:',match1
        print 'match2:',match2
        print 'possible matches for',key1,key2,'start at',filtered
        print ''
    return allAnswers

#problem 4
def subStringMatchExactlyOneSub(key, target):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    print 'target:',target
    print 'key:',key
    print ''
    for miss in range(0,len(key)):
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]
        print 'breaking key','\''+key+'\'','into','key1: '+'\''+key1+'\''+' and key2: '+'\''+key2+'\''
        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)
        # when we get here, we have two tuples of start points
        # need to filter pairs to decide which are correct
        filtered = constrainedMatchPair(match1,match2,len(key1))
        cache = ()
        for i in filtered:
            if i not in subStringMatchExact(target,key):
                cache += i,
        del filtered
        filtered = ()
        filtered = cache
        allAnswers = allAnswers + filtered
        print 'match1:',match1
        print 'match2:',match2
        print 'possible matches for',key1,key2,'start at',filtered
        print ''
    return allAnswers
   
##if __name__ == "__main__":
##    main()

#Problem Set 2
#Name: Andrew
#Time: 3-5 hours
#Collaborators: Curious Reef

def getCombination(n): #returns a dictionary of combinations for a quantity of n chicken nuggets if you can only get them in units of 6, 9, and 20.
    numOfCombos = 0
    combos = {}
    for a in range(0, n/6 + 1):
        for b in range(0, n/9 + 1):
            for c in range(0, n/20 + 1):
                if (a*6) + (b * 9) + (c * 20) == n:
                    print "a = ",a," b = ",b, " c = ",c, " n = ", n
                    numOfCombos += 1
                    combos["a"+str(numOfCombos)] = a
                    combos["b"+str(numOfCombos)] = b
                    combos["c"+str(numOfCombos)] = c
                    combos["n"+str(numOfCombos)] = n
    return combos

def middle(v1,v2,v3): ##returns the middle value for a set of three numbers
    nums = []
    smallest = min(v1,v2,v3)
    largest = max(v1,v2,v3)

    nums = [smallest, largest]

    if not v1 in nums:
        return v1
    elif not v2 in nums:
        return v2
    else:
        return v3
    
def newGetCombo(n, v1,v2,v3): ##for problem number four. built upon the first getCombination() function.
    numOfCombos = 0
    combos = {}
    for a in range(0, n/min(v1,v2,v3) + 1):
        for b in range(0, n/middle(v1,v2,v3) + 1):
            for c in range(0, n/max(v1,v2,v3) + 1):
                if (a*v1) + (b * v2) + (c * v3) == n:
                    print "a = ",a," b = ",b, " c = ",c, " n = ", n
                    numOfCombos += 1
                    combos["a"+str(numOfCombos)] = a
                    combos["b"+str(numOfCombos)] = b
                    combos["c"+str(numOfCombos)] = c
                    combos["n"+str(numOfCombos)] = n
    return combos

def problemOne():
    for n in range(50,56):
        getCombination(n)

def problemThree():
    for i in range(1,1000):
        if len(getCombination(i)) > 0:
            for j in range(1,6):
                if len(getCombination(i+j)) > 0:
                    if j == 5:
                        print "Largest number of McNuggets that cannot be bought in exact quantity: %d" % (i-1)
                        return i-1
                else:
                    i += j+1
                    break

def problemFour():
    print "Give me three McNugget sizes: " 
    v1 = input()
    v2 = input()
    v3 = input()
    for i in range(1,150):
        if len(newGetCombo(i,v1,v2,v3)) > 0:
            for j in range(1,min(v1,v2,v3)):
                if len(newGetCombo((i+j),v1,v2,v3)) > 0:
                    if j == min(v1,v2,v3)-1:
                        print "Largest number of McNuggets that cannot be bought in exact quantity: %d" % (i-1)
                        return i-1
                else:
                    i += j+1
                    break

def main():
##    problemOne()
##    problemThree()
    problemFour()

if __name__ == "__main__":
    main()

#Andrew
#Assignment 0

first_name = raw_input("What is your first name? ")
last_name = raw_input("What is your last name? ")
print "Hello "+first_name,last_name+", nice to meet you!"