shaggorama

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

import random
import string
import time

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 = "/home/dave/Documents/python/Assignments/ps5and6/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_time_limit(points_dict, k):
    """
    Return the time limit for the computer player as a function of the
    multiplier k.
    points_dict should be the same dictionary that is created by
    get_words_to_points.
    """
    start_time = time.time()
    # Do some computation. The only purpose of the computation is so we can
    # figure out how long your computer takes to perform a known task.
    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

# (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
	"""
	score = 0
	for letter in word:
		score += SCRABBLE_LETTER_VALUES[letter]
	if len(word) == n:
		score += 50
	return score	

def get_words_to_points(word_list):
	"""
	Return a dict that maps every word in word_list to its point value.
	"""
	scores = {}
	for word in word_list:
		score = get_word_score(word, HAND_SIZE)
		scores[word] = score
	return scores

def rearrange_letters(word):
	list1 = []
	for letter in word:
		list1.append(letter)
	list1.sort()
	word = ""
	for letter in list1:
		word = word + letter
	return word

def get_word_rearrangements(word_list):
	d ={}
	for word in word_list:
		word2 = rearrange_letters(word)
		try:
			indict = d[word2]
			dict_score = get_word_score(indict, HAND_SIZE)
			new_score = get_word_score(word, HAND_SIZE)
			if new_score > dict_score:
				d[word2] = word
			else:
				continue
		except KeyError:
			d[word2] = word
	return d
#
# 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 all on the same line
            print letter,     
# function in template was an empty 'print' statement, 
# but the fucntion kept printing 'None' instead of a new line. This fixed it.	          
    return ""				

#
# 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)
	"""
	# remove letters used by word. Returns new hand minus 'word.' 
	# Does not deal new letters into hand.
	hand2 = hand.copy()	
	for letter in word:
		hand2[letter] += -1
	return hand2


#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, points_dict):
	"""
    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
	"""
	length_hand = sum(hand.values())
	if len(word) > length_hand:
		return False
	else:
		word_dict = get_frequency_dict(word)
		hand_temp = hand.copy()
		for letter in word_dict.keys():
			if letter not in hand.keys():
				return False
			else:
				hand_temp[letter] -= word_dict[letter]
				if hand_temp[letter] < 0:
					return False
		try:
			points_dict[word]
			return True
		except KeyError:
			return False

#
# Problem #4: Playing a hand
#


def pick_best_word(hand, points_dict):
	"""
    Return the highest scoring word from points_dict that can be made with the
    given hand.
    Return '.' if no words can be made with the given hand.
	"""
	best_word = ""
	best_score = 0
	for word in points_dict.keys():
		if is_valid_word(word, hand, points_dict):
			if points_dict[word] > best_score:
				best_word = word
	print best_word
	return best_word

def all_hands_sorted(hand):
	n = len(hand)
	hands = [hand]
	all_hands = build_hand(hand, hands, n)
	for hand in all_hands:
		hand.sort()
	return hands

# There has to be a better way to implement this. It's so dirty...
def build_hand(hand, hands, n):
	for letter in hand:
		hand2 = hand[:]
		hand2.remove(letter)
		if hand2 not in hands:
			hands.append(hand2)
			build_hand(hand2, hands, n-1)
		else:
			build_hand(hand2, hands, n - 1)
	return hands

def pick_best_word_faster(hand_dict, rearrange_dict):
	hand = []
	for letter in hand_dict.keys():
	        for j in range(hand_dict[letter]):
	            hand.append(letter)
	hands = all_hands_sorted(hand)
	best_word = ""
	score = 0
	for hand in hands:
		hand_string = ''
		for letter in hand:
			hand_string = hand_string + letter
		try:                        
			word = rearrange_dict[hand_string]
			new_score = get_word_score(word, HAND_SIZE)
			if new_score > score:
				best_word = word
				score = new_score
			
		except KeyError:
			continue
	print best_word
	return best_word

def play_hand(hand, points_dict, limit, plyr):
	"""
    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
	"""
	n = sum(hand.values())
	score = 0
	while True:
		if sum(hand.values()) == 0:
			print "\nFinal score: ", score
			return
		else:
			print "Current hand: ", display_hand(hand)
			start_time = time.time()
			if plyr == 'c':
				word = pick_best_word_faster(hand, rearrange_dict)
				if word == '':
					word = '.'
			else:
				word = raw_input("\nEnter word, or a . to indicate that you are finished: ")
			end_time = time.time()
			total_time = end_time - start_time
			if total_time == 0:
				total_time = 0.0001
				print "It took %.2f seconds to provide an answer." % total_time
			if limit <= total_time:
				print "Time limit exceeded."
				print "Final score: ", score
				return
			else:
				limit -= total_time
			if is_valid_word(word, hand, points_dict):
				hand = update_hand(hand, word)
				word_score = get_word_score(word, n)
				word_score_t = word_score/total_time
				score += word_score_t
				print "Word score: ", word_score
				print "Score with time penalty %.2f" % word_score_t
				print "Current score: %.2f" % score
			elif word == '.':
				print "Final score: %.2f" % score
				return
			else:
				print "Not a valid word."
			print "Time remaining: %.2f" % limit

#
# Problem #5: Playing a game
# Make sure you understand how this code works!
# 
def play_game(points_dict):
    """
    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
    k = get_time_limit(points_dict, 1)
    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 == 'e':
		break
	else:
		while True:	
			plyr = raw_input('Human player (h) or computer player (c)?')
			if (plyr == 'h') or (plyr == 'c'):
				break
			else:
				print "Invalid input."
	if plyr == 'c':
		limit = k
	else:
		limit = int(raw_input('Enter time limit (sec) for players: '))
	if cmd == 'n':
       		hand = deal_hand(HAND_SIZE)
       		play_hand(hand.copy(), points_dict, limit, plyr)
       		print
       	elif cmd == 'r':
       		play_hand(hand.copy(), points_dict, limit, plyr)
       		print
       	else:
       		print "Invalid command."

#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    word_list = load_words()
    points_dict = get_words_to_points(word_list)
    rearrange_dict = get_word_rearrangements(word_list)
    play_game(points_dict)

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

import random

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

WORDLIST_FILENAME = "/home/dave/Documents/python/Assignments/ps5/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
    word_list = []
    for line in inFile:
        word_list.append(line.strip().lower())
    print "  ", len(word_list), "words loaded."
    return word_list

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)
# -----------------------------------

# Load the dictionary of words and point to it with 
# the wordlist variable so that it can be accessed from anywhere
# in the program.
# word_list = load_words()

#def generate_letter():
#	'''Returns a random, lowercase letter'''
#	index = random.randint(0, 25)
#	char = string.lowercase[index]
#	return char

# returns true if sequence is a valid word longer than 3 characters
def is_valid_word(word, 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. DOES NOT FAIL IF word IS AN 
    INVALID WORD FRAGMENT.
    
    word: string
    hand: dictionary (string -> int)
    word_list: list of lowercase strings
	"""
	if len(word) < 4:
		return False
	elif word in word_list:
		return True
	else:
		return False

#
# returns true if input is a valid word fragment or word, else returns false. To confirm 'word' is a playable fragment, contrast result with is_valid_word()
def is_valid_fragment(fragment, word_list):
	n = len(fragment)
	for word in word_list:
		if len(word) < n:   # if 'word' is smaller than frag, skip
			continue
		for i in range(0,n):
			if word[i] == fragment[i]:   # stepwise comparison iterating by index
				if i == (n - 1):
					return True
				else:
					i += 1
					continue
			else:
				break
	return False

def update_player(player):
	if player is 1:
		player = 2
	else:
		player = 1
	return player

# tests word sequence. If valid word fragment, returns 1. If invalid word fragment, returns 2. If valid word longer than 3 characters, returns 0.
def word_test(word, word_list):
	is_word = is_valid_word(word, word_list)
	if is_word:
		return 0
	else:
		frag = is_valid_fragment(word, word_list)
		if frag:
			return 1
		else:
			return 2

def new_game(word_list):
	newgame = raw_input("Play again? (y/n)\n")
	if newgame == 'y':
		play_game(word_list)
	elif newgame == 'n':
		print "Thanks for playing!"
		return ""
	else:
		print newgame, " is not a valid option."
		new_game(word_list)
					
# Effectively plays a round. Accepts user input. converts uppercase to lower case, requests new input if not a valid character. User can input '.' to exit.
def play_char(word_list, word, player):
	print "Current word fragment: ", word
	print "\nPlayer", player, 
	char = raw_input("plays letter: ")
	if char == '.':
		print "Thanks for playing!"
		return ''
	elif char in string.letters:
		char = string.lower(char)
		word_temp = word[:] + char
		test = word_test(word_temp, word_list)
		if test == 2:
			print word_temp, " is not a valid word fragment. Please try again.\n"
			play_char(word_list, word, player)
		elif test == 0:
			print word_temp, "is a word."
			print "GAME OVER."
			new_game(word_list)
		elif test == 1:
			player = update_player(player)
			word = word_temp
			play_char(word_list, word, player)
	else:
		print char, " is not a valid character."
		play_char(word_list, word, player)
	

## initiates computers turn
## def computer_plays():
##
## initiates two player game. Prompts whether player wants to go first.
## def two_players(word_list):
##	pass
##
## initiates a single player game
## def single_player(word_list):
##	pass

# initiate game. 
# ONCE GAME IS BUILT: prompt number of players. If 1, player vs. computer. If 2, human vs. human. After each round, prompt player if they want to play again. Also, insert option to track score later on.
def play_game(word_list):
	word = ''
	player = 1
	print "Welcome to Ghost!"
	print "Player 1 goes first. Type '.' to quit round."
	play_char(word_list, word, player)


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

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

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 = "/home/dave/Documents/python/Assignments/ps5/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
	"""
	score = 0
	for letter in word:
		score += SCRABBLE_LETTER_VALUES[letter]
	if len(word) == n:
		score += 50
	return score	

#
# 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
    return ""				# function in template was an empty 'print' statement, but the fucntion kept printing 'None' instead of a new line. This fixed it.	
#    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)
	"""
	# remove letters used by word. Returns new hand minus 'word.' 
	# Does not deal new letters into hand.
	hand2 = hand.copy()	
	for letter in word:
		hand2[letter] += -1
	return hand2


#
# 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
	"""
	length_hand = sum(hand.values())
	if len(word) > length_hand:
		return False
	elif word not in word_list:
		return False
	else:	
		word_dict = get_frequency_dict(word)
		hand_temp = hand.copy()
		for letter in word_dict.keys():
			if letter not in hand.keys():
				return False
			else:
				hand_temp[letter] -= word_dict[letter]
				if hand_temp[letter] < 0:
					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
	"""
	n = sum(hand.values())
	score = 0
	while True:
		if sum(hand.values()) == 0:
			print "\nFinal score: ", score
			return
		else:
			print "Current hand: ", display_hand(hand)
			word = raw_input("\nEnter word, or a . to indicate that you are finished: ")
			if is_valid_word(word, hand, word_list):
				hand = update_hand(hand, word)
				word_score = get_word_score(word, n)
				score += word_score
				print "Word score: ", word_score
				print "Current score: ", score
			elif word == '.':
				print "Final score: ", score
				return
			else:
				print "Not a valid word."

#
# 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.
    """
    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 4

def first_N(n):
	'''Prints the first n perfect squares that are not even numbers.'''
	i = 1
	guess = 0
	while i <= n:
		guess += 1
		sq = guess*guess
		if sq%2 == 0:
			continue
		else:
			print sq
			i += 1
			
# Problem 6

def findSide():
	"""asks the user to enter the area of a rectangle and the length of one side of the
rectangle. Returns a floating point number that is the length of the adjacent side."""
	area = raw_input("Area: ")
	side = raw_input("Side: ")
	try:
		area = float(area)
		side = float(side)
	except:
		print "Input must be a number."
		findSide()
	length = area/side
	print "The length of the other side is %.2f" % length

# Problem 8

## Here is the smallest possible program based on my results
## from assignment 2:

def CanBuyMcNuggets(guess):
	possible = [6, 9, 12, 15, 18, 20, 21, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 40, 41, 42]
	if guess > 43:
		return True
	elif guess in possible:
		return True
	else:
		return False

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

def nestEggFixed(salary, save, growthRate, years):
	"""
    - 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).
    - growthRate: the annual percent increase in your investment account (an
      integer between 0 and 100).
    - years: the number of years to work.
    - return: a list whose values are the size of your retirement account at
      the end of each year.
	"""
	F = []
	F.append(salary * save * 0.01)
	year = 1
	assert type(years) == int, "Years must be an integer"
	assert type(growthRate) == int, "Growthrate must be an integer"
	assert 0 <= years < 101, "Years must be between 0 and 100"
	assert 0 <= growthRate < 101, "Growthrate must be between 0 and 100"
	if years == 0:
		return F
	while (years > year):
		F.append(F[year-1] * (1 + 0.01 * growthRate) + salary * save * 0.01)
		year += 1
	return F



def testNestEggFixed():
    salary     = 10000
    save       = 10
    growthRate = 4
    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.

# testNestEggFixed()

#
# Problem 2
#

def nestEggVariable(salary, save, growthRates):
	"""
    - 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).
    - growthRate: a list of the annual percent increases in your investment
      account (integers between 0 and 100).
    - return: a list of your retirement account value at the end of each year.
	"""
	years = len(growthRates)
	F = []
	F.append(salary * save * 0.01)
	year = 0
	if years == 0:
		return F
	else:
		while years > year:
			if year == 0:
				year += 1
			else:
				growthRate = growthRates[year]
				assert type(growthRate) == int, "Growthrate must be an integer"
				assert 0 <= growthRate < 101, "Growthrate must be between 0 and 100"
				F.append(F[year-1] * (1 + 0.01 * growthRate) + salary * save * 0.01)
				year += 1
		return F

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.

# testNestEggVariable()

#
# 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.
	"""
	years = len(growthRates)
	F = []
	year = 0
	F.append(savings * (1 + 0.01 * growthRates[year]) - expenses)
	if years == 0:		
		return F
	else:
		while years > year:
			if year == 0:
				year += 1
			else:
				growthRate = growthRates[year]
				assert type(growthRate) == int, "Growthrate must be an integer"
				assert 0 <= growthRate < 101, "Growthrate must be between 0 and 100"
				F.append(F[year-1] * (1 + 0.01 * growthRates[year]) - expenses)
				year += 1
		return F


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]

#testPostRetirement()

#
# 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.
	"""
	savings = nestEggVariable(salary, save, preRetireGrowthRates)[-1]
	high = savings + epsilon
	low = 0
	expenses = (high + low)/2
	end_balance = postRetirement(savings, postRetireGrowthRates, expenses)[-1]
	while abs(end_balance) > epsilon:
		if end_balance < 0:	
			high = expenses
		else:
			low = expenses
		expenses = (high + low)/2
		end_balance = postRetirement(savings, postRetireGrowthRates, expenses)[-1]
		print end_balance	
	return expenses



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

testFindMaxExpenses()

#! /usr/bin/env python
# -*- coding: utf8 -*-

# these are some example strings for use in testing your code

#  target strings

target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

targets = (target1, target2)

# key strings

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

keys = (key10, key11, key12, key13)

### the following procedure you will use in Problem 3

def subStringMatchOneSub(key,target):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    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,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))
        allAnswers = allAnswers + filtered
        ##print 'match1',match1
        ##print 'match2',match2
        ##print 'possible matches for',key1,key2,'start at',filtered
    return allAnswers

#######################################################################

## PROBLEM 1

from string import *

def countSubStringMatch(target,key):
	counter = [-1]
	tryrange = range(0, len(target) + 1)
	for x in tryrange:
		location = find(target, key, x) 
		if location not in counter:
			counter.append(location)
	if counter == -1:
		return 0
	else:
		counter.remove(-1)		
		return len(counter)

def helpcountSubStringMatchRecursive(target, key, incr, counter):
	position = find(target, key, incr)
	incr += 1	
	if position not in counter:
		counter.append(position)
		helpcountSubStringMatchRecursive(target, key, incr, counter)
	if incr -1 >= len(target):
		return counter
	else:
		helpcountSubStringMatchRecursive(target, key, incr, counter)

def countSubStringMatchRecursive(target, key):
	counter = [-1] 
	helpcountSubStringMatchRecursive(target, key, 0, counter)
	counter.remove(-1)
	return len(counter)

## PROBLEM 2

def subStringMatchExact(target,key):
	counter = [-1]
	tryrange = range(0, len(target) + 1)
	for x in tryrange:
		location = find(target, key, x) 
		if location not in counter:
			counter.append(location)
	if counter == -1:
		return 0
	else:
		counter.remove(-1)	
		return tuple(counter)

## PROBLEM 3

def constrainedMatchPair(firstMatch, secondMatch, length):
	matches = []
	for n in firstMatch:
		for k in secondMatch:
			m = length			
			if n + m + 1 == k:
				matches.append(n)
	return tuple(matches)


## PROBLEM 4

def subStringMatchExactlyOneSub(target,key):
	exact = subStringMatchExact(target,key)	
	close = subStringMatchOneSub(key,target)
	onesub = []
	for index in close:
		if index not in exact:
			onesub.append(index)
	return tuple(onesub)

##TEST FUNCTION
for target in targets:
	for key in keys:
		print "\nTarget: ", target
		print "Key: ", key		
		print subStringMatchExactlyOneSub(target, key)

#! /usr/bin/env python
# -*- coding: utf8 -*-
## (i'm using linux now. Much easier. For the uninitiated: the 
## above invokes python in a terminal window to interpret the 
## script file I write my code in.)

# Problem 2
## If you can buy x, x+ 1... x + 5,
## adding 6 to your previous values will get the next numbers in the sequence. 
## Therefore, if you can find solutions for 6 in a row, then you can find solutions
## for aall greater values of x.

# Problem 3

## maxval(box, guess) finds the largest feasible number
## of boxes worth trying for a given guess. This will later be 
## converted into a range. In retrospect, this function could 
## just as well have returned the range.

def maxval(box, guess):
	counter = 0
	x = 0
	while x <= guess:
		counter += 1
		x += box
	if counter > 1:	
		return counter
	else:
		return 1

## The code below "return False" is the workhorse of solving this
## problem. As the code finds solutions to the equation 6a + 9b 
## +20c, it stores them in the list 'solutions.' 
## sixconsecutive(list, value) appends the value to the list if it's ## not there already, then checks to see if there are 6 consecutive ## values in a row. If not, the function returns 'False.' If yes, the 
## function returns "True," which will return a solution below.

def sixconsecutive(placeholder, newitem):
	if newitem not in placeholder:
		placeholder.append(newitem)
	if (len(placeholder) >= 6) and (placeholder[-1] - placeholder[-6] == 5):
		return True
	else:
		return False

##initializing some variables
guess = 0
solutions = []
solution = False
while solution == False:
	guess += 1
	# generating ranges to test
	ma = maxval(6, guess)
	mb = maxval(9, guess)
	mc = maxval(20, guess)
	Arange = range(0, ma)
	Brange = range(0, mb)
	Crange = range(0, mc)
	for a in Arange:
		for b in Brange:
			for c in Crange:
				if (6*a + 9*b + 20*c) == guess:
					print guess, solutions, a, b, c
					solution = sixconsecutive(solutions, guess)				
print "Largest number of McNuggets that cannot be bought in exact quantity: ", guess - 6

# Problem 4

a = int(raw_input("a: "))
b = int(raw_input("b: "))
c = int(raw_input("c: "))
packages = (a, b, c)
smallest = min(packages)

# Used the exact same strategy from problem 3 and most of the same code. Basically, I just replaced 6, 9, and 20 with the values given by 'packages,' and replaced '6' with min(packages) where appropriate.

def maxconsecutive(placeholder, newitem):
	if newitem not in placeholder:
		placeholder.append(newitem)
	if (len(placeholder) >= smallest) and (placeholder[-1] - placeholder[-smallest] == smallest -1):
		return True
	else:
		return False

guess = 0
solutions = []
solution = False
p = packages[0]
q = packages[1]
r = packages[2]
while solution == False:
	guess += 1
	ma = maxval(p, guess)
	mb = maxval(q, guess)
	mc = maxval(r, guess)
	Arange = range(0, ma)
	Brange = range(0, mb)
	Crange = range(0, mc)
	for a in Arange:
		for b in Brange:
			for c in Crange:
				if (p*a + q*b + r*c) == guess:
					print guess, solutions, a, b, c
					solution = maxconsecutive(solutions, guess)				
print "Largest number of McNuggets that cannot be bought in exact quantity: ", guess - smallest

primes = [2]

## factor(n) returns a list of the factors of n
def factor(n):
    factors = []
    factorcandidate = n + 1
    while factorcandidate > 3:
        factorcandidate = factorcandidate - 1
        if n%factorcandidate == 0:
            factors.append(factorcandidate)            
    return factors

## findprimes(x) takes a list (of factors) and identifes which 
## elements in the list are primes, then appends them to the list 
## 'primes' if they are not already elements.
def findprimes(factors):
    for f in factors:
        if f not in primes:
            factorable = 0
            for p in primes:
                if f%p == 0:
                    factorable = factorable + 1
            if factorable == 0:
                primes.append(f)
                primes.sort()

## nprime(n) returns the nth-prime number. In the process, all the 
## primes from 1 to nprime(n) are generated and stored in the list 
## 'primes' in ascending order.
def nprime(n):
    counter = 1
    if len(primes) >= n:
        return primes[n-1]
    else:
        while len(primes) < n:
            counter = counter + 2
            findprimes(factor(counter))
    return primes[n-1]

#PROBLEM 2

from math import *

#Generatest the primes up to a number n. Includes the number n if n is prime.
def generateprimes(n):
    counter = 2
    if n < counter:
        return primes
    else:
        while counter <= n - 1:
            counter = counter + 1
            findprimes(factor(counter))
    return primes

## returns a list of primes up to (and including) a number n.
def smallerprimes(n):
    generateprimes(n)
    listprimes = []
    for x in primes:
        if x <= n:
            listprimes.append(x)
    return listprimes

## takes a number n and feeds it to smallerprimes() to generate the list of primes to sum for building the ratio. 
def primeratio(n):
    listofprimes = smallerprimes(n)
    logs = []
    for prime in listofprimes:
        logs.append(log(prime))
    logofprimes = sum(logs)
    ratio = logofprimes/n
    print "Sum of logs of primes = ", logofprimes
    print "n = ", n
    print "ratio of logs/n = ", ratio

; Ex. 1.3.

(define (exerc3) 
	(lambda (a b c) 
		(define (square z) (z*z))
		(cond 
			(and (< c a) (< c b)) (+ (square a) (square b))
			(and (< b a) (< b c)) (+ (square a) (square c))
			(else (+ (square b) (square c)))
		)
		
	)
)		




; Ex. 1.8

(define (cbrt-iter guess x)
	(if (cbrt-good-enough? guess x)
		guess
		(cbrt-iter (cbrt-improve guess x)
			x)))

(define (cbrt-improve guess x)
	(avg guess (/ (+ (* guess 2) (/ x (square guess))) 3)))

(define (avg x y)
	(/ (+ x y) 2))

(define (square x) (* x x))

(define (cube x) (* x x x)

(define (cbrt-good-enough? guess x)
	(< (abs (- (cube guess) x)) 0.001)))

(define (cbrt x)
	(cbrt-iter 1.0 x))