Selection Sort—Python

Selection sorts are a very common method of sorting. Here is a selection sort that is implemented in Python.

def selection_sort(items):
    for i in range(len(items) - 1):
        # Assume that the smallest item is located at index i
        smallest = i

        # Now loop through the rest of the list
        for j in range(i + 1, len(items)):
            # Is our item at index j smaller than our smallest item?
            if items[j] < items[smallest]:
                smallest = j

        #  Now swap elements to perform the sort
        temp = items[smallest]
        items[smallest] = items[i]
        items[i] = temp

if __name__ == '__main__':
    items = ['Bob Belcher', 'Linda Belcher', 'Gene Belcher', 'Tina Belcher', 'Louise Belcher']
    print(items, '\n')

    print('Sorting...')
    selection_sort(items)
    print(items)

Selection sorts use nested loops to iterate over a list. We check if the item at index j is less than the current smallest item. If j is smaller than smaller, we assign smaller to j.

Once we complete the nested loop, we can perform a swap. Our driver program demonstrates this with strings, but thanks to Python's duck typing system, this will sort any object that implements __lt__.

When run, we get this output

['Bob Belcher', 'Linda Belcher', 'Gene Belcher', 'Tina Belcher', 'Louise Belcher'] 

Sorting...
['Bob Belcher', 'Gene Belcher', 'Linda Belcher', 'Louise Belcher', 'Tina Belcher']
Advertisements

Bubble Sort—Java

The bubble sort is a very common algorithm that many computer science students are expected to learn. Yesterday I did a post that shows a Python implementation of the bubble sort which you can view here. Today I will demonstrate the same technique in Java.

import java.util.Arrays;

public class BubbleSort {

public static void main(String [] args){
Integer [] nums = {9, 4, 2, 1, 10};
System.out.println("Unsorted is " + Arrays.toString(nums));

bubbleSort(nums);
System.out.println("Sorted is " + Arrays.toString(nums));
}

public static<T extends Comparable> void bubbleSort(T [] array){
int n = array.length;
T temp;

for(int i = 0; i < n; i++){
for (int j = 1; j  0){
//Swap the elements
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
}
}

Java is a little more verbose than Python. Since it is a statically typed language (which means you have to declare the data type up front, as opposed to Python’s duck typing method), I chose to use generics to implement this sort.

Generics were introduced in JDK 1.5. They allow us to write code that is widely applicable to many types of objects without forcing us to use the Object class. You can find a wide use of generics in the java.util package.

In this case, I declared my generic method like this

public static<T extends Comparable> void bubbleSort(T [] array){

Let’s go through this one word at a time.

  1. public—This is the keyword that makes this method publically available
  2. static—This keyword attaches this method to the class rather than an object
  3. <T extends Comparable>—This is the code that declares this method to be a generic method. T is the type of the object, followed by extends Comparable which means that any object that implements the Comparable interface is accetable to this method.
  4. T [] array—This declares an array of type T (which is any class that implements Comparable in this case)

Now that we have declared this to be a generic method, this method will work with any object that implements the Comparable interface. The Comparable interface is widely used throughout Java in sorting. It declares a compareTo(T obj) method which returns a positive number when an item is greater than the comparing object, zero when the two objects are equal, and a negative number when the comparing object is less than the other object.

Since this interface exists, Java lets us sort anything that implements this interface easily. That allows programmers a high degree of freedom and flexibility when creating custom classes because the programmer gets to decide how one object is greater than, less than, or equal to another object.

We apply the Comparable interface to this bubble sort method here

if(array[j - 1].compareTo(array[j]) > 0){
//Swap the elements
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}

If the left hand portion array[j - 1].compareTo(array[j]) is 0, then these two items are 0. If the result is a negative number then array[j - 1] is less than array[j], otherwise array[j - 1] is greater than array[j] and it needs to get swapped.

When run, we get this output

Unsorted is [9, 4, 2, 1, 10]
Sorted is [1, 2, 4, 9, 10]

Python Jeopardy (Part 1)

Introduction

Once upon a time, I was tutoring a student who had taken an introduction to Java course who had a unique course project. The student’s job was to build an implementation of Jeopardy throughout the course. At the beginning, they would start simple with a basic program that read user input from the console. At the end of the semester, they had a full fledged GUI program that communicated over network sockets, communicated with a database, and even had multi-threading.

I loved this project because it literally covered every possible programming topic outside of web programming. This student had to learn out how read and react to user input from both the GUI and the console. The requirements of the program required them how to learn to read from a file. There was plenty of opportunity to learn Object Orientated Programming (OOP). I was so impressed with the material that was covered with this project that I asked the student to share the assignments with me when the semester was over. Thankfully, the student agreed!

Python Jeopardy

This is the beginning of a series of posts where we will recreate the Jeopardy program using the Python language. Our first task is to start by creating a plain text file that will contain our Jeopardy game board. Here is an excerpt of the file.

Earthquakes::Jeoportmanteau!::Ashes to Ashes::Dust To Dust::"K" Mart
400::800::1200::1600::2000
Earthquakes::400::This well-known fault is considered the main boundary between the North American & Pacific plates::the San Andreas Fault
...
FJ::Last name of Sir Clifford, whose crippling war injuries make life difficult for his wife::Chatterley

The first line of the input file lists our categories in our game of Jeopardy. Since it’s common to use commas in Jeopardy questions, we use :: to seperate each of our categories. Our requirements state that we have to have five categories or the file is invalid.

The next line of the file lists all of the possible point values. Like the categories line, we use :: to seperate each point. There have to be five points and they must be whole numbers.

The next twenty-six lines contain the questions for the game of Jeopardy. We start with the question’s category, followed by it’s point value. After the points we have the question (or the answer, depending how you wish to view it). and then finally we have the question’s answer. Our requirements state that we have to have 25 questions.

However we have a special question that can appear anywhere in this file exception for the first two lines. This is the final Jeopardy question. This line starts with FJ and the program needs to respond correctly when it sees the final jeopardy question. An example of the final jeopardy line is found on the last line of our example.

Implementation

Python supports object orientated programming, which lets us model components in the system as objects. At this point, we have two objects in our system. Our first kind of an object is our standard question. Let’s begin by making a class that models this component.

GameTile

class GameTile:
    def __init__(self, category='', points=0, question='', answer=''):
        self.category = category  # The question category
        self.points = points  # The point value of this question
        self.question = question  # The question
        self.answer = answer  # The answer

    def __str__(self):  # This method creates a string representation of this object
        # Let's store all of our properties in a dict object
        result = {'category': self.category,
                  'points': self.points,
                  'question': self.question,
                  'answer': self.answer}

        # Now we can convert the dict to a string which will give us friendly formatting
        return str(result)

    def __repr__(self):  
        # This method also creates a String representation of a Python object
        # The Python debugger calls this method rather than __str__
        # But we can just reuse our code by calling __str__
        return self.__str__()

So this is our first Python class of this project. One thing users who are familiar with other languages such as Java may notice is that none of the properties of this class are encapsulated. This may seem odd but keep in mind that Python is about readability and conciseness. We certianly could use Python’s psuedo-private techniques and then add getters and setters, but doing so will simply bloat the code.

At this point, we don’t have a lot of behavior in this class. This class defines a constructor (__init__) and it overrides the __str__ and __repr__ methods to provide us with string representations of this object. In __str__, we store all of our properties in a Python dict variable and then use str() to convert it to a String. __repr__ just simply uses the code in __str__ so that we can get String representations in the console.

Here is the next class in our script that represents the Final Jeopardy question.

FinalJeopardyTile

class FinalJeopardyTile:
    def __init__(self, question='', answer=''):
        self.question = question
        self.answer = answer

    def __str__(self):
        result = {'question': self.question, 'answer': self.answer}
        return str(result)

    def __repr__(self):
        return self.__str__()

Once again, we haven’t added much in terms of behavior in this class. That will come later. However both GameTile and FinalJeopardy serve a useful purpose in that we are grouping related information together into a single entity. Later on, we can add behavior to these classes to work on the data.

Now we have to process our game file and create these objects. Python is a lot like C++ in that we don’t have put our code exclusively in class. At this point in the project, reading the game file isn’t the job of any one particular class so we are going to define a module level function that does the job of reading the file and will return a dict of questions.

Reading the Game File

Here is enter readGameBoard function. Don’t get overwhelmed by the size of it because we are going to break it up into sections and explain each portion.

# These are custom exceptions that we are going to use.
class InvalidGameFile(Exception):
    pass


class IllegalCategoryCount(Exception):
    pass


class IllegalPointsCount(Exception):
    pass

def readGameBoard(gameFile):
    # Read the entire file into memory
    rawLines = open(gameFile, 'r').readlines()

    # Check that we have 28 lines in the game file
    if len(rawLines) != 28:
        # Throw our custom exception to indicate the file is invalid
        raise InvalidGameFile

    # Now this is going to store our files
    fileLines = []
    for line in rawLines:  # Iterate through rawLines one item at a time
        # Now we need to remove any '\n' characters and store them in fileLines
        fileLines.append(line.strip())

    points = []  # Store the points to validate the file later
    gameTiles = {}  # Store all of the questions here

    # There has to be 5 unique categories
    # We are going to split the first line apart by the :: character
    categories = fileLines[0].split('::')

    # Now check that we have 5 unique categories. We use the set() function that
    # will remove any duplicates and then we are going to check the length. It has to be
    # 5 per the requirements
    if len(set(categories)) != 5:
        raise IllegalCategoryCount  # Raise one of our custom exceptions

    # There has to be 5 unique points
    # So now we read the second line and split it one our :: character
    pointValues = fileLines[1].split('::')

    # Now, we have Strings in pointValues, but we need them to be integers
    # So we iterate through pointValues and convert each item to an int
    # before storing it in points. We use the int() function to do the conversion
    for pv in pointValues:
        points.append(int(pv))

    # Now once again, we need to for 5 unique points so we use set again to remove
    # the duplicates and then len to check the size
    if len(set(points)) != 5:
        raise IllegalPointsCount  # Throw a custom exception

    # Now read everything else
    for line in fileLines[2:]:  # Slice off the first two lines
        #  Get a line and split it into its parts
        parts = line.split('::')

        #  Now we check that the category and points are valid
        if parts[0] in categories and int(parts[1]) in points:
            # We can create a GameTile object at this point
            gameTile = GameTile(category=parts[0],
                                points=int(parts[1]),
                                question=parts[2],
                                answer=parts[3])

            # If this our first insertion, we need to create a new list object to store our
            # GameTiles in our dictionary
            if parts[0] not in gameTiles:
                gameTiles[parts[0]] = []
            else:
                # Otherwise we can add our gameTile to gameTiles. Notice that the category is the key
                gameTiles[parts[0]].append(gameTile)

        # This handles the final jeopardy case
        elif parts[0] == 'FJ':
            # gameTiles uses FJ as the key for Final Jeopardy and then we store a FinalJeopardyTile
            gameTiles['FJ'] = FinalJeopardyTile(question=parts[1], answer=parts[2])
        else:
            # Throw our custom exception
            raise InvalidGameFile
    return gameTiles  # Return our dictionary that contains our question and final Jeopardy

Read a file

The first thing we do is open a file. Python makes it super easy to read an entire file into memory with just one line of code!


The open fucntion opens the file. It takes the path to the file (which is stored in gameFile and a flag that tells it kind of open operation we are performing. In this case 'r' means read. Then we just use the readlines() method to read the entire file into memory.

<h4>Check for the proper number of lines</h4>
Our file is only valid if it has 28 lines. Let's check that next.

if len(rawLines) != 28:
    raise InvalidGameFile

Whenever you need to know the len of a string, list, tuple, etc, you can use the built-in len function. In our case, we are calling len on our rawLines variable. If the result is anything beside 28, our file is invalid and we will raise our custom InvalidGameFile exception.

Remove unwanted characters

Our next job is to remove any special characters such as newline '\n' from the game file. The way we do it is below

fileLines = []
for line in rawLines:
    fileLines.append(line.strip())

This code starts by creating an empty list object to store the modified file lines. Then we enter a for loop to go through each item in rawLines one item at a time. We use String's strip() function to remove unwanted characters and we then add it to fileLines.

Validate Categories

Our requirements expect us to have five unique categories. Here is the code that validates the categories.

categories = fileLines[0].split('::')

if len(set(categories)) != 5:
    raise IllegalCategoryCount 

Python Strings have a split method that will split a string into parts based on a supplied character. In our case, we use the :: character to section off each part of our line. Doing so removes the :: characters in the line and it returns a collection of Strings. One item for each portion of our String.

Our next job is to make sure we have five unique categories. We already met the len() function above, but now we have the set() function. This function takes an iterable and removes all duplicates. By wrapping len() around a set() and checking for five, we can be sure that we only have 5 unique categories. Any more or less categories will cause us to raise our custom exception.

Validate Points

We also require that we have 5 unique values for points. We can do this very similar to categories with only a small change.

points = []
pointValues = fileLines[1].split('::')

for pv in pointValues:
    points.append(int(pv)) # Convert to integer here

if len(set(points)) != 5:
    raise IllegalPointsCount

When we start by spliting our string, we end up with hopefully five strings. Python is a strongly typed language. If we want to make a number out of a String, we have use the appropriate function to do so. In our case, we use int() to convert a String to an integer (whole number) value.

If you attempt to call int() on a String that isn't a number, you will get an exception and your program will crash. This is a good thing because we can trace the program back to the point of failure and debug it.

Other than converting the Strings to integers, the logic of this section of code is identitcal to categories.

Creating the GameTiles and Final Jeopardy

Our last order of business is to process the remainder of the file and create our game tile and final jeopardy objets.

gameTiles = {}

for line in fileLines[2:]:  # Slice off the first two lines
    parts = line.split('::')

    if parts[0] in categories and int(parts[1]) in points:
        gameTile = GameTile(category=parts[0],
                            points=int(parts[1]),
                            question=parts[2],
                            answer=parts[3])

        if parts[0] not in gameTiles:
            gameTiles[parts[0]] = []
        else:
            gameTiles[parts[0]].append(gameTile)

    elif parts[0] == 'FJ':
        gameTiles['FJ'] = FinalJeopardyTile(question=parts[1], answer=parts[2])
    else:
        raise InvalidGameFile
return gameTiles

We begin by creating a dict object that will hold our GameTile and FinalJeopardyTile objects. The categories will be used as the keys, and the value will be a list. Combining a dict and a list in this fashion let's use associate multiple values with a single key.

Now we are going to iterate through the remaining lines in the file. Notice that we use the slice operator [2:]. This is a neat Python trick that let's use exclude the first two entries in our list, which we do because we have already processed those lines at this point.

Next we need to validate the category and points that are associated with each question. We can check that parts[0] (the category) is in our category list that we created earlier. The same holds true for points (parts[1]) but notice that we convert to int here again. If the category and points are value, we move onto to create a GameTile using it's constructor.

Next, we need to check if gameTiles has a list associated with a category. If it doesn't have one yet, we need to create it. After that, we can look up a list with a category and then append the GameTile to that list. This keeps the questions organized by their category.

The elif block handles the final jeopardy case. If the parts[0] == 'FJ', we have ran into our final jeopardy question. In this case, we create a special FinalJeopardyTile and associate it with the 'FJ' key in the dictionary. There is no list here because we only want to hold one final jeopardy object.

Finally we can return our newly constructed dictionary.

Running the code

Python make it easy to develop applications quickly because we can easily run modules as standalone applications.

if __name__ == '__main__':
    print(readGameBoard('questions.txt'))

This code only executes when the module is ran on it's own. When it is run, it will look for a file called questions.txt in the same folder as the module. When run successfully, we get this output.

{'Earthquakes': [{'category': 'Earthquakes', 'points': 800, 'question': "... (continues)

You can get the entire code for this tutorial from here: python_tutorial_1