Bi-sectional Search

As part of the MIT introduction to Python course, we wrote code that would help calculate the fixed monthly payment we would need to make on a credit card over a 12 month period with a fixed interest rate and starting balance. To speed up the calculation and zero in on the answer faster, we used the concept of bi-sectional search.

Bi-sectional search works by essentially making a series of guesses and checking if they are either too high or too low. If too high, all values above that are thrown out and the set shrinks by half. If too low, the same process is done but with all values below.

Sample code:

monthlyInterestRate = (annualInterestRate / 12)
low = balance / 12
high = (balance * (1 + monthlyInterestRate)**12)/12
t_balance = balance
payment = low

while t_balance != range(-1,1):
    months = 0
    temp_balance = balance
    while months <= 12:
        if months == 0:
            unpaid = temp_balance - payment
        else:
            temp_balance = unpaid + (unpaid * (annualInterestRate/12))
            unpaid = temp_balance - payment
        months += 1
    t_balance = temp_balance
    if int(temp_balance) in range(-1,1):
        break
    if temp_balance > 0:
        low = payment
        payment = high - (high - low)/2
    else:
        high = payment
        payment = (low + ((high - low)/2))
    
print(round(payment,2))

Hangman game

In this Python function, we wrote a simple game of hangman.

Once you pass in a “secret word” then the player (who is hopefully not also the programmer) can make guesses about the letters in the word. The exercise used to get us more familiar with while loops and the use of if & else clauses.

Sample code:

def hangman(secretWord):
    '''
    secretWord: string, the secret word to guess.

    Starts up an interactive game of Hangman.

    * At the start of the game, let the user know how many 
      letters the secretWord contains.

    * Ask the user to supply one guess (i.e. letter) per round.

    * The user should receive feedback immediately after each guess 
      about whether their guess appears in the computers word.

    * After each round, you should also display to the user the 
      partially guessed word so far, as well as letters that the 
      user has not yet guessed.

    Follows the other limitations detailed in the problem write-up.
    '''
    print('Welcome to the game Hangman!')
    print('I am thinking of a word that is ', len(secretWord),' letters long.')
    numbguess = 8
    lettersguessed = []
    while numbguess > 0:
        if isWordGuessed(secretWord, lettersguessed) == True:
            break
        print('-------------')
        print('You have ', numbguess,' guesses left.')
        print('Available letters: ', getAvailableLetters(lettersguessed))
        guess = input('Please guess a letter: ')
        if guess in lettersguessed:
            print("Oops! You've already guessed that letter: ", getGuessedWord(secretWord,lettersguessed))
        elif guess in secretWord:
            lettersguessed += guess
            print("Good guess: ", getGuessedWord(secretWord,lettersguessed))
        else:
            lettersguessed += guess
            numbguess -= 1
            print('Oops! That letter is not in my word: ', getGuessedWord(secretWord,lettersguessed))
    if isWordGuessed(secretWord, lettersguessed) == False:
        print('-------------')
        print("Sorry, you ran out of guesses. The word was",secretWord)
    else:
        print('-------------')
        print("Congratulations, you won!")

Words with friends game

In this session we created a series of functions to play a words with friends or Scrabble type game.

The player was issued a hand of letters and had to try to spell out words. As a part of the game, we wrote a function to check the word submitted to ensure it was valid. We also wrote a function to score the word, breaking the string down into component pieces and running them through a dictionary where each letter was associated with a certain number of points. Lastly we also created functions to help us deal new hands and start new games.

Sample code for scoring:

def getWordScore(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, multiplied by the length of the word, PLUS 50 points if all n
    letters are used on the first turn.

    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 (see SCRABBLE_LETTER_VALUES)

    word: string (lowercase letters)
    n: integer (HAND_SIZE; i.e., hand size required for additional points)
    returns: int >= 0
    """
    score = 0 
    for let in range(len(word)):
        score += SCRABBLE_LETTER_VALUES.get(word[let])
    score *= len(word)
    if len(word) == n:
        score += 50
        return score
    else:
        return score

Basic encryption

Using classes and functions, we were able to create a way to encrypt and decode information.

We created a ~very~ sophisticated encryption system that shifted all the letters in a message by one in order to make it hard to understand what was being written.

Sample code:

class Message(object):
    def __init__(self, text):
        '''
        Initializes a Message object
                
        text (string): the message's text

        a Message object has two attributes:
            self.message_text (string, determined by input text)
            self.valid_words (list, determined using helper function load_words
        '''
        self.message_text = text
        self.valid_words = load_words(WORDLIST_FILENAME)

    def get_message_text(self):
        '''
        Used to safely access self.message_text outside of the class
        
        Returns: self.message_text
        '''
        return self.message_text

    def get_valid_words(self):
        '''
        Used to safely access a copy of self.valid_words outside of the class
        
        Returns: a COPY of self.valid_words
        '''
        return self.valid_words[:]
        
    def build_shift_dict(self, shift):
        '''
        Creates a dictionary that can be used to apply a cipher to a letter.
        The dictionary maps every uppercase and lowercase letter to a
        character shifted down the alphabet by the input shift. The dictionary
        should have 52 keys of all the uppercase letters and all the lowercase
        letters only.        
        
        shift (integer): the amount by which to shift every letter of the 
        alphabet. 0 <= shift < 26

        Returns: a dictionary mapping a letter (string) to 
                 another letter (string). 
        '''
        lets = "abcdefghijklmnopqrstuvwxyz"
        upperlets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        self.encrypting_dict = {}
        n = 1
        for let in lets:
            ind = n+shift
            while ind > 26:
                ind -= 26 
            self.encrypting_dict[let] = lets[ind-1]
            n += 1
        
        n = 1
        for let in upperlets:
            ind = n+shift
            while ind > 26:
                ind -= 26 
            self.encrypting_dict[let] = upperlets[ind-1]
            n += 1        
        return self.encrypting_dict

    def apply_shift(self, shift):
        '''
        Applies the Caesar Cipher to self.message_text with the input shift.
        Creates a new string that is self.message_text shifted down the
        alphabet by some number of characters determined by the input shift        
        
        shift (integer): the shift with which to encrypt the message.
        0 <= shift < 26

        Returns: the message text (string) in which every character is shifted
             down the alphabet by the input shift
        '''
        self.message_text_encrypted = ''
        encr = self.build_shift_dict(shift)
        for let in self.message_text:
            try:
                self.message_text_encrypted += encr.get(let) 
            except:
                self.message_text_encrypted += let
        return self.message_text_encrypted

Python Scripts

Bi-sectional Search

Bi-sectional search works by essentially making a series of guesses and checking if they are either too high or too low. If too high, all values above that are thrown out and the set shrinks by half. If too low, the same process is done but with all values below.

Sample code:

Hangman game

In this Python function, we wrote a simple game of hangman.

Once you pass in a “secret word” then the player (who is hopefully not also the programmer) can make guesses about the letters in the word. The exercise used to get us more familiar with while loops and the use of if & else clauses.

Sample code:

Words with friends game

In this session we created a series of functions to play a words with friends or Scrabble type game.

Sample code for scoring:

Basic encryption

Using classes and functions, we were able to create a way to encrypt and decode information.

We created a ~very~ sophisticated encryption system that shifted all the letters in a message by one in order to make it hard to understand what was being written.

Sample code: