0

Merge Sort

With recursion, it is simple:

def merge(L1, L2):
    """
    Function to merge two sorted lists into one sorted one.
    Returns a new list that contains both elements of L1 and L2 in sorted order
    """
    i=0
    j=0
    mergedList = []
    
    while i < len(L1) and j < len(L2):
        if L1[i] < L2[j]:
            mergedList.append(L1[i])
            i += 1
        else:
            mergedList.append(L2[j])
            j += 1

    while i < len(L1):
        mergedList.append(L1[i])
        i += 1

    while j < len(L2):
        mergedList.append(L2[j])
        j += 1

    return mergedList
    
def mergeSort(L):
    """
    Function to sort the elements of the list using merge sort.
    Does not sort the list in place, but instead returns a new list which
    is sorted.
    """
    if len(L) < 2:
        # an empty list or a list of one element is already sorted!
        return L
    mid = len(L)/2
    L1 = mergeSort(L[0:mid])
    L2 = mergeSort(L[mid:])
    mergedList = merge(L1, L2)
    return mergedList
Advertisements
0

Insert New Lines

With recursion, thinking is simple:

def insertNewlines(text, lineLength):
    """
    Given text and a desired line length, wrap the text as a typewriter would.
    Insert a newline character ("\n") after each word that reaches or exceeds
    the desired line length.

    text: a string containing the text to wrap.
    line_length: the number of characters to include on a line before wrapping
        the next word.
    returns: a string, with newline characters inserted appropriately. 
    """
    if len(text) <= lineLength:
        return text
    elif text[lineLength - 1] == ' ':
        return text[:lineLength] + "\n" + insertNewlines(text[lineLength:], lineLength)
    else:
        spaceAt = text[lineLength:].find(' ')
        return text[:spaceAt+lineLength] + "\n" + insertNewlines(text[lineLength+spaceAt+1:], lineLength)

0

Find Whether a word is x_ian

With recursion, thinking is very simple:

def x_ian(x, word):
    """
    Given a string x, returns True if all the letters in x are
    contained in word in the same order as they appear in x.

    >>> x_ian('eric', 'meritocracy')
    True
    >>> x_ian('eric', 'cerium')
    False
    >>> x_ian('john', 'mahjong')
    False
    
    x: a string
    word: a string
    returns: True if word is x_ian, False otherwise
    """
    if len(x) == 0:
        return True
    idx = word.find(x[0])
    if idx == -1:
        return False
    else:
        return x_ian(x[1:], word[idx+1:])
0

My Python Version of Selection Sort

def mySelectSort(L):
    """
    sorts the elements of the list using selection sort
    """
    def myRecurSelectiveSort(L, cur):
        if cur == len(L) -  1:
            return
        
        minIdx = cur
        for i in range(cur+1, len(L)):
            if L[i] < L[minIdx]:
                minIdx = i

        if minIdx != cur:
            tmp = L[cur]
            L[cur] = L[minIdx]
            L[minIdx] = tmp

        myRecurSelectiveSort(L, cur+1)

    myRecurSelectiveSort(L, 0)
            
0

On Binary Search

I was just trying to execute this code snippet for binary search:

def search(L, e):
    def binarySearch(L, e, low, high):
        if (low == high):
            return L[low] == e
        mid = low + int((high-low)/2)
        if L[mid] == e:
            return True
        if L[mid] > e:
            return binarySearch(L, e, low, mid - 1)
        else:
            return binarySearch(L, e, mid + 1, high)

    if len(L) == 0:
        return False
    else:
        return binarySearch(L, e, 0, len(L) - 1)

For elements that are in the list, this code works fine, but for the elements that are not in the list, this goes on for a toss. The reason is that depending on the element being left of low or right of high, mid will reach low or high respectively eventually. Once it reaches that point, for the first case, mid – 1 will be -1. And the problem is (-1/2) in python is, for some unknown reason, -1 and not 0. So, mid will also be -1 in the current run and in the next pass mid will be -2. Given that -2/2 is also -1, we are stuck with the same values of low, mid and high from there on.

The fix is to keep this small check when calling the recursive function:

def search(L, e):
    def binarySearch(L, e, low, high):
        print "(%d, %d)" % (low, high)
        if (low == high):
            return L[low] == e
        mid = (low + high)/2
        if L[mid] == e:
            return True
        if L[mid] > e:
            return binarySearch(L, e, low, max(low, mid - 1))
        else:
            return binarySearch(L, e, min(mid + 1, high), high)

    if len(L) == 0:
        return False
    else:
        return binarySearch(L, e, 0, len(L) - 1)

When passing mid, we keep a check.

0

Scrabble

Here is the scrabble program:

#
# Problem #1: Scoring a word
#
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 i in word:
        score += SCRABBLE_LETTER_VALUES[i]

    score = score * len(word)

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

    return score



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

    For example:
    >>> displayHand({'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

#
# Problem #2: Make sure you understand how this function works and what it does!
#
def dealHand(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={}
    numVowels = n / 3
    
    for i in range(numVowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]
        hand[x] = hand.get(x, 0) + 1
        
    for i in range(numVowels, 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 updateHand(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 modify hand.

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

    # dictionary, contains the hand after dealing with the word
    modifiedHand = hand.copy()
    for i in word:
        modifiedHand[i] = modifiedHand[i] - 1
   
    return modifiedHand



#
# Problem #3: Test word validity
#
def isValidWord(word, hand, wordList):
    """
    Returns True if word is in the wordList and is entirely
    composed of letters in the hand. Otherwise, returns False.

    Does not mutate hand or wordList.
   
    word: string
    hand: dictionary (string -> int)
    wordList: list of lowercase strings
    """
    if word not in wordList:
        return False

    wordDict = getFrequencyDict(word)
    
    for i in wordDict.keys():
        if wordDict[i] > hand.get(i, 0):
            return False

    return True
    


#
# Problem #4: Playing a hand
#

def calculateHandlen(hand):
    """ 
    Returns the length (number of letters) in the current hand.
    
    hand: dictionary (string-> int)
    returns: integer
    """
    return sum(hand.values())
    



def playHand(hand, wordList, n):
    """
    Allows the user to play the given hand, as follows:

    * The hand is displayed.
    * The user may input a word or a single period (the string ".") 
      to indicate they're done playing
    * Invalid words are rejected, and a message is displayed asking
      the user to choose another word until they enter a valid word or "."
    * 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 or the user
      inputs a "."

      hand: dictionary (string -> int)
      wordList: list of lowercase strings
      n: integer (HAND_SIZE; i.e., hand size required for additional points)
      
    """
    
    # Keep track of the total score
    totalScore = 0
    
    # As long as there are still letters left in the hand:
    while calculateHandlen(hand) > 0:
        # Display the hand
        displayHand(hand)        
        # Ask user for input
        input = raw_input('Enter word, or a "." to indicate that you are finished: ')
        # If the input is a single period:
        if input == '.':
            # End the game (break out of the loop)
            break
        # Otherwise (the input is not a single period):
        elif not isValidWord(input, hand, wordList):
            # If the word is not valid:
            # Reject invalid word (print a message followed by a blank line)
            print "That is not a valid word. Please choose another word"
        # Otherwise (the word is valid):
        else:
            currentWordScore = getWordScore(input, n)
            totalScore += currentWordScore
            # Tell the user how many points the word earned, and the updated total score, in one line followed by a blank line
            print '"%s" earned %d points. Total: %d points' % (input, currentWordScore, totalScore)
            # Update the hand 
            hand = updateHand(hand, input)           
    # Game is over (user entered a '.' or ran out of letters), so tell user the total score
    print "Total score: %d points." % totalScore

#
# Problem #5: Playing a game
# 

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

    1) Asks the user to input 'n' or 'r' or 'e'.
      * If the user inputs 'n', let the user play a new (random) hand.
      * 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, tell them their input was invalid.
 
    2) When done playing the hand, repeat from step 1    
    """
    currentHand = {}
    while 1:
        key = raw_input("Enter n to deal a new hand, r to replay the last hand, or e to end game:")
        key = key.lower()
        if key == 'e':
            break
        elif key == 'n':
            currentHand = dealHand(HAND_SIZE)
            playHand(currentHand, wordList, HAND_SIZE)
        elif key == 'r':
            playHand(currentHand, wordList, HAND_SIZE)
        else:
            print "Invalid input, try again"
        

#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    wordList = loadWords()
    playHand({'n':1, 'e':1, 't':1, 'a':1, 'r':1, 'i':2}, wordList, 7)
    playGame(wordList)

0

Hangman

Here is the python version of the hangman, one of the problem sets in the edX course:

# Load the list of words into the variable wordlist
# so that it can be accessed from anywhere in the program
wordlist = loadWords()

def isWordGuessed(secretWord, lettersGuessed):
    '''
    secretWord: string, the word the user is guessing
    lettersGuessed: list, what letters have been guessed so far
    returns: boolean, True if all the letters of secretWord are in lettersGuessed;
      False otherwise
    '''
    # FILL IN YOUR CODE HERE...
    for i in secretWord:
        if i not in lettersGuessed:
            return False

    return True
            



def getGuessedWord(secretWord, lettersGuessed):
    '''
    secretWord: string, the word the user is guessing
    lettersGuessed: list, what letters have been guessed so far
    returns: string, comprised of letters and underscores that represents
      what letters in secretWord have been guessed so far.
    '''
    # FILL IN YOUR CODE HERE...
    guessedWord = ""
    for i in secretWord:
        if i in lettersGuessed:
            guessedWord += i
        else:
            guessedWord += " _ "

    return guessedWord



def getAvailableLetters(lettersGuessed):
    '''
    lettersGuessed: list, what letters have been guessed so far
    returns: string, comprised of letters that represents what letters have not
      yet been guessed.
    '''
    # FILL IN YOUR CODE HERE...
    availableLetters=""
    for i in "abcdefghijklmnopqrstuvwxyz":
        if i not in lettersGuessed:
            availableLetters += i

    return availableLetters
    

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.
    '''
    # FILL IN YOUR CODE HERE...
    wordLen = len(secretWord)
    numGuesses = 8
    guessedLetters = ""
    
    print "Welcome to the game, Hangman!"
    print "I am thinking of a word that is " + str(wordLen) + " letters long"
    
    while numGuesses > 0:
        availableLetters = getAvailableLetters(guessedLetters)
        print "-------------"
        if isWordGuessed(secretWord, guessedLetters):
            print "Congratulations, you won!"
            break
        print "You have %d guesses left." % numGuesses
        print "Available letters: " + availableLetters
        guess = raw_input("Please guess a letter: ")
        if len(guess) > 1:
            print "Please enter only one letter"
            continue
        guess = guess.lower()
        if guess not in availableLetters:
            print "Oops! You've already guessed that letter: " + getGuessedWord(secretWord, guessedLetters)
        elif guess in secretWord:
            guessedLetters = guessedLetters + guess
            print "Good Guess: " + getGuessedWord(secretWord, guessedLetters)
        else:
            guessedLetters = guessedLetters + guess
            print "Oops! That letter is not in my word: " + getGuessedWord(secretWord, guessedLetters)
            numGuesses -= 1

    if numGuesses == 0:
        print "Sorry, you ran out of guesses. The word was " + secretWord


# When you've completed your hangman function, uncomment these two lines
# and run this file to test! (hint: you might want to pick your own
# secretWord while you're testing)

secretWord = chooseWord(wordlist).lower()
hangman(secretWord)